1

I am using std::map to implement my local hash table, which will be accessed by multiple threads at the same time. I did some research and found that std::map is not thread safe. So I will use a mutex for insert and delete operations on the map. I plan to have separate mutex(es), one for each map entry so that they can be modified independently.

Do I need to put find operation also under critical section? Will find operation be affected by insert/delete operations? Is there any better implementation than using std::map that can take care of everything?

Groovy
  • 516
  • 5
  • 16

5 Answers5

5

Binary trees are not particularly suited to Multi-Threading because the rebalancing can degenerate in a tree-wide modification. Furthermore, a global mutex will very negatively access the performance.

I would strongly suggest using an already written thread-safe containers. For example, Intel TBB contains a concurrent_hash_map.

If you wish to learn however, here are some hints on building a concurrent sorted associative container (I believe a full introduction to be not only out of my reach but also out of place, here).

Reader/Writer

Rather than a regular Mutex, you may want to use a Reader/Writer Mutex. This means parallelizing Reads, while Writes remain strictly sequential.

Own Tree

You can also build your own red-black or AVL tree. By augmenting the tree structure with a Reader/Writer Mutex per node. This allows you to only block part of the tree, rather than the whole structure, even when rebalancing. eg inserts with keys far enough apart can be parallel.

Skip Lists

Linked lists are much more amenable to concurrent manipulations, because you can easily isolate the modified zone.

A Skip List builds on this strength, but augments the structure to provide O(log N) access by key.

The typical way to walk a list is using the hand over hand idiom, that is, you grab the mutex of the next node before releasing the one of the current node. Skip Lists add a 2nd dimension as you can dive between two nodes, thus releasing both of them (and letting other walkers go ahead of you).

Implementations are much simpler than for binary search trees.

Persistent

Another interesting piece is the idea of persistent (or semi-persistent) data-structures, often found in functional programming. Binary Search Tree are particularly amenable for it.

The basic idea is to never change a node (or its content) once it exists. You do so by sharing a mutable head, that will point to the later version.

  • To Read: you copy the current head, then use it without worry (the information is immutable)
  • To Write: each node that you would modify in a regular tree is instead copied and the copy modified, therefore you rebuild part of the tree (up to the root) each time, and update the head to point to the new root. There are efficient ways to rebalance on descending the tree. Writes are sequential

The main advantage is that a version of the map is always available. That is, you can always read even when another thread is performing an insert or delete. Furthermore, because read access only require a single concurrent read (when copying the root pointer), they are near lock-free, and thus have excellent performance.

Reference counting (intrinsic) is your friend for those nodes.

Note: copies of the tree are very cheap :)

I do not know any implementation in C++ of either a concurrent Skip List or a concurrent Semi-Persistent Binary Search Tree.

Matthieu M.
  • 287,565
  • 48
  • 449
  • 722
  • Matthieu M: If the binary tree is a red-black tree there will never be more than a constant number of rebalancing operations, although there may be a logarithmic number of recoloring operations. It is possible to implement them in such a way that other threads can read while the recoloring is taking place as longt as no other threads update the tree. Only the actual rebalancing would have to be exclusive and even that would only need to be per subtree. – Jørgen Fogh Aug 17 '11 at 22:34
  • @Jorgen: Thanks for the exact impact. – Matthieu M. Aug 18 '11 at 06:13
1

Yes, if the insert or delete results in a rebalance I believe that find could be affected too.

Mark B
  • 95,107
  • 10
  • 109
  • 188
1

Yes - You would need to put insert, delete and find in a critical section. There are techniques to enable multiple finds at the same time.

Ed Heal
  • 59,252
  • 17
  • 87
  • 127
1

You will in deed need to put find in a critical section, but you might want to have two different locks, one for writing and one for reading. The write lock is exclusive but if no thread holds the write lock several threads may read concurrently with no problems.

Such an implementation would work with most STL implementations but it would not be standards compliant, however. std::map is usually implemented using a red-black tree which doesn't change when elements are read. If the map was implemented using a splay tree instead, the tree would change during lookup and only one thread could read at a time.

For most purposes I would recommend using two locks.

Jørgen Fogh
  • 7,516
  • 2
  • 36
  • 46
  • I partially buy your argument, but read lock will also be shared between multiple threads. Somehow, I need to maintain how many threads are doing find operation, so that read lock can be freed. Also, write lock can be taken only when all reads are finished, so they dont get affected. In a way, insert/delete/find all operations need to wait for same lock. – Groovy Aug 16 '11 at 13:49
  • @Ashish: but you can have multiple concurrent `find` with a write/read lock, while with a single lock you could only have one `find` at a time. – Matthieu M. Aug 16 '11 at 14:07
0

From what I can see, a similar question has been answered here, and the answer includes the explanation for this question also, as well as a link explaining the thread safety in more details.

Thread safety of std::map for read-only operations

Community
  • 1
  • 1
penelope
  • 8,251
  • 8
  • 45
  • 87
  • It's not really the same. That other question is about having multiple threads read a map that never changes. This question is about thread-safe concurrent reads and modifications. – Kristopher Johnson Aug 16 '11 at 13:27
  • uh, right, the question is not the same, but the answer explains the situations and ways in which accessing maps from multiple threads is safe, and the situations and ways in which it isn't, and answers this question also. It also gives a link with a more detailed explanation about thread safety. Will rephrase my answer – penelope Aug 16 '11 at 13:30
  • I think the more important lesson to take from that answer is that thread safety depends on the implementation of stl that you are using – Harald Scheirich Aug 16 '11 at 13:41
  • The question is not the same. In my case, map can be modified on the go. – Groovy Aug 16 '11 at 13:43
  • So find operation can be concurrent with insert/delete operations and with any other find operation as well. – Groovy Aug 16 '11 at 13:50