map vs switch performance in go

Question

Consider this benchmark, where we compare map access vs switch

var code = []int32{0, 10, 100, 100, 0, 10, 0, 10, 100, 14, 1000, 100, 1000, 0, 0, 10, 100, 1000, 10, 0, 1000, 12}
var mapCode = map[int32]int32{
    0:    1,
    10:   2,
    100:  3,
    1000: 4,
}

func BenchmarkMap(b *testing.B) {
    success := int32(0)
    fail := int32(0)
    for n := 0; n < b.N; n++ {
        // for each value in code array, do a specific action
        for _, v := range code {
            c, ok := mapCode[v]
            if !ok {
                fail++
            } else {
                success += c
            }
        }
    }
}

func BenchmarkSwitch(b *testing.B) {
    success := int32(0)
    fail := int32(0)
    for n := 0; n < b.N; n++ {
        // for each value in code array, do a specific action
        for _, v := range code {
            switch v {
            case 0:
                success++
            case 10:
                success += 2
            case 100:
                success += 3
            case 1000:
                success += 4
            default:
                fail++
            }
        }
    }
}

Here is the results:

BenchmarkMap-2           5000000           277 ns/op           0 B/op          0 allocs/op
BenchmarkSwitch-2       30000000            48.2 ns/op         0 B/op          0 allocs/op

So using map seems to be way slower than switch.

I'm currently trying to optimize a function using a code similar to BenchmarkMap(), where the map access is the bottleneck, but I can't use switch as the map is dynamically generated when the program start (ie it may change according to input arguments)

Is there a way to get similar performance as switch x {} with dynamically generated map ?

Aid

Answer 1

Not with a map, since indexing maps are evaluated at runtime, and getting an element from a map involves more operations than just a single (slice-)indexing. Certain switches (with case branches having constant expressions) can / may be optimized even at compile-time.

But map is not the only "dynamic" structure. For another one, there's slices. Slices can be indexed, just like maps.

Yes, a slice is a descriptor for a contiguous segment of an underlying array. Which means if you have an index like 1000, the slice needs to have at least 1000+1 = 1001 elements.

So if you're willing to sacrifice some memory for the sake of performance and use a slice instead of a map, you can even make your solution faster than the one using the switch statement:

var sliceCode = []int32{
    0:    1,
    10:   2,
    100:  3,
    1000: 4,
}

func BenchmarkSlice(b *testing.B) {
    success := int32(0)
    fail := int32(0)
    for n := 0; n < b.N; n++ {
        // for each value in code array, do a specific action
        for _, v := range code {
            c := sliceCode[v]
            if c == 0 {
                fail++
            } else {
                success += c
            }
        }
    }
}

And the benchmark results:

BenchmarkMap-4          10000000               148 ns/op
BenchmarkSlice-4        100000000               17.6 ns/op
BenchmarkSwitch-4       50000000                31.0 ns/op

The slice solution in this concrete example outperforms the switch solution by being twice as fast!

Notes:

I mentioned above that if you have an index like 1000, you need at least 1001 elements. This is partly true. For example if you'd have indices like 990..1000, you could have a simple index transformation logic like index - 990, and then a slice with just 11 elements would be perfectly enough.

Also note that while indexing a map using the comma-ok idiom we were able to tell if the element was in the map. With slices we don't have that option. So we have to designate a value from the valid set of the element type, and use that as the "missing" signal. In the above example, 0 was perfect for us as that wasn't used (and all elements not explicitly listed are set to 0 by default). If in your example all valid int32 values could be used, another option would be to use a wrapper or pointer type as the element type of the slice which could have a nil value, indicating that the element for the index is missing.

Preview

I'd also mention sort.Search which is a generalized tool to search in sorted slices using binary search algorythm. – Skell

@Skell Yes, but using binary search on a sorted slice will most likely perform worse than a map lookup. – Preview

Just implemented it in my function and got a nice 30% speedup, thanks a lot ! – Aid

Answer 2

These results still hold five years later on go version 1.19 (after recent optimisations of the switch statement):

BenchmarkMap-10         14947908                76.78 ns/op
BenchmarkSwitch-10      49444435                23.01 ns/op
BenchmarkSlice-10       100000000               10.74 ns/op

Bonkers

Answer 3

Is there a way to get similar performance as switch x {} with dynamically generated map ?

No. I'm sorry.

Clairvoyant

@felix, …but you could look at code generation to generate swaths of switch branches automatically -- given certain data. – Skell