How about performance of map against slice?

Getting Help
1

I often use maps over slices for easily reaching and deleting keyable stuff but how about the performance does looping over a slice have performance advantages over key looking up in a map (not looping )

for example lets say i have some user multi session data

type session SomeType

type user struct{sessions []session }

type user map[sessionId]session

So in the case above its much easier to deal with the maps but how about performance will it be better or worse if worse does it really cost to deal with structs?

2

Hey @nikosEfthias,

Maps will normally be faster for lookups as opposed to looping to find something within a slice (for only a few items, slice might be faster to just loop over).

You should read this article for a simple explanation. I found this recently:

In general though, maps would normally be O(1) complexity, meaning that it takes a constant time to lookup any element in any part of the map by it’s key, whereas the complexity for a slice would be 0(n), meaning that it can take as long as the number of elements in the slice to find a single element since you have to loop over each element to find any given element if not searching by index. If you know the index of the item that you want in a slice though, that should be 0(1) complexity as well.

Edit: Here is a list of data structures and their time complexities for things such as lookups, inserts, deletes etc. https://en.wikipedia.org/wiki/Search_data_structure#Asymptotic_amortized_worst-case_analysis

1 Like
3

Damian Gryski gave a talk about this at dotGo last year. Sadly the talk has not been released yet. I’ll link it up here when it is.

TL;DR for certain algorithms, binary search of a slice vastly out performs map access.

The key word in that previous sentence is certain algorithms. As always, don’t guess where the problem is, profile your code then you’ll know where the problem is.

1 Like
4

Is this the talk you mean (slides only)? Looks interesting.

https://go-talks.appspot.com/github.com/dgryski/talks/dotgo-2016/slices.slide#1

1 Like
5

thank you this was what i was looking for . How did you find this article? i spent quite a lot of time on duckduckgo before finally i write here.

6

Hey @nikosEfthias,

I think I remember finding it originally recently on the golang subreddit. https://www.reddit.com/r/golang/. Lots of cool articles and things get posted there so I check it every day (same as this forum).

When I was trying to find it to send to you though, I probably googled something along the lines of golang maps vs slices since I knew it had something like that in the title, then it was one of the first page’s results. It’s usually easy to find what you want if you know what you need to look for I suppose :slight_smile:

7

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.