-
Dave Watson authored
Summary: A ConcurrentHashMap with wait-free readers, as in Java's ConcurrentHashMap. It's a pretty generic closed-addressing chaining hashtable, except find() uses two hazard pointers to do hand-over-hand traversal of the list, so it never takes a lock. On rehash, only the part of the chain that remains the same (i.e. is still hashed to the same bucket) is reused, otherwise we have to allocate new nodes. Reallocating nodes means we either have to copy the value_type, or add in an extra indirection to access it. Both are supported. There's still a couple opportunities to squeeze some more perf out with optimistic loading of nodes / cachelines, but I didn't go that far yet, it sill looks pretty good. Reviewed By: davidtgoldblatt Differential Revision: D5349966 fbshipit-source-id: 022e8adacd0ddd32b2a4563caa99c0c4878851d8
f0b5826b