9 ms·

Finding unique items: hash vs. sort

137 points by douglasorr 7y ago

rurban 7y ago
What he didn't show in the main article, only in subsequent code, is that std::unordered_map is way too slow to be useful. With a proper fast map, he called it custom_map, it outperforms sort-unique until the data set exceeds the L3 cache size.
- nartz 7y ago
  Right well, its clear that at least in java, he doesn't pre-allocate the size of the hashmap. Thus, when the hashmap hits its maximum size, of course the resize operation has to copy all of the data into a new map, which makes this no longer O(N) but something like O(NlogN) or O(N^2) depending.
  - aidenn0 7y ago
    If you do O(N) work every time the hashmap is "full" and double the size of the hashmap, it's still O(N). Hand-wavy proof: If your last insert caused a rehash, then you have done O(N) work plus O(N/2) plus O(N/4)... the limit of which is equal to O(2N), and thus only a constant factor more.
  - matvore 7y ago
    No, it's still O(N) amortized. Imagine if the hashmap doubles in capacity whenever it is full or hits its max load factor. Then you end up having O(N) copy operations. O(2 * N) = O(N)
    - yxhuvud 7y ago
      While your objection stands, repeated trainings of a hash table can be very impactful on the actual walltime spent, and it is a bad benchmark not to include the optimization of preallocating.
rwem 7y ago
The implementations in the benchmark are all pretty naive. You might get a different outcome with more careful implementations of the functions.
umvi 7y ago
I've seen this before, where big-O obsessed co-workers love to make every algorithm and task O(1) by using hash maps, etc. but are then flabbergasted when "inferior" O(n) code written by someone else outperforms their theoretical perfection by a long shot. I have to remind them that O(1) is just a rule of thumb for scaling and that technically a dictionary lookup + sleep(5) is still O(1)
- oddity 7y ago
  Big-O is a way to talk about scaling, but in general, the average CS program does a disservice by not talking more about the critical question: "of what?" Bright students will connect their algorithm course with their systems course and recognize that, maybe, ALU ops aren't a very useful measure in a real world context. Interested students may take a rigorous complexity theory class that will get into various computation models and their nuanced interaction with time/space/communication complexity. However, enough students seem to go through a CS program without learning this that I'm convinced this is a failing of the curriculum and not the students.
  - agumonkey 7y ago
    the theoretical aspect is too "emphased", they really forget to root it in practical situations
- Waterluvian 7y ago
  I run into this case all the time with my React apps that handle huge amounts of mapping data. You know what's beautiful? Just keep it simple, measure it, and add the extra complexity (eg. Array to dict memoized selectors) where performance is actually an issue. I'm not saying all cases can be deferred until later. Sometimes you really need to address it up front. But I think most can be refactored later.
- chillee 7y ago
  I understand the sentiment, but O(n) vs O(1) and O(n^2) vs O(n log n) are huge jumps in complexity. Even with relatively small sizes like N=100, you're already starting with 2 orders of magnitude disadvantage. The example in this post is a log N factor. log N is a relatively small growth, you'd need 1000 elements to get 1 order of magnitude and you'll never run into 2 orders of magnitude. If you can come up with reasonable code where an order N complexity slower algorithm is faster in practice - I'd love to see it.
redis_mlc 7y ago
My favorite is gratuitous ORDER BY clauses. I suggest you look at your SQL and see if that's needed.
- perl4ever 7y ago
  Not having an ORDER BY when you need one is vastly worse and more common than having one that you don't.
  - Waterluvian 7y ago
    I'm curious. Can you explain why?
    - anonytrary 7y ago
      I'm guessing it has something to do with sort indexes being very fast.
    - perl4ever 7y ago
      People tend to believe the order of query results without ORDER BY is deterministic.
      - yxhuvud 7y ago
        Also, the query optimizer are more eager to use indices when ordered.
    - repsilat 7y ago
      The former is incorrect, the latter merely slower than necessary.
    - flukus 7y ago
      Implicit ordering can outsource it to users and result in some awful to use software. I think I've told this story before here but the best bug I've ever fixed is adding an order by clause to a query. The client was trying to find items in a combo box that were essentially randomly ordered, it was literally taking hours out of their day to find stuff in this list and forcing them to do overtime to keep up with the workload, they literally cried when I fixed it. I had to sneak the change past management but I'm not sure if I was successful, it may have played a role in my short tenure there. That's a particularly bad example but like perl4ever I've found this to be more common and in practice a much bigger deal than gratuitous order by clauses. I've seen many variations where the natural ordering is fine but once it's combined with top, or joined, or filtered the results become very random to users.
kccqzy 7y ago
The default hash functions in most C++ implementations are surprisingly slow—implementations tend to aim for hash quality rather than speed. I can be totally wrong, but I suggest trying a simpler hash such as FNV. It might outperform the sort-based approach. I also suggest replacing the hash table implementation with something better, such as absl::flat_hash_map. The C++ std::unordered_map is hampered by compatibility requirements: the designers wanted these unordered containers to be a good substitute for the preexisting std::map, and necessitated certains design decisions such as pointer stability which is not necessary for most applications.
- aidenn0 7y ago
  A slow hash-function doesn't explain the increasing time-per-element as the hash table grows though. A poor fit between the keys and hash-function might though.
- chillee 7y ago
  Actually, I believe the default hash functions have terrible hash quality - they're literally the identity function for integers. I do agree that unordered_map is extremely slow.
herf 7y ago
Memory latency is everything once a hash table gets big enough. Anytime you see 100ns you should think, random read from main memory!
aidenn0 7y ago
All this article has shown is that std::sort is much more optimal than std::unordered_map on the C++ standard library used. Every std::unordered_map I've used is surprisingly slow. Normally hash-tables are slow because it's so easy to write a slow hash-table, but std::unordered_map is slow for other reasons that I have had explained to me and then quickly forgot :(. I also find it strange that unordered_map is used rather than unordered_set. Not sure if it would make a performance difference, but if we are going for naive implementations, that should be at the top of the list.
- kyllo 7y ago
  It'd be interesting to see how std::map (implemented with a red-black tree) would do on these same benchmarks. A high ratio of inserts to lookups could favor the tree-based map.
  - chopin 7y ago
    A tree map is O(n*log n) on inserts, though. For a hash map to be faster, you'd need to trade memory for speed, i.e have significantly more buckets than the expected size. This may however collide with good caching performance which I suspect is what the author observes.
  - jonstewart 7y ago
    It’s hard to get slower than std::map and std::set. They combine logarithmic algorithms with nonlocal memory access.
- noctune 7y ago
  One reason why unordered map is slow is that it has to be a chained hash map due to the spec not allowing iterator invalidation when resizing.
  - aidenn0 7y ago
    that's certainly annoying...
  - 7y ago
deleted 7y ago
[deleted]
macdice 7y ago
If the keys are in random order, and the hash table is larger than L3, I bet you can make the hash version faster by looking ahead N items and issuing __builtin_prefetch() on the hash table array. (There are papers on this for hash joins in databases.)
BeeOnRope 7y ago
You could use a faster sort implementation, such as radix sort which is O(n) and also probably faster in practice when well-implemented. One option is this one [1] which I actually wrote as part of this exact task: de-duplicating a list of integers, as part of working on [2]. I wrote about the types of speedups you can expect with radix sort here [3] - it depends on the size of the input elements and their distribution (e.g., if many top bits are zero, radix sort will be much faster), but in my test case I see a ~5x speedup for moderate or large input sizes (thousands of elements or more). Of course, the same could be said about hash tables... [1] https://github.com/travisdowns/sort-bench/blob/master/radix7.cpp https://github.com/travisdowns/sort-bench/blob/master/radix7... [2] https://lemire.me/blog/2019/05/07/almost-picking-n-distinct-numbers-at-random/ https://lemire.me/blog/2019/05/07/almost-picking-n-distinct-... [3] https://travisdowns.github.io/blog/2019/05/22/sorting.html https://travisdowns.github.io/blog/2019/05/22/sorting.html
- fwip 7y ago
  Radix sort is not O(1), did you mean O(n)? And even then it's only true for a constant k (where k is the size of the possible key space).
  - kragen 7y ago
    Patricia is O(N) in the size of the input data to be sorted, even without a bound on the key size, as are several more recently discovered suffix array sorting algorithms. Some other radix sorts are not, it's true.
    - rocqua 7y ago
      I did some work on suffix arrays, but didn't come across sorting algorithms. Would you mind linking a few papers?
      - kragen 7y ago
        They're pretty new! I think the first linear-time suffix-sorting algorithm was the "skew algorithm" introduced in "Linear work suffix array construction," J. Kärkkäinen, P. Sanders, and S. Burkhardt. Journal of the ACM, 53(6):918–936, 2006, although I think Kärkkäinen and Sanders published it in 2003 ("Simple linear work suffix array construction", J.C.M. Baeten et al. (Eds.): ICALP 2003, LNCS 2719, pp. 943–955, 2003.) SA-IS, from 2009, has a vulgar explanation (by Satan!) at https://zork.net/~st/jottings/sais.html; https://zork.net/~st/jottings/sais.html; he cites the paper as “Linear Suffix Array Construction by Almost Pure Induced-Sorting” by G. Nong, S. Zhang and W. H. Chan, which seems to be http://ge-nong.googlecode.com/files/Linear%20Suffix%20Array%20Construction%20by%20Almost%20Pure%20Induced-Sorting.pdf http://ge-nong.googlecode.com/files/Linear%20Suffix%20Array%... (404; from https://code.google.com/archive/p/ge-nong/ https://code.google.com/archive/p/ge-nong/). Nong seems to have gone on to do related external-sorting work until at least 2014, which is of course very important if you want to use suffix arrays to index large corpuses. In 2016 Gonzalo Navarro and a couple of other guys published https://arxiv.org/abs/1607.04346 https://arxiv.org/abs/1607.04346, "Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time", J. Ian Munro, Gonzalo Navarro, Yakov Nekrich (Submitted on 15 Jul 2016 (v1), last revised 14 Nov 2016 (this version, v2)). This constructs not only the suffix array but in fact an entire compressed index similar to the FM-index. This seems to follow up 2014 work by Belazzougui. I think there's a third totally different linear-time suffix-array construction algorithm from the mid-oughties but I can't remember it.
sagarm 7y ago
std::unordered_map is usually slow while std::sort is quite fast. std::unordered_map's API includes pointer stability across map resizes, which requires storing the contents of the map out-of-line in a separately allocated memory block. This results in poor cache utilization and higher memory management overhead. The SwissTable family of containers are much faster if you do not have this requirement. See https://abseil.io/about/design/swisstables https://abseil.io/about/design/swisstables for more on the optimizations that make them fast. I wrote a quick benchmark to compare sorting, std::set, std::unordered_set, and ska::flat_hash_set (an older version of SwissTable I believe) and flat_hash_set was generally ~2.4x faster, even up to 100M integers. https://pastebin.com/y5UsPek5 https://pastebin.com/y5UsPek5
mda 7y ago
If author just used a fast hash table (swiss table etc) results would immediately look very different.
magicalhippo 7y ago
This is a case where the optimal strategy depends a lot on your input I think. For example, long ago I wrote a small program to find file duplicates. My first step was to use the fact that files with different lengths can't be duplicates. Thus only files which had the same length had to be checked further. For files on your average hard drive, that simple test screens the vast majority of them.
xvector 7y ago
I wonder how the following compares: - Putting a bloom filter in front of the hash table - Hashing the keys and performing radix sort on them
mlochbaum 7y ago
The hash table implementation can be much faster. Dyalog APL's Unique (∪) computes exactly the same function using a dedicated hash table. ∪ 'AABBADCAB' ABDC ≢∪ a←{⍵[?⍨≢⍵]} {⍵,⍵[(?⍴)⍨≢⍵]} 5e5?2e9 ⍝ 1e6 ints with 50% unique 500000 cmpx '∪a' ⍝ Time taken by ∪a in seconds 1.8E¯2 So 18ns per element on a million elements (at 3.5GHz). Characteristics of the hash table we use include: - Hashing with the Murmur3 mixing function (at the top of [1]), not the full hash function - Open addressing with ints stored directly in the hash table - Sentinel value for empty slots chosen to be outside the argument's range - [edit] Preallocated fixed-sized table. It should be resizable when the argument is large enough; I will fix that some day. We know the range of the argument since we check it in order to possibly apply small-range code, which can use an ordinary lookup table rather than a hash table. In 18.0, which features a largely rewritten Unique implementation (not much faster here), I applied some careful logic in order to use the first entry of the argument as the sentinel rather than trying to find a value not in the hash table. [1] http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html http://zimbry.blogspot.com/2011/09/better-bit-mixing-improvi...
- mlochbaum 7y ago
  But Dyalog's sorting actually beats its own Unique! cmpx '{(1,2≠/⍵)/⍵} {⍵[⍋⍵]} a' 1.3E¯2 ({(1,2≠/⍵)/⍵} {⍵[⍋⍵]} a) ≡ ({⍵[⍋⍵]} ∪a) 1 The function {⍵[⍋⍵]} (index the argument by its own grade) sorts a vector ascending. {(1,2≠/⍵)/⍵} gets unique elements from a sorted numeric vector by taking all those elements which are first or unequal to their predecessor: 2≠/⍵ tests for inequality on all pairs of adjacent elements, and / uses a boolean vector on the left to filter elements on the right. The second line tests that this unique-sort code gives the same result as sorting the result of Unique. We use a radix sort for vectors of 4-byte or larger numbers. Unfortunately we can't use sorting to implement Unique in this way because Unique has to preserve the ordering in the original argument. However, it could be used to implement the sort-Unique or Unique-sort combination.
alecco 7y ago
Related Sort vs Hash revisited [joins] (VLDB 2009) https://15721.courses.cs.cmu.edu/spring2016/papers/kim-vldb2009.pdf https://15721.courses.cs.cmu.edu/spring2016/papers/kim-vldb2... It's interesting they predicted sort would surpass hashing when the registers got to 512b, and we got AVX512 nowadays. TBH, their SSE4 sort implementation was quite complex (but beautiful).
maury91 7y ago
You could use a modified version of merge sort where if an element already exists you don't add it (you end up adding only unique elements), this will save the extra O(n) where you remove the duplicates.

137 points by douglasorr 7y ago

What he didn't show in the main article, only in subsequent code, is that std::unordered_map is way too slow to be useful. With a proper fast map, he called it custom_map, it outperforms sort-unique until the data set exceeds the L3 cache size.

nartz 7y ago
Right well, its clear that at least in java, he doesn't pre-allocate the size of the hashmap. Thus, when the hashmap hits its maximum size, of course the resize operation has to copy all of the data into a new map, which makes this no longer O(N) but something like O(NlogN) or O(N^2) depending.
- aidenn0 7y ago
  If you do O(N) work every time the hashmap is "full" and double the size of the hashmap, it's still O(N). Hand-wavy proof: If your last insert caused a rehash, then you have done O(N) work plus O(N/2) plus O(N/4)... the limit of which is equal to O(2N), and thus only a constant factor more.
- matvore 7y ago
  No, it's still O(N) amortized. Imagine if the hashmap doubles in capacity whenever it is full or hits its max load factor. Then you end up having O(N) copy operations. O(2 * N) = O(N)
  - yxhuvud 7y ago
    While your objection stands, repeated trainings of a hash table can be very impactful on the actual walltime spent, and it is a bad benchmark not to include the optimization of preallocating.

rwem 7y ago

The implementations in the benchmark are all pretty naive. You might get a different outcome with more careful implementations of the functions.

umvi 7y ago

I've seen this before, where big-O obsessed co-workers love to make every algorithm and task O(1) by using hash maps, etc. but are then flabbergasted when "inferior" O(n) code written by someone else outperforms their theoretical perfection by a long shot. I have to remind them that O(1) is just a rule of thumb for scaling and that technically a dictionary lookup + sleep(5) is still O(1)

oddity 7y ago
Big-O is a way to talk about scaling, but in general, the average CS program does a disservice by not talking more about the critical question: "of what?" Bright students will connect their algorithm course with their systems course and recognize that, maybe, ALU ops aren't a very useful measure in a real world context. Interested students may take a rigorous complexity theory class that will get into various computation models and their nuanced interaction with time/space/communication complexity. However, enough students seem to go through a CS program without learning this that I'm convinced this is a failing of the curriculum and not the students.
- agumonkey 7y ago
  the theoretical aspect is too "emphased", they really forget to root it in practical situations
Waterluvian 7y ago
I run into this case all the time with my React apps that handle huge amounts of mapping data. You know what's beautiful? Just keep it simple, measure it, and add the extra complexity (eg. Array to dict memoized selectors) where performance is actually an issue. I'm not saying all cases can be deferred until later. Sometimes you really need to address it up front. But I think most can be refactored later.
chillee 7y ago
I understand the sentiment, but O(n) vs O(1) and O(n^2) vs O(n log n) are huge jumps in complexity. Even with relatively small sizes like N=100, you're already starting with 2 orders of magnitude disadvantage. The example in this post is a log N factor. log N is a relatively small growth, you'd need 1000 elements to get 1 order of magnitude and you'll never run into 2 orders of magnitude. If you can come up with reasonable code where an order N complexity slower algorithm is faster in practice - I'd love to see it.

redis_mlc 7y ago

My favorite is gratuitous ORDER BY clauses. I suggest you look at your SQL and see if that's needed.

perl4ever 7y ago
Not having an ORDER BY when you need one is vastly worse and more common than having one that you don't.
- Waterluvian 7y ago
  I'm curious. Can you explain why?
  - anonytrary 7y ago
    I'm guessing it has something to do with sort indexes being very fast.
  - perl4ever 7y ago
    People tend to believe the order of query results without ORDER BY is deterministic.
    - yxhuvud 7y ago
      Also, the query optimizer are more eager to use indices when ordered.
  - repsilat 7y ago
    The former is incorrect, the latter merely slower than necessary.
  - flukus 7y ago
    Implicit ordering can outsource it to users and result in some awful to use software. I think I've told this story before here but the best bug I've ever fixed is adding an order by clause to a query. The client was trying to find items in a combo box that were essentially randomly ordered, it was literally taking hours out of their day to find stuff in this list and forcing them to do overtime to keep up with the workload, they literally cried when I fixed it. I had to sneak the change past management but I'm not sure if I was successful, it may have played a role in my short tenure there. That's a particularly bad example but like perl4ever I've found this to be more common and in practice a much bigger deal than gratuitous order by clauses. I've seen many variations where the natural ordering is fine but once it's combined with top, or joined, or filtered the results become very random to users.

kccqzy 7y ago

The default hash functions in most C++ implementations are surprisingly slow—implementations tend to aim for hash quality rather than speed. I can be totally wrong, but I suggest trying a simpler hash such as FNV. It might outperform the sort-based approach. I also suggest replacing the hash table implementation with something better, such as absl::flat_hash_map. The C++ std::unordered_map is hampered by compatibility requirements: the designers wanted these unordered containers to be a good substitute for the preexisting std::map, and necessitated certains design decisions such as pointer stability which is not necessary for most applications.

aidenn0 7y ago
A slow hash-function doesn't explain the increasing time-per-element as the hash table grows though. A poor fit between the keys and hash-function might though.
chillee 7y ago
Actually, I believe the default hash functions have terrible hash quality - they're literally the identity function for integers. I do agree that unordered_map is extremely slow.

herf 7y ago

Memory latency is everything once a hash table gets big enough. Anytime you see 100ns you should think, random read from main memory!

aidenn0 7y ago

All this article has shown is that std::sort is much more optimal than std::unordered_map on the C++ standard library used. Every std::unordered_map I've used is surprisingly slow. Normally hash-tables are slow because it's so easy to write a slow hash-table, but std::unordered_map is slow for other reasons that I have had explained to me and then quickly forgot :(. I also find it strange that unordered_map is used rather than unordered_set. Not sure if it would make a performance difference, but if we are going for naive implementations, that should be at the top of the list.

kyllo 7y ago
It'd be interesting to see how std::map (implemented with a red-black tree) would do on these same benchmarks. A high ratio of inserts to lookups could favor the tree-based map.
- chopin 7y ago
  A tree map is O(n*log n) on inserts, though. For a hash map to be faster, you'd need to trade memory for speed, i.e have significantly more buckets than the expected size. This may however collide with good caching performance which I suspect is what the author observes.
- jonstewart 7y ago
  It’s hard to get slower than std::map and std::set. They combine logarithmic algorithms with nonlocal memory access.
noctune 7y ago
One reason why unordered map is slow is that it has to be a chained hash map due to the spec not allowing iterator invalidation when resizing.
- aidenn0 7y ago
  that's certainly annoying...
- 7y ago

deleted 7y ago

[deleted]

macdice 7y ago

If the keys are in random order, and the hash table is larger than L3, I bet you can make the hash version faster by looking ahead N items and issuing __builtin_prefetch() on the hash table array. (There are papers on this for hash joins in databases.)

BeeOnRope 7y ago

You could use a faster sort implementation, such as radix sort which is O(n) and also probably faster in practice when well-implemented. One option is this one [1] which I actually wrote as part of this exact task: de-duplicating a list of integers, as part of working on [2]. I wrote about the types of speedups you can expect with radix sort here [3] - it depends on the size of the input elements and their distribution (e.g., if many top bits are zero, radix sort will be much faster), but in my test case I see a ~5x speedup for moderate or large input sizes (thousands of elements or more). Of course, the same could be said about hash tables... [1] https://github.com/travisdowns/sort-bench/blob/master/radix7.cpp https://github.com/travisdowns/sort-bench/blob/master/radix7... [2] https://lemire.me/blog/2019/05/07/almost-picking-n-distinct-numbers-at-random/ https://lemire.me/blog/2019/05/07/almost-picking-n-distinct-... [3] https://travisdowns.github.io/blog/2019/05/22/sorting.html https://travisdowns.github.io/blog/2019/05/22/sorting.html

fwip 7y ago
Radix sort is not O(1), did you mean O(n)? And even then it's only true for a constant k (where k is the size of the possible key space).
- kragen 7y ago
  Patricia is O(N) in the size of the input data to be sorted, even without a bound on the key size, as are several more recently discovered suffix array sorting algorithms. Some other radix sorts are not, it's true.
  - rocqua 7y ago
    I did some work on suffix arrays, but didn't come across sorting algorithms. Would you mind linking a few papers?
    - kragen 7y ago
      They're pretty new! I think the first linear-time suffix-sorting algorithm was the "skew algorithm" introduced in "Linear work suffix array construction," J. Kärkkäinen, P. Sanders, and S. Burkhardt. Journal of the ACM, 53(6):918–936, 2006, although I think Kärkkäinen and Sanders published it in 2003 ("Simple linear work suffix array construction", J.C.M. Baeten et al. (Eds.): ICALP 2003, LNCS 2719, pp. 943–955, 2003.) SA-IS, from 2009, has a vulgar explanation (by Satan!) at https://zork.net/~st/jottings/sais.html; https://zork.net/~st/jottings/sais.html; he cites the paper as “Linear Suffix Array Construction by Almost Pure Induced-Sorting” by G. Nong, S. Zhang and W. H. Chan, which seems to be http://ge-nong.googlecode.com/files/Linear%20Suffix%20Array%20Construction%20by%20Almost%20Pure%20Induced-Sorting.pdf http://ge-nong.googlecode.com/files/Linear%20Suffix%20Array%... (404; from https://code.google.com/archive/p/ge-nong/ https://code.google.com/archive/p/ge-nong/). Nong seems to have gone on to do related external-sorting work until at least 2014, which is of course very important if you want to use suffix arrays to index large corpuses. In 2016 Gonzalo Navarro and a couple of other guys published https://arxiv.org/abs/1607.04346 https://arxiv.org/abs/1607.04346, "Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time", J. Ian Munro, Gonzalo Navarro, Yakov Nekrich (Submitted on 15 Jul 2016 (v1), last revised 14 Nov 2016 (this version, v2)). This constructs not only the suffix array but in fact an entire compressed index similar to the FM-index. This seems to follow up 2014 work by Belazzougui. I think there's a third totally different linear-time suffix-array construction algorithm from the mid-oughties but I can't remember it.

sagarm 7y ago

std::unordered_map is usually slow while std::sort is quite fast. std::unordered_map's API includes pointer stability across map resizes, which requires storing the contents of the map out-of-line in a separately allocated memory block. This results in poor cache utilization and higher memory management overhead. The SwissTable family of containers are much faster if you do not have this requirement. See https://abseil.io/about/design/swisstables https://abseil.io/about/design/swisstables for more on the optimizations that make them fast. I wrote a quick benchmark to compare sorting, std::set, std::unordered_set, and ska::flat_hash_set (an older version of SwissTable I believe) and flat_hash_set was generally ~2.4x faster, even up to 100M integers. https://pastebin.com/y5UsPek5 https://pastebin.com/y5UsPek5

mda 7y ago

If author just used a fast hash table (swiss table etc) results would immediately look very different.

magicalhippo 7y ago

This is a case where the optimal strategy depends a lot on your input I think. For example, long ago I wrote a small program to find file duplicates. My first step was to use the fact that files with different lengths can't be duplicates. Thus only files which had the same length had to be checked further. For files on your average hard drive, that simple test screens the vast majority of them.

xvector 7y ago

I wonder how the following compares: - Putting a bloom filter in front of the hash table - Hashing the keys and performing radix sort on them

mlochbaum 7y ago

The hash table implementation can be much faster. Dyalog APL's Unique (∪) computes exactly the same function using a dedicated hash table. ∪ 'AABBADCAB' ABDC ≢∪ a←{⍵[?⍨≢⍵]} {⍵,⍵[(?⍴)⍨≢⍵]} 5e5?2e9 ⍝ 1e6 ints with 50% unique 500000 cmpx '∪a' ⍝ Time taken by ∪a in seconds 1.8E¯2 So 18ns per element on a million elements (at 3.5GHz). Characteristics of the hash table we use include: - Hashing with the Murmur3 mixing function (at the top of [1]), not the full hash function - Open addressing with ints stored directly in the hash table - Sentinel value for empty slots chosen to be outside the argument's range - [edit] Preallocated fixed-sized table. It should be resizable when the argument is large enough; I will fix that some day. We know the range of the argument since we check it in order to possibly apply small-range code, which can use an ordinary lookup table rather than a hash table. In 18.0, which features a largely rewritten Unique implementation (not much faster here), I applied some careful logic in order to use the first entry of the argument as the sentinel rather than trying to find a value not in the hash table. [1] http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html http://zimbry.blogspot.com/2011/09/better-bit-mixing-improvi...

mlochbaum 7y ago
But Dyalog's sorting actually beats its own Unique! cmpx '{(1,2≠/⍵)/⍵} {⍵[⍋⍵]} a' 1.3E¯2 ({(1,2≠/⍵)/⍵} {⍵[⍋⍵]} a) ≡ ({⍵[⍋⍵]} ∪a) 1 The function {⍵[⍋⍵]} (index the argument by its own grade) sorts a vector ascending. {(1,2≠/⍵)/⍵} gets unique elements from a sorted numeric vector by taking all those elements which are first or unequal to their predecessor: 2≠/⍵ tests for inequality on all pairs of adjacent elements, and / uses a boolean vector on the left to filter elements on the right. The second line tests that this unique-sort code gives the same result as sorting the result of Unique. We use a radix sort for vectors of 4-byte or larger numbers. Unfortunately we can't use sorting to implement Unique in this way because Unique has to preserve the ordering in the original argument. However, it could be used to implement the sort-Unique or Unique-sort combination.

alecco 7y ago

Related Sort vs Hash revisited [joins] (VLDB 2009) https://15721.courses.cs.cmu.edu/spring2016/papers/kim-vldb2009.pdf https://15721.courses.cs.cmu.edu/spring2016/papers/kim-vldb2... It's interesting they predicted sort would surpass hashing when the registers got to 512b, and we got AVX512 nowadays. TBH, their SSE4 sort implementation was quite complex (but beautiful).

maury91 7y ago

You could use a modified version of merge sort where if an element already exists you don't add it (you end up adding only unique elements), this will save the extra O(n) where you remove the duplicates.