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

Why Hashbrown Does a Double Lookup

gankro.github.io

Post reply on HN
Print view View original

101–110 of 116 posts

Re: Why Hashbrown Does a Double Lookup

#101

Post by btym »

btym wrote: post #89

>And so our "two loops" are usually just "do two simple SIMD operations". Not quite so offensive when you say it like that! No, it's not quite so offensive, but this doesn't explain why it's the best option. Is there no equally-fast way to write the first-tombstone implementation with SIMD instructions? The answer seems to be in the sketch of the implementation, which I'm having trouble understanding. EDIT: I'm watch…

Ok, I got it. They're exactly the same. Either way you'd need to do a second search, because you're trying to differentiate between 3 states: "probably a match", "empty", or "deleted". A much better way than stealing a bit from the hash prefix is using a special value that represents "empty or deleted", and that's exactly what SwissTable does: https://github.com/abseil/abseil-cpp/blob/256be563447a315f2a...

Re: Why Hashbrown Does a Double Lookup

#102

Post by _urga »

Diggsey wrote: post #80
cbhl wrote: post #48

If memory overhead (load factor) isn't a big issue, readers may also find cuckoo hashing rather interesting. (Theoretically, it has a worst-case constant lookup time. Learned about it in one of my university algorithms classes, but have yet to see an implementation in practice.) https://en.wikipedia.org/wiki/Cuckoo_hashing

This seems to assume that all information needed to determine if two keys are equal is incorporated into the resulting hash value. It's premised on the idea that you can dynamically change the hash function such that eventually you will find one with fewer than some fixed number of items sharing the same hash value. There are two problems: 1) It completely undermines the "worst-case constant lookup", because there is…

Those are really questions and issues of implementation than of theory.

1. Tabulation hashing provides guarantees against chosen key attacks.

2. In addition, bucketized cuckoo hashing provides guarantees on the probability of resize (low compared to linear probing), and multiple resizes (very low compared to linear probing).

3. Further, most hash table implementations that I know of have layers of defense, including limiting the number of sequential resizes for a given key.

Putting everything together, if anything, I would be more concerned with the failure mode for linear probing (scanning the whole table before resizing) than for Cuckoo hashing (scanning two fixed-size buckets before resizing).

Re: Why Hashbrown Does a Double Lookup

#103

Post by 0815test »

bsder wrote: post #97
nkurz wrote: post #74

Earlier quoted context omitted.

Could you explain your reasoning? I would think that bounds and overflowing checking should have fantastic performance on modern processors. The almost-always-false test gets correctly predicted as false, speculative execution chooses the correct branch without delay, and a few cycles later (but without visible delay) some simple math confirms that the correct branch was chosen. In my mind, the hardware support is al…

> he almost-always-false test gets correctly predicted as false, speculative execution chooses the correct branch without delay, and a few cycles later (but without visible delay) some simple math confirms that the correct branch was chosen. So, why don't compilers do this already? Nothing stops them. The answer is that they lose a ton of performance. There is a lot of housekeeping in order to keep track of speculati…

> ... So your tight loops all look like "increment I; compare I to 0; compare I to X; do real work" ...

Compilers are generally smart enough to hoist these comparisons out of the loop, at least in a static, AOT-compiled language like Rust.

You're right though that in-order chips are a lot more power-efficient, and the in-order approach is the one that's taken in most RISC-V implementations (which seems to be a highly comparable architecture to the Alpha you mention).

Re: Why Hashbrown Does a Double Lookup

#104

Post by throwaway808080 »

_urga wrote: post #100
cbhl wrote: post #48

If memory overhead (load factor) isn't a big issue, readers may also find cuckoo hashing rather interesting. (Theoretically, it has a worst-case constant lookup time. Learned about it in one of my university algorithms classes, but have yet to see an implementation in practice.) https://en.wikipedia.org/wiki/Cuckoo_hashing

"If memory overhead (load factor) isn't a big issue, readers may also find cuckoo hashing rather interesting." The issue with memory overhead (load factor) is actually something that Cuckoo hashing solves compared to linear probing. Bucketized Cuckoo hashing supports much higher load factors than linear probing. You can have your cake and eat it too. I have implemented hash tables with open addressing and tombstones…

How does cuckoo hashing work for 80% load factor. It may be possible that you fill out both the positions and your eviction algorithm is then no longer constant time for worst case.

AFAIK, cuckoo works best when load factor is less than 50%. Wikipedia seems to also agree with me.

Re: Why Hashbrown Does a Double Lookup

#105

Post by rurban »

asveikau wrote: post #93
rurban wrote: post #87

Earlier quoted context omitted.

It's accepted knowledge that the Google Swisstable is currently the fastest hashtable around. (The C++ implementation) But there are three variants, and this looks like the slowest of the three, but the best for dynamic languages.

It should depend a lot on what you put into it and the access pattern, no? You can talk about averages, about complexity, about benchmarks, but I feel like "fastest hashtable around" is a very odd expression, as if to desire the world to be a lot less complex than it is and for there to be exactly one best.

As I said there are two best, plus the worse third variant. Not implemented by google, only described, but now apparently implemented in Rust. Haven't checked closely, because Rust is kinda unreadable compared to C what exactly is going on. Need to see the SIMD assembly also. You cannot really trust much what's going on with Rust, as there's too much hype and lies, but it undeniably got better recently.

Re: Why Hashbrown Does a Double Lookup

#106

Post by jolux »

mikeash wrote: post #72
jolux wrote: post #69

Earlier quoted context omitted.

It will rebuild the hashtable when that happens. As long as the load factor remains below 50%, (for the most basic implementation) insertions will remain constant anyways. You don't need to allocate new tables.

How is that possible? I insert three pathological keys. The third one collides with both, so it rebuilds the table. The third one still collides with both, so it rebuilds the table again. Repeat. Eventually either we fail or we end up in something that’s worse than constant time.

Have you read about how the algorithm works?

Re: Why Hashbrown Does a Double Lookup

#107

Post by devit »

bsder wrote: post #58
devit wrote: post #24

Earlier quoted context omitted.

The things Rust wants more than other languages are support for fast array bounds checks and fast integer overflow checks. Unfortunately none of the current popular architectures seem to have either.

Unfortunately, fast array bounds checks and fast integer overflow checks are anathema to speculative execution so aren't happening any time soon. I'm becoming convinced that we really need to just go back to the Alpha 21164 architecture and stamp out multiple copies with really fast interconnect.

In Rust you can probably get away with not speculating and thus having "imprecise exceptions" for overflow and maybe array reads (if you don't care about side channels), since panic essentially destroys all non-Mutex-protected accessible memory anyway and Mutex-protected memory is made inaccessible via poisoning (as long as they don't get moved through things like library calls and atomic ops).

It would require a minor compatibility break, significant checking work and changes to unsafe code to make it work, but it should be doable.

Array writes do need precise checking though, since otherwise you can write to arbitrary memory.

Re: Why Hashbrown Does a Double Lookup

#108

Post by mikeash »

jolux wrote: post #106
mikeash wrote: post #72

Earlier quoted context omitted.

How is that possible? I insert three pathological keys. The third one collides with both, so it rebuilds the table. The third one still collides with both, so it rebuilds the table again. Repeat. Eventually either we fail or we end up in something that’s worse than constant time.

Have you read about how the algorithm works?

A bit. When you collide in both tables, you switch to a different hash function and try again. With real-world data, that should work great. But with pathological data (i.e. the worst case behavior) that will never succeed.

Re: Why Hashbrown Does a Double Lookup

#109

Post by [deleted] »

cperciva wrote: post #95
btym wrote: post #86

Earlier quoted context omitted.

I would argue that "the table" is not mutated, only the internal state of its implementation. Every time you access any information, a cache at some layer below you is updated. Is that also gross?

Yes. Normally you can have one thread writing to a data structure OR many threads reading the data structure at any given time and not need to worry about them causing problems. (This situation is common enough that we have things called "reader-writer mutexes" or "shared-exclusive" mutexes.) As soon as your reads can modify the internal state of the data structure, it might modify the state in a way which trips up a…

[deleted]

Re: Why Hashbrown Does a Double Lookup

#110

Post by shittyadmin »

cperciva wrote: post #95
btym wrote: post #86

Earlier quoted context omitted.

I would argue that "the table" is not mutated, only the internal state of its implementation. Every time you access any information, a cache at some layer below you is updated. Is that also gross?

Yes. Normally you can have one thread writing to a data structure OR many threads reading the data structure at any given time and not need to worry about them causing problems. (This situation is common enough that we have things called "reader-writer mutexes" or "shared-exclusive" mutexes.) As soon as your reads can modify the internal state of the data structure, it might modify the state in a way which trips up a…

But you don't need to write every time, only on occasion, so you can actually use a read write lock and in the nominal case many threads can read just fine.

That said, it's probably still better to avoid this unless it's absolutely necessary to modify the underlying structure sometimes, I recently had to do this for an LRU cache.

Post reply on HN