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

41–50 of 116 posts

Re: Why Hashbrown Does a Double Lookup

#41

Post by barrkel »

amalcon wrote: post #23
shittyadmin wrote: post #14

Earlier quoted context omitted.

Interesting, both the Qt and Java ones seem to use chaining, but I guess they're not designed with these sorts of extremely demanding applications in mind.

One thing to note is that this performance tradeoff is actually the reverse of what it was ~20 years ago. This is because CPU speeds have improved dramatically more than RAM speeds over a similar period. Open addressing does do more comparisons than chaining. It used to save time to traverse the linked list rather than to spend CPU cycles on those additional comparisons. Now, because CPU cycles are relatively cheaper…

If hash codes are stored inline alongside keys, code comparisons can be made without an indirection while key comparison (often strings, seldom anything without an indirection) usually needs an indirection. Hash codes are very cheap to compare.

These indirections have always been costly on any machine with virtual memory. TLB misses aren't free. I'd have put any estimate on the tradeoff being the other way around to more than 25 years.

Re: Why Hashbrown Does a Double Lookup

#42

Post by steveklabnik »

wahern wrote: post #40
Sharlin wrote: post #37

Earlier quoted context omitted.

But surely Rust hashtables just store the objects in the table itself? Rust has value semantics, after all. No indirections unless you opt in and `Box` your objects.

AFAIU it depends on the object and its traits. I'm curious how Rust's hash tables are used in practice , i.e. whether the common use case is copying vs taking ownership of the object itself. Though either way what really matters is whether indirection is required to verify the key (e.g. String). In C I prefer red-black trees over hash tables because memory management is easier, you get smooth performance characterist…

Ownership is the usual, at least in the ones I’ve seen. Otherwise you have to start reasoning about lifetimes and that’s trickier.

Re: Why Hashbrown Does a Double Lookup

#43

Post by temac »

simcop2387 wrote: post #33
hyperman1 wrote: post #31

Earlier quoted context omitted.

x86 seems reasonable to me: Fast array bounds checking is, handling the lower bound by unsigned integer math : cmp index,bound ja crash_handler Overflow handling is mostly jo crash_handler That's 1 or 2 instructions and the jump has perfect prediction. I'd assume the cost is negligible compared with jump mispredicts and cache misses. I read somewhere the main problem is LLVM not being quite capable of optimizing thes…

I seem to recall, that at least jo has terrible pipelining implications because of the dependency on the flag register that way, no idea about the bounds check (might be a better way)

I don't see why JO would be any different from other Jcc, especially since JL is SF ≠ OF. Maybe you were thinking of the problem with INC/DEC and CF, but even then that's a problem of INC/DEC, not of Jcc.

Re: Why Hashbrown Does a Double Lookup

#44

Post by rurban »

barrkel wrote: post #39
0815test wrote: post #22

Earlier quoted context omitted.

I'm not sure that backshifting is as easy as "moving all items in the chain forward by one slot". Consider the hashtable [A, B1, B2, _, _], where one element is subsequently added after B2, giving [A, B1, B2, X, _]. Now when we remove B1 and shift B2 forward one slot ([A, B2, _, X, _]), we have to shift X forward if it hashes to the second or the third slot in the table, but not the fourth. So there might be multiple…

Yup, the chains can be interleaved. Often it's best to save the hash of each key as well as the key itself. Comparing the full hash (rather than the modulus of the hash) will eliminate many keys faster than doing a full key comparison, and having the full hash available means recreation on expansion is cheap, as all the keys don't need rehashing. The full hashes can then be used to distinguish between different chain…

Certainly not with open addressing as it will destroy all the cache-line advantages. with seperate chaining it's very common, esp. for resizing.

Re: Why Hashbrown Does a Double Lookup

#45

Post by aswanson »

devit wrote: post #24
aswanson wrote: post #6

I wonder if there is any research into hardware architectures optimized for Rust.

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.

Could the concept of "ownership" be optimized for somehow in hardware?

Re: Why Hashbrown Does a Double Lookup

#46

Post by mjevans »

blattimwind wrote: post #16
mehrdadn wrote: post #13

Earlier quoted context omitted.

How does open addressing handle deletions? I never figured this out. Update: So I just read the article (I didn't have the chance earlier) and I see it explains tombstones, which seem like a pretty clever solution I wasn't thinking about. What I had been confused about, though was the other more-obvious attempt at a solution, which is backshifting. I think I had gotten stuck is what you do with the spot that opens up…

The easiest one is tombstones (i.e. "this item is deleted") to keep the chain alive, or backshifting (i.e. moving all items in the chain forward one slot).

For back-shifting, I'd prefer to actually seek for the tail item in the list (just before you prove the key doesn't exist) and move that BACK to the evicted slot, rather than update all of the keys.

However the tombstone idea fits better with minimizing mutations and improving the potential for concurrency if the design only cares that inserts/deletes are atomic (not that they're propagated in parallel instantly).

For the 'move back' idea to be that safe I'd still want to use a tombstone value, but it would need to also include a pointer to the moved location. The list of tombstones would need to be submitted (as in, message queue) to a kind of garbage collection thread that sat on the messages for a pre-determined validity time and then did a scrub of the key/value to make sure the compaction still made sense. A shorter interval might also allow for that deferred compaction to be replaced by a new entry instead.

I don't like any of that as a generic solution though, as the trade-offs with each bit of extra effort and code complexity seem likely to be premature optimization and sources of potential bugs when not considered in a specific problem domain.

Re: Why Hashbrown Does a Double Lookup

#47

Post by hinkley »

gopher_protocol wrote: post #8
shittyadmin wrote: post #4

So - what's the motivation to use "open addressing" vs chaining, which I thought was the more common approach to solving this. I assume there must be a substantial performance gain for this to be used as it seems significantly more complicated, any information on how much better it is?

Open addressing has better cache performance, and for most workloads is much faster than chaining implementations. Hashbrown's implementation is based on Google's SwissTable, and they explained the reasoning behind their choices in this CppCon talk: https://www.youtube.com/watch?v=ncHmEUmJZf4

Cliff Click (of JVM fame) did a presentation once on an open addressing hash table implementation that he believed was lock free (it used CAS and possibly some memory barriers). I wouldn't want to argue with Cliff Click on concurrency but everybody makes mistakes. I haven't checked back if anyone found any bugs yet.

I'm also curious if or how that implementation would translate to other languages. What he did might not be declarable in the Rust ownership model.

Re: Why Hashbrown Does a Double Lookup

#48

Post by cbhl »

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

Re: Why Hashbrown Does a Double Lookup

#49

Post by posnet »

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

https://blog.acolyer.org/2016/11/03/algorithmic-improvements...

https://github.com/efficient/libcuckoo

Re: Why Hashbrown Does a Double Lookup

#50

Post by half-kh-hacker »

aswanson wrote: post #45
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.

Could the concept of "ownership" be optimized for somehow in hardware?

I'm not a Rust expert, but I think ownership and borrowing go away after compile-time.
Post reply on HN