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:

Continue reading

Advertisements
Posted in golang, programming, Uncategorized | Leave a comment

Sensu Monitoring

Sensu is now in the top of the coolest projects I’ve worked in the recent past. It’s a recommended alternate to Nagios. We started monitoring our Openstack cloud infrastructure end to end using Sensu, at a crucial time when the org is moving towards achieving a highly available private cloud infrastructure to support a huge customer base.

Key points on Sensu:

  • More scalable solution for monitoring the cloud infrastructure.
  • Subscription based – a new infrastructure when comes up, identifies itself (like – ‘i am a webserver’) and gets tagged to checks relevant to that subscription. With an automation like Chef this eliminates need to install agents or define clients in server side. Easy to manage with a CMS!
  • Supports plugins written in different languages. Easy to re-use plugins from nagios.
  • Rabbitmq used for messaging, Redis noSql db for data storage.
  • Light weight application written in Ruby.
  • We had several availability issues with nagira api for nagios. Compared to that, I feel sensu api is performing much better.
  • JSON format.
  • Standalone checks -> sensu-client can run it’s own standalone checks and report results to the server.

Our architecture of Sensu involves these components:

  • Sensu-Server, Rabbitmq, Redis and Uchiwa dashboard in a two node cluster (planning to expand to 4 across different data centers)
  • High Availability -> Rabbitmq clustering, Redis Sentinel. Sensu Server will assign the master automatically.
    • Redis deployed in 3 nodes with Sentinel. In an event where master redis goes down, it will automatically promote a slave to master and “business as usual”.
    • Here is a quick reference to implementing HA for Sensu
    • In our setup we use HAProxy in all the nodes and created a global vip to access the components.
  • Integrated handlers to send alerts to HP-Operations manager for the NOC Team.
  • Configured several metric checks to feed into Graphite (https://github.com/opower/sensu-metrics-relay)
  • Ansible cookbook plugs in the Graphite URL for the host so that Uchiwa shows basic system metrics adjacent to the checks.
Posted in Technology | Tagged , , , | Leave a comment

padham kondu nadathum..

“Padham kondu nadathum vaazhkai
Maavuthan avanum indri
Kadham kondu thuzhaikum veiyya
Angusam adhuvum indri
Madham konda vezham pola
Thirigiren pandu nAngu
vidham konda maraigal potrum
aranga ma nagar ulane”

– My life proceeds on foot without a mahout,
nor goad to give directions,
like a demented rogue elephant, I roam
Oh lord Ranganatha of srirangam! who is praised in 4 vedas, I surrender to you.

These verses are recited in Hey Ram when Kamal moves from Bengal to Srirangam after the horrific happenings.

This may sound like an alwar pasuram but is not. These verses were composed by Gnanakoothan

Posted in Uncategorized | Leave a comment

Bliss

Saint Thyagaraja bows down to lord Rama and let both of them thank MS Amma. Magical Mayamalavagowla..

Posted in raaga | 1 Comment

Protected: India: Elections, News traders, poor journalism!

This content is password protected. To view it please enter your password below:

Posted in Uncategorized

Protected: On India general elections 2014, press reporters, change of guards..etc..

This content is password protected. To view it please enter your password below:

Posted in Uncategorized

“Select Raga from tbl_Carnatic where Song ‘X’ LIKE Song ‘%Y%'”;

For carnatic/film song raga enthusiasts, this place may be of some great info.

Some favorites like Sahana and Madhuvanti briefed.

Posted in Uncategorized | Tagged , , , , | Leave a comment