Hacker News Reader

Comment by vlovich123 | Hacker News Reader

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.

View on HN

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.

But the other implementations were against other PMEM hash tables unless I misread? Like no comparison against common c++ or rust implementations.

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.

You’re right. I didn’t see later in the paper where they compare against TBB.

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.

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

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).

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.

Reply on news.ycombinator.com