Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Scientists find optimal space-time balance for hash tables

quantamagazine.org

Post reply on HN
Print view View original

11–20 of 67 posts

Re: Scientists find optimal space-time balance for hash tables

#11

Post by andersa »

jiggawatts wrote: post #6

This 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.…

Yep, it's the same thing every time. "We propose this new thing with optimal time complexity blah blah blah" - don't care. Show benchmark. What do you mean it's slower than this basic but cache efficient hash table implemented in 100 lines of c++?

Re: Scientists find optimal space-time balance for hash tables

#13

Post by zogrodea »

kevinventullo wrote: post #9
jiggawatts wrote: post #6

This 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?

Related sentiment to the above post: https://golem.ph.utexas.edu/category/2009/09/the_mathematica... .

Re: Scientists find optimal space-time balance for hash tables

#14

Post by vlovich123 »

trentnelson wrote: post #8
jiggawatts wrote: post #6

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

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

Re: Scientists find optimal space-time balance for hash tables

#15

Post by abbeyj »

madars wrote: post #5

Somewhat 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/…

This is quick and dirty but it works on this particular site:

javascript:void(addEventListener('keydown',e=>e.keyCode==32&&e.stopPropagation(),true)

Re: Scientists find optimal space-time balance for hash tables

#16

Post by vlovich123 »

andersa wrote: post #11
jiggawatts wrote: post #6

This 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.…

Yep, it's the same thing every time. "We propose this new thing with optimal time complexity blah blah blah" - don't care. Show benchmark. What do you mean it's slower than this basic but cache efficient hash table implemented in 100 lines of c++?

This is a totally different result. It’s providing a proof of an algorithmic complexity. So let’s say you have 10^18 items, it’s likely you’d be using this even if certain algorithms are faster at smaller numbers. It’s also important to note the particularly interesting result is how the mathematicians proved that the earlier design was optimal (upper and lower bound). The technique is the valuable part as it adds to the mathematician tool kit of how to prove such results. This article is about math papers / functional theoretic math, not about applies CS ideas.

Re: Scientists find optimal space-time balance for hash tables

#17

Post by vlovich123 »

jakedowns wrote: post #3
vlovich123 wrote: post #2

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…

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

Re: Scientists find optimal space-time balance for hash tables

#18

Post by jiggawatts »

zogrodea wrote: post #13
kevinventullo wrote: post #9

Earlier quoted context omitted.

What is a theorist if not someone who works on interesting problems which have a tenuous-at-best relationship with reality?

Related sentiment to the above post: https://golem.ph.utexas.edu/category/2009/09/the_mathematica... .

For reference, I enjoy (and have formally studied) both theoretical physics and pure theoretical mathematics. I get the "value" of both, even when the value is extremely abstract and removed from practical utility.

However.

Theoretical physics especially is grounded in reality. Sure, it has its frictionless cows and whatnot, but generally a connection with the real world is maintained.[1] In other words, it's possible to take an idealised theory and then sprinkle the messy details on top, such as friction and air resistance.

What I'm seeing in computer science is different. Their theories are not the type that need a slight quantitative adjustment to match reality in the sense of adding a 1% extra fine-tuning factors, but they're qualitatively wrong. They're wrong not by constant factors or constant offsets, but big-O notation wrong. The equations have the wrong powers in them! Missing square roots or logarithms!

It's as if the working engineers had switched from Newtonian to Relativistic Mechanics because we've colonised the Solar System, but all theoretical physicists are basically pretending that only Newtonian mechanics is worthy of study and that Lorentzian mechanics is just a fudge factor that can be ignored forever and ever. Even when we all live in space with multi-hour communication delays caused by the speed of light. "Just set that to zero and then..."

[1] One notable exception to this that grinds my gears is a habit of publishing papers about results that only apply in non-real toy models, such as 2+2 dimensional spacetime, but not putting a big warning box before the abstract to warn journalists that nothing in the paper applies to our reality.

Re: Scientists find optimal space-time balance for hash tables

#19

Post by mabster »

jiggawatts wrote: post #6

This 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.…

I haven't kept up in this space, but there was a bunch of papers under "cache agnostic algorithms" that were actually taking the concept of cache into account. The cache agnostic here being regardless of cache size, sort of treating cache in the O() sense.

You could still beat them by tweaking for your hardware. But for the first time there was research into why Q sort is faster than heap sort

Re: Scientists find optimal space-time balance for hash tables

#20

Post by andrewp123 »

In 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.
Post reply on HN