81–90 of 116 posts
The author is also in the thread on /r/rust if you have any questions for them: https://www.reddit.com/r/rust/comments/b38cwz/why_hashbrown_...
I went to university with him. Really nice guy. Every time we talk, I say something like "any day now dude, I'm going to really get into Rust" and then I never do because I'm awful.
Earlier quoted context omitted.
You can eliminate tombstones over time by: # any time a tombstone immediately preceeds a empty, it can be marked empty [ $ _ ] -> [ _ _ ] # any time you lookup a key, it can be swapped with a tombstone immediately preceeding it [ $ A ] -> [ A $ ] # (moving the tombstone closer to a empty that will destroy it) # if you don't have iterators, you can also jump over other keys [ $ B A ] -> [ A B $ ] [ $ B C A ] -> [ A B…
Mutating the table on lookup seems pretty gross, though.
TBH, the right answer is always due to the users use case (Amortization and housekeeping really help with purely functional data structures), and benchmark data.
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.
Earlier quoted context omitted.
I went to university with him. Really nice guy. Every time we talk, I say something like "any day now dude, I'm going to really get into Rust" and then I never do because I'm awful.
I've been saying the same since last year. I'm finally picking it up just trying to use it for regular everyday scripting work. It's been slow but atleast I'm starting now.
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?
Earlier quoted context omitted.
You can eliminate tombstones over time by: # any time a tombstone immediately preceeds a empty, it can be marked empty [ $ _ ] -> [ _ _ ] # any time you lookup a key, it can be swapped with a tombstone immediately preceeding it [ $ A ] -> [ A $ ] # (moving the tombstone closer to a empty that will destroy it) # if you don't have iterators, you can also jump over other keys [ $ B A ] -> [ A B $ ] [ $ B C A ] -> [ A B…
Mutating the table on lookup seems pretty gross, though.
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.
Where does it say that this is the fastest hash table implementation?
Earlier quoted context omitted.
You can eliminate tombstones over time by: # any time a tombstone immediately preceeds a empty, it can be marked empty [ $ _ ] -> [ _ _ ] # any time you lookup a key, it can be swapped with a tombstone immediately preceeding it [ $ A ] -> [ A $ ] # (moving the tombstone closer to a empty that will destroy it) # if you don't have iterators, you can also jump over other keys [ $ B A ] -> [ A B $ ] [ $ B C A ] -> [ A B…
Mutating the table on lookup seems pretty gross, though.
No, it's not quite so offensive, but this doesn't explain why it's the best option. Is there no equally-fast way to write the first-tombstone implementation with SIMD instructions? The answer seems to be in the sketch of the implementation, which I'm having trouble understanding.
EDIT: I'm watching the original SwissTable talk now... would it really have been worse to use 2 bits for empty/tombstone/full/sentinel, and 6 bits for hash prefix?
EDIT 2: More implementation info. Tombstones are actually rare, because if any element in your 16-wide chunk is empty, you don't have to create a tombstone. In the very best case (a perfectly distributed hash function), your hashmap has to be ~94% full before it's even possible to fail this. Because tombstones are so rare, it's better to save the single bit for extra confidence in the hash prefix.
So, here is my understanding of the implementation and its rationale:
* Every bucket in the backing array has a corresponding byte in a metadata array
* 1 bit of this byte stores whether the bucket is empty, the other 7 bits are for a hash prefix
* SIMD instructions search 16 bytes at a time, checking: this bucket is not empty, this bucket's key matches the first 7 bits of my key
* Since 16 buckets are checked for emptiness at the same time, you can avoid creating a tombstone for a bucket if any of the other 15 buckets are empty (just set it to empty, i.e. set the first bit to 0)
* This means that tombstones are very unlikely- you'll probably rehash before you get to the load factor where you start seeing tombstones
* Since tombstones are so unlikely, it's more valuable to add an extra bit to the hash prefix than it is to quickly find tombstones
My question remains: why can't the first search return the offset of the first empty bucket? In this loop, why is there not an else that saves the offset?: https://github.com/abseil/abseil-cpp/blob/256be563447a315f2a...
Earlier quoted context omitted.
You can eliminate tombstones over time by: # any time a tombstone immediately preceeds a empty, it can be marked empty [ $ _ ] -> [ _ _ ] # any time you lookup a key, it can be swapped with a tombstone immediately preceeding it [ $ A ] -> [ A $ ] # (moving the tombstone closer to a empty that will destroy it) # if you don't have iterators, you can also jump over other keys [ $ B A ] -> [ A B $ ] [ $ B C A ] -> [ A B…
Mutating the table on lookup seems pretty gross, though.