6

I am facing a concurrency problem here. I have a std::map, there is one occasional writer and multiple frequent readers from different threads, this writer will occasionally add keys (key is a std::string)to the map, and I can not guarantee when exactly the readers perform reading and stop reading. I don't want to put locks for the readers, since reading is very frequent and checking locks frequently will hurt performance.

If the readers will always access the map by keys (not map iterators), will it be always thread-safe? If not, any idea how to design the code so that the readers will always access valid keys (or map iterators )?

Other approaches using different containers solving this problem are also welcome.

NathanOliver
  • 171,901
  • 28
  • 288
  • 402
Allanqunzi
  • 3,230
  • 1
  • 26
  • 58

2 Answers2

5

I have to disagree with the previous answer. When they talk about "concurrently accessing existing elements" (when talking about insert()), that presumes that you already have a pointer/reference/iterator to the existing element. This is basically acknowledging that the map isn't going to move the elements around in memory after the insertion. It also acknowledges that iterating the map is not safe during an insert.

Thus, as soon as you have an insert, attempting to do an at() on the same container (at the same time) is a data race. During the insert the map must change some sort of internal state (pointers to tree nodes, perhaps). If the at() catches the container during that manipulation, the pointers may not be in a consistent state.

You need some sort of external synchronization (such as a reader-writer lock) as soon as you have the possibility of both an insert() and at() (or operator[]) occurring at the same time.

Andre Kostur
  • 770
  • 1
  • 6
  • 15
  • I think if I use `std::unordered_map` instead of `std::map`, then inserting will not affect how other existing elements are accessed if a rehash is guaranteed not to happen. – Allanqunzi Aug 13 '15 at 22:05
  • @Allanqunzi the insert on `std::unorderd_map` might also affect other elements: the hash table points to buckets (i.e. linked lists) in case of hash collision. If there were no problem here, there would be no alternative [`concurrent_unordered_map`](https://msdn.microsoft.com/en-us/library/hh750089.aspx) arround – Christophe Aug 13 '15 at 22:22
  • I have to agree with your disagreement :-) Personally I find the standard's wording somewhat ambiguous. And I'm not the only one, looking at other answers (after C+11) and the number of people thinking its safe or unsafe. But your interpretation is finally the right one, as confirmed by the alomost authoritative references I could find. – Christophe Aug 13 '15 at 22:30
  • @Christophe, because of performance concern I am still reluctant to use `concurrent_unordered_map`, luckily, in my case, I can check all possible keys (not very huge numer) which can be given to the map, so I will test if the default `std::unordered_map` hash function for `std::string` will give collisions or not. – Allanqunzi Aug 13 '15 at 22:36
  • @Allanqunzi Does the Standard define what the hash function must be for std::string? You're going down a dark, dark path of implementation-specific behaviour which may change tomorrow when your compiler or perhaps runtime is updated. (Or you need to add one more key later on...) And then your program goes boom once every third blue moon. – Andre Kostur Aug 13 '15 at 23:01
  • @Allanqunzi you could then be interested in [lock-free access](http://stackoverflow.com/questions/14338732/is-it-possbile-to-implement-lock-free-map-in-c). It'll be safer than tricking with the hash function. – Christophe Aug 13 '15 at 23:07
  • @AndreKostur how does the `map` even know I already have made an iterator, or reference, or a copy, or the address of the existing elements? – Allanqunzi Aug 14 '15 at 19:09
  • @Allanqunzi It doesn't, nor does it care. That's why there are clauses in the Standard as to when pointers, references, and/or iterators are invalidated. Such as in a `map`, if you `erase` an element, all pointers, references, and iterators to that element are invalidated. Pointers, references, and iterators to other elements remain valid. – Andre Kostur Aug 15 '15 at 07:01
2

Attention: fundamentally edited answer

As a reflex I would put a lock.

At first sight, it seems not required to put a lock in your case:

  • For insert(), it's said that "Concurrently accessing existing elements is safe, although iterating ranges in the container is not."
  • For at() , it's said that: "Concurrently accessing or modifying other elements is safe."

The standard library addresses thread-safe aspects:

23.2.2. Container data races

1) For purposes of avoiding data races (17.6.5.9), implementations shall consider the following functions to be const: begin, end, rbegin, rend, front, back, data, find, lower_bound, upper_bound, equal_range, at and, except in associative or unordered associative containers, operator[].

2) Notwithstanding (17.6.5.9), implementations are required to avoid data races when the contents of the contained object in different elements in the same sequence, excepting vector,are modified concurrently.

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

Nevertheless, we know that iterating ranges in the container is not safe when an insert is done. And access to an element requires before somehow iterating to find the element. So, while the standard clarifies safety for concurent access to different elements when you already have their address, the wording leaves potential container concurrency issues open.

I have tried a simulation scenario with multiple read and single write on MSVC, and it never failed. But this is not engough to make the point : implementations are allowed to avoid more data races than what is foressen in the standard (see 17.5.6.9) (or maybe I was simply many times lucky).

Finally, I have found two serious (post C++11) references stating unambiguously that a user lock is required to be safe :

  • GNU document on concurrency in the standard library: "The standard places requirements on the library to ensure that no data races are caused by the library itself (...) The user code must guard against concurrent function calls which access any particular library object's state when one or more of those accesses modifies the state."

  • GotW #95 Solution: Thread Safety and Synchronization, by Herb Sutter : "Is the code correctly synchronized (...) ? No. The code has one thread reading (via const operations) from some_obj, and a second thread writing to the same variable. If those threads can execute at the same time, that’s a race and a direct non-stop ticket to undefined behavior land."

Based on these two almost authoritative interpretations, I revise my first answer and come back to my initial reflex : you'll have to lock your concurrent accesses.

Alternatively you could use non standard-libraries with concurrent implementation of maps such as for example Microsoft's concurrent_unordered_map from the Parallel Pattern Library or Intel's concurrent_unordered_map from the Threading Building Blocks (TBB) or lock-free library as described in this SO answer

Community
  • 1
  • 1
Christophe
  • 68,716
  • 7
  • 72
  • 138
  • 1
    No, this needs an external lock, as the other answer correctly explains. – T.C. Aug 13 '15 at 19:36
  • @T.C. following your remark, I've looked for additional up-to-date references that would confirm your statement, and finally found some trustworthy ones. I've edited my answer accordingly. – Christophe Aug 13 '15 at 22:15
  • 1
    It doesn't leave anything open. The rules in 17.6.5.9 apply across the entire library. 23.2.2 makes a small tweak to those rules for containers. – T.C. Aug 13 '15 at 22:23
  • @T.C. "leaves open" = "doesn't exclude" – Christophe Aug 13 '15 at 22:51