Why Hashbrown Does a Double Lookup • Hacker News Board

Re: Why Hashbrown Does a Double Lookup

#111

Post by laughinghan » Thu, Mar 21, 2019, 6:13 PM UTC

throwaway808080 wrote: post #104

_urga wrote: post #100

Earlier quoted context omitted.

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

Did you read the link?

> Each bucket contains up to 8 elements to support a hash table load factor of 80% or higher, unlike linear or chained hash tables which support a load factor (elements / capacity) of at most 50% and which waste the other 50% of memory.

Re: Why Hashbrown Does a Double Lookup

#112

Post by laughinghan » Thu, Mar 21, 2019, 6:47 PM UTC

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…

What are you talking about?

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

Why would you think there are any fixed numbers? The OP is about a stdlib hash table (for Rust). Comparable hash table implementations all resize the table when necessary to decrease the load factor. Performance with respect to load factor still matters, of course, less resizing is better, but there are no fixed numbers of anything.

> It completely undermines the "worst-case constant lookup", because there is no upper bound on the number of times you might have to change the hash function and rebuild the table before you find one with sufficiently few collisions.

Why would you need to change the hash function or rebuild anything during lookup? It's lookup. Nobody is changing anything.

> It is a much stronger requirement on the keys than other hash tables have.

What hash table doesn't require keys to be hashable?

Re: Why Hashbrown Does a Double Lookup

#113

Post by laughinghan » Thu, Mar 21, 2019, 6:51 PM UTC

rurban wrote: post #87

haggy wrote: post #83

Earlier quoted context omitted.

Where does it say that this is the fastest hash table implementation?

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.

Is there anywhere we can read more about who says Google Swisstable is the fastest and why?

Re: Why Hashbrown Does a Double Lookup

#114

Post by incog-neato » Thu, Mar 21, 2019, 10:45 PM UTC

aswanson wrote: post #77

half-kh-hacker wrote: post #50

Earlier quoted context omitted.

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

Of course, but what pre-compile architectural decisions could be made to accommodate such a higher level construct?

The point of the borrow checker is that it's run at compile time rather than runtime. Putting something similar into the architecture necessarily implies a runtime check, which is similar to the idea of a smart pointer, which exists in Rust as well as other languages.

Re: Why Hashbrown Does a Double Lookup

#115

Post by BeeOnRope » Mon, Mar 25, 2019, 1:07 AM UTC

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…

I had a bit of a hard time following your argument, but nkurz is right here in the sense that things like overflow and bounds checks are practically the poster child for things that perform well on wide OoO processors. They are leaves in dependency graph and hence don't add to dependency chains, and on wide designs the ALU op(s) will often execute almost for free.

It is in-order designs that take a slightly larger relative penalty since in some sense "all instructions matter" there so bounds checks cost similar to surrounding operations that do real work.

You make a lot of valid observation about the cost of actually implementing a modern, deep and wide out of order architecture: it is much harder and uses more silicon that some in-order designs, but once you have it (and largely that's what we have today as general purpose CPUs), the type of branches that are involved in overflow and bounds checks are not costly.

Re: Why Hashbrown Does a Double Lookup

#116

Post by cbhl » Tue, Mar 26, 2019, 4:14 PM UTC

mikeash wrote: post #67

cbhl wrote: post #65

Earlier quoted context omitted.

It's constant-time lookup (only two possible places to check). But if you give it the "return 4" hash function, it will fail to insert after the second or third entry. The result is the same, you have to fall back to something (changing the hash function; making the table larger; open addressing with chaining; etc.)

That’s boring. Any algorithm can be constant time if you’re allowed to fail after a constant amount of work.

If you phrase the problem as "design a better hash table, given the hash function h(x) = 4", then the obvious first thing to do is discard the provided hash function, and use any reasonable hash table implementation with a new hash function, say h'(x) = x. (If x "is an object" instead of a primitive type; then some underlying representation of x in a register is a pointer; that memory address can typically be converted to an integer that can be the hash value.)

Thus, I would argue that the problem reduces to the case where you have a reasonable hash function.