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

51–60 of 67 posts

Re: Hashed sorting is typically faster than hash tables

#51

Post by gus_massa »

Retric wrote: post #47
gus_massa wrote: post #39

> 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.

N bits doesn’t mean n operations.

Probably N/64 depending, perhaps less if you can use the SIMD but I'm not sure it's possible.

Re: Hashed sorting is typically faster than hash tables

#52

Post by tmyklebu »

Seems like the author is missing a trick?

You can use a simple hash table without probing to classify each number as either (1) first instance of a number in the table, (2) known duplicate of a number in the table, or (3) didn't fit in the table.

If you use a hash table with n buckets and one item per bucket and the input is random, then at least 63% of the distinct numbers in the input will fall into cases 1 or 2 in expectation. Increasing table size or bucket size improves this part of the math.

On really big inputs, it's probably still healthy to do a pass or two of radix sort so that the hash table accesses are cheap.

Re: Hashed sorting is typically faster than hash tables

#53

Post by OskarS »

gregorygoc wrote: post #46
tomp wrote: post #45

Very interesting and cool article, if you love low-level optimisation (like myself!) Interestingly, recently I've been thinking that basically the Big-O notation is essentially a scam, in particular the log(N) part. For small values of N , log(N) is essentially a constant, O(N) . For large values, even so-called linear algorithms (e.g. linear search) are actually O(N log(N)) , as the storage requirements for a single…

> For small values of N, log(N) is essentially a constant, How can I unread this?

If the person who taught you big-O notation didn't point out that for all practical values of N, log(N) is tiny, then they did you a disservice. It is indeed "practically constant" in that sense.

However, when someone says an operation is O(1) vs O(log N), it still tells you something important. Very broadly speaking (tons of caveats depending on problem domain, of course) O(log N) usually implies some kind of tree traversal, while O(1) implies a very simple operation or lookup. And with tree traversal, you're chasing pointers all over memory, making your cache hate you.

So, like, if you have a binary tree with 65000 elements in it, we're talking a height of 15 or 16, something like that. That's not that much, but it is 15 or 16 pointers you're chasing, possibly cache-missing on a significant amount of them. Versus a hash-table lookup, where you do a single hash + one or two pointer dereferences. If this is in a hot path, you're going to notice a difference.

Again, lots of caveats, this article provides a good exception. In this case, the sorting has much more beneficial cache behavior than the hash table, which makes sense. But in general, log(N) hints at some kind of tree, and that's not always what you want.

But yes, don't be afraid of log(N). log(N) is tiny, and log(N) operations are very fast. log(N) is your friend.

Re: Hashed sorting is typically faster than hash tables

#54

Post by SAI_Peregrinus »

henrydark wrote: post #49
gregorygoc wrote: post #46

Earlier quoted context omitted.

> For small values of N, log(N) is essentially a constant, How can I unread this?

I've given the following exercise to developers in a few workplaces: What's the complexity of computing the nth fibonacci number? Make a graph of computation time with n=1..300 that visualizes your answer. There are those that very quickly reply linear but admit they can't get a graph to corroborate, and there are those that very quickly say linear and even produce the graph! (though not correct fibonacci numbers...)

Binet's (or Euler's or de Moivre's) formula for the nth Fibonacci number is (((sqrt(5)+1)/2)^n-(-(sqrt(5)+1)/2)^-n)/sqrt(5). Additions are O(n). Multiplications vary depending on the algorithm, the best known (Harvey-Hoeven) is O(n log(n)) but comes with some nasty constants that probably mean classic Karatsuba or Toom-Cook multiplication (O(n^1.X) for some X will be faster for the range to be graphed, but I'll stick with O(n log(n)) for this. The exponentials will be O(n log(n)^2) in the best known case IIRC. That factor dominates, so I'd say it's probably O(n log(n)^2) but that a graph probably won't start cooperating quickly due to the algorithms picked having factors that are ignored by big-O notation for the small inputs given.

However you do it it probably can't be linear, since multiplication is probably at best O(n log(n)), though that lower bound hasn't been proven. A naive recursive calculation will be even worse since that has exponential complexity.

Re: Hashed sorting is typically faster than hash tables

#55

Post by domador »

orlp wrote: post #23
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…

I (Orson Peters) am also here if anyone has any questions :)

Orson, what motivated you to tune Rust's out-of-the-box sort in this way?

Re: Hashed sorting is typically faster than hash tables

#56

Post by orlp »

domador wrote: post #55
orlp wrote: post #23

Earlier quoted context omitted.

I (Orson Peters) am also here if anyone has any questions :)

Orson, what motivated you to tune Rust's out-of-the-box sort in this way?

Well, years back I released an unstable sort called pdqsort in C++. Then stjepang ported it to the Rust standard library. So at first... nothing. Someone else did it.

A couple years later I was doing my PhD and I spent a lot of time optimizing a stable sort called glidesort. Around the same time Lukas Bergdoll started work on their own and started providing candidate PRs to improve the standard library sort. I reached out to him and we agreed to collaborate instead of compete, and it ended up working out nicely I'd say.

Ultimately I like tinkering with things and making them fast. I actually really like reinventing the wheel, find out why it has the shape that it does, and see if there's anything left to improve.

But it feels a bit sad to do all that work only for it to disappear into the void. It makes me the happiest if people actually use the things I build, and there's no broader path to getting things in people's hands than if it powers the standard library.

Re: Hashed sorting is typically faster than hash tables

#57

Post by kazinator »

This sounds like a spherical cow problem.

The one time in your career you run into it, the next day your boss will add the requirement that entries are going to be inserted and deleted all the time, and your sorting approach is fucked.

If the entries can change all the time, we can use two hash tables, U and D. U maintains the set of unique items at all times, D maintains duplicates. An item is never in both at the same time. In D, it is associated with a count that is at least 2.

A new item is inserted into U. The first duplicate insertion removes the item from U and adds it into D with a count of 2. Subsequent insertions increment the count for that item in D.

A deletion first tries to decrement a count in D, and when that hits below 2, the item is removed from D. If it's not in D, it is removed from U.

At any time we can walk through U to visit all the unique items, without having to deal with spaces of non-unique item.

That has implications for complexity. For instance suppose that for whatever reason, the number of unique items is bounded to sqrt(N). Then iterating over them is O(sqrt(N)), whereas if we just had one hash table, it would be O(N) to iterate over all items and skip the non-unique ones.

Re: Hashed sorting is typically faster than hash tables

#58

Post by krackers »

gus_massa wrote: post #39

> 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.

I guess you have to distinguish between # of elements vs the max bit-width of a an element. But if you're leaving the constant-memory access model (where you can assume each element fits in memory and all arithmetic on them is constant time), then doesn't it take O(n log k) (k is the numeric value of the maximum element, n is total number of elements) to simplify write out the array? You physically can't do O(n) [ignoring the k]

Maybe relevant comments [1, 2, 3]

[1] https://news.ycombinator.com/item?id=44854520 [2] https://news.ycombinator.com/item?id=43005468 [3] https://news.ycombinator.com/item?id=45214106

Re: Hashed sorting is typically faster than hash tables

#59

Post by daemontus »

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.

One detail most comments seem to be missing is that the O(1) complexity of get/set in hash tables depends on memory access being O(1). However, if you have a memory system operating in physical space, that's just not possible (you'd have to break the speed of light). Ultimately, the larger your dataset, the more time it is going to take (on average) to perform random access on it. The only reason why we "haven't noticed" this yet that much in practice is that we mostly grow memory capacity by making it more compact (the same as CPU logic), not by adding more physical chips/RAM slots/etc. Still, memory latency has been slowly rising since the 2000s, so even shrinking can't save us indefinitely.

One more fun fact: this is also the reason why Turing machines are a popular complexity model. The tape on a Turing machine does not allow random access, so it simulates the act of "going somewhere to get your data". And as you might expect, hash table operations are not O(1) on a Turing machine.

Re: Hashed sorting is typically faster than hash tables

#60

Post by randomNumber7 »

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…

All programming languages do what you say, the question is more about how easy it is to say something inappropriate.

For me Rust rarely hits the sweet spot since there are easier languages for high level programs (python, C#, Swift...) and for low level programs you usually want to do unsafe stuff anyway.

I can see usefull applications only where you cannot have a garbage collector AND need a safe high level language. Even there Swift's ARC could be used.

Post reply on HN