How to handle entries of concurrent iterators concurrently?

[xamidi]

A tbb::concurrent_unordered_map<string, string>::iterator object is apparently a solist_iterator.

Since none of the methods of concurrent_unordered_map that obtain iterators are declared unsafe, I assume multiple such iterators of the same element are meant to be usable in multiple threads without extra synchronization by the user.

But is something like

// Thread A
tbb::concurrent_unordered_map<string, string> map;
...

// Many concurrent threads that are not A
pair<tbb::concurrent_unordered_map<string, string>::iterator, bool> emplaceResult = map.emplace(..., ...);
...
tbb::concurrent_unordered_map<string, string>::iterator& concurrentIt = emplaceResult.first;
concurrentIt->second = newValue;

really somehow thread-safe?
Or do I need to modify the iterator's value by using a different method?

[*] The only way I see in which the above code could be thread-safe is that concurrentIt actually contains a local copy of its entry in map, which is synchronized with map (hopefully based on modification timestamps so that only latest changes persist) at points in time where its values are not being modified by the single thread which created concurrentIt and is supposed to use it (e.g. when one of its methods is being called). Each synchronization would have to take all iterators by all threads of the same entry into account, so there should be an extra "not currently being modified" buffer for each thread and iterator to be requestable from other threads. (This wouldn't solve that obsolete data could be exposed to different threads, though, with no apparent way to update it when no method of the iterator was used for modification.)

I have similar code that upon execution seems to be reliable, but it just doesn't look reliable and I wonder whether or how I should improve it. Using extra mutexes for synchronization would be a terrible solution, since that would greatly impair performance for an issue that seems to never happen.

Is [*] really how it works, with the "obsolete data" issue somehow being solved, and is my highlighted code thereby perfectly fine?

[kboyarinov]

@xamidi,

In general, the code above is not thread-safe because multiple threads can assign to the same bool object inside of the map simultaneously. concurrent_unordered_map iterators are represented as simple pointers to elements inside of the map without any additional synchronizations around.
unsafe_ prefix for the method generally means that the actions under the hood are thread-safe from the container perspective i.e. does not break the internal structure and invariants because of data races. From the container side, this code is safe since the internal structure is not broken, but generally there is still a data race while accessing the element inside.
If such a behavior is strictly required, the simplest way for code above would be to have std::atomic<bool> as a mapped value type instead of bool to prevent data races while accessing it.
I don't know if such an approach works for your real code and I need a bit more time to take a look on it to advice something more.

[xamidi]

because multiple threads can assign to the same bool object inside of the map

The map does not contain bool objects afaik, can you elaborate?

iterators are represented as simple pointers to elements inside of the map without any additional synchronizations around

Ok, this is bad, so iterators are inherently unsafe?!

the simplest way for code above would be to have std::atomic<bool> as a mapped value type

I suppose you somehow overlooked that the map in question has type tbb::concurrent_unordered_map<string, string>.

[kboyarinov]

Oh, sorry. I thought bool relates to the mapped type in the map. Now I see it is actually string.

Ok, this is bad, so iterators are inherently unsafe?!

It is still concurrently safe to read elements from the map using iterators and actually iterate over the map is thread-safe as well.
Modification of the element under the iterator is not thread-safe if the type of mapped value results in data races while accessed concurrently and hence the additional synchronization may be required.

[xamidi]

Modification of the element under the iterator is not thread-safe if the type of mapped value results in data races while accessed concurrently and hence the additional synchronization may be required.

But as I said, using std::mutex would be a terribly underperforming solution.

So this boils down to:

• Do tbb::concurrent_[...] types have any methods that synchronize access to their elements from multiple threads?, or
• Does TBB have any abstraction to make std::string access thread-safe (similar to std::atomic for flat types)?

If not:

• Maybe these things would be useful additions to TBB?
• Is there even a way to avoid having to use std::mutex for "additional synchronization", and if so, what would be the most performant way? Possibly with a combination of different data types?

[kboyarinov]

I thought one more time about your use case and I think it is important to mention that if you are using only concurrent insertion of some set of elements, you can safely modify the it->second value if the insertion was done by the current thread (i.e. emplace returned pair with the second element true). If you want to unconditionally update element, it is still not thread-safe.

Do tbb::concurrent_[...] types have any methods that synchronize access to their elements from multiple threads?, or

If the solution above does not work for you, consider using concurrent_hash_map and its write_accessor instead of iterator. It supports a built-in read-write mutex protecting the access to the element inside the map.

Does TBB have any abstraction to make std::string access thread-safe (similar to std::atomic for flat types)?

Currently, we don't have any synchronization primitives other that mutexes to make access thread-safe. And currently I don't have any ideas on how such a primitive can work.

[xamidi]

if you are using only concurrent insertion of some set of elements, you can safely modify the it->second value if the insertion was done by the current thread

Could you elaborate why this is thread-safe?

consider using concurrent_hash_map and its write_accessor instead of iterator. It supports a built-in read-write mutex protecting the access to the element inside the map.

Thank you. I will look into this.