One random writer, several frequent readers for std :: map

Question

I ran into concurrency problem. I have std::map , there is one random writer and several frequent readers from different streams, this author sometimes adds keys (the std::string key) to the map, and I can not guarantee when exactly readers will read and stop reading. I don’t want to set locks for readers, because reading is very common, and checking for locks will often hurt performance.

If readers always access the map using keys (non-therapists map ), will it always be safe for streams? If not, any idea how to create the code so that readers always get access to valid keys (or map iterators)?

Other approaches that use different containers to solve this problem are also welcome.

Answer 1

Note: fundamentally edited answer

As a reflex, I would put a lock.

At first glance, it seems you don't need to set a lock in your case:

• For insert() he said that "concurrent access to existing elements is safe, although there is no iteration of ranges in the container."
• For at() he said that: "Accessing or modifying other elements at the same time is safe."

The standard library addresses thread-safe aspects:

23.2.2. Container Racing

1) In order to avoid data investigations (17.6.5.9), implementations should consider the following functions as const: start, end, rbegin, rend, front, back, data, find, lower_bound, upper_bound, equal_range, at and, in addition to associative or disordered associative containers, operator [].

2) Despite (17.6.5.9), to avoid data jumps when the contents of the contained object in different elements in the same sequence , except for the vector, change simultaneously.

There are several other SO answers that interpret this as a thread safe guarantee, as I originally did.

However, we know that iterative ranges in the container are unsafe when the insert is done. And access to the element requires before you somehow repeat the search for the element. Thus, although the standard clarifies security for compatible access to various elements, when you already have your address, the wording leaves the potential concurrency container open.

I tried a simulation script with multiple reads and single write on MSVC and it never worked. But it’s not so important to do so: implementations are allowed to avoid more data than what is known in the standard (see 17.5.6.9) (or maybe I just got lucky many times).

Finally, I found two serious (post C ++ 11) links that clearly state that user locking should be safe:

• GNU document on concurrency in the standard library : “The standard establishes requirements for the library to ensure that race data are not caused by the library itself (...) User code must protect against simultaneous calls to functions that access any particular state of the library object when one or more of them refer to a state change. "

• GotW # 95 Solution: Thread Security and Synchronization, Herb Sutter : "Is the code (...) correctly synchronized? No. There is one reading of the stream (through const operations) from some_obj in the code and a second stream writing the same variable. If these threads can run at the same time, this is a race and a direct non-stop ticket to the undefined behavior of the earth. "

Based on these two almost authoritative interpretations, I revise my first answer and return to my original reflection: you will have to block simultaneous access.

Alternatively, you can use non-standard libraries with parallel implementation of maps, for example, Microsoft concurrent_unordered_map from the parallel template library or Intel concurrent_unordered_map from Threading Building Blocks (TBB) or without blocking, as described in this SO answer

Answer 2

I must disagree with the previous answer. When they talk about "concurrent access to existing elements" (when it comes to insert() ), it assumes that you already have a pointer / link / iterator to the existing element. This basically recognizes that the map is not going to move elements around in memory after insertion. He also acknowledges that map iteration is unsafe during insertion.

Thus, as soon as you have an insert, trying to do at() in one container (at the same time) is a data expense. During insertion, the map should change some internal state (possibly pointers to tree nodes). If at() catches the container during this manipulation, the pointers may not be in a consistent state.

You will need some kind of external synchronization (for example, a read-write lock), as soon as you have the option to simultaneously insert() and at() (or operator[] ).