CODEWITHSUNDEEP
c++multithreadingtbb
Gr-Disarray
Gr-Disarray

Reputation: 534

Concurrent hash table in C++

In my application I basically have multiple threads that perform inserts and mostly one thread that is iterating through a map and removing items if it meets certain criteria. The reason I wanted to use a concurrent structure is that it would have provided finer grain locking in the code that removes items from the queue which looks similar to this which is not ideal for various reasons including that the thread could get pre-empted while holding the lock.

Function_reap()
{
   while(timetaken != timeoutTime)
   {
      my_map_mutex.lock();

      auto iter = my_unordered_map.begin();
      while(iter != my_unordered_map.end())
      {
        if(status_completed == iter->second.status)
        {
          iter = my_unordered_map.erase(iter);
        }
      }

      my_map_mutex.unlock();
   }
}

Was going through the documentation for Intel TBB(Threading Building Blocks) and more specifically the concurrent_unordered_map documentation (https://software.intel.com/en-us/node/506171) to see if this is a good fit for my application and came across this excerpt.

Description concurrent_unordered_map and concurrent_unordered_multimap support concurrent insertion and traversal, but not concurrent erasure. The interfaces have no visible locking. They may hold locks internally, but never while calling user-defined code. They have semantics similar to std::unordered_map and std::unordered_multimap respectively, except as follows:

  • The erase and extract methods are prefixed with unsafe_, to indicate that they are not concurrency safe.

Upvotes: 1

Views: 4949

Answers (1)

mpoeter
mpoeter

Reputation: 2949

Well, it is difficult to design a solution that (efficiently) supports all operations. TBB has the concurrent_unordered_map which supports concurrent insert, find and iteration, but no erase - and the concurrent_hash_map which supports concurrent insert, find and erase, but no iteration.

There are several other libraries that provide concurrent hash maps like libcds, or my own one called xenium.

ATM xenium contains two concurrent hash map implementations:

  • harris_michael_hash_map - fully lock-free; supports concurrent insert, erase, find and iteration. However, the number of buckets has to be defined at construction time and cannot be adapted afterwards. Each bucket contains a linked list of items, which is not very cache friendly.
  • vyukov_hash_map - is a very fast hash map that uses fine grained locking for insert, erase and iteration; find operations are lock-free. However, if are using iterators you have to be careful to avoid deadlocks (i.e., a thread should not try to insert or erase a key while holding an iterator). However, there is an erase overload that takes an iteration, so you can safely remove the item the iterator points to.

I am currently working to make xenium fully windows compatible.

Upvotes: 3

Related Questions