Undergraduate shows that searches within hash tables can be much faster

> I'm beginning to think that the best way to approach a problem is by either not being aware of or disregarding most of the similar efforts that came before. This makes me kind of sad, because the current world is so interconnected, that we rarely see such novelty with their tendency to "fall in the rut of thought" of those that came before. The internet is great, but it also homogenizes the world of thought, and that kind of sucks.

I think this is true only if there is a novel solution that is in a drastically different direction than similar efforts that came before. Most of the time when you ignore previous successful efforts, you end up resowing non-fertile ground.

In my experience the best approach is to first try to solve the problem without having read the prior work, then read the prior work, then improve your approach based on the prior work.

If you read the prior work too early to you get locked into existing mindsets. If you never read it then you miss important things you didn’t thought of.

Even if your approach is less good than the prior work (the normal case) you gain important insights into why the state of the art approach is better by comparing it with what you came up with.

> The developer of Balatro made an award winning deck builder game by not being aware of existing deck builders.

He was aware of deck builders and was directly inspired by Luck be a Landlord, but he was not aware of just how massive the genre is.

Direct quote from the developer:

> The one largest influence on Balatro was Luck Be a Landlord. I watched Northernlion play for a few videos and loved the concept of a non-fanatsy themed score attach roguelike a ton, so I modified the card game I was working on at the time into a roguelike.

> I cut myself off from the genre at that point intentionally, I wanted to make my own mistakes and explore the design space naively just because that process is so fun. I hear the comparison to Slay the Spire a lot but the truth is that I hadn't played that game or seen footage of it when I designed Balatro, not until much later.

https://www.reddit.com/r/Games/comments/1bdtmlg/comment/kup7...

  “They’re cheering for you,” she said with a smile. 
  “But I could never have done it,” [Milo] objected, “without everyone else’s help.”
  “That may be true,” said Reason gravely, “but you had the courage to try; 
     and what you can do is often simply a matter of what you will do.”
  “That’s why,” said King Azaz, “there was one very important thing about your quest 
     that we couldn’t discuss until you returned.”
  “I remember,” said Milo eagerly. “Tell me now.”
  “It was impossible,” said the king, looking at the Mathemagician.
  “Completely impossible,” said the Mathemagician, looking at the king.
  “Do you mean … ,” said the bug, who suddenly felt a bit faint.
  “Yes, indeed,” they repeated together, “but if we’d told you then, you might not have gone … 
    and, as you’ve discovered, so many things are possible just as long as you don’t know they’re impossible.”

A professor I had in college, whose first published result was from a piece of homework he turned in where he incidentally solved an open question about bound on a problem, had a curious habit.

I ended up failing and taking his course again (because I had A Lot going on in college), and thus, noticed something.

Each semester, on one of the assignments in the latter half of the class, he assigned one problem out of, perhaps, 30 in the problem set, where as written, it was actually an open problem, and then a day or two before they were due, he'd send out an "oops, my bad" revised version.

I suspect that this was not an accident, given that it always happened only once.

I think going one layer lower - the fundamental issue is that the internet drives people to unrealistic perceptions of the competence of others. Think about all of the undeniably brilliant people that have been involved in software over the past 40 years, and how many of them used hash tables in performance critical environments. Let alone mathematicians and others using them in applied domains. And you think there's something fundamental that all of these people just somehow missed?

The argument of 'if that's such a good idea, why wouldn't somebody have just done it already?' seems to have grown exponentially with the advent of the internet. And I think it's because the visibility of competence of other's became so much more clear. For those who lived through e.g. Carmack's Golden Age you knew you were never going to be half the coder he was, at least based on the image he successfully crafted. That 'slight' at the end is not to say he wasn't a brilliant developer or even perhaps the best in the world at his peak, but rather that brilliance + image crafting creates this Gargantuan beast of infallibility and exceptionalism that just doesn't really exist in reality. I think it's from this exact phenomena that you also get the practical fetishism of expertise.

Picking two examples out of all people approaching problems, while ignoring wasted effort and failures to make progress because of not understanding current knowledge, is an absolutely terrible reason to approach from ignorance.

The biggest gains in theory and in practice are far more often obtained by masters of craft, giving much more weight to attacking problems from a position of knowledge.

In fact, even in this case, this progress required that the author was aware of very recent results in computer science, was thinking deeply about them, and most likely was scouring the literature for pieces to help. The “Tiny Pointers” paper is mentioned directly.

A similar idea came up in Veritasium's latest video today. Training AI by DeepMind to predict protein folding greatly improved by withholding the most evident information about a protein's primary structure — its linear polypeptide chain — within the The Structure Module step. [0]

After asking ChatGPT not to agree with me that your comment and these two different approaches to solving problems are the alike, it concluded there still might be similarities between the two.

[0] https://youtu.be/P_fHJIYENdI?feature=shared&t=1030

[1] https://chatgpt.com/share/67aa8340-e540-8004-8438-3200e0d4e8...

Actually they propose two algorithms: Funnel Hashing and Elastic Hashing. Funnel Hashing is "greedy" and defeats the Yao's conjecture that concerns greedy hash mechanisms. Elastic Hashing is "non-greedy" and provides a better amortized time than greedy algorithms.

That it circumvents Yao’s conjecture by being non-greedy contradicts the article. Is the article wrong or is your understanding of the paper? I don’t know, just want to see if you’re noticing something the article’s authors don’t know.

One thing I don't understand from watching the video, is what happens in the (very rare) case that you get collisions all the way down the funnel. I assume this is related to the "One special final level to catch a few keys" (around 14:41 in the video), but given that it has to be fixed size, this can also get full. What do you do in that case?

Quite a neat idea that could be useful for memory-constrained environments.

[Shameless plug]:

If you are into hashtables, you might want to check out Dandelion Hashtable [0]. We use it in our next-generation databases, and it was published in HPDC'24. It is currently the fastest in-memory hashtable in practice.

It improves closed addressing via bounded-cacheline chaining to surpass 1B in-memory requests/second on a commodity server.

[0] https://dandelion-datastore.com/#dlht

Funnel hashing is greedy.

This strikes me as something that many people probably figured out a non-rigorous version of and didn't think it was special.

It's kind of one of those resource management hacks you do when you're constrained and screwed by limitations. Splitting things up by priority is a common go-to for resource allocation. This is a spin on that.

I wonder how many other "in the trenches hacks" people have done that overturn widely accepted things the inventors didn't realize were a big deal: "well I usually have a bunch of deliveries to make and I've figured out a clever way to map out the quickest path... "

Don't get me wrong - recognizing it and then formalizing it, doing the work, publishing the paper - that's a lot of effort. I'm not taking that away.

Thanks so much for this link. I remain convinced that papers are so much more understandable with an accompanying talk by the creators. I wish papers would just come with a video talk included.

Thanks for the video, def a lot better than the article.

I do find it a bit weird that this is somehow better than just over-allocating (and thus reducing the chances of key collisions, which also makes worst case 'less worse') given his approach also allocates more memory through the aux arrays.

I might be misreading their algorithm, but from my look at the paper the key improvement is a non-uniform strategy where they divide the array into buckets and focus on different buckets as they fill the table. This increases the average number of locations to be probed even when the table is emptier. They still place the item in the first empty slot they see with this strategy.

The "skipping slots" has to do with jumping ahead in the hash sequence.

But you could do some hybrid, where you do greedy fill for a while and then switch to this fancier fill once your table is approaching full (using some heuristic)?

Easy stuff.

Convert table row to a string, json to whatever

Apply base16 to the that variable

You've now got a base16 string of that data.

Create a hash table, setup a key value for that base16 string.

You now have a container holding the data.

All you need to do is decode the hex string and you've got base32 data.

Proofs of constant time operations include time taken to resize the table. This takes much more time (linear in the size of the table), on insertions when the table is resized, but that time is amortized over all the insertions already done. It still works out to constant average time if you grow the table enough each time (once it starts to get too full) so it happens with decreasing frequency.

>What seemed crazy was how they could be so much better than trees, which to me were intuitively the most efficient way to store data.

Trees (sorted) are good at finding subsets and ranges "scanning" or "searching" but hashmaps are better at "seeking" like a key-value lookup

I think this is only true in the imperative world, where mutation is used. For the functional world it is probably still trees.

It looks to me like the idea is, as you generally describe, that you segment your table into a 2d structure (well conceptually) and proceed to fill one ‘row’ at a time until it’s about 75% full, at which point you move on to the next one.

I don’t have time to fully grok the paper, but they claim this makes insertion consistently fast (I believe this until we’re at 75% of total capacity, but maybe they have some other mode for filling when they’re at 75% in every row?). They also claim retrieval is fast, and I didn’t read enough to understand how even retrieval works, or why it is faster.

I’ll put out that there a lot of times that it would be really nice to have a nearly full hash table still, you know, work. You can’t always change the size of one during execution of a program. And, in some environments memory counts a lot. That said, I would like to see and play with an implementation — I’m not sure this is ‘worth it’ in the general case.

It is also probably cache inefficient, as are most things about hash tables, with the exception of linear probing for reading out of a fairly full one, in which case, you get to just keep pulling stuff directly out of memory to check it. So, it’s not clear to me that this is performance wise worth it. Anyway, I’d like to fully understand it, it seems like an interesting new idea.

I haven't read the paper, but sometimes asymptotic improvements do not translate to real world improvements due to a large multiplicative factor in the complexity that gets factored out in the O() analysis. So the dataset required to see speed-up is impractically large.

I'm not up to date on the state of the art but I've implemented hash tables a few times and we would expand the hash table whenever it was 75% full, which means x is never greater than 4. Improving the runtime from O(x) to O((log x)^2) doesn't matter when x is so small.

I imagine there are some niche memory-constrained applications where you'd let x get larger but I never ran into them personally.

I'm pretty sure nobody uses uniform probing hash tables in the wild. Every time I have wanted to have very high load factors (>90%), cuckoo hashing has been good enough, and below 70-80%, linear probing is blazing fast and absolutely good enough.

In practice the worst-case operations are avoided by reserving a little more space for the hash table. And the new results come at the cost of slower “good case” insertions.

Complexity analysis and actual systems programming have been diverging for a while. I don't see anything in the paper that will inform practice.

Most real-world hash table implementations are not "theoretical" but depends on "real" parameters like L2 cache, assembly instruction sizes, etc

Isn’t the problem that the scaling behavior only dominates with infinite n?

If you have a constant factor, that doesn’t go into the scaling rule, so having something scale (log x)2 could still be 100 times more expensive than something that scales linearly with x for all x smaller than 2^100.

it improves the worse case cost given a nearly full hash map, it hurts raises the cost in other cases.

Yes, which is what most real world hash tables do. They resize themselves once hash collision is too probable.

In reality 75% is the standard fill factor for linear probe that also exhibits the best locality (if the table gets too full it just allocated double (or x) the memory, and copies the existing entries). Most non-linear probe tables (e.g. cookoo) suffer due to the fact RAM is not 'random' at all.

Put my attempt here: https://github.com/sternma/optopenhash