Earlier quoted context omitted.
Could the concept of "ownership" be optimized for somehow in hardware?
I'm not a Rust expert, but I think ownership and borrowing go away after compile-time.
That’s correct.
Why Hashbrown Does a Double Lookup
71–80 of 116 posts
Re: Why Hashbrown Does a Double Lookup
#72Earlier quoted context omitted.
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.
How is that possible? I insert three pathological keys. The third one collides with both, so it rebuilds the table. The third one still collides with both, so it rebuilds the table again. Repeat. Eventually either we fail or we end up in something that’s worse than constant time.
Re: Why Hashbrown Does a Double Lookup
#73The 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.
Re: Why Hashbrown Does a Double Lookup
#74Earlier 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.
Unfortunately, fast array bounds checks and fast integer overflow checks are anathema to speculative execution so aren't happening any time soon. I'm becoming convinced that we really need to just go back to the Alpha 21164 architecture and stamp out multiple copies with really fast interconnect.
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 already there and almost perfect; it's the languages and compilers that are lagging. But maybe I'm missing something obvious. Where do you think the issue is?
Re: Why Hashbrown Does a Double Lookup
#75All good points in the article.
> it was doing something that was so offensive to people who care about collection performance
Hmm. It also helps here to go back to academia. Big O notation doesn't usually express coefficients/constants, it usually only deals with exponents.[1] The Wikipedia page has a good explanation as to why.
Opinion: coefficients/constants are, however, useful if you're running over a network or some other latency-bound operation.
[1]: https://en.wikipedia.org/wiki/Big_O_notation#Properties
Re: Why Hashbrown Does a Double Lookup
#76Earlier quoted context omitted.
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…
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.
Re: Why Hashbrown Does a Double Lookup
#77Earlier quoted context omitted.
Could the concept of "ownership" be optimized for somehow in hardware?
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?
Re: Why Hashbrown Does a Double Lookup
#78Earlier 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.
The main case that I know of where you really don't want to use open addressing (using tombstones) is when you have both of the following requirements: a) need to repeatedly insert and delete items, and b) can't tolerate (relatively) really bad worst case insertion performance. I can't speak directly to the performance of non-tombstone based open addressing implementations, but it definitely seems like the need to mo…
If there is metadata available at every slot then you can track overflows rather than tombstones. These let you terminate the search earlier (you don't need to find an empty) and can be cleaned up on erase, because they are a property of the keys in the map rather than the keys that are no longer in the map.
folly's F14 maps use this strategy, and handle erase + insert workloads fine with no rehashing needed. https://github.com/facebook/folly/blob/master/folly/containe...
Re: Why Hashbrown Does a Double Lookup
#79> . For instance, when compiled with sse2 support it can search 16 buckets at once.
Does Neon get similar order of magnitude benefit?
Re: Why Hashbrown Does a Double Lookup
#80If 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 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.
2) It is a much stronger requirement on the keys than other hash tables have. With other hash tables I can simply omit "difficult to hash" data from my hash function, on the basis that enough other data is hashed to avoid a significant performance penalty. With this implementation, the entire hash table will simply fail.
This additional failure mode is also a security concern - if an untrusted user can affect what data is added to the table, it could cause a severe DoS where the table will either enter an infinite loop trying to find a non-conflicting hash function, or have an unexpected failure mode (most people don't expect their hash tables to randomly fail). Even if it is somehow designed such that a hash function can always be found, the attacker could spend time up-front finding values that take a long time for that hash function to be reached, causing numerous re-hashes of the table.