Scientists find optimal space-time balance for hash tables
quantamagazine.org
Scientists find optimal space-time balance for hash tables
1–10 of 67 posts
Re: Scientists find optimal space-time balance for hash tables
#2For 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.
Re: Scientists find optimal space-time balance for hash tables
#3For 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…
love when things like this are ready and waiting on the shelf for when we need them
Re: Scientists find optimal space-time balance for hash tables
#4For 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…
love when things like this are ready and waiting on the shelf for when we need them
In 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.
Re: Scientists find optimal space-time balance for hash tables
#5Somewhat 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
Re: Scientists find optimal space-time balance for hash tables
#6This 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.
Re: Scientists find optimal space-time balance for hash tables
#7Somewhat 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/…
I 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/##LY5BDsIgEEX3PcXsgKQS9wYXRpMu3HkCAlMdbYFQ2q...
Re: Scientists find optimal space-time balance for hash tables
#8This 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.…
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.)
Re: Scientists find optimal space-time balance for hash tables
#9This 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.…
What is a theorist if not someone who works on interesting problems which have a tenuous-at-best relationship with reality?
Re: Scientists find optimal space-time balance for hash tables
#10Earlier quoted context omitted.
love when things like this are ready and waiting on the shelf for when we need them
In 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.
Or 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.