11 ms·
Deduplicate a slice in Go, use sort or a map?
- ggorlen 4y agoSmall nitpick: if !encountered[elements[v]] == true { is a double negative and hard to understand. I'd write it as if !encountered[elements[v]] { or if you must use the bare bool, if encountered[elements[v]] == false {
- cyri 4y agohttps://github.com/mpvl/unique https://github.com/mpvl/unique
- cnity 4y agoCache is one thing, but also you don't need to repeatedly perform hash functions. Array index lookup is of course far faster than map lookup.
- preseinger 4y agoalso doing those map lookups twice per iteration, for some reason
- cnity 4y agoSeems likely to be optimised by the compiler, not sure though.
- sethammons 4y ago> You could probably improve the above by using an interface rather than a bool to reduce the memory impact. If you need a function that preserves the order that might be a better implementation. Maps don't preserve order. The benchmark also is using 10 element slices. That is likely too small to get performance improvements via map lookup and I think the benchmark would still favor unsorted slices over maps. I'm afk but I suggest using map[uint64]struct{} to reduce memory usage over map[uint64]bool and I recommend benchmarking different sized source slices. 10 items is nothing. Bump that up a few orders of magnitude. There is no way 10 element slices are what they are seeing in production that is causing memory pressure. Still, if the problem is memory, an in-place sort is better that a full copy as a map. And as the author suggests, cpu caching should help with the slice operations.
- cnity 4y ago> I'm afk but I suggest using map[uint64]struct{} to reduce memory usage over map[uint64]bool and I recommend benchmarking different sized source slices. 10 items is nothing. Author covers both of these comments in the article (though they don't disclose how large their "larger" slice is). (edit: actually I misread you, sorry. You're right about empty structs vs interface). > Maps don't preserve order The author's approach using maps preserves order in the result, they are comparing the approach to the sort solution which does not preserve order, not claiming that maps themselves preserve order.
- ssd532 4y ago> You could probably improve the above by using an interface rather than a bool to reduce the memory impact. If you need a function that preserves the order that might be a better implementation. An empty interface occupies 16 bytes. Perhaps the author meant an empty struct which consumes nothing.
- Cthulhu_ 4y agoIt's weird, I've heard of the author plenty of times (and frequently use https://github.com/boyter/scc https://github.com/boyter/scc), I would've thought they knew about using an empty interface to emulate a set with no overhead in Go.
- boyter 4y agoThat’s what I get for turning throwaway slack posts into blog posts without looking over it. Didn’t expect it to end up being read. It was more “I wrote this on slack I should save a copy”. Indeed should be struct for lower overhead. I’ll fix it tomorrow once my ego recovers from the inevitable comments that suggest I should give up programming and never write any technical post again.
- timmy777 4y agoSorry, the internet is full of people with low empathy. Mistakes on internet are corrected in very harsh ways, and many times rarely forgiven. But hey, keep writing, keep learning, keep reflecting and taking feedbacks to improve. Everyone does this
- ssd532 4y agoI appreciate the effort you've put into sharing your learnings. My intention was not to criticize. I just wanted to point it out for everyone's benefit. I apologize if my comment came across as harsh.
- boyter 4y agoNot at all. I annoyed the fediverse a while back and that was what I would call harsh. Well that and some reddit comments. I actually appreciate comments like yours. I did indeed make a mistake. Just as mentioned never intended this post to end up here. Hence the spelling errors and problems like this.
- blibble 4y agocreating the map with an appropriate capacity would probably speed up its implementation significantly having to rehash several times is nasty
- bayindirh 4y agoIf it also causes re-allocations when the capacity is set to too low a la C++, the speedup will be more than significant.
- masklinn 4y agoIt necessarily does. That is also the case where it might cause a rehash, however that’s less certain as many hashmaps will trade memory for storing the hashes to avoid recomputing them over and over. I’d assume they can use these hashes directly when reallocating, though they still need to perform collision resolution. Either way properly sizing the hashmap is a good idea. Though load factor needs to be take in account, and I’m not sure whether the average hashmap multiplies the capacity by the maximum load factor in order to ensure there’s actually space for the number of items intended. I’d hope so, but…
- avg_dev 4y agoI’ve never actually seen a length passed to make() when creating a map - does it work? Edit: yep - https://go.dev/ref/spec#Making_slices_maps_and_channels https://go.dev/ref/spec#Making_slices_maps_and_channels
- tialaramex 4y ago[From that link] > map of type T with initial space for approximately n elements That "approximately" isn't great there. Nobody wants "approximately". If "exactly" is difficult - which it might be in many conceivable designs for this data structure - then what you want to offer is "at least". If I'm a programmer and I know I want to put all 623 of these Doodads in the data structure, offering me a way to get a data structure with space for exactly 623 is great. One with space for at least 623 is fine, whereas approximately 623 is barely useful. Should I try asking for 624 in case that helps ? Do I need to dig into the detailed implementation to figure out, OK, 700 will definitely ensure 623 will fit ?
- Attummm 4y agoWhat is missing are benchmarks use the tested functions.The difference between them might dissappear again.
- boyter 4y agoAdded them in for you.
- mseepgood 4y agosort.Slice and then https://pkg.go.dev/slices@master#Compact https://pkg.go.dev/slices@master#Compact
- sethammons 4y agoOp had memory pressure; compact uses the same slice. This is a good solution.
- mbnull 4y ago> TL;DR: If you don’t need to preserve order of the elements, sort the slice first and dedupe. And if you need to preserve order of elements, there is always sort.Stable!
- Karliss 4y agoI don't se how stable sort would help preserving input order when deduplicating uint64. Stable sorting preserves the order of "identical" elements. It's only useful if the elements have other distinguishable properties which are not taken into account for sorting order. For a list of plain uin64 sort and stable sort would produce the same output. Even if you attached some other information to distinguish them, for the purpose of deduplicating you want the values with the same key to be in sequence. Stable sort could help you to choose whether you keep the first or last of the duplicate, but the initial order of unique elements would be lost just like with regular sort.
- mbnull 4y agoYes, sometimes you want to de-duplicate pieces of information by a part of the piece and preserve order. The article tldr sounded like you can only de-duplicating by first sorting with package sort if you don't have to preserve order. However as I just wanted to point out, it works if you have to preserve order just as well. Edit: I see now that the original article meant preserving output order. And i have not clarified that i meant input order.
- avg_dev 4y agoI am curious how much of a difference there would be if the author would use result := make([]unit64, 0, len(elements)) in the old func. I think that the way it is written, it will continually have to be expanded as the backing array exceeds its capacity (in the course of append() calls). And as others have pointed out, maybe use an empty struct (as opposed to a bool or empty interface) as the map value type. Also TIL about make(map[T]S, len) - didn’t know you could set len, or at least hadn’t seen it in practice, but it was suggested here and I think it would likely help as well. Edited: I forgot to set len to 0.
- cyber_kinetist 4y agoIn C++'s STL you can reserve() a specific capacity for the std::vector to use, and at the end of your operation you can trim off the remaining memory using shrink_to_fit(): std::vector<int> elems; elems.reserve(max_bound_num_of_elems); // do some push_back()'s elems.shrink_to_fit(); Is there anything similar in Go?
- avg_dev 4y agoInteresting idea. I am not sure that such is available in Go. In Go, with slices, once the backing array has been allocated, I don’t think you can deallocate some at the end of it. But I might be wrong. There is a difference in Go’s slices between length and capacity. Length is the number of elements in the slice, and capacity is the number of elements that can fit in the backing array (so len <= cap).
- tomohawk 4y agoYes. You can make a slice with zero length but the required capacity and append to it as you go. You can also make a slice of the estimated length and then reslice to the actual length. arr := make([]uint64, estimatedLength) ... arr = arr[:actualLength]
- shakow 4y agoThis would reallocate, wouldn't it?
- madmax96 4y agoNice article. I discovered this myself recently, but in a slightly different context: Taking the union of two sets represented as arrays. To my surprise, sorting the arrays and iteratively computing their union was faster than a hashset. Others in this thread have mentioned that computing the hash takes time. This is true. Let n be the size of the array. When n in small, the (constant) overhead of computing the hash >> O(n * log n) sorting. Now, consider what happens as n becomes large: Virtually every access becomes a cache miss. The (constant) overhead of a cache miss is >> O(n * log n). At the time, I did the math, and determined that n would need to be some unreasonably gargantuan quantity (on the order of the number of stars in the visible universe) before log n is big enough to overtake the effects of cache misses.
- nottorp 4y ago> One thing that stood out to me when doing so was a call I made to remove duplicate values from an array/slice of uint64. A fairly simple fuction that appeared often enough in the output. But do those arrays need to contain duplicates, or the code can be changed elsewhere to not generate them?
- boyter 4y agoThe values come from the result of many hash functions. I actually need them sorted as well hence they are added to an array, and deduplicated. I had a look and didn’t see any obvious way to eliminate them hence the initial function, and the subsequent faster one.
- nottorp 4y agoOnly you can decide that, but it's always worth the ask IMO.
- deleted 4y ago[deleted]