CODEWITHSUNDEEP
c++multithreadingdictionary
Weitao Wang
Weitao Wang

Reputation: 199

Why map is not multithread safe in C++?

I met this problem when I tried to solve an concurrency issue in my code. In the original code, we only use a unique lock to lock the write operation on a cache which is a stl map. But there is no restrictions on read operation to the cache. So I was thinking add a shared lock to the read operation and keep the unique lock to the write. But someone told me that it's not safe to do multithreading on a map due to some internal caching issue that it itself does.

Can someone explain the reason in details? What does the internal caching do?

Upvotes: 1

Views: 1568

Answers (4)

OOEngineer
OOEngineer

Reputation: 447

I really don't see why there would be any caching issue...

If I refer to the stl definition of a map, it should be implemented as a binary search tree.

A binary search tree is simply a tree with a pool of key-value nodes. Those nodes are sorted following the natural order of their keys and, to avoid any problem, keys must be unique. So no internal caching is needed at all.

As no internal caching is required, read operations are safe in multi-threading context. But it's not the same story for write operations, for those you must provide your own synchronization mechanism as for any non-threading-aware data structure.

Just be aware that you must also forbid any read operations when a write operation is performed by a thread, because this write operation can result in a slow and complete rebalancing of the binary tree, i.e. a quick read operation during a long write operation would return a wrong result.

Upvotes: 1

mionic
mionic

Reputation: 41

All const member functions of std types can be safely called from multiple threads in C++11 without explicit synchronization. In fact, any type that is ever used in conjunction with the standard library (e.g. as a template parameter to a container) must fulfill this guarantee.

Clarificazion: The standard guarantees that your program will have the desired behaviour as long as you never cause a write and any other access to the same data location without a synchronization point in between. The rationale behind this is that modern CPUs don't have strict sequentially consistent memory models, which would limit scalability and performance. Under the hood, your compiler and standard library will emit appropriate memory fences at places where stronger memory orderings are needed.

Upvotes: 1

James Kanze
James Kanze

Reputation: 153909

The implementations of std::map must all meet the usual guarantees: if all your do is read, then there is no need for external synchrionization, but as soon as one thread modifies, all accesses must be synchronized.

It's not clear to me what you mean by "shared lock"; there is no such thing in the standard. But if any one thread is writing, you must ensure that no other threads may read at the same time. (Something like Posix' pthread_rwlock could be used, but there's nothing similar in the standard, at least not that I can find off hand.)

Upvotes: 6

Angew is no longer proud of SO
Angew is no longer proud of SO

Reputation: 171127

Since C++11 at least, a const operation on a standard library class is guaranteed to be thread safe (assuming const operations on objects stored in it are thread safe).

Upvotes: 1

Related Questions