TGrowOnlyLockFreeHash

Navigation

API > API/Runtime > API/Runtime/Core > API/Runtime/Core/Experimental > API/Runtime/Core/Experimental/Containers

References

Syntax

template<typename EntryType, typename KeyType, typename ValueType>  
class TGrowOnlyLockFreeHash  
Copy full snippet

template<typename EntryType, typename KeyType, typename ValueType> class TGrowOnlyLockFreeHash

Remarks

Hash table with fast lock free reads, that only supports insertion of items, and no modification of values. KeyType must be an integer. EntryType should be a POD with an identifiable "empty" state that can't occur in the table, and include the following member functions: KeyType GetKey() const; // Get the key from EntryType ValueType GetValue() const; // Get the value from EntryType bool IsEmpty() const; // Query whether EntryType is empty void SetKeyValue(KeyType Key, ValueType Value); // Write key and value into EntryType (ATOMICALLY! See below) static uint32 KeyHash(KeyType Key); // Convert Key to more well distributed hash static void ClearEntries(EntryType* Entries, int32 EntryCount); // Fill an array of entries with empty values

The function "SetKeyValue" must be multi-thread safe when writing new items! This means writing the Key last and atomically, or writing the entire EntryType in a single write (say if the key and value are packed into a single integer word). Inline is recommended, since these functions are called a lot in the inner loop of the algorithm. A simple implementation of "KeyHash" can just return the Key (if it's already reasonable as a hash), or mix the bits if better distribution is required. A simple implementation of "ClearEntries" can just be a memset, if zero represents an empty entry.

A set can be approximated by making "GetValue" a nop function, and just paying attention to the bool result from FindEntry, although you do need to either reserve a certain Key as invalid, or add space to store a valid flag as the Value. This class should only be used for small value types, as the values are embedded into the hash table, and not stored separately.

Writes are implemented using a lock it would be possible to make writes lock free (or lock free when resizing doesn't occur), but it adds complexity. If we were to go that route, it would make sense to create a fully generic lock free set, which would be much more involved to implement and validate than this simple class, and might also offer somewhat worse read perf. Lock free containers that support item removal either need additional synchronization overhead on readers, so writers can tell if a reader is active and spin, or need graveyard markers and a garbage collection pass called periodically, which makes it no longer a simple standalone container.

Lock free reads are accomplished by the reader atomically pulling the hash table pointer from the class. The hash table is self contained, with its size stored in the table itself, and hash tables are not freed until the class's destruction. So if the table needs to be reallocated due to a write, active readers will still have valid memory. This does mean that tables leak, but worst case, you end up with half of the memory being waste. It would be possible to garbage collect the excess tables, but you'd need some kind of global synchronization to make sure no readers are active.

Besides cleanup of wasted tables, it might be useful to provide a function to clear a table. This would involve clearing the Key for all the elements in the table (but leaving the memory allocated), and can be done safely with active readers. It's not possible to safely remove individual items due to the need to potentially move other items, which would break an active reader that has already searched past a moved item. But in the case of removing all items, we don't care when a reader fails, it's expected that eventually all readers will fail, regardless of where they are searching. A clear function could be useful if a lot of the data you are caching is no longer used, and you want to reset the cache.

Constructors

Destructors

Functions

Constants