Why Hashbrown Does a Double Lookup • Hacker News Board

Re: Why Hashbrown Does a Double Lookup

#31

Post by hyperman1 » Wed, Mar 20, 2019, 7:19 PM UTC

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.

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 these decently: It has to handle all these extra jumps which causes lots of extra basic blocks.

Re: Why Hashbrown Does a Double Lookup

#32

Post by simcop2387 » Wed, Mar 20, 2019, 7:28 PM UTC

jeanmichelx wrote: post #12

So how does this degrade for bigger hash tables? Surely the two loops implementation is less efficient since your cache is trashed by the time you do the second look up

Not necessarily, as the sibling mentioned load of the table matters, but also the fact that the single loop has to do other housekeeping may also mean that it could ruin any cache prefetching that could be happening because of the less predicable pattern. Ideally the housekeeping variables are going to be in registers but that's not always going to be possible. In this case, two loops that look at the data sequentially are going to predict very very nicely and probably load more of the cache as it's searching than anything that could be random.

Re: Why Hashbrown Does a Double Lookup

#33

Post by simcop2387 » Wed, Mar 20, 2019, 7:30 PM UTC

hyperman1 wrote: post #31

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.

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)

Re: Why Hashbrown Does a Double Lookup

#34

Post by digikata » Wed, Mar 20, 2019, 7:38 PM UTC

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.

I suspect ADA would like those too, if available.

Re: Why Hashbrown Does a Double Lookup

#35

Post by wahern » Wed, Mar 20, 2019, 7:40 PM UTC

blattimwind wrote: post #10

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?

All* high performance hashtables use open addressing, because chaining tends to mean (multiple) indirection to addresses outside the table. * not sure if that's literally true, but I've never seen anyone do chaining in performance-sensitive applications, and all the papers on fast hash tables use some way of open addressing.

I think it largely depends on whether you're using intrusive data structures or not. Even in open addressing you still must always load the object to verify the correct key, so collisions still result in [wasted] random memory access. If the hash table uses dedicated nodes then you have to indirect twice just to verify the key. But in all the hash tables I've written the hash node is already a part of the object, so there's no additional indirection.

However, Rust is allergic to intrusive data structures. Which is a little ironic as single ownership ostensibly would otherwise make intrusive data structures more practical as you're already effectively precluded from inserting an object into multiple hash tables and so there's no potential for contention over the object's internal node fields.

I suppose linear probing also permits prefetching of successive buckets, though ideally collisions should be the exception so such prefetching might just waste bandwidth.

Re: Why Hashbrown Does a Double Lookup

#36

Post by [deleted] » Wed, Mar 20, 2019, 7:42 PM UTC

usefulcat wrote: post #27

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 article mentions a couple of options, one of which is tombstones. In a chaining implementation, the load factor is straightforward: num_items / table_size. Adding items increases the load factor and deleting items reduces it. With open addressing, deletions do not decrease the load factor (at least not immediately, in general), because a deleted item becomes a tombstone. So for open addressing, load factor is (nu…

[deleted]

Re: Why Hashbrown Does a Double Lookup

#37

Post by Sharlin » Wed, Mar 20, 2019, 7:53 PM UTC

wahern wrote: post #35

blattimwind wrote: post #10

Earlier quoted context omitted.

All* high performance hashtables use open addressing, because chaining tends to mean (multiple) indirection to addresses outside the table. * not sure if that's literally true, but I've never seen anyone do chaining in performance-sensitive applications, and all the papers on fast hash tables use some way of open addressing.

I think it largely depends on whether you're using intrusive data structures or not. Even in open addressing you still must always load the object to verify the correct key, so collisions still result in [wasted] random memory access. If the hash table uses dedicated nodes then you have to indirect twice just to verify the key. But in all the hash tables I've written the hash node is already a part of the object, so…

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.

Re: Why Hashbrown Does a Double Lookup

#38

Post by jeanmichelx » Wed, Mar 20, 2019, 7:54 PM UTC

mbrubeck wrote: post #19

jeanmichelx wrote: post #12

So how does this degrade for bigger hash tables? Surely the two loops implementation is less efficient since your cache is trashed by the time you do the second look up

This varies not with the size of the whole hash table, but with the distance from any given index to the first empty bucket. By keeping the load factor constant, you can grow the hash table as much as you want without degrading the expected performance.

Good point, thanks!

Re: Why Hashbrown Does a Double Lookup

#39

Post by barrkel » Wed, Mar 20, 2019, 7:55 PM UTC

0815test wrote: post #22

blattimwind wrote: post #16

Earlier quoted context omitted.

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

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 chains if you decide to do backfilling, again cheaper than recalculating key hashes.

Of course, having the hashes available also speeds up recreation, should the tombstone approach be used.

Basically, keep the full hashes around :)

Re: Why Hashbrown Does a Double Lookup

#40

Post by wahern » Wed, Mar 20, 2019, 7:58 PM UTC

Sharlin wrote: post #37

wahern wrote: post #35

Earlier quoted context omitted.

I think it largely depends on whether you're using intrusive data structures or not. Even in open addressing you still must always load the object to verify the correct key, so collisions still result in [wasted] random memory access. If the hash table uses dedicated nodes then you have to indirect twice just to verify the key. But in all the hash tables I've written the hash node is already a part of the object, so…

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 characteristics (no resize hiccups), and you're immune from computational complexity attacks without sweating over hashing algorithms. But I use intrusive node fields for my trees, and also tend to keep keys (even string keys) internal to the object as well, which substantially closes the cache performance gap.