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

61–70 of 116 posts

Re: Why Hashbrown Does a Double Lookup

#61

Post by senderista »

barrkel wrote: post #60
rurban wrote: post #44

Earlier quoted context omitted.

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

The key is usually indirected, which means a pointer, which is usually bigger than the hash code. (And of course you could use parallel arrays if you're super concerned about cache lines, though the tradeoffs would very much depend on whether hash misses or hits are the expected mode.)

And if it’s not a pointer but a word-size integer, just use an invertible hash function (aka permutation aka block cipher) so you can store the hash code in place of the key :)

Re: Why Hashbrown Does a Double Lookup

#64

Post by 19870213 »

mikeash wrote: post #56
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

I assume that’s constant lookup time assuming well distributed hash values? The absolute worst case for a hash table is when every key has the same hash, and then you must fall back to something that’s at best log-n time.

The standard Java java.util.HashMap currently falls back to a Tree(Map) if a bucket gets too full (more than 5? Not sure, a LinkedList if not too full). But I wonder, couldn't you not use a different hash and have use a HashMap as a bucket?

Re: Why Hashbrown Does a Double Lookup

#65

Post by cbhl »

mikeash wrote: post #56
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

I assume that’s constant lookup time assuming well distributed hash values? The absolute worst case for a hash table is when every key has the same hash, and then you must fall back to something that’s at best log-n time.

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

Re: Why Hashbrown Does a Double Lookup

#66

Post by mikeash »

19870213 wrote: post #64
mikeash wrote: post #56

Earlier quoted context omitted.

I assume that’s constant lookup time assuming well distributed hash values? The absolute worst case for a hash table is when every key has the same hash, and then you must fall back to something that’s at best log-n time.

The standard Java java.util.HashMap currently falls back to a Tree(Map) if a bucket gets too full (more than 5? Not sure, a LinkedList if not too full). But I wonder, couldn't you not use a different hash and have use a HashMap as a bucket?

You could, but it’s theoretically possible to have keys whose hashes always collide, even with different hash functions.

This is not a purely theoretical concern, I should note. There are practical DoS attacks that can be carried out by deliberately crafting colliding keys. The current state of the art seems to be to make it impractical for attackers to accomplish this by incorporating secret data into the hash function, rather than by ensuring the theoretical worst case is acceptable. Which is probably the right approach.

Re: Why Hashbrown Does a Double Lookup

#67

Post by mikeash »

cbhl wrote: post #65
mikeash wrote: post #56

Earlier quoted context omitted.

I assume that’s constant lookup time assuming well distributed hash values? The absolute worst case for a hash table is when every key has the same hash, and then you must fall back to something that’s at best log-n time.

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.

Re: Why Hashbrown Does a Double Lookup

#68

Post by est31 »

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…

Yeah, part of the unexplored optimization potential that Rust has is that LLVM was originally written with C in mind, and Rust achieves great results with it, but sometimes it can't use the additional info that the better typesystem provides because nobody wrote the code in LLVM, or because LLVM has bugs so the Rust devs have to turn off that additional info.

Re: Why Hashbrown Does a Double Lookup

#69

Post by jolux »

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.

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.

Re: Why Hashbrown Does a Double Lookup

#70

Post by jacobolus »

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

Here’s a practical implementation in Twitter’s cache backend, https://github.com/twitter/pelikan/tree/master/src/storage/c...
Post reply on HN