Go Slice vs Maps

https://boltandnuts.wordpress.com/2017/11/20/go-slice-vs-maps/

Posted on November 20, 2017 by Qwerty Ytrewq

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.

Slice:

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:

Maps in GO are similar for other languages (the internals may vary). Map in GO creates buckets (each bucket can hold 8 keys).

Performance Stats:

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.

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.

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.

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).

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:

Source Code:

  1. //m-c02jn0m1f1g4:slicevsmap user1$ cat slicemap.go
  2. package slicemap
  3. //You can uncomment print to see the results(to confirm if code is working).
  4. //But for benchmark, we don't care about printing results.We are concerned about time it takes to run
  5. //import "fmt"
  6. func RangeSliceInt(input []int, find int) (index int) {
  7. for index,value := range input {
  8. if (value == find) {
  9. // fmt.Println("found at",index)
  10. return index
  11. }
  12. }
  13. return -1
  14. }
  15. func RangeSliceIntPrint(input []int) {
  16. for _,_ = range input {
  17. continue
  18. }
  19. }
  20. func MapLookupInt(input map[int]int, find int) (key,value int) {
  21. if value,ok := input[find];ok {
  22. // fmt.Println("found at", find,value)
  23. return find,value
  24. }
  25. return 0,0
  26. }
  27. func MapRangeInt(input map[int]int) {
  28. for _,_ = range input {
  29. continue
  30. }
  31. }
  32. func DirectSliceInt(input []int, index int) int {
  33. return input[index]
  34. }
  35. // FOR STRINGS //
  36. func RangeSliceString(input []string, find string) (index int) {
  37. for index,value := range input {
  38. if (value == find) {
  39. //fmt.Println("found at",index)
  40. return index
  41. }
  42. }
  43. return -1
  44. }
  45. func RangeSliceStringPrint(input []string) {
  46. for _,_ = range input {
  47. continue
  48. }
  49. }
  50. func MapLookupString(input map[string]string, find string) (key,value string) {
  51. if value,ok := input[find];ok {
  52. // fmt.Println("found at", find,value)
  53. return find,value
  54. }
  55. return "0","0"
  56. }
  57. func MapRangeString(input map[string]string) {
  58. for _,_ = range input {
  59. continue
  60. }
  61. }
  62. func DirectSliceString(input []string, index int) string {
  63. return input[index]
  64. }
  1. //m-c02jn0m1f1g4:slicevsmap user1$ cat slicemap_test.go
  2. package slicemap
  3. import (
  4. "testing"
  5. "strconv"
  6. )
  7. func Benchmark_TimeRangeSliceInt(b *testing.B) {
  8. b.StopTimer()
  9. input := make([]int, 100000, 500000)
  10. for i := 0; i < 100000; i++ {
  11. input[i] = i+10
  12. }
  13. b.StartTimer()
  14. b.N = 2000000 //just to avoid millions of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)
  15. for i := 0; i < b.N; i++ {
  16. RangeSliceInt(input, 100009) //check for the last item for worst case
  17. }
  18. }
  19. func Benchmark_TimeDirectSliceInt(b *testing.B) {
  20. b.StopTimer()
  21. input := make([]int, 100000, 500000)
  22. for i := 0; i < 100000; i++ {
  23. input[i] = i+10
  24. }
  25. b.StartTimer()
  26. b.N = 2000000 //just to avoid millions of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)
  27. for i := 0; i < b.N; i++ {
  28. DirectSliceInt(input, 99999) //directly check for value given a index. o(1). sending the index
  29. }
  30. }
  31. func Benchmark_TimeMapLookupInt(b *testing.B) {
  32. b.StopTimer()
  33. input := make(map[int]int)
  34. //throw in some values into the map
  35. for i := 1; i <=100000; i++ {
  36. input[i] = i+10
  37. }
  38. b.StartTimer()
  39. b.N = 2000000 //just to avoid millions of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)
  40. for k := 0; k < b.N; k++ {
  41. MapLookupInt(input, 100000)
  42. }
  43. /*
  44. to run this
  45. go test -bench=Benchmark_TimeMapLookup
  46. */
  47. }
  48. func Benchmark_TimeSliceRangeInt(b *testing.B) {
  49. b.StopTimer()
  50. input := make([]int, 5, 10)
  51. for i := 0; i < 5; i++ {
  52. input[i] = i+10
  53. }
  54. b.StartTimer()
  55. b.N = 2000000 //just to avoid millions of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)
  56. for k := 0; k < b.N; k++ {
  57. RangeSliceIntPrint(input)
  58. }
  59. }
  60. func Benchmark_TimeMapRangeInt(b *testing.B) {
  61. b.StopTimer()
  62. input := make(map[int]int)
  63. //throw in some values into the map
  64. for i := 1; i <=100000; i++ {
  65. input[i] = i+10
  66. }
  67. b.StartTimer()
  68. b.N = 2000 //just to avoid millions of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)
  69. for k := 0; k < b.N; k++ {
  70. MapRangeInt(input)
  71. }
  72. }
  73. // Tests for String
  74. func Benchmark_TimeRangeSliceString(b *testing.B) {
  75. b.StopTimer()
  76. input := make([]string, 100000, 500000)
  77. for i := 0; i < 100000; i++ {
  78. input[i] = strconv.FormatInt(int64(i+10),10)
  79. }
  80. b.StartTimer()
  81. b.N = 2000000 //just to avoid millions of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)
  82. for i := 0; i < b.N; i++ {
  83. RangeSliceString(input, "100009") //check for the last item for worst case
  84. }
  85. }
  86. func Benchmark_TimeDirectSliceString(b *testing.B) {
  87. b.StopTimer()
  88. input := make([]string, 100000, 500000)
  89. for i := 0; i < 100000; i++ {
  90. input[i] = strconv.FormatInt(int64(i+10),10)
  91. }
  92. b.StartTimer()
  93. b.N = 2000000 //just to avoid millions of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)
  94. for i := 0; i < b.N; i++ {
  95. DirectSliceString(input, 99999) //directly check for value given a index. o(1)
  96. }
  97. }
  98. func Benchmark_TimeMapLookupString(b *testing.B) {
  99. b.StopTimer()
  100. input := make(map[string]string)
  101. //throw in some values into the map
  102. for i := 1; i <=100000; i++ {
  103. input[strconv.FormatInt(int64(i),10)] = strconv.FormatInt(int64(i+10),10)
  104. }
  105. b.StartTimer()
  106. b.N = 2000000 //just to avoid millions of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)
  107. for k := 0; k < b.N; k++ {
  108. MapLookupString(input, "100000")
  109. }
  110. /*
  111. to run this
  112. go test -bench=Benchmark_TimeMapLookupString
  113. */
  114. }
ft_authoradmin  ft_create_time2017-12-05 13:57
 ft_update_time2017-12-05 14:04