Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Hashed sorting is typically faster than hash tables

reiner.org

Post reply on HN
Print view View original

11–20 of 67 posts

Re: Hashed sorting is typically faster than hash tables

#11

Post by shiandow »

Anon_troll wrote: post #8
markisus wrote: post #5

Interesting article. It’s actually very strange that the dataset needs to be “big” for the O(n log n) algorithm to beat the O(n). Usually you’d expect the big O analysis to be “wrong” for small datasets. I expect that in this case, like in all cases, as the datasets become gallactically large, the O(n) algorithm will start winning again.

The hash-based algorithm is only O(n) because the entry size has a limit. In a more general case, it would be something more like O(m(n * e)). Here n is the number of entries, e is the maximum entry size and m is a function describing how caching and other details affect the computation. With small enough data, the hash is very fast due to CPU caches, even if it takes more steps, as the time taken by a step is smalle…

Interestingly you need a hash function big enough to be unique for all data points with high probability, it doesn't take much to point out that this is at least O(log(n)) if all items are unique.

Also if items take up k bytes then the hash must typically be O(k), and both the hashing and radix sort are O(n k).

Really radix sort should be considered O(N) where N is the total amount of data in bytes. It can beat the theoretical limit because it sorts lexicographically, which is not always an option.

Re: Hashed sorting is typically faster than hash tables

#12

Post by Ar-Curunir »

markisus wrote: post #5

Interesting article. It’s actually very strange that the dataset needs to be “big” for the O(n log n) algorithm to beat the O(n). Usually you’d expect the big O analysis to be “wrong” for small datasets. I expect that in this case, like in all cases, as the datasets become gallactically large, the O(n) algorithm will start winning again.

why is it strange? the case where asymptotically better = concretely worse is usually the exception, not the norm.

Re: Hashed sorting is typically faster than hash tables

#13

Post by simiones »

Ar-Curunir wrote: post #12
markisus wrote: post #5

Interesting article. It’s actually very strange that the dataset needs to be “big” for the O(n log n) algorithm to beat the O(n). Usually you’d expect the big O analysis to be “wrong” for small datasets. I expect that in this case, like in all cases, as the datasets become gallactically large, the O(n) algorithm will start winning again.

why is it strange? the case where asymptotically better = concretely worse is usually the exception, not the norm.

We expect asymptotically better algorithms to be, well, asymptotically better. Even if they lose out for small N, they should win for larger N - and we typically expect this "larger N" to not be that large - just big enough so that data doesn't fit in any cache or something like that.

However, in this particular case, the higher-complexity sorting algorithms gets better than the hash algorithm as N gets larger, even up to pretty large values of N. This is the counter-intuitive part. No one is surprised if an O(n log n) algorithm beats an O(n) algorithm for n = 10. But if the O(n log n) algorithm wins for n = 10 000 000, that's quite surprising.

Re: Hashed sorting is typically faster than hash tables

#15

Post by ants_everywhere »

aDyslecticCrow wrote: post #9
markisus wrote: post #5

Interesting article. It’s actually very strange that the dataset needs to be “big” for the O(n log n) algorithm to beat the O(n). Usually you’d expect the big O analysis to be “wrong” for small datasets. I expect that in this case, like in all cases, as the datasets become gallactically large, the O(n) algorithm will start winning again.

That is what baffles me. The difference in big O complexity should be more visible with size, but thats where it looses to the "worse" algorithm. I could imagine the hash table wins again beyond a even greater threshold. Like what about 120GB and beyond?

As others have pointed out, radix sort is O(64N) = O(N) for a fixed key length of uint64s as in this article

So it comes down to the cost of hashing, hash misses, and other factors as discussed in the article.

I remember learning that radix sort is (almost?) always fastest if you're sorting integers.

A related fun question is to analyze hash table performance for strings where you have no bound on string length.

Re: Hashed sorting is typically faster than hash tables

#17

Post by [deleted] »

tialaramex wrote: post #3

Though big enough to be worthwhile at scale, it's notable how small, relatively, the difference is from the out-of-box Rust unstable sort to the tuned radix sort. Lukas Bergdoll and Orson Peters did some really important heavy lifting to get this stuff from "If you're an expert you could probably tune a general purpose sort to have these nice properties" to "Rust's general purpose sort has these properties out of the…

[deleted]

Re: Hashed sorting is typically faster than hash tables

#20

Post by cdavid »

aDyslecticCrow wrote: post #9
markisus wrote: post #5

Interesting article. It’s actually very strange that the dataset needs to be “big” for the O(n log n) algorithm to beat the O(n). Usually you’d expect the big O analysis to be “wrong” for small datasets. I expect that in this case, like in all cases, as the datasets become gallactically large, the O(n) algorithm will start winning again.

That is what baffles me. The difference in big O complexity should be more visible with size, but thats where it looses to the "worse" algorithm. I could imagine the hash table wins again beyond a even greater threshold. Like what about 120GB and beyond?

the big O copmlexity makes assumptions that break down in this case. E.g. it "ignores" memory access cost, which seems to be a key factor here.

[edit] I should have said "basic big O complexity" makes assumptions that break down. You can ofc decide to model memory access as part of "big O" which is a mathematical model

Post reply on HN