Hashed sorting is typically faster than hash tables
1–10 of 67 posts
Re: Hashed sorting is typically faster than hash tables
#2Great article. Informative and well written.
Re: Hashed sorting is typically faster than hash tables
#3Though 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 box" and that's going to make a real difference to a lot of software that would never get hand tuned.
Re: Hashed sorting is typically faster than hash tables
#4I 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
Re: Hashed sorting is typically faster than hash tables
#5Interesting 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.
Re: Hashed sorting is typically faster than hash tables
#6Could you reduce the BW requirement of the hash table by using an atomic increment instruction instead of read-modify-write ? It still performs a read modify write, but further down in the hierarchy, where more parallelism is available.
Re: Hashed sorting is typically faster than hash tables
#7I 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.
Re: Hashed sorting is typically faster than hash tables
#8Interesting 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 smaller. The article explains this topic in a less handwavey manner.
Also, memory access is constant time only to some upper limit allowed by the hardware, which requires significant changes to the implementation when the data does not fit the system memory. So, the hash algorithm will not stay O(n) once you go past the available memory.
The sorting algorithms do not suffer from these complexities quite as much, and similar approaches can be used with data sets that do not fit a single system's memory. The sorting-based algorithms will likely win in the galactically large cases.
Edit: Also, once the hash table would need to grow beyond what the hash function can describe (e.g. beyond 64 bit integers), you need to grow the function's data type. This is essentially a hidden log(n) factor, as the required length of the data type is log(n) of the maximum data size.
Re: Hashed sorting is typically faster than hash tables
#9Interesting 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?
Re: Hashed sorting is typically faster than hash tables
#10Interesting 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 analysis in the "Why does sorting win?" section of this article gave us a way to estimate that threshold.
Here's my attempt at it, based on that analysis:
Suppose each item key requires s bytes
For the hash table, assuming s The bandwidth to sort one key is p(N) * 2 * s where p(N) is the number of passes of 1024-bucket radix sort required to sort N elements, and 2 comes from 1 read + 1 write per 1024-bucket radix sort pass
p(N) = ceil(log2(N) / log2(buckets))
Suppose N is the max number of items we can distinguish with an s=8 byte item key, so N = 2^64
then p(N) = ceil(64 / 10) = 7 passes
7 radix passes * (1 read + 1 write) * 8 bytes per item key = 112 bytes of bandwidth consumed, this is still less than the bandwidth of the hash table 2 * 64.
We haven't found the threshold yet.
We need to either increase the item count N or increase the item key size s beyond 8 bytes to find a threshold where this analysis estimates that the hash map uses less bandwidth. But we cant increase the item count N without first increasing the key size s. Suppose we just increase the key size and leave N as-is.
Assuming N=2^64 items and an item size of b=10 bytes gives an estimate of 140 bytes of bandwidth for sorting vs 128 bytes of bandwidth. we expect sorting to be slower for these values, and increasing b or N further should make it even worse.
(the bandwidth required for hash map hasnt increased as our 10 byte b is still less than the size of a cache line)
edit: above is wrong as i'm getting mixed up with elements vs items. elements are not required to be unique items. if elements are unique items then the problem is trivial. So N is not bounded by the key size, and we can increase N beyond 2^64 without increasing the key size s beyond 8 bytes.
keeping key size s fixed at 8 bytes per item suggests the threshold is at N=2^80 items
given by solving for N for the threshold where bandwidth estimate for sort = bandwidth estimate for hash table
2 * 8 * (log2(N) / log2(1024)) = 2 * 64