91–100 of 116 posts
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.
Rust's implicit overflow checks are only in debug mode I think. Overflow is defined to wrap in release mode.
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…
Isn’t that a general problem [1] that is addressed with randomization of the input data before hashing?
[1] https://www.purehacking.com/blog/josh-zlatin/introduction-to...
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.
All 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…
Earlier quoted context omitted.
Mutating the table on lookup seems pretty gross, though.
I would argue that "the table" is not mutated, only the internal state of its implementation. Every time you access any information, a cache at some layer below you is updated. Is that also gross?
As soon as your reads can modify the internal state of the data structure, it might modify the state in a way which trips up another read; so you can no longer have many threads reading the data structure at once.
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.
> fast integer overflow checks Rust's implicit overflow checks are only in debug mode I think. Overflow is defined to wrap in release mode.
Earlier quoted context omitted.
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 al…
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 speculative execution and it happens on every single mathematical operation in your regime. And you pay that continually for an operation that happens "very rarely" as you point out.
Overflow/underflow probably isn't so bad, but array bounds checks are very bad. You have at least one bound that is variable and so causes an extra "Compare to X" where X is a non-zero constant and so needs to be loaded. So your tight loops all look like "increment I; compare I to 0; compare I to X; do real work" That's two extra instructions that the speculative execution system has to keep track of every loop and it eats a lot of the speculative execution resources very quickly.
An in-order chip like the 21164 doesn't execute the loops any faster, but it doesn't have to pay hardware chip area because of speculative execution. Given that everything is moving to high multi-core, it would be better to let a stuck core give way to another quickly than to try speculate deeper--especially as SSDs continue to increase in speed--and especially because, quite often in a battery operated world, your would rather shut down while waiting.
In addition, if you trap on these, it will break an enormous amount of software in existence. Look at how many people went absolutely ape over gcc suddenly doing aggressive optimizations on undefined behavior.
(And, by the way, every microprocessor used to compute underflow on arithmetic instructions (8080, Z80, 6800, etc.), so you need to ask why that went away.)
Earlier quoted context omitted.
I would argue that "the table" is not mutated, only the internal state of its implementation. Every time you access any information, a cache at some layer below you is updated. Is that also gross?
Yes. Normally you can have one thread writing to a data structure OR many threads reading the data structure at any given time and not need to worry about them causing problems. (This situation is common enough that we have things called "reader-writer mutexes" or "shared-exclusive" mutexes.) As soon as your reads can modify the internal state of the data structure, it might modify the state in a way which trips up a…
Earlier quoted context omitted.
I would argue that "the table" is not mutated, only the internal state of its implementation. Every time you access any information, a cache at some layer below you is updated. Is that also gross?
Yes. Normally you can have one thread writing to a data structure OR many threads reading the data structure at any given time and not need to worry about them causing problems. (This situation is common enough that we have things called "reader-writer mutexes" or "shared-exclusive" mutexes.) As soon as your reads can modify the internal state of the data structure, it might modify the state in a way which trips up a…
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
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 in the past (linear probing, triangular probing etc.) and I much prefer Cuckoo hashing now.
When Cuckoo hashing is combined with a bloom filter in the first position to reduce cache misses to the second position, it's almost perfect in every way: fast (drastically reduced cache misses), constant lookup time in the worst case (not so for linear probing), higher load factors (80% or more for Cuckoo hashing vs at most 50% for linear probing - this also affects amortized resize latency), not to mention elegant simplicity.
In case anyone is interested, here are some design details and decisions for an optimized bucketized Cuckoo hash table with bloom filters implemented for Node.js: