That's a fallback implementation for platforms without SIMD. The real code is lower down.
sparsehash is still more memory efficient, but it is quite slow in comparison. Also, in practice it doesn't reach the ultra-low space overheads claimed by the documentation. It allocates memory blocks of many different…
I haven't seen those discussions, but is it possible that they were trying to rehash the results of Object.hashCode rather than pass all of the bytes of the original value through a new hash algorithm? If you haven't…
F14 supports stateful hashers, so in situations that need to be resilient to hash poisoning we can use a hasher designed for that purpose.
It would be nice to have a deeper understanding of how/why this works, but in practice it seems fine. Under a continuous insert and erase workload the number of chunks with an overflow fluctuates a bit but stays low…
https://github.com/rust-lang/hashbrown is a port of Google's SwissTable algorithm (abseil flat_hash_map). It also uses SIMD filtering and has the potential to be quite good.
You're right, it's been available for a while now. This is the first time we've made an announcement about it.
Non-SIMD algorithms work better in some cases, for example if you look up the same key over and over (so the control flow is predictable) or when all of the data is in the L1. The SIMD approach tends to be more robust…
I'm one of the authors. Seeing the Google presentation at CPPCon convinced us that the potential wins were worth the effort to productionize, but the similarity in the designs is a case of convergent evolution. Since…
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…
Sharding your product so that no cross-shard links are possible is robust and scalable, but it requires you to understand your final product very well at design time. If you start down that path and then bolt on some…
So to get back to Spanner's availability (if you need it), you need the Calvin sequencer Paxos groups to span data centers. Since you're not exploiting the commutativity structure of transactions you need either a…
I mistyped, I meant to say that a stalled sequencer stalls all schedulers. It's true that Corfu has impressive per-sequencer throughput (by moving most of the work onto other nodes), but you have to move to multiple…
The all-to-all dependency step between Calvin's sequencer layer and scheduler layer seems like it will be a problem as things scale, because it means that a single stalled sequencer [edit, orig: scheduler] blocks all…
Thank you for publishing the code for your paper. It's an excellent contribution by itself, and should help people understand and evaluate the ideas. Are you going to publish the TLA+ specification as well?
One option for compatibility on non-futex platforms is to write your own futex emulation using striped std::mutex or pthread_mutex_t. The emulated futex API still has the same slow-path-only goodness as a real futex,…
Metastability comes in when you think about the problem that originally triggered congestion. A normal network overload caused by a bulk transfer, for example, can be fixed by canceling the transfer. Once you add the…
When the pool was originally coded, MySQL had one thread per open connection. That made the auto-sizing MRU pool a pretty big win, because it kept the connection counts as low as possible while using the warmest…
One of the reasons this took a long time to figure out is that it was a failure amplifier, so there was always a more typical network problem preceding it. Network failures in a data center cause lots of changes to the…
I coded the fix. We considered some options that had a bias away from the slow links, but we thought it was safer to avoid bias completely. It was fine in my tests, but I couldn't prove that biasing toward the faster…
That's a fallback implementation for platforms without SIMD. The real code is lower down.
sparsehash is still more memory efficient, but it is quite slow in comparison. Also, in practice it doesn't reach the ultra-low space overheads claimed by the documentation. It allocates memory blocks of many different…
I haven't seen those discussions, but is it possible that they were trying to rehash the results of Object.hashCode rather than pass all of the bytes of the original value through a new hash algorithm? If you haven't…
F14 supports stateful hashers, so in situations that need to be resilient to hash poisoning we can use a hasher designed for that purpose.
It would be nice to have a deeper understanding of how/why this works, but in practice it seems fine. Under a continuous insert and erase workload the number of chunks with an overflow fluctuates a bit but stays low…
https://github.com/rust-lang/hashbrown is a port of Google's SwissTable algorithm (abseil flat_hash_map). It also uses SIMD filtering and has the potential to be quite good.
You're right, it's been available for a while now. This is the first time we've made an announcement about it.
Non-SIMD algorithms work better in some cases, for example if you look up the same key over and over (so the control flow is predictable) or when all of the data is in the L1. The SIMD approach tends to be more robust…
I'm one of the authors. Seeing the Google presentation at CPPCon convinced us that the potential wins were worth the effort to productionize, but the similarity in the designs is a case of convergent evolution. Since…
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…
Sharding your product so that no cross-shard links are possible is robust and scalable, but it requires you to understand your final product very well at design time. If you start down that path and then bolt on some…
So to get back to Spanner's availability (if you need it), you need the Calvin sequencer Paxos groups to span data centers. Since you're not exploiting the commutativity structure of transactions you need either a…
I mistyped, I meant to say that a stalled sequencer stalls all schedulers. It's true that Corfu has impressive per-sequencer throughput (by moving most of the work onto other nodes), but you have to move to multiple…
The all-to-all dependency step between Calvin's sequencer layer and scheduler layer seems like it will be a problem as things scale, because it means that a single stalled sequencer [edit, orig: scheduler] blocks all…
Thank you for publishing the code for your paper. It's an excellent contribution by itself, and should help people understand and evaluate the ideas. Are you going to publish the TLA+ specification as well?
One option for compatibility on non-futex platforms is to write your own futex emulation using striped std::mutex or pthread_mutex_t. The emulated futex API still has the same slow-path-only goodness as a real futex,…
Metastability comes in when you think about the problem that originally triggered congestion. A normal network overload caused by a bulk transfer, for example, can be fixed by canceling the transfer. Once you add the…
When the pool was originally coded, MySQL had one thread per open connection. That made the auto-sizing MRU pool a pretty big win, because it kept the connection counts as low as possible while using the warmest…
One of the reasons this took a long time to figure out is that it was a failure amplifier, so there was always a more typical network problem preceding it. Network failures in a data center cause lots of changes to the…
I coded the fix. We considered some options that had a bias away from the slow links, but we thought it was safer to avoid bias completely. It was fine in my tests, but I couldn't prove that biasing toward the faster…