CODEWITHSUNDEEP
c++multithreadingstldictionarythread-safety
Maanu
Maanu

Reputation: 5203

stl map find thread safe

Is find call on stl map thread safe?

Upvotes: 16

Views: 13865

Answers (4)

Asker
Asker

Reputation: 55

I tried to find the answer to the question.

https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-3.4/stl__map_8h-source.html

you can see stl map souce.

search find(). It is found in 497 line, 524 line. Code is written as _M_t.find(__x);

Then search _M_t.

It is found in 124 line. It is written as _Rep_type _M_t;

If property _M_t is created per thread, It could be thread safe. But I don't think so. If 2 thread use find concurrently, they would use _M_t concurrently. _Rep_type is connected to _Rb_tree.

You can see _Rb_tree in below source.

https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.1/stl__tree_8h-source.html

find() do tree travel(see below code). unwilled change in __x and __y would occur.

01307   template<typename _Key, typename _Val, typename _KeyOfValue,
01308            typename _Compare, typename _Alloc>
01309     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01310     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01311     find(const _Key& __k)
01312     {
01313       _Link_type __x = _M_begin(); // Current node.
01314       _Link_type __y = _M_end(); // Last node which is not less than __k.
01315 
01316       while (__x != 0)
01317     if (!_M_impl._M_key_compare(_S_key(__x), __k))
01318       __y = __x, __x = _S_left(__x);
01319     else
01320       __x = _S_right(__x);
01321 
01322       iterator __j = iterator(__y);
01323       return (__j == end()
01324           || _M_impl._M_key_compare(__k,
01325                     _S_key(__j._M_node))) ? end() : __j;
01326     }

Upvotes: 3

the swine
the swine

Reputation: 11031

Actually, the STL shipped with Microsoft Visual Studio 2008 seems to have some locks on operations that modify the map (and i assume it is the same for set). It is rather annoying, as i'm building more maps in multiple threads and it is killing my performance.

Upvotes: 0

Doug T.
Doug T.

Reputation: 65599

No, the C++ spec makes no guarantees on thread safety in the spec for operations on any STL containers. If thread safety is important, the you should provide your own locking.

That being said, different implementations seem to offer different guarantees. Most seem to allow multiple concurrent readers, for example, as long as no writing is being performed concurrently. If you don't care about portability, you can research the documentation for your implementation. For example from here for SGI STL:

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.

From this answer, a similar guarantee seems to be made by Dinkumware (they make Microsoft's STL implementation).

Multiple threads can safely read the same container object. (There are nunprotected mutable subobjects within a container object.)

Two threads can safely manipulate different container objects of the same type. (There are no unprotected shared static objects within a container type.)

You must protect against simultaneous access to a container object if at least one thread is modifying the object. (The obvious synchronization primitives, such as those in the Dinkum Threads Library, will not be subverted by the container object.)

Upvotes: 15

Fred Foo
Fred Foo

Reputation: 363547

No: when another thread is updating the map concurrently with your find, behavior is undefined.

Upvotes: 5

Related Questions