Slices and Maps are two important data types in Go. This blog will document some of my key findings about the performance of these two data structures.
Before going into the performance aspects, let’s briefly look into Slices and Maps.
Slices are an abstract data structure built on top of arrays. Slice has a pointer to the beginning of an array, the length of the array and maximum capacity that the slice can use from the array. Slices can grow or shrink as needed. Growing a slice typically involves reallocating memory for the underlying array. Functions like copy and append can help with growing the array.
Maps in GO are similar for other languages (the internals may vary). Map in GO creates buckets (each bucket can hold 8 keys).
I ran few benchmark tests with both the data-structures and results documented below.
TEST-1: Lookup an INT element in the slice vs lookup an element in map –
Here let’s try to lookup an item in a slice of length ‘n’ and compare with a lookup of a key in a map. To lookup an item in slice, we will range through the slice and do a simply `if` to check for the element. For the map, we will do a simple lookup of the key. I am looking for the worst case scenario in all our testing.
|Total Samples||len_size ( n )||f(n)- int (o(N)) – for loop and if (lcheck for last element)||map[int]int direct lookup o(1)|
|2 million||5||5.42 ns/op||12.7 ns/op|
|2 million||10||8.19 ns/op||17.8 ns/op|
|2 million||100||63.3 ns/op||16.5 ns/op|
|2 million||200||118 ns/op||16.6 ns/op|
|2 million||400||228 ns/op||18.4 ns/op|
|2 million||1000||573 ns/op||17.0 ns/op|
|2 million||10000||5674 ns/op||17.6 ns/op|
|2 million||100000||55141 ns/op||15.1 ns/op|
As you can see (and as expected), map lookups are constant complexity (O(1)) for various ‘n’. However, it is interesting to see that a simple for loop and if comparison of a small ‘n’ slice takes less time than a map. Larger ‘n’ values expectedly take more time.
Conclusion: I recommend using maps for lookups given a key. For a small size ( n ), it is still ok to use slice.
TEST-2: Lookup a STRING element in the slice vs lookup an STRING Key in map –
We are doing the exact same steps as in TEST-1, only difference is here we use String.
|Total Samples||len – size ( n )||f(n) string [for loop and if (lcheck for last element)]||f(n) map[string]string|
|2 million||5||30.4 ns/op||32.7 ns/op|
|2 million||10||56.5 ns/op||23.5 ns/op|
|2 million||100||128 ns/op||25.7 ns/op|
|2 million||200||665 ns/op||23.6 ns/op|
|2 million||400||1766 ns/op||23.7 ns/op|
|2 million||1000||905 ns/op||25.7 ns/op|
|2 million||10000||8488 ns/op||24.4 ns/op|
|2 million||100000||82444 ns/op||25.9 ns/op|
From the data above, we see looking up a string given a key (using MAP) has a O(1) complexity. Maps beat slices for string comparison.
Conclusion: I recommend using maps for lookups given a key of string type. Even for smaller ‘n’ it’s good to use map.
TEST-3: Lookup a slice element given an index.
If we know the index then looking up an slice in GO is similar to looking up an array in any language and is as simple as it is.
|Total Samples||len – size||int (direct index lookup) – O(1)||string (direct index lookup) – O(1)||map[int]int direct lookup o(1)||map[string]string o(1)|
|2 million||5||0.30 ns/op||0.29 ns/op||12.7||32.7|
|2 million||10||0.29 ns/op||0.29 ns/op||17.8||23.5|
|2 million||100||0.29 ns/op||0.29 ns/op||16.5||25.7|
|2 million||200||0.29 ns/op||0.29 ns/op||16.6||23.6|
|2 million||400||0.29 ns/op||0.29 ns/op||18.4||23.7|
|2 million||1000||0.29 ns/op||0.29 ns/op||17||25.7|
|2 million||10000||0.58 ns/op||0.57 ns/op||17.6||24.4|
|2 million||100000||0.58 ns/op||0.55 ns/op||15.1||25.9|
As seen above direct lookup of slice is a O(1) constant growth rate.
CONCLUSION: Direct lookups are constant complexity so it doesn’t matter which one you use given that you know the index. However slice/array lookup is still much faster than map lookup given that index in known.
TEST-4: Range a Slice vs Range a Map
Here I attempt to loop over a map and slice and perform a constant operation inside the loop. The overall complexity will remain to be O(N).
|Total Samples||len – size ( n )||Range Int slice O(N)||Range int Map O(N)|
|2 million||5||9.02 ns/op||107 ns/op|
|2 million||10||12.5 ns/op||196 ns/op|
|2 million||100||59.2 ns/op||1717 ns/op|
|2 million||200||84.9 ns/op||3356 ns/op|
|2 million||400||155 ns/op||6677 ns/op|
|2 million||1000||315 ns/op||18906 ns/op|
|2 million||10000||2881 ns/op||
|2 million||100000||29012 ns/op||
As we see above, looping over slice is approximately 20x faster than looping over a map. The reason for this is slice (abstracted over arrays) are created over a contiguous memory blocks unlike maps. In case of maps, the loop has to iterate over the keyspace (called buckets in Go) and the memory allocation may not contiguous. This is the reason why results of iterating over map shows key/values in different order each time you run.
Conclusion: If the requirement is to print or perform an operation other than lookup on the entire list of elements, then slice is the best option. Maps take more time to loop over for reasons described above.
Also, note that an append operation on a slice guarantees a O(1) just like an insert to map but this is an amortized constant. Append may occasionally require reallocating memory for the underlying array.
( *** ) – Sample size reduced to 2000 instead of 2 million as Go benchmark function times out for large maps.
Details about the tests:
|System Details||goos: darwin||Go-1.9.2|