Hacker News Reader

This is a bit pessimistic.

Most STOC papers don't directly give an incredibly practical algorithm. But what they do give is insight, and that insight can often be used to improve the practical state of the art. And new bounds get you thinking; there's power in just knowing we can do better. It's like breaking the 4 minute mile -- a lot follows.

From a personal perspective: I quite like some of the techniques they use in the STOC'22 paper, and I have some ideas about how to turn that into a practical improvement for some of my data structures, which _do_ take into account CPU and cache because I'm that kind of geek. (To save you some googling, I'm one of the co-creators of the cuckoo filter, and of the techniques that underlie many practical implementations of cuckoo hashing, particularly those with concurrent access, and some other stuff. A lot of what I do in practical data structures-meets-systems comes from seeing what's happening in theory and finding ways to apply it, even though in doing so I often give up on the optimality bounds, the insights that come from the theory folks are the basis of it.)

Also, note that there are a few flavors of theory. A lot of US theory is quite on the math side of things, with a few exceptions (Mitz, quoted in the article, being one of them). But there's a very thriving applied algorithms community in the world, with a lot of energy in the area in both Europe and South America, and the stuff published in those venues -- again, often derived from or inspired by work such as this STOC paper -- is more immediately applicable.

Cuckoo hashing is such a joy to work with, and feels like a gem produced from the pressure at the intersection of theory and practice.

They are much easier to implement yet feel more fundamental than other open accessing shemes.

I've used tiny cuckoo hash tables with a bounded size of 2,4,...,256 elements as a compression technique for an Adaptive Radix Trie that doesn't require heterogeneous nodes, and I think I've never had more fun in my career as a computer scientist/software engineer.

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

What’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.

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.

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.

> let’s say you have 10^18 items

You won't. Not on a single node.

> The technique is the valuable part as it adds to the mathematician tool kit of how to prove such results.

Agreed.

I'm struggling to think of any possible application that would need anywhere remotely close to 10^18 items. Do you have an example?

I pulled that specific number out of the air and it was intentionally an over exaggeration. We don’t know the crossover point.

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

I think these are more-often called "cache oblivious" algorithms