3 ms·

For 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 o

For 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 ago
love when things like this are ready and waiting on the shelf for when we need them
- opticfluorine 3y ago
  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.
  - TeMPOraL 3y ago
    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.
- vlovich123 3y ago
  Kinda 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 ago
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.
- 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 ago
IcebergHT 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 ago
  But the other implementations were against other PMEM hash tables unless I misread? Like no comparison against common c++ or rust implementations.
  - randomizedalgs 3y ago
    I 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 ago
      You’re right. I didn’t see later in the paper where they compare against TBB.

jakedowns 3y ago

love when things like this are ready and waiting on the shelf for when we need them

opticfluorine 3y ago
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.
- TeMPOraL 3y ago
  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.
vlovich123 3y ago
Kinda 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 ago

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.

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 ago

IcebergHT 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 ago
But the other implementations were against other PMEM hash tables unless I misread? Like no comparison against common c++ or rust implementations.
- randomizedalgs 3y ago
  I 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 ago
    You’re right. I didn’t see later in the paper where they compare against TBB.