Why Hashbrown Does a Double Lookup

#1

Post by mbrubeck » Wed, Mar 20, 2019, 5:17 PM UTC

Why Hashbrown Does a Double Lookup
gankro.github.io

Re: Why Hashbrown Does a Double Lookup

#2

Post by prudhvis » Wed, Mar 20, 2019, 5:43 PM UTC

This is pretty amazing, i really like the fact that a fastest hash table implementation is going to be part of the Rust's stdlib.

Re: Why Hashbrown Does a Double Lookup

#3

Post by ChrisSD » Wed, Mar 20, 2019, 5:49 PM UTC

Answer: SIMD.

What looks like "two loops" is really "do two simple SIMD operations".

Re: Why Hashbrown Does a Double Lookup

#4

Post by shittyadmin » Wed, Mar 20, 2019, 5:51 PM UTC

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?

Re: Why Hashbrown Does a Double Lookup

#5

Post by [deleted] » Wed, Mar 20, 2019, 5:52 PM UTC

[deleted]

Re: Why Hashbrown Does a Double Lookup

#6

Post by aswanson » Wed, Mar 20, 2019, 5:56 PM UTC

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

Re: Why Hashbrown Does a Double Lookup

#7

Post by ars » Wed, Mar 20, 2019, 5:58 PM UTC

aswanson wrote: post #6

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

There is nothing rust specific about this algorithmic.

Re: Why Hashbrown Does a Double Lookup

#8

Post by gopher_protocol » Wed, Mar 20, 2019, 5:59 PM UTC

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

Re: Why Hashbrown Does a Double Lookup

#9

Post by jeanmichelx » Wed, Mar 20, 2019, 5:59 PM UTC

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?

Pointer chasing is very expensive if your chains end up in different cache lines. The bottleneck on a lot of application isn't how fast your instructions run, but how fast you can get data to them.

Re: Why Hashbrown Does a Double Lookup

#10

Post by blattimwind » Wed, Mar 20, 2019, 6:00 PM UTC

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.