Go Slice vs Maps

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.

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.

1.jpeg

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.

2

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.

3

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

178804 ns/op***

2 million 100000 29012 ns/op

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

4

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
 MAC-OSX goarch: amd64

 

Source Code:

m-c02jn0m1f1g4:slicevsmap user1$ cat slicemap.go 

package slicemap

//You can uncomment print to see the results(to confirm if code is working). 

//But for benchmark, we don't care about printing results.We are concerned about time it takes to run

//import "fmt"

func RangeSliceInt(input []int, find int) (index int) {

	for index,value := range input {

		if (value == find) {

//			fmt.Println("found at",index)

			return index

		}

	}

	return -1

}


func RangeSliceIntPrint(input []int) {

	for _,_ = range input {

		continue

	}

}


func MapLookupInt(input map[int]int, find int) (key,value int) {
	if value,ok := input[find];ok {

//		fmt.Println("found at", find,value)

		return find,value

	}

	return 0,0
}


func MapRangeInt(input map[int]int) {

	for _,_ = range input {

		continue

	}

}

func DirectSliceInt(input []int, index int) int {

	return input[index]

}


// FOR STRINGS //

func RangeSliceString(input []string, find string) (index int) {

        for index,value := range input {

                if (value == find) {

                      //fmt.Println("found at",index)

                        return index

                }

        }

        return -1

}


func RangeSliceStringPrint(input []string) {

        for _,_ = range input {

                continue

        }

}


func MapLookupString(input map[string]string, find string) (key,value string) {

        if value,ok := input[find];ok {

//              fmt.Println("found at", find,value)

                return find,value

        }

        return "0","0"
}


func MapRangeString(input map[string]string) {

        for _,_ = range input {

                continue

        }

}


func DirectSliceString(input []string, index int) string {

        return input[index]

}
m-c02jn0m1f1g4:slicevsmap user1$ cat slicemap_test.go

package slicemap


import (

"testing"

"strconv"

)


func Benchmark_TimeRangeSliceInt(b *testing.B) {

	b.StopTimer()

	input := make([]int, 100000, 500000)

	for i := 0; i < 100000; i++ {

		input[i] = i+10

	}

	b.StartTimer()

	b.N = 2000000  //just to avoid millions of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)

	for i := 0; i < b.N; i++ {

		RangeSliceInt(input, 100009)  //check for the last item for worst case

	}

}


func Benchmark_TimeDirectSliceInt(b *testing.B) {

	b.StopTimer()

        input := make([]int, 100000, 500000)

        for i := 0; i < 100000; i++ {

                input[i] = i+10

        }

        b.StartTimer()        

        b.N = 2000000  //just to avoid millions of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)    

		for i := 0; i < b.N; i++ {

                DirectSliceInt(input, 99999)  //directly check for value given a index. o(1). sending the index

        }

}

func Benchmark_TimeMapLookupInt(b *testing.B) {

	b.StopTimer()

	input := make(map[int]int)

	//throw in some values into the map

	for i := 1; i <=100000; i++ {

		input[i] = i+10

	}

	b.StartTimer()

	b.N = 2000000  //just to avoid millions of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)

	for k := 0; k < b.N; k++ { 

		MapLookupInt(input, 100000)

	}

/*

to run this 

go test -bench=Benchmark_TimeMapLookup

*/

}


func Benchmark_TimeSliceRangeInt(b *testing.B) {

	b.StopTimer()

        input := make([]int, 5, 10)

        for i := 0; i < 5; i++ {

                input[i] = i+10

        }

        b.StartTimer()

        b.N = 2000000  //just to avoid millions of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)

        for k := 0; k < b.N; k++ {

                RangeSliceIntPrint(input)

        }

}


func Benchmark_TimeMapRangeInt(b *testing.B) {

        b.StopTimer()

        input := make(map[int]int)

        //throw in some values into the map

        for i := 1; i <=100000; i++ {

                input[i] = i+10

        }

        b.StartTimer()

        b.N = 2000  //just to avoid millions of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)

        for k := 0; k < b.N; k++ {

                MapRangeInt(input)

        }

}


// Tests for String

func Benchmark_TimeRangeSliceString(b *testing.B) {

        b.StopTimer()

        input := make([]string, 100000, 500000)


        for i := 0; i < 100000; i++ {

                input[i] = strconv.FormatInt(int64(i+10),10)

        }

        b.StartTimer()

        b.N = 2000000  //just to avoid millions of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)

        for i := 0; i < b.N; i++ {

                RangeSliceString(input, "100009")  //check for the last item for worst case

        }

}


func Benchmark_TimeDirectSliceString(b *testing.B) {

	b.StopTimer()

        input := make([]string, 100000, 500000)

        for i := 0; i < 100000; i++ {

                input[i] = strconv.FormatInt(int64(i+10),10)

        }

        b.StartTimer()

        b.N = 2000000  //just to avoid millions of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)
        for i := 0; i < b.N; i++ {

                DirectSliceString(input, 99999)  //directly check for value given a index. o(1)

        }
}


func Benchmark_TimeMapLookupString(b *testing.B) {

        b.StopTimer()

        input := make(map[string]string)

        //throw in some values into the map

        for i := 1; i <=100000; i++ {

                input[strconv.FormatInt(int64(i),10)] = strconv.FormatInt(int64(i+10),10)

        }

        b.StartTimer()

        b.N = 2000000  //just to avoid millions of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)

        for k := 0; k < b.N; k++ {

                MapLookupString(input, "100000")

        }


/*

to run this

go test -bench=Benchmark_TimeMapLookupString

*/

}

Advertisements
This entry was posted in golang, programming, Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s