The world's easiest lock-free hash table / Wunder Fund Blog

A non-blocking hash table is a two-way medal. In some cases, they allow you to achieve a performance that cannot be obtained in other ways. On the other hand, they are quite complex.

The first working non-blocking table that I heard about was written in Java by Dr. Cliff Click. Its code was released back in 2007, in the same year the author made a presentation on Google. I confess that when I first watched this presentation, I did not understand most of it. The main thing I realized is that Dr. Cliff Click must be some kind of sorcerer.



Fortunately, six years was enough for me to (almost) catch up with Cliff in this matter. As it turned out, you don’t need to be a magician to understand and implement the simplest, but at the same time perfectly working, non-blocking hash table. Here I will share the source code of one of them. I am sure that anyone who has experience in multi-threaded development in C ++ and who is ready to carefully study the previous posts of this blog will understand it without any problems.

The hash table is written using Mintomic , a portable library for developing without blocking in C / C ++, which I released last month.. It is built and launched out of the box on several x86 / 64, PowerPC and ARM platforms. And since every Mintomic function has an equivalent in C ++ 11, converting this table to C ++ 11 is a trivial task.

Limitations

We, programmers, have the instinct to write data structures immediately as universal as possible, so that it is convenient to reuse them. This is not bad, but it can do us a disservice if you turn it into a goal from the very beginning. For this post, I hit the other extreme, creating as limited and narrowly specialized a non-blocking hash table as I could. Here are its limitations:

• Stores only 32-bit integer keys and 32-bit integer values.
• All keys must be nonzero.
• All values ​​must be nonzero.
• A table has a fixed maximum number of records that it can store, and this number should be a power of two.
• There are only two operations: SetItem and GetItem.
• No delete operation.

Be sure when you master a limited version of this hash table, it will be possible to consistently remove all restrictions without changing the approach radically.

An approach

There are many ways to implement hash tables. The approach I chose is just a simple modification of the class ArrayOfItemsdescribed in my previous post, A Lock-Free ... Linear Search? I strongly recommend that you read it before continuing.

Similarly ArrayOfItems, this hash table class, which I called HashTable1, is implemented using a simple giant array of key / value pairs.

struct Entry
{
    mint_atomic32_t key;
    mint_atomic32_t value;
};
Entry *m_entries;

There HashTable1are no linked lists to resolve hash collisions outside the table; there is only the array itself. A null key in the array indicates an empty entry, and the array itself is initialized with zeros. And just like in ArrayOfItems, values ​​are added and arranged in HashTable1using a linear search.

The only difference ArrayOfItems, and HashTable1that ArrayOfItemsis always a linear search begins with the zero index, while HashTable1starting each line with a search index, calculated as a hash of the key . As a hash function, I chose MurmurHash3's integer finalizer , as it is fast enough and encodes integer data well.

inline static uint32_t integerHash(uint32_t h)
{
    h ^= h >> 16;
    h *= 0x85ebca6b;
    h ^= h >> 13;
    h *= 0xc2b2ae35;
    h ^= h >> 16;
    return h;
}

As a result, each time when we call SetItemeither GetItemwith the same key, a linear search will start from the same index, but when we pass different keys, the search in most cases will start from completely different indexes. Thus, the value is much better distributed over the array than in ArrayOfItems, and cause SetItemand GetItemof several parallel flows becomes safe.



HashTable1uses a circular search, which means when SetItemorGetItemreaches the end of the array, it just goes back to the zero index and continues the search. Since the array will never be filled, each search is guaranteed to end with either the discovery of the search key or the discovery of the record with key 0, which means that the search key does not exist in the hash table. This technique is called open addressing with linear probing , and in my opinion, this is the most lock-free-friendly hash table of the existing ones. In fact, Dr. Click uses the same trick in his Java non-blocking hash table.

The code

Here is a function that implements SetItem. It passes through the array and stores the value in the first record whose key is 0 or matches the desired key. Its code is almost identical to the code ArrayOfItems::SetItem, as described in the previous post . The differences are only an integer hash and a bitwise “and” applied to idx, which prevents it from going beyond the bounds of the array.

void HashTable1::SetItem(uint32_t key, uint32_t value)
{
    for (uint32_t idx = integerHash(key);; idx++)
    {
        idx &= m_arraySize - 1;
        uint32_t prevKey = mint_compare_exchange_strong_32_relaxed(&m_entries[idx].key, 0, key);
        if ((prevKey == 0) || (prevKey == key))
        {
            mint_store_32_relaxed(&m_entries[idx].value, value);
            return;
        }
    }
}

The code GetItemalso almost matches with ArrayOfItems::GetItemthe exception of minor modifications.

uint32_t HashTable1::GetItem(uint32_t key)
{
    for (uint32_t idx = integerHash(key);; idx++)
    {
        idx &= m_arraySize - 1;
        uint32_t probedKey = mint_load_32_relaxed(&m_entries[idx].key);
        if (probedKey == key)
            return mint_load_32_relaxed(&m_entries[idx].value);
        if (probedKey == 0)
            return 0;          
    }
}

Both of the above functions are thread safe without locking for the same reasons as their counterparts in ArrayOfItems: all operations with array elements are performed using atomic library functions, values ​​are mapped to keys using compare-and-swap (CAS) on keys, and all The code is resistant to memory reordering. And again, for a more complete understanding, I advise you to refer to the previous post .

And finally, just like in the previous article, we optimize SetItemby first checking whether CAS is really necessary, and if not, not using it. Thanks to this optimization, the sample application that you find below works almost 20% faster.

void HashTable1::SetItem(uint32_t key, uint32_t value)
{
    for (uint32_t idx = integerHash(key);; idx++)
    {
        idx &= m_arraySize - 1;
        // Load the key that was there.
        uint32_t probedKey = mint_load_32_relaxed(&m_entries[idx].key);
        if (probedKey != key)
        {
            // The entry was either free, or contains another key.
            if (probedKey != 0)
                continue;           // Usually, it contains another key. Keep probing.
            // The entry was free. Now let's try to take it using a CAS.
            uint32_t prevKey = mint_compare_exchange_strong_32_relaxed(&m_entries[idx].key, 0, key);
            if ((prevKey != 0) && (prevKey != key))
                continue;       // Another thread just stole it from underneath us.
            // Either we just added the key, or another thread did.
        }
        // Store the value in this array entry.
        mint_store_32_relaxed(&m_entries[idx].value, value);
        return;
    }
}

All is ready! You now have the easiest non-blocking hash table in the world. Here are links to the source code and the header file .

Short warning: as in ArrayOfItems, all operations with are HashTable1made with weak (relaxed) restrictions on memory ordering. Therefore, if you want to make any data available to other streams by writing a flag to HashTable1, it is necessary that this record has “ release semantics ”, which can be guaranteed by placing a release fence (“release barrier”) immediately before the instruction . Likewise, accessing a GetItemstream that wants to receive data needs to be provided with an acquisition fence (“acquisition barrier”).

// Shared variables
char message[256];
HashTable1 collection;
void PublishMessage()
{
    // Write to shared memory non-atomically.
    strcpy(message, "I pity the fool!");
    // Release fence: The only way to safely pass non-atomic data between threads using Mintomic.
    mint_thread_fence_release();
    // Set a flag to indicate to other threads that the message is ready.
    collection.SetItem(SHARED_FLAG_KEY, 1)
}

Application example

To evaluate HashTable1the work, I created another simple application, very similar to the example from the previous post. It each time chooses from two experiments:

• Each of the two streams adds 6,000 values ​​with unique keys,
• Each thread adds 12,000 different values ​​with the same keys.

The code is on GitHub, so you can compile it and run it yourself. Assembly instructions can be found in README.md . Since the hash table will never overflow - for example, less than 80% of the array will be used - it will show remarkable performance. Perhaps I should confirm this with measurements, but based on previous experience in measuring the performance of single - threaded hash tables , I bet you will not be able to create a faster, non-blocking hash table than . May seem awesome but



HashTable1HashTable1ArrayOfItemsthat underlies it shows terrible performance. Of course, as with any hash table, there is a non-zero risk of hashing a large number of keys in a single array index, and then performance will equal the speed ArrayOfItems. But with a sufficiently large table and a good hash function such as MurmurHash3, the likelihood of such a scenario is negligible.

I used non-lock tables like this in real projects. In one case, in the game I was working on, the fierce competition of threads for shared locks created a bottleneck every time memory monitoring was turned on. After switching to non-blocking hash tables, the frame rate in the worst case scenario improved from 4 FPS to 10 FPS.