Thread Safety of Std::Map for Read-Only Operations

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

This will work from multiple threads as long as your map remains the same. The map you use is immutable de facto so any find will actually do a find in a map which does not change.

Here is a relevant link: http://www.sgi.com/tech/stl/thread_safety.html

The SGI implementation of STL is
thread-safe only in the sense that
simultaneous accesses to distinct
containers are safe, and simultaneous
read accesses to to shared containers
are safe. If multiple threads access a
single container, and at least one
thread may potentially write, then the
user is responsible for ensuring
mutual exclusion between the threads
during the container accesses.

You fall into he "simultaneous read accesses to shared containers" category.

Note: this is true for the SGI implementation. You need to check if you use another implementation. Of the two implementations which seem widely used as an alternative, STLPort has built-in thread safety as I know. I don't know about the Apache implementation though.

C++ thread safety - map reading

If you are talking about the standard std::map^† and no thread writes to it, no synchronization is required. Concurrent reads without writes are fine.

If however at least one thread performs writes on the map, you will indeed need some sort of protection like a mutex.

Be aware that std::map::operator[] counts as write, so use std::map::at (or std::map::find if the key may not exist in the map) instead. You can make the compiler protect you from accidental writes by only referring to the shared map via const map&.

---

^†Was clarified to be the case in the OP. For completeness' sake: Note that other classes may have mutable members. For those, even access through const& may introduce a race. If in doubt, check the documentation or use something else for parallel programming.

What operations are thread-safe on std::map?

In theory no STL containers are threadsafe. In practice reading is safe if the container is not being concurrently modified. ie the standard makes no specifications about threads. The next version of the standard will and IIUC it will then guarantee safe readonly behaviour.

If you are really concerned, use a sorted array with binary search.

Thread safety of fixed sized stl map

No, you do not need to add extra synchronization to make this use of std::map thread-safe. You are only modifying the map nodes during initialization, and after that you are only reading the map. Concurrent reading of the map is no problem, because its structure does not change.

The fact that you are modifying the values in the map does not matter, because they don't contribute to the ordering and structure of the map.

Are find and read operations on std::map threadsafe?

Yes. As long as none of your threads do a write

i.e. Construct the data structure in memory

Use as many threads to find/read as you require.

If the leaf needs altering put a mutex there.

std::map thread-safety

The C++11 standard guarantees that const method access to containers is safe from different threads (ie, both use const methods).

In addition, [container.requirements.dataraces] states

implementations are required to avoid data races when the contents of
the contained object in different elements in the same sequence,
excepting vector<bool>

In other words, except for vector<bool> modifying distinct contents is not a data race.

Now, if one thread invalidates an iterator used by another thread, clearly this is a data race (and results in undefined behavior). If one thread does non-const access to a container, and another does const access, that is a data race (and undefined behavior). (Note: a number of functions are "considered const" for the purpose of multithreading, including begin, end and other functions (and methods) that are non-const simply because they return non-const iterators. [] is included in this set of pseudo-const for thread safety reasons, except for map and unordered_set etc -- 23.2.2.1).

However, it appears that if you have a reference to an element within the container, and engage in operations that do not invalidate that reference in another thread, and never write to that element in another thread, you can safely read from that reference. Similarly, if other threads never even read from the element, then writing to that element shouldn't result in undefined behavior.

For standards references, 17.6.5.9.5 seems to guarantee that functions from the standard library won't run away and read/write elements needlessly.

So the short answer: you are safe, so long as the other thread doesn't directly mess with that particular entry in the map.

thread safety in std::map

It is safe as long as none of the threads are modifying the map. It is also safe if threads are modifying different elements of the map (provided the elements themselves don't cause race conditions by, for example, modifying some global state):

In 17.6.5.9 Data race avoidance, the standard library guarantees that concurrent const access to containers is safe (at least as far s the containers go. If the elements allow mutation via const access there could be data races at the element level.)

In 23.2.2 Container data races further guarantees are made: non-const concurrent access is safe if the modifications/reads are to different elements of the container¹.

As soon as you have one thread making modifications to the container or to the same element in the container while others read or write, you are open to race conditions and undefined behaviour.

---

^{1 With the exception of std::vector<bool>}

Is it safe to read a single c++ std::map object by different threads simultaneously without synchronization mechanisms?

Yes this will be OK provided nobody is writing to the map. See here for full details.

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

Thread-safety of reading and writing from/to std::map in C++

No. As Diemtar Kühl has pointed out, you need a lock on the container,
which must be acquired anytime you access the container. So your
scenario for most access would be (C is the container lock,
O the lock for an individual object:

acquire C
find object
acquire O
release C
process object
release O

and if you delete, either:

acquire C
find object
acquire O
delete object
release O
release C

, or if you need to process first before deciding to delete:

acquire C
find object
acquire O
release C
process, determine that deletion is needed
acquire C
release O
release C

This creates several problems. The most obvious is that RAII cannot be
used to manage the locks, at least not in its natural fashion. (It can
still be used to ensure that the locks are freed in case of an
exception, but the release of the container lock in the first scenario
must be manual.) More importantly, it is subject to deadlock in at
least two cases:

• If your threads need to access more than one object at a time. In
  this case, in the first scenario, you have thread 1 which acquires C,
  then acquires O1, then releases C. Following that thread 2 acquires
  C, then blocks on O1. Thread 1 then resumes, and decides that it also
  needs to access object 2. So it tries to acquire C, and blocks,
  waiting for thread 2 to release it. (Thread 2 is, of course, blocked
  until thread 1 releases O1.)

• If you're using the second scenario for deletion, then it's sufficient
  that a second thread attempt to access the object you're working on
  while you are processing it. As above, the second thread will block
  on O (which the first thread holds), and the first thread will block
  on C (the second acquire C in the scenario). And neither thread will
  go anywhere, both waiting for the other one to proceed.

If no thread every locks more than one object, and the first scenario is
used for delete, the pattern will work. But it is very
fragile—it's too easy to imagine a maintenance programmer
violating one of these conditions—and I would strongly recommend
against it. (Of course, if none of the alternatives provide sufficient
throughput, you may have to use it. And even the second scenario for
delete can be made to work if you release O before attempting the
second acquisition of C, then reacquire O, once you have C. The key
conditions are that you must always acquire C, then O in that order, and
that you never try to acquire C when you have an O.)

Also note that having each object contain a mutex can be tricky, since
you have to hold the mutex until after the object has been removed from
the map. This means that either the map itself holds pointer to the
objects (and keep a pointer to the object after removing it from the
map, and free the lock and delete the object through this pointer), or
that the object keeps the a pointer to the mutex.

The simplest solution is to just use a single lock on C, and maintain it
during the processing of O. If the processing isn't too long, this
might be acceptable; if the reason you're using multithreading is to be
able to process on several cores simultaneously, this won't work.

Failing that, you might want to consider using a rwlock on the
container, and holding on to it for the entire time you hold O. Simple
access can then proceed, since it's only a read access, and the lock
allows multiple read accesses. For delete, you'll need a write access,
which will block until all read accesses have finished; you'll also
still need the special handling for the second scenario of deletion,
since attempting to upgrade the access from read to write can cause
deadlock, exactly as described above. (To upgrade from read to write,
it is necessary that no other thread hold read access.)

---

Related Topics