6 ms·
Scientists find optimal space-time balance for hash tables
- vlovich123 3y agoFor 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 “practical” IcebergHT data structure isn’t even one you’d likely encounter as it seems to be a research hash table focusing on persistent memory which isn’t hardware you typically would encounter.
- jakedowns 3y agolove when things like this are ready and waiting on the shelf for when we need them
- opticfluorine 3y agoIn 200 years this is going to be like when we discover yet another proof of Euler or Gauss, 20 years after a current mathematician arrived at the same result.
- TeMPOraL 3y agoOr it could be like multipoint touch screens, early version of which were a solved problem in 1980s or earlier, and just needed compute power to catch up, which it did over subsequent decades. Or it could be like code=data and homoiconity and other CS fundamentals that were figured out 40+ years ago, but are still mostly ignored by software industry/culture.
- vlovich123 3y agoKinda but often times such research isn’t even “waiting on the shelf”. You can see that in the Iceberg paper which describes how earlier constructions optimized for PMEM Hw did a bad job because they were built against simulated hardware. In practice you need to actually iterate with real designs. I doubt such designs will find practical uses (iceberg maybe but the pure math designs seem unlikely).
- refulgentis 3y agoThis 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.
- hinkley 3y ago> “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.
- randomizedalgs 3y agoIcebergHT isn't just for persistent memory (although I can see why you might think it is based on the paper's title). The paper also gives experiments showing that the hash table performs very well in standard RAM, much better than other concurrent implementations.
- vlovich123 3y agoBut the other implementations were against other PMEM hash tables unless I misread? Like no comparison against common c++ or rust implementations.
- randomizedalgs 3y agoI think you may have a backwards. Libcuckoo, CLHT, and TBB are widely used high performance C/C++ DRAM hash tables. I think TBB is the hash table Intel maintains, if I remember right. So the DRAM experiments are apples to apples. It's actually the PMEM experiments, I think, that are comparing a new hash table on a new technology to previous hash tables that weren't designed specifically for that technology.
- vlovich123 3y agoYou’re right. I didn’t see later in the paper where they compare against TBB.
- madars 3y agoSomewhat off-topic but does anyone have a bookmarklet that would remove annoying scrolling behavior on sites like Quanta? I.e. pressing space bar should immediately scroll down a page, not do it slowly with awkward mechanics. In exchange I'm happy to share a bookmarklet that "unsticks" sticky elements of the page (e.g. an ever-visible header like on WaPo, though they are not the worst offender): https://pastebin.com/Vh594168 https://pastebin.com/Vh594168
- btdmaster 3y agoI think they're using sscroll from npm, but not entirely sure. I was able to fix it, but too well, in that now it'll scroll with unbounded speed: https://tio.run/##LY5BDsIgEEX3PcXsgKQS9wYXRpMu3HkCAlMdbYFQ2qYxPTtidTWT935m/lNPejCRQtoNgSzG3rsXLjlbb8YeXZLa2stUlisNCR1GzoofA6sBvxjUEd4VALXANyCNtwhKKWC3oA0ysXn4xWWI2zxjq8cucXGYyVk/y1LCd91p4fv6T8iVbw3S/ZFEObBWq4CcPw https://tio.run/##LY5BDsIgEEX3PcXsgKQS9wYXRpMu3HkCAlMdbYFQ2q...
- abbeyj 3y agoThis is quick and dirty but it works on this particular site: javascript:void(addEventListener('keydown',e=>e.keyCode==32&&e.stopPropagation(),true)
- NooneAtAll3 3y ago...spacebar? shouldn't "down a page" be done with PageDown? who came up with binding this behavior to a spacebar as well??
- jiggawatts 3y agoThis 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. The best current hashtable implementations are all quite far from the purely theoretical computer science optimums, but are faster despite this because they take these factors into account. Back when CPUs were simple and had no virtual memory or caches, there was a good correspondence between theoretical CS algorithms and their real implementations. Now? Everything I see published in this space is basically pure maths with little or no practical utility. It’s still interesting, sure, but it’s a bit sad that the theorists have retreated into a virtual world to escape the messy details of our reality.
- trentnelson 3y agoHey, if you're looking for a real-world pragmatic and performant implementation of a theoretically-cool algorithm, my https://github.com/tpn/perfecthash 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.)
- vlovich123 3y agoMy hunch is that boomphf will outperform and also supports any key type: https://github.com/10XGenomics/rust-boomphf 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 https://arxiv.org/abs/1702.03154
- trentnelson 3y agoWhat’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.
- sylware 3y agooptimal for which use cases?
- andrewp123 3y agoIn 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.
- dkural 3y agoFor 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!
- tdstein 3y agoIt’s a great thing that this report addresses both space and time!
- Donaldoben 3y ago[dead]
- klyrs 3y agoI'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?
- 082349872349872 3y agoThe anti-curious commentary strikes me as being analogous to meth cooks complaining about https://en.wikipedia.org/wiki/High-pressure_chemistry https://en.wikipedia.org/wiki/High-pressure_chemistry research results not being applicable to their (1 bar) "real world" problems. (Edit: it would appear that meth cooks are more appreciative of theoretical advances than programmers; recent european lab busts have revealed synthesis pathways using [similar to Haber-Bosch and Bergius] hundreds of atmospheres of pressure)
- optimalsolver 3y ago>Often times, the first algorithm to establish an asymptotic limit is entirely too complicated and doesn't help at human scale https://en.wikipedia.org/wiki/Galactic_algorithm https://en.wikipedia.org/wiki/Galactic_algorithm
- eimrine 3y agoI expected some cool graphics or livehacks but I see photos of researchers and it is not obvious what link I should follow to move from promotional content to more scientifical one.
- coldtea 3y agoHow about searching for it in Google, instead of clicking a link?
- yalok 3y agoHash 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...
- yalok 3y ago(from https://python-fiddle.com/saved/lN9D7DOQl0bQ8sqnDA94?code=true&output=true&run=true https://python-fiddle.com/saved/lN9D7DOQl0bQ8sqnDA94?code=tr...)
- wenc 3y ago> 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)) And you'll get this result: 10000 values dict size: 501060 10000 values list size: 426620 10000 values array size: 80056 10000 values sparse array size: 80276 EDIT: looks like I was wrong -- I made a mistake in the code. The sparse structure is actually larger. 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.
- cushpush 3y agoWhat is the ratio. Tell me.
- rurban 3y agoHere is the code https://github.com/splatlab/iceberghashtable https://github.com/splatlab/iceberghashtable (from https://prashantpandey.github.io/publication/sigmod23_iceberg/ https://prashantpandey.github.io/publication/sigmod23_iceber...) Need to compare it against my other concurrent hash tables, as they measured only 64bit int performance for keys and values, which is a bit unrealistic. And they only used murmurhash.
- NooneAtAll3 3y agoSecond paper's lower bound has some strange "log(^U_n)" term. Can anyone explain what does that even mean? Logarithm of combinations, as in "log(U!/n!/(U-n)!)"?
- igiveup 3y agoWhat is an optimum in a two-objective (time, space) problem? Also, how exactly does time help to save space? Is this about some sophisticated hash functions? Handling collisions?