5 ms·

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 beca

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

trentnelson 3y ago
Hey, if you're looking for a real-world pragmatic and performant implementation of a theoretically-cool algorithm, my https://github.com/tpn/perfecthash 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.)
- vlovich123 3y ago
  My hunch is that boomphf will outperform and also supports any key type: https://github.com/10XGenomics/rust-boomphf 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 https://arxiv.org/abs/1702.03154
  - trentnelson 3y ago
    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.
kevinventullo 3y ago
What is a theorist if not someone who works on interesting problems which have a tenuous-at-best relationship with reality?
- zogrodea 3y ago
  Related sentiment to the above post: https://golem.ph.utexas.edu/category/2009/09/the_mathematical_vocation.html https://golem.ph.utexas.edu/category/2009/09/the_mathematica... .
  - jiggawatts 3y ago
    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.
andersa 3y ago
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++?
- vlovich123 3y ago
  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.
  - Dylan16807 3y ago
    > 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.
  - andersa 3y ago
    I'm struggling to think of any possible application that would need anywhere remotely close to 10^18 items. Do you have an example?
    - vlovich123 3y ago
      I pulled that specific number out of the air and it was intentionally an over exaggeration. We don’t know the crossover point.
mabster 3y ago
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
- randomizedalgs 3y ago
  I think these are more-often called "cache oblivious" algorithms
dgacmu 3y ago
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.
- j-pb 3y ago
  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.

trentnelson 3y ago

Hey, if you're looking for a real-world pragmatic and performant implementation of a theoretically-cool algorithm, my https://github.com/tpn/perfecthash 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.)

vlovich123 3y ago
My hunch is that boomphf will outperform and also supports any key type: https://github.com/10XGenomics/rust-boomphf 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 https://arxiv.org/abs/1702.03154
- trentnelson 3y ago
  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.

kevinventullo 3y ago

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

zogrodea 3y ago
Related sentiment to the above post: https://golem.ph.utexas.edu/category/2009/09/the_mathematical_vocation.html https://golem.ph.utexas.edu/category/2009/09/the_mathematica... .
- jiggawatts 3y ago
  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.

andersa 3y ago

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

vlovich123 3y ago
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.
- Dylan16807 3y ago
  > 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.
- andersa 3y ago
  I'm struggling to think of any possible application that would need anywhere remotely close to 10^18 items. Do you have an example?
  - vlovich123 3y ago
    I pulled that specific number out of the air and it was intentionally an over exaggeration. We don’t know the crossover point.

mabster 3y ago

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

randomizedalgs 3y ago
I think these are more-often called "cache oblivious" algorithms

dgacmu 3y ago

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.

j-pb 3y ago
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.