folly::AtomicUnorderedInsertMap

template<
    typename Key,
    typename Value,
    typename Hash = std::hash<Key>,
    typename KeyEqual = std::equal_to<Key>,
    bool SkipKeyValueDeletion = (std::is_trivially_destructible<Key>::value && std::is_trivially_destructible<Value>::value),
    template<typename> typename Atom = atomic,
    typename IndexType = uint32_t,
    typename Allocator = /* implementation-defined */>
struct AtomicUnorderedInsertMap;

Description

LIMITATIONS:

* Insert only (*) - the only write operation supported directly by AtomicUnorderedInsertMap is findOrConstruct. There is a (*) because values aren't moved, so you can roll your own concurrency control for in-place updates of values (see MutableData and MutableAtom below), but the hash table itself doesn't help you.

* No resizing - you must specify the capacity up front, and once the hash map gets full you won't be able to insert. Insert performance will degrade once the load factor is high. Insert is O(1/(1-actual_load_factor)). Note that this is a pretty strong limitation, because you can't remove existing keys.

* 2^30 maximum default capacity - by default AtomicUnorderedInsertMap uses uint32_t internal indexes (and steals 2 bits), limiting you to about a billion entries. If you need more you can fill in all of the template params so you change IndexType to uint64_t, or you can use AtomicUnorderedInsertMap64. 64-bit indexes will increase the space over of the map, of course.

WHAT YOU GET IN EXCHANGE:

* Arbitrary key and value types - any K and V that can be used in a std::unordered_map can be used here. In fact, the key and value types don't even have to be copyable or moveable!

* Keys and values in the map won't be moved - it is safe to keep pointers or references to the keys and values in the map, because they are never moved or destroyed (until the map itself is destroyed).

* Iterators are never invalidated - writes don't invalidate iterators, so you can scan and insert in parallel.

* Fast wait-free reads - reads are usually only a single cache miss, even when the hash table is very large. Wait-freedom means that you won't see latency outliers even in the face of concurrent writes.

* Lock-free insert - writes proceed in parallel. If a thread in the middle of a write is unlucky and gets suspended, it doesn't block anybody else.

COMMENTS ON INSERT-ONLY

This map provides wait-free linearizable reads and lock-free linearizable inserts. Inserted values won't be moved, but no concurrency control is provided for safely updating them. To remind you of that fact they are only provided in const form. This is the only simple safe thing to do while preserving something like the normal std::map iteration form, which requires that iteration be exposed via std::pair (and prevents encapsulation of access to the value).

There are a couple of reasonable policies for doing in-place concurrency control on the values. I am hoping that the policy can be injected via the value type or an extra template param, to keep the core AtomicUnorderedInsertMap insert-only:

CONST: this is the currently implemented strategy, which is simple, performant, and not that expressive. You can always put in a value with a mutable field (see MutableAtom below), but that doesn't look as pretty as it should.

ATOMIC: for integers and integer-size trivially copyable structs (via an adapter like tao/queues/AtomicStruct) the value can be a std::atomic and read and written atomically.

SEQ-LOCK: attach a counter incremented before and after write. Writers serialize by using CAS to make an even->odd transition, then odd->even after the write. Readers grab the value with memcpy, checking sequence value before and after. Readers retry until they see an even sequence number that doesn't change. This works for larger structs, but still requires memcpy to be equivalent to copy assignment, and it is no longer lock-free. It scales very well, because the readers are still invisible (no cache line writes).

LOCK: folly's SharedMutex would be a good choice here.

MEMORY ALLOCATION

Underlying memory is allocated as a big anonymous chunk. If the SkipKeyValueDeletion template param is true then deletion of the map consists of deallocating the backing memory, which is much faster than destructing all of the keys and values. Feel free to override if std::is_trivial_destructor isn't recognizing the triviality of your destructors.