Why is iterating over a map so much slower than iterating over a slice in Golang?

Question

I was implementing a sparse matrix using a map in Golang and I noticed that my code started taking much longer to complete after this change, after dismissing other possible causes, seems that the culprit is the iteration on the map itself. Go Playground link (doesn't work for some reason).

package main

import (
    "fmt"
    "time"
    "math"
)

func main() {
    z := 50000000
    a := make(map[int]int, z)
    b := make([]int, z)

    for i := 0; i < z; i++ {
        a[i] = i
        b[i] = i
    }

    t0 := time.Now()
    for key, value := range a {
        if key != value { // never happens
            fmt.Println("a", key, value)
        }
    }
    d0 := time.Now().Sub(t0)

    t1 := time.Now()
    for key, value := range b {
        if key != value { // never happens
            fmt.Println("b", key, value)
        }
    }
    d1 := time.Now().Sub(t1)

    fmt.Println(
        "a:", d0,
        "b:", d1,
        "diff:", math.Max(float64(d0), float64(d1)) / math.Min(float64(d0), float64(d1)),
    )
}

Iterating over 50M items returns the following timings:

alix@local:~/Go/src$ go version
go version go1.3.3 linux/amd64
alix@local:~/Go/src$ go run b.go 
a: 1.195424429s b: 68.588488ms diff: 17.777154632611037

I wonder, why is iterating over a map almost 20x as slow when compared to a slice?

Answer 1

This comes down to the representation in memory. How familiar are you with the representation of different data structures and the concept of algorithmic complexity? Iterating over an array or slice is simple. Values are contiguous in memory. However iterating over a map requires traversing the key space and doing lookups into the hash-table structure.

The dynamic ability of maps to insert keys of any value without using up tons of space allocating a sparse array, and the fact that look-ups can be done efficiently over the key space despite being not as fast as an array, are why hash tables are sometimes preferred over an array, although arrays (and slices) have a faster "constant" (O(1)) lookup time given an index.

It all comes down to whether you need the features of this or that data structure and whether you're willing to deal with the side-effects or gotchas involved.