51–60 of 116 posts
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
There's the related cuckoo filter as well: https://github.com/efficient/cuckoofilter
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…
Earlier quoted context omitted.
I seem to recall, that at least jo has terrible pipelining implications because of the dependency on the flag register that way, no idea about the bounds check (might be a better way)
I don't see why JO would be any different from other Jcc, especially since JL is SF ≠ OF. Maybe you were thinking of the problem with INC/DEC and CF, but even then that's a problem of INC/DEC, not of Jcc.
Earlier quoted context omitted.
How does open addressing handle deletions? I never figured this out. Update: So I just read the article (I didn't have the chance earlier) and I see it explains tombstones, which seem like a pretty clever solution I wasn't thinking about. What I had been confused about, though was the other more-obvious attempt at a solution, which is backshifting. I think I had gotten stuck is what you do with the spot that opens up…
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…
# 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 C $ ] # etc
# (this will cause a iterator at A to yield B again, or at B to skip A)
Earlier quoted context omitted.
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
How does open addressing handle deletions? I never figured this out. Update: So I just read the article (I didn't have the chance earlier) and I see it explains tombstones, which seem like a pretty clever solution I wasn't thinking about. What I had been confused about, though was the other more-obvious attempt at a solution, which is backshifting. I think I had gotten stuck is what you do with the spot that opens up…
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
Earlier quoted context omitted.
I don't see why JO would be any different from other Jcc, especially since JL is SF ≠ OF. Maybe you were thinking of the problem with INC/DEC and CF, but even then that's a problem of INC/DEC, not of Jcc.
It's not usually a big difference, but on modern Intel there is a some difference in performance between the different CMP/JCC options. The more common ones will "fuse" with the CMP and be executed as a single µop, but the rarer ones (like JO and JS) do not fuse with CMP, and thus can add a cycle of delay (and have the overhead associated with executing another µop). The optimization is called "macro op fusion". Deta…
I wonder if there is any research into hardware architectures optimized for Rust.
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.
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.
Earlier quoted context omitted.
Yup, the chains can be interleaved. Often it's best to save the hash of each key as well as the key itself. Comparing the full hash (rather than the modulus of the hash) will eliminate many keys faster than doing a full key comparison, and having the full hash available means recreation on expansion is cheap, as all the keys don't need rehashing. The full hashes can then be used to distinguish between different chain…
Certainly not with open addressing as it will destroy all the cache-line advantages. with seperate chaining it's very common, esp. for resizing.
(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.)