CODEWITHSUNDEEP
c++dictionaryconcurrencystlthread-safety
Michał Fronczyk
Michał Fronczyk

Reputation: 1891

STL map implementation in Visual C++ 2010 and thread safety

I know that it's allowed to read some cells and concurrently write to different cells of an STL vector as long as no resizing is needed. I'm wondering if it's allowed to concurrently get values for some keys and in the same time inserting new key-value pairs to the STL map in Visual C++ 2010, if I guarantee that each thread accesses/inserts a different key.

From http://www.cplusplus.com/reference/map/map/operator[]/:

Data races:

The container is accessed, and potentially modified. The function accesses an element and returns a reference that can be used to modify its mapped value. Concurrently accessing other elements is safe. If the function inserts a new element, concurrently iterating ranges in the container is not safe.

So this says that if I insert a new element, I can't iterate over the container. The question is whether accessing a different element requires iterating over the container or not. Is that safe then?

Will it be safe if I guarantee that the size of the container never exceeds N? Then maybe the internal data structures of the map could be pre-allocated and stay constant - like vector's internals as long as the vector isn't resized.

I know that there are thread-safe implementations of map available, but they're much slower probably, so I'm wondering if the standard map is enough in my case, because the code I'm modifying is a hotspot in my app.

Thanks, Michal

Upvotes: 1

Views: 963

Answers (1)

Evgeny Panasyuk
Evgeny Panasyuk

Reputation: 9199

I'm wondering if it's allowed to concurrently get values for some keys and in the same time inserting new key-value pairs to the STL map in Visual C++ 2010, if I guarantee that each thread accesses/inserts a different key.

No, it is not allowed. Lookup involves traversal of internal data structures (for std::map common approach for internal representation is binary search tree like Red–black tree). On the other hand insert modifies internal structures.

If simultaneous lookups and inserts would be thread-safe, then each access, even in single-thread environment, would involve high syncronization cost for operations, which contradicts C++ princple - "you do pay for what you don't use".

Thread Safety in MSVC 2010:

If a single object is being written to by one thread, then all reads and writes to that object on the same or other threads must be protected. For example, given an object A, if thread 1 is writing to A, then thread 2 must be prevented from reading from or writing to A.

That said, if you already have reference to element before insert operations in other thread - it would be safe to access element via that reference, because object is not moved during internal rebalancing.

ISO C++11 23.2.4/9:

The insert and emplace members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements.

MSVC 2012 (but not MSVC 2010) has concurrency::concurrent_unordered_map associative container (note it is unordered which makes it similar to std::unordered_map, i.e. it requires hash and equality for keys rather than strict weak ordering):

The concurrent_unordered_map class is a concurrency-safe container that controls a varying-length sequence of elements of type std::pair<const _Key_type, _Element_type>. The sequence is represented in a way that enables concurrency-safe append, element access, iterator access, and iterator traversal operations.

Intel TBB library has similar container - tbb::concurrent_unordered_map:

Template class for associative container that supports concurrent insertion and traversal.

Upvotes: 5

Related Questions