3

I have an unordered_map in code, which has a fixed number of elements initialized at the startup of my program

std::unorderd_map<int, bool> flags;
//Initialize all needed values in the map
// Start thread T1
// Start thread T2

all entries initialized to false in the beginning. There are two threads (T1 & T2). T1 can alter the value of each entry in the map. T2 just reads the entries periodically. In this case, do I need to use a lock? The total number of elements in the unordered_map stays the same throughout the life of the program.

whitetiger
  • 412
  • 1
  • 4
  • 13
  • 1
    What you're describing is an example of a [race condition](https://stackoverflow.com/questions/34510/what-is-a-race-condition). – Blastfurnace Dec 03 '20 at 20:23

6 Answers6

4

Yes, this causes a problem. The wording from the standard (§ [intro.races]/21.2) is:

The execution of a program contains a data race if it contains two potentially concurrent conflicting actions, at least one of which is not atomic, and neither happens before the other, except for the special case for signal handlers described below. Any such data race results in undefined behavior.

So, if you only read from multiple threads, you don't get "conflicting actions", but if even one thread writes, you need to synchronize the access.

In the specific case of unordered_map, I can see a situation where writing and reading concurrently could lead to a really serious problem.

An unordered_map uses a hash table with collision chaining. That means if two (or more) keys hash to the same value, they're all stored in the same "bucket", which is basically a linked-list of the values. So, looking something up in an unordered_map can involve traversing a linked list.

Experience shows that in a typical case, we can usually expect some elements in a collection to be accessed more often than others, often following something like the commonly known 80:20 rule (20% of the elements will account for 80% of the accesses).

That being the case, one way to optimize a hash table is to try to keep the most commonly accessed elements at the heads of their respective linked lists. To do that, writing a value could not only modify the value itself, but also move its node to (or toward) the beginning of the linked list. So, your reading thread could try to traverse the linked list just as the writing thread is trying to move a node forward in the linked list, so the linked list is completely corrupt at the time (e.g., contains a next pointer that hasn't been initialized yet).

So even when you don't do any insertion of deletion, and change the value in the map from bool to std::atomic<bool>, you still have a potential race condition. You really need to use a lock to protect access to the map itself.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • say the update is done using `m[k] = v` for existing key _k_, that's guaranteed not to invalidate iterators - wouldn't that mean the linked list at that node can't be reordered (per the optimisation postulated in your answer) because doing so would affect any subsequent use of the iterator (continued iteration would either skip or repeat elements - while it wouldn't crash, I'm not sure that's allowed for a not-invalidated iterator?). Given `T& operator[](const Key&)`, the write to the value itself isn't to any kind of proxy that could do reordering after the `operator[]` call. – Tony Delroy Dec 07 '20 at 22:59
  • (Regardless, if someone were concerned about this and wanted to avoid locking, they could have a second `unordered_map*>` in the updating thread and write through that, though of course two maps means more demand on cache which may or may not be more significant than locking performance-wise.) – Tony Delroy Dec 07 '20 at 23:01
  • @TonyDelroy: Rearranging nodes in a linked list doesn't normally require modifying the address of any node, so it's easy to do it without affecting validity of an existing pointer to that node. The standard doesn't really go into a lot of detail about whether seeing the same entry twice would be allowed; but it could also build synchronization into incrementing an iterator that didn't happen when/if you just did normal lookups from two separate threads. – Jerry Coffin Dec 07 '20 at 23:15
  • I don't see how synchronisation could be build in so it only kicked in (and slowed down operations) when there's a writing thread. Anyway, [contrainer.requirements.dataraces] ([here](http://eel.is/c++draft/container.requirements.dataraces)) requires _"for the purposes of avoiding data races"_ that `find` shall be considered `const`. So, if you avoided `operator[]` in favour of `find`, then modified/read `atomic` elements from however many threads, it _must_ be free of race conditions. – Tony Delroy Dec 08 '20 at 04:25
  • @TonyDelroy: It would probably slow things down at least a little even when there was no writing, but without writing you could probably keep contention to a minimum. Haven't tried to implement it though, and (at least in my experience) it's hard to be sure of the details until you really deal with them. – Jerry Coffin Dec 08 '20 at 04:28
3

So many ways to answer this question. Almost all of them are "yes, this is a problem".

If T1 inserts or removes elements from the map, then the map could change underneath T2 while it is doing lookups. If you're very lucky, this would cause a consistent crash.

Assuming that T1 only updates existing values in the map, then T2 could read a value that is in the process of being updated, and could get an unusual (as in, not true, and not false) value for the boolean. This could be avoided by using an unorderd_map<int, atomic<bool>>.

Assuming you avoid both the above problems, you will probably still have data races. A lock of some kind will avoid that.

[Added] Actually, a lock will avoid all three of these problems.

Marshall Clow
  • 15,972
  • 2
  • 29
  • 45
  • Even in the absence of insertion/deletion, I *think* an `unordered_map>` can still have a race condition (described in my answer). – Jerry Coffin Dec 03 '20 at 21:47
2

Since T1 is writing new values to the unordered_map, you need to protect the values from concurrent access, yes. Whether you use a std::mutex, std::atomic, etc, that is up to you to decide. But you need some kind of synchronization mechanism between the writing and the reading. Otherwise, T1 could be writing a new value at the exact same moment that T2 is trying to read that same value, which will cause race issues. T2 could easily end up receiving stale or incomplete data.

Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
  • is this a "race condition"? I never grasped the formal definition. I was going to propose this as dupe https://stackoverflow.com/questions/34510/what-is-a-race-condition, but got confused by the accepted answer starting with "A race condition occurs when two or more threads can access shared data and they try to change it at the same time" but then continues with an example where one thread only reads while another is writing – 463035818_is_not_an_ai Dec 03 '20 at 20:24
  • 1
    @largest_prime_is_463035818 I think is a better description is "two or more threads accessing shared data and at least one of them is a writer". – Blastfurnace Dec 03 '20 at 20:25
  • @Blastfurnance ok thats what I always understood. Maybe I am just misreading it,but I'll complain on that answer – 463035818_is_not_an_ai Dec 03 '20 at 20:26
  • 3
    He doesn't need a lock. As the data structure itself isn't changing there's no need for a lock around it. The value in each element however may change so he needs some synchronisation there. Something like a `std::unordered_map>` would probably be more lightweight than a fat lock. – Mike Vine Dec 03 '20 at 20:26
  • @remy Lebeau - I'm ok to have T2 read the previous value (while T1 is updating the value). Since here the value is a bool , do I need a lock? – whitetiger Dec 03 '20 at 20:30
  • 1
    @whitetiger Yes. Because the standard says so. – Mike Vine Dec 03 '20 at 20:30
  • 1
    @whitetiger "*I'm ok to have T2 read the previous value*" - the problem with such a data race is that the data may be incomplete, not just stale. A `bool` is 1 byte, but the CPU can't just read/write 1 byte, it has to read/write whole words at a time instead. Might not be noticable for `bool` data, but try 2+ byte data, like `short`, `int`, etc and you can easily see cases where only partial bytes have been written so far when a read occurs, thus you end up with a mix of bytes from different values. Atomic/synced access prevents that. – Remy Lebeau Dec 03 '20 at 20:32
  • 3
    There's also no guarantee that a `bool` will be one byte (and that's not just theoretical--there are real compilers that use 4 bytes for a bool). As long as that's aligned correctly, it'll *probably* happen atomically at the hardware level. On the other hand, it's fairly trivial to allocate it so it crosses a cache line boundary, so there's basically no way for it to even have a hope of happening atomically. – Jerry Coffin Dec 03 '20 at 20:40
  • 1
    I'm reasonably certain concurrent reading/writing can do more than just result in stale or corrupt data. It can result in things like accessing uninitialized memory (my answer describes how). – Jerry Coffin Dec 03 '20 at 22:00
0

Please use a lock. Even though T2 is reading data, you don't want T2 to be reading at the same time T1 is modifying/writing into the map. If that occurs you can have a race condition with undefined behavior where T2 reads the wrong item from the map.

Abhijit Raman
  • 86
  • 3
0
std::unorderd_map<int, bool> flags;

...In this case, do I need to use a lock?

Yes... you'd need a lock around the entire unordered_map. After all - even if you just had...

bool flag;

...you'd need locking. Jerry Coffin quotes the relevant verse in his answer - reproduced here for convenience: §[intro.races]/21.2

The execution of a program contains a data race if it contains two potentially concurrent conflicting actions, at least one of which is not atomic, and neither happens before the other, except for the special case for signal handlers described below. Any such data race results in undefined behavior.

Alternatively, you could use:

std::unorderd_map<int, std::atomic_bool> flags;

[container.requirements.dataraces] guarantees you can safely do concurrent find operations to lookup the atomic<bool> elements. std::unordered_map<...>::find returns an iterator by value, so each thread will have an independent object to dereference - there's no potential race there. Then reads/writes to the atomic_bool from different threads can obviously be done safely - that's the whole point of atomic.

Tony Delroy
  • 102,968
  • 15
  • 177
  • 252
-4

Nope, if you're only reading and you're not changing the data in T2, then you should be fine. However, you might want to look into synchronizing the threads so T2 doesn't read right before T1 writes.

Manuel
  • 1
  • 3
  • 1
    "*T1 can alter the value of each entry in the map*" - which means it is not safe for T2 to read the values without protection – Remy Lebeau Dec 03 '20 at 20:21