Is concurrent_map[key].fetch_add(val) thread safe?

[carlos-souto]

For example, consider this code to build a sparse matrix in the coordinate format:

using TKey = std::pair<size_t, size_t>;
using TVal = std::atomic<double>;

tbb::concurrent_map<TKey, TVal> sparse_matrix;

tbb::parallel_for(i_start, i_stop, [&](size_t i) {
    // some computation for the i-th index is performed, resulting in a key and a corresponding value
    // key may or may not have been computed before

    // update map
    sparse_matrix[key].fetch_add(val); // is this thread safe?
});

Although rare, two threads may need to fetch/insert the same key and update the corresponding value.

My understanding is that, if the key does not exist, concurrent_map ensures safe insertion, and if the key does exist concurrent_map ensures safe lookup. std::atomic<T>::fetch_add ensures the value itself is updated safely.

My questions:

1. Is sparse_matrix[key].fetch_add(val), as shown above, safe? Or should I precompute every key and preallocate the map with 0s using insert (is insert or emplace safer)?
2. Do I need std::atomic or is sparse_matrix[key] += val safe?

[pavelkumbrasev]

Hi @carlos-souto,
I checked the implementation and your understanding of operator[] is correct.

1. You can safely use sparse_matrix[key].fetch_add(val).
2. You should use std::atomic because as you said 2 threads can modify the same variable simultaneously.

[kboyarinov]

@carlos-souto, I agree with @pavelkumbrasev,
Just want to explain the answer a bit: that usage of std::atomic is strictly required if for some indices [i_start, i_stop) the same key can be produced and hence the same variable in the concurrent_map would be accessed (that is unsafe as Pavel mentioned).
The std::atomic is not required if for each index of parallel_for the unique key is produced and the container is only used to ensure concurrent insertion from multiple threads.
Following your comments and the code snippet provided, it seems like you are in the first scenario, I just wanted to highlight the second one in case some of our understanding is incorrect:)