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

31–40 of 67 posts

Re: Hashed sorting is typically faster than hash tables

#31

Post by swiftcoder »

aDyslecticCrow wrote: post #7
nasretdinov wrote: post #4

I imagine it must make a bigger difference in languages where allocations are more costly too. E.g. in Go sorting to count uniques is most certainly much faster than using a map + it saves memory too

This doesnt concerns in-language allocations at all. There is only one large allocation for both, done up-front. The slowdowm has to do with cashe misses and cpu cashe capacity, which is optimisations the cpu does when executing. Granted, a language like go may have more of the cpu cashe used up by different runtime checks. Basically, i think this analysis largely language agnostic.

It's not language agnostic in the sense that some languages don't have the necessary functionality to allocate everything up front and avoid allocations in the hot loop.

For example, if you were to benchmark this in Java, the HashMap class allocates (twice!) on every insertion. Allocations are a bit cheaper with the GC than they would be via malloc/friends, but still we'd expect to see significant allocator and hence GC overhead in this benchmark

Re: Hashed sorting is typically faster than hash tables

#32

Post by tialaramex »

aDyslecticCrow wrote: post #7
nasretdinov wrote: post #4

I imagine it must make a bigger difference in languages where allocations are more costly too. E.g. in Go sorting to count uniques is most certainly much faster than using a map + it saves memory too

This doesnt concerns in-language allocations at all. There is only one large allocation for both, done up-front. The slowdowm has to do with cashe misses and cpu cashe capacity, which is optimisations the cpu does when executing. Granted, a language like go may have more of the cpu cashe used up by different runtime checks. Basically, i think this analysis largely language agnostic.

If we used C++ the standard library's hash set type std::unordered_set doesn't have the all-in-one reserve mechanic. We can call reserve, but that just makes enough hashtable space, the linked list items it will use to store values are allocated separately each time one is created.

I mean, that type is also awful, so early in tuning for this application you'd pick a different map type, but it is the standard in their language.

Re: Hashed sorting is typically faster than hash tables

#33

Post by o11c »

Note that "fixes bad distributions" is the same thing as "causes bad distributions" if your input is untrusted (or even if you're just unlucky). Especially when you are deliberately choosing a bijective function and it is trivial for an attacker to generate "unfortunate" hashes.

The usual trie tricks can avoid this problem without letting the worst case happen. But as often, adding the extra logic can mean worse performance for non-worst-case input.

Re: Hashed sorting is typically faster than hash tables

#34

Post by pygy_ »

o11c wrote: post #33

Note that "fixes bad distributions" is the same thing as "causes bad distributions" if your input is untrusted (or even if you're just unlucky). Especially when you are deliberately choosing a bijective function and it is trivial for an attacker to generate "unfortunate" hashes. The usual trie tricks can avoid this problem without letting the worst case happen. But as often, adding the extra logic can mean worse perf…

You could also use a random salt (for i64, add it up with wrap around overflow) with minimal overhead.

Re: Hashed sorting is typically faster than hash tables

#35

Post by tialaramex »

bluecalm wrote: post #25

While the main conclusion of the article isn't unexpected to me I am very surprised a well optimized quicksort isn't faster than radix sort. My experience in C is that you can significantly speed-up quick sort by removing function calls and doing insertion sorts on small arrays at the end. I was never able to get radix sort even close to that performance wise. I don't know Rust at all so it would be pointless for me…

> it would be pointless for me to try to code an optimized quick sort in it.

Perhaps more so than you've realised. Hint: Rust's old unstable sort was its take on the pattern defeating quicksort. The article is talking about the new unstable sort which has better performance for most inputs.

Rust uses monomorphization and its function types are unique, so the trick you're used to with a macro is just how everything works all the time in Rust.

Re: Hashed sorting is typically faster than hash tables

#36

Post by bluecalm »

tialaramex wrote: post #35
bluecalm wrote: post #25

While the main conclusion of the article isn't unexpected to me I am very surprised a well optimized quicksort isn't faster than radix sort. My experience in C is that you can significantly speed-up quick sort by removing function calls and doing insertion sorts on small arrays at the end. I was never able to get radix sort even close to that performance wise. I don't know Rust at all so it would be pointless for me…

> it would be pointless for me to try to code an optimized quick sort in it. Perhaps more so than you've realised. Hint: Rust's old unstable sort was its take on the pattern defeating quicksort. The article is talking about the new unstable sort which has better performance for most inputs. Rust uses monomorphization and its function types are unique, so the trick you're used to with a macro is just how everything wo…

The trick is not about macros but about removing function calls altogether. Macros are there only to generate functions for specific types. The way the trick works is to implement the stack manually and put indexes there instead of passing them as function arguments. This removes a lot of overhead and makes the implementation I linked to significantly faster than C's and C++'s standard library implementation.

Re: Hashed sorting is typically faster than hash tables

#38

Post by kbolino »

tialaramex wrote: post #29
randomNumber7 wrote: post #24

Earlier quoted context omitted.

I would be happy with code that does what I intended it to do by default.

Do-What-I-Mean isn't possible. What Rust does give you is Do-What-I-Say which mostly leaves the problem of saying what you mean, a significant task but one that is hopefully what software engineering was training you to be most effective at. One important trick is ruling out cases where what you said is nonsense. That can't be what you meant so by ruling it out we're helping you fall into the pit of success and Rust…

What is "Rice" referring to?

Re: Hashed sorting is typically faster than hash tables

#39

Post by gus_massa »

> Hash tables win the interview O(n) vs O(n log n),

If the original table has n entries, the hash must have at least log(n) bits to get most of the time a different hash. I don't know the current state of the art, but I think the recommendation was to have at most a 95% filled array, so the are not too many collision. So both methods are O(n log n), one under the hood and the other explicitly.

Re: Hashed sorting is typically faster than hash tables

#40

Post by zahlman »

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.

Radix sort isn't a comparison-based sort, so it isn't beholden to the O(n log n) speed limit in the same way. It's basically O(n log k), where k is the number of possible different values in the dataset. If we're using machine data types (TFA is discussing 64-bit integers) then k is a constant factor and drops out of the analysis. Comparison-based sorts assume, basically, that every element in the input could in principle be distinct.

Basically, the hashed sorting approach is effectively actually O(n), and is so for the same reason that the "length of hash table" approach is. The degenerate case is counting sort, which is a single pass with a radix base of k. (Which is analogous to pointing out that you don't get hash collisions when the hash table is as big as the hashed key space.)

Post reply on HN