ngbronson

6 ms·

1.
by ngbronson 7y ago
That's a fallback implementation for platforms without SIMD. The real code is lower down.
2.
by ngbronson 7y ago
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 sizes, so the do
3.
by ngbronson 7y ago
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 seen it befor
4.
by ngbronson 7y ago
F14 supports stateful hashers, so in situations that need to be resilient to hash poisoning we can use a hasher designed for that purpose.
5.
by ngbronson 7y ago
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 enough to keep prob
6.
by ngbronson 7y ago
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.
7.
by ngbronson 7y ago
You're right, it's been available for a while now. This is the first time we've made an announcement about it.
8.
by ngbronson 7y ago
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 inside a larger progra
9.
by ngbronson 7y ago
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 then Google and Fa
10.
by ngbronson 8y ago
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
11.
by ngbronson 9y ago
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 cross-shard data, the
12.
by ngbronson 9y ago
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 leader-based co
13.
by ngbronson 9y ago
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 sequencers to get
14.
by ngbronson 9y ago
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 writes in the syst
15.
by ngbronson 11y ago
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?
16.
by ngbronson 11y ago
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, but is fully portable.
17.
by ngbronson 12y ago
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 feedback loop, however,
18.
by ngbronson 12y ago
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 database threads. MySQL has
19.
by ngbronson 12y ago
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 packets, because of r
20.
by ngbronson 12y ago
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 link in a 2 link s