21–30 of 67 posts
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.
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?
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…
It's nice that we can write relatively performant code with the batteries included in these languages and no hand tuning. I only wished it was as easy as that to write code that is secure by default.
Just in case someone feels like porting it to Rust, here is a link to a good and simple quick sort implementation that significantly outperforms standard library one: https://www.ucw.cz/libucw/doc/ucw/sort.html
Earlier quoted context omitted.
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.
It's nice that we can write relatively performant code with the batteries included in these languages and no hand tuning. I only wished it was as easy as that to write code that is secure by default.
I would be happy with code that does what I intended it to do by default.
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 does an admirable job of that part.
Unfortunately because of Rice we must also rule out some cases where what you said wasn't nonsense when we do this. Hopefully not too many. It's pretty annoying when this happens, however, it's also logically impossible to always be sure, Rice again - maybe what you wrote was nonsense after all. So I find that acceptable.
Earlier quoted context omitted.
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…
It's O(k * n), where k is constant with respect to the key size.
For 64-bit keys with 1024 buckets, k==8, so it's O(8 * n) = O(n)