Go maps vs switches
Tagged with: [ go ] [ benchmarking ]
Sometimes, things aren’t faster because you think it is,.. but because you benchmarked them. One of Go’s nice things is that it makes it easy to benchmark things to see if your hunches are correct quickly. And sometimes, they turn out not.
Switch vs. maps
Once in a while, I need to map a string, int, or another type to something else. This usually turns out to become a switch statement where I map each element to something else. It works fine for a small number of elements, but a large list of case statements isn’t very readable as soon as you have a lot. It also increases your gocyclo complexity.
So I tend to use maps instead. That way, I have a small amount of code plus a readable map that doesn’t suffer for readability:
Since both are lookup tables, you would expect both to be pretty similar in performance. Or at least, so I thought. Let’s see what happens when we do a benchmark on both:
Running it with go test --bench=.
gives us the following result:
There was an issue that it seems that Go had optimized the whole testing code out, resulting in a way too low ns/op. I’ve added some additional code that should not optimize the functionality we want to test out.
It seems that the map lookup is almost 10 times slower (still fast, though). I’ve compiled the code to assembly to figure out what’s going on. It seems that the switch is fast because it is not directly a jump-table (as I expected), but a linked list (is the code 200, no goto next check etc).
However, the map takes a lot more time. This is probably because it calls runtime.mapaccess2_fast64(SB)
, which might still be a fast access call, but it is still a call and compared to a simple compare in the switch code quite slow.
Mapping from string to int
So let’s turn things around: instead of mapping ints to strings. Let’s map the string to an int instead.
And the result:
It seems that both functions perform pretty much the same.
When compiled to assembler, we see that the map functionality compiles into pretty much identical code, except now we have
a call to runtime.mapaccess2_faststr
. The switch statement has changed too. Instead of comparing simple ints, it first
checks the length of a given string against the length of the string we match (so in the first case, it checks if the
length of message
is 2). If this isn’t equal, there is no point in checking the rest of the string, but if it does match,
it will continuously load 8 bytes of string and compare it against the message (8 bytes, since that what can fit in the 64-bit
register). Still, it’s a fast process because of the fast-failures in the system.
So which one should we be using?
So it looks like the switch wins, but it seems to have aO(N)
complexity because of the iteration overall cases, while the map has an O(1)
complexity. It doesn’t necessarily mean that the map is better than the switch, since we need to consider the number of elements (it takes a while before the O(1) is faster), and of course, readability is an issue. It depends on the situation what you would use, and in some cases, I will go for the maps, and other cases for the switch. But if speed is your concern, benchmark your stuff!