3

I'm trying to design a message queue for an object. There is a set of X threads that can all send message (to be processed later) to this object. If I have a std::map<thread_id_t, message>, is this thread safe, assuming thread one only adds messages with a key of 1, thread 2 to key 2, etc..?

Sam Kellett
  • 1,277
  • 12
  • 33
  • 1
    No, it is not thread-safe. – Andy Prowl Jan 07 '15 at 22:29
  • No, you need to sync access. The map is a shared resource, each call from different threads alters its state. – Marius Bancila Jan 07 '15 at 22:30
  • Do you have a link to the standard stating that? This answer: http://stackoverflow.com/a/15067564/649140 mentions that "implementations are required to avoid data races when the contents of the contained object in different elements in the same sequence, excepting vector" -- does this not apply here? – Sam Kellett Jan 07 '15 at 22:31
  • @SamKellett: That's different. What you're modifying concurrently here (by inserting new key-value pairs) is the data structure itself, not the individual elements contained in it :) – Andy Prowl Jan 07 '15 at 22:37

2 Answers2

5

std::map is not thread safe for multiple simultaneous writers.

One of the many reasons why STL maps are not thread safe is that the underlying implementation of an STL map is an AVL tree that needs to be rebalanced every once in a while after a number of insertions. Rebalancing the map affects multiple nodes and is definitely not thread safe.

Refer to the excellent Dr. Dobb's article on lock-free data structures if any of this sounds interesting to you.

EyasSH
  • 3,679
  • 22
  • 36
  • Ah ok, so would something like: `std::vector>` where each thread id is mapped 1-1 to an index in the outer vector be a better idea? – Sam Kellett Jan 07 '15 at 22:32
  • You will still need to make sure that each thread ID exists in the outer vector 'a priori'. Multiple insertions in a vector are also not thread safe as they can lead to a resizing of the underlying array. – EyasSH Jan 07 '15 at 22:33
  • @DietmarKühl: my statement was it is "not thread safe for multiple simultaneous writers". I think that's fairly accurate, right? – EyasSH Jan 07 '15 at 22:35
  • @EyasSH, ok that can be done on thread-creation. So they'd be allowed to modify their own inner vector's concurrently? – Sam Kellett Jan 07 '15 at 22:35
  • 1
    Separate vectors can be modified concurrently, yes. That said, you need to make sure that these vectors are inserted in the outer vector sequentially and linearly. If "on thread creation" means in the parent (spawning) thread, then that might be fine. – EyasSH Jan 07 '15 at 22:36
  • 1
    @SamKellett: actually, even that might not be advisable, unless all threads are created before any thread starts running, since any insertion might move the vectors contained in the outer vector. If you know the maximum number of threads you have, just have an array of vectors, or array of pointers to vectors-- not resizable, and perfectly accessible in parallel. – EyasSH Jan 07 '15 at 22:37
  • 1
    I know how many threads, but at runtime not compile time so will need to use a vector. But can guarantee that the outer vector is populated and 'frozen' before any of the inner vectors will ever be used. – Sam Kellett Jan 07 '15 at 22:40
  • If you can guarantee that-- i.e. only use `const` methods of the outer vector at any given point in time after creation, and having creation not overlap at all with thread access, then you should be all set. – EyasSH Jan 07 '15 at 22:42
  • That said, heap allocated arrays can also have runtime constant (and compile-time unknown) sizes :) – EyasSH Jan 07 '15 at 22:43
1

The general rule for classes in the standard C++ library is this: if you call a non-const method on an object (with the exception of some methods like std::vector<T>::operator[]()) you cannot have any other thread accessing this object in any way concurrently. If you need to use the operations you need to make synchronize the accesses between the different threads somehow. The relevant clauses in the standard are 17.6.4.10 [res.on.objects] paragraph 1:

The behavior of a program is undefined if calls to standard library functions from different threads may introduce a data race. The conditions under which this may occur are specified in 17.6.5.9.

... and 17.6.5.9 [res.on.data.races] which describes that the standard C++ library isn't allowed to do mutate objects except when a non-const member function is called on them.

Since inserting an object into a std::map<...> is clearly a non-const operations, you cannot do it concurrently from multiple threads without synchronization.

Dietmar Kühl
  • 150,225
  • 13
  • 225
  • 380