c++c++11openmp

OpenMP atomic update of map value


Is the follwing increment operation thread safe?

std::map<std::uint64_t, std::uint64_t> val_counts{};

#pragma omp parallel for num_threads(32)
for (std::uint16_t ix = 0; ix < 96; ++ix) {

#pragma omp atomic update
    val_counts[ix%5]++;

}

Based on my experiments, it seems to be thread safe. Howewer, I wanted to be sure, as I am not sure what this translates into. An alternative would be using #pragma omp critical, of course.


Solution

  • I believe the answer is might be yes, but I'm not 100% sure by any means.

    The OpenMP specification gives the following list as the forms the expression is allowed to take:

    x++;
    x--;
    ++x;
    --x;
    x binop= expr;
    x = x binop expr;
    x = expr binop x;
    

    It further specifies that:

    x, r (result), and v (as applicable) are lvalue expressions with scalar type.

    Finally, it says that when it uses scalar, it means what that means in the underlying language (C++, in this case).

    That leads to a bit of a difficulty though. The OpenMP spec talks about an expression of scalar type, but the C++ standard only talks about "scalar" with respect to objects, not expressions.

    So, while your code may fall within the intent of the specification, given the difference in wording between the two, it's difficult to be at all sure of how to read this for a case like this where the increment may easily have two entirely separate side-effects (one of inserting an item into the map, and one of incrementing that object after it's inserted).

    Although it's still not entirely clear with respect to the rules, I suspect most problems this could potentially cause would probably be cured by separating the job into three phases. One would be to pre-populate the map, in a single thread. In this case, you're using only keys from 0 to 5, so you could do something like this:

    for (int i=0; i<5; i++)
        val_counts[i] = 0;
    

    The point of this is that you never insert a new key into the map from more than one thread. Then in the multi-threaded portion, you'd probably separate the lookup from the update, and carry out the update atomically:

    auto &val = val_counts[ix%5];
    
    #pragma omp atomic update
    ++val;
    

    That at least makes it explicit exactly what needs to be atomic, eliminating any chance of misinterpretation leading to (for example) the function call being what you care bout being done atomically.

    For a lot of uses of a map, however, that's not going to be practical--you frequently don't know the keys you're going to use ahead of time, which makes inserting them essentially impossible.

    Without that, it's not clear whether the #pragma omp atomic is really doing to protect inserting a new item into the map, or only the update to the associated value (but given the emphasis on "scalar", more likely the latter).

    Reference

    OpenMP 5.2 Specification