[dead]
Scientists find optimal space-time balance for hash tables
21–30 of 67 posts
Re: Scientists find optimal space-time balance for hash tables
#22In my opinion space limited solutions are not very interesting. Time complexity is always >= space complexity, so finding optimal time solutions is always more interesting. And we already knew the optimal time complexity. I appreciate a theoretical time vs space relation, but it doesn’t seem applicable to other areas.
For achieving speed, often you'd like to keep your hash table in RAM. Space limits result in speed trade-offs. This is very much a real-world concern when writing genome aligners. Hash-based mappers were at a disadvantage early on due to the memory constraints of most servers back around 2009-2012, thus the more efficient Burrows-Wheeler transform based algorithms became popular, partly due to significantly reduced RAM needs - one could now align genomes on a laptop!
Re: Scientists find optimal space-time balance for hash tables
#23For anyone curious this is about a 2023 paper proving that a 2022 theoretical hash table construction achieved not only an upper bound in performance in terms of time and space, the construction also achieved a lower bound. It’s a theoretical construction so not actually a practical one you’d find in your software toolkit (constants are too large for most applications, likely even realistic databases). The referenced…
This is so strange to me.
I'm hoping because Quanta's explanation was approachable, but ultimately, wrong when I try applying it the following way:
Theorists will spend an enormous amount of time developing algorithms that are O(kNlog(N)) that are impractical in practice because
- K approximates infinity
- It is well-known K approximates infinity.
- It is not expected for K to decrease.
Re: Scientists find optimal space-time balance for hash tables
#24Earlier quoted context omitted.
Hey, if you're looking for a real-world pragmatic and performant implementation of a theoretically-cool algorithm, my https://github.com/tpn/perfecthash project might fit the bill. It's geared to generating perfect hash tables with the fastest possible lookup/index times (for 32-bit keys), for key sets in the <=100,000 range. (It scales well up to millions of keys, but the solving time takes a lot longer.)
My hunch is that boomphf will outperform and also supports any key type: https://github.com/10XGenomics/rust-boomphf Construction is ~10m keys/s on old hardware and uses very few bits per key. Implementation is based on the bbhash paper: https://arxiv.org/abs/1702.03154
What’s its fastest index function look like in assembly? My MultiplyShiftRX clocks in at like 5 cycles on x64 and 3 cycles on my M1. Mine is optimized for offline table generation so construction speed isn’t really relevant for its primary use.
Re: Scientists find optimal space-time balance for hash tables
#25I'm a bit sad to see the anti-curious commentary here. This result is really cool, and finds the asymptotic sweet spot for hash table memory usage. Often times, the first algorithm to establish an asymptotic limit is entirely too complicated and doesn't help at human scale. If the world collectively ignores such results, as many here seem inclined to do, that's the end of the story. But when somebody continues bashing their head into this wall, sometimes a really good algorithm falls out, which hits that asymptotic performance benefit at a human-useful scale.
The thing I'm curious about (as I haven't had time to cozy up with the paper, and I'm about to run) is how they hit that runtime. What's the big idea? Or is it just the gestalt of a dozen slightly clever ideas?
Re: Scientists find optimal space-time balance for hash tables
#26This kind of thing is unfortunately not useful at any scale. Real computer systems have performance that varies due to memory locality and size. Locality because of things such as cache hierarchy and even the size of cache lines and memory pages. Size because of physical implementation: larger memories are physically bigger and hence further away. The speed of light makes access to larger memories inescapably slower.…
This is a bit pessimistic.
Most STOC papers don't directly give an incredibly practical algorithm. But what they do give is insight, and that insight can often be used to improve the practical state of the art. And new bounds get you thinking; there's power in just knowing we can do better. It's like breaking the 4 minute mile -- a lot follows.
From a personal perspective: I quite like some of the techniques they use in the STOC'22 paper, and I have some ideas about how to turn that into a practical improvement for some of my data structures, which _do_ take into account CPU and cache because I'm that kind of geek. (To save you some googling, I'm one of the co-creators of the cuckoo filter, and of the techniques that underlie many practical implementations of cuckoo hashing, particularly those with concurrent access, and some other stuff. A lot of what I do in practical data structures-meets-systems comes from seeing what's happening in theory and finding ways to apply it, even though in doing so I often give up on the optimality bounds, the insights that come from the theory folks are the basis of it.)
Also, note that there are a few flavors of theory. A lot of US theory is quite on the math side of things, with a few exceptions (Mitz, quoted in the article, being one of them). But there's a very thriving applied algorithms community in the world, with a lot of energy in the area in both Europe and South America, and the stuff published in those venues -- again, often derived from or inspired by work such as this STOC paper -- is more immediately applicable.
Re: Scientists find optimal space-time balance for hash tables
#27Hash tables are nice & all, and it's very convenient to use them,
BUT I really regret how they create propensity for junior developers to use them even in cases where they are not really needed and more memory-efficient (and perf too) data structure could be used.
Anecdotally, in my recent year of interviewing new candidates, I keep asking this simple question: come up with the most efficient data structure to store highly sparse data (say vector), that will need to be access only sequentially. E.g., we have a 1M int32 values vector, and only 10K values are non-zero.
90% of the candidates suggest using the hash table (especially if they prefer to use Python for the interview).
I then ask them to estimate (roughly) the size of the memory, required to store those 10K values.
Some say they need 10KB (they struggle to convert int32 to the count of bytes as well ;( ). Some say 40KB (a bit better, but they forget about keys). Less than 20% arrive to 80KB. Very few suggest that it's something higher than 80KB...
Most struggle to account for the pointers that inevitably should be there if values are not allocated in contiguous memory. Most forget about the hashmap itself.
Fwiw, here's some primitive comparison of memory taken by Python's dict, list and numpy's array:
10000 values dict size: 500568
10000 values list size: 426516
10000 values array size: 80056
500KB/80KB - > 6x times overhead...
Re: Scientists find optimal space-time balance for hash tables
#28Hash tables are nice & all, and it's very convenient to use them, BUT I really regret how they create propensity for junior developers to use them even in cases where they are not really needed and more memory-efficient (and perf too) data structure could be used. Anecdotally, in my recent year of interviewing new candidates, I keep asking this simple question: come up with the most efficient data structure to store…
Re: Scientists find optimal space-time balance for hash tables
#29Hash tables are nice & all, and it's very convenient to use them, BUT I really regret how they create propensity for junior developers to use them even in cases where they are not really needed and more memory-efficient (and perf too) data structure could be used. Anecdotally, in my recent year of interviewing new candidates, I keep asking this simple question: come up with the most efficient data structure to store…
(from https://python-fiddle.com/saved/lN9D7DOQl0bQ8sqnDA94?code=tr... )
> come up with the most efficient data structure to store highly sparse data (say vector), that will need to be access only sequentially.
There's something even more efficient -- a sparse array. I worked in the sparse linear algebra space, and you can gain a lot from sparsity. Add this to your fiddle:
from scipy.sparse import csc_array
sp_array = csc_array(my_list, dtype=np.int32)
print(SZ, " values sparse array size: ", get_obj_size(sp_array))
10000 values dict size: 501060
10000 values list size: 426620
10000 values array size: 80056
10000 values sparse array size: 80276
Also in my earlier result of 280 bytes, the get_obj_size might be reading the metadata part of the data structure. 10k int32 objects (4 bytes) each will not compress to 280 bytes.
But my point in general holds -- sparse structures are usually more efficient to work with than dense structures, especially when you have really large matrices.
Re: Scientists find optimal space-time balance for hash tables
#30For anyone curious this is about a 2023 paper proving that a 2022 theoretical hash table construction achieved not only an upper bound in performance in terms of time and space, the construction also achieved a lower bound. It’s a theoretical construction so not actually a practical one you’d find in your software toolkit (constants are too large for most applications, likely even realistic databases). The referenced…
This is so strange to me. I'm hoping because Quanta's explanation was approachable, but ultimately, wrong when I try applying it the following way: Theorists will spend an enormous amount of time developing algorithms that are O(kNlog(N)) that are impractical in practice because - K approximates infinity - It is well-known K approximates infinity. - It is not expected for K to decrease.
> “But in practice, constants really matter,” he said. “In the real world, a factor of 10 is a game ender.”
Working at a place who kept losing customers to a competitor whose software was less than 2x as fast as ours fundamentally changed how I view optimization and how I view constant overhead C. And crystalized once I saw how delivering steady gains milestone after milestone can buy a lot more goodwill than one fast and dirty optimization.
Speed doesn't matter if you're the only game in town (a monopoly). For everything else it matters.