OpenMP plus reduction on unordered_map

Question

I would like to parallelize a for loop in which values of an unordered_map are updated:

unordered_map<string,double> umap {{"foo", 0}, {"bar", 0}};

#pragma omp parallel for reduction(my_reduction:umap)
for (int i = 0; i < 100; ++i)
{
    // some_string(i) would return either "foo" or "bar"
    umap[some_string(i)] += some_double(i);
}

So, no new entries in the unordered_map would be created, only the existing entries would be updated with a sum.

In this answer a user declared reduction is defined for the case of a vector. Could a user declared reduction be similarly defined in the case of the unordered_map?

Off topic: I'd use `umap.find` rather than `umap[]`. That way you're guaranteed not to add any new elements, don't have the extra unused code to add one if it isn't found, and can error check/assert that you really found what you were looking for. — 1201ProgramAlarm, Oct 18 '18 at 03:23

Qubit · Accepted Answer · 2018-10-18T12:31:34.313

It can be done using a similar approach to the one taken in the answer you linked. The one issue we face is that std::transform uses an unfortunate line when it comes to maps.

//GCC version, but the documentation suggests the same thing. 
*__result = __binary_op(*__first1, *__first2);

Since maps store types std::pair<const T1, T2> (i.e. the first must always be const, you can't modify the key), this would cause an error, because the operator= is deleted for this case.

For that reason we end up having to write this whole thing ourselves (the answer that follows could be made cleaner, I just hard-coded your type...).

We could just start with the examples of std::transform (look at example implementation 2) and modify the problematic part, but @Zulan raises a good point in the comments that simultaneously traversing unordered maps might not be a good idea (as they are, by definition, not ordered). While it might make some sense that the copy constructor retain the order, it seems that this is not guaranteed by the standard (at least I couldn't find it anywhere), as such the approach that std::transform takes becomes pretty useless.

We can resolve this issue with a slightly different reduction.

#include <unordered_map>
#include <string>
#include <iostream>
#include <utility>

void reduce_umaps(\
    std::unordered_map<std::string, double>& output, \
    std::unordered_map<std::string, double>& input)
{
    for (auto& X : input) {
      output.at(X.first) += X.second; //Will throw if X.first doesn't exist in output. 
    }
}

#pragma omp declare reduction(umap_reduction : \
    std::unordered_map<std::string, double> : \
    reduce_umaps(omp_out, omp_in)) \
    initializer(omp_priv(omp_orig))

using namespace std;

unordered_map<string, double> umap {{"foo", 0}, {"bar", 0}};

string some_string(int in) {
    if (in % 2 == 0) return "foo";
    else return "bar";
}

inline double some_double(int in) {
    return static_cast<double>(in);
}

int main(void) {
#pragma omp parallel for reduction(umap_reduction:umap)
for (int i = 0; i < 100; ++i) {
        umap.at(some_string(i)) += some_double(i);
    }
    std::cerr << umap["foo"] << " " << umap["bar"] << "\n";
    return 0;
}

You can also generalise this to allow the addition of keys within the parallel loop, but that won't parallelise well unless the number of added keys remains much smaller than the number of times you increase the values.

As a final side note, I replaced umap[some_string(i)] with umap.at(some_string(i)), to avoid accidentally adding elements much like was suggested in the comments, but find isn't the most practical function for that purpose.

I don't think simultaneously going through the iterators works for an **unordered** map. — Zulan, Oct 18 '18 at 08:59
@Zulan While your comment sounds reasonable at first, I'm not so sure. Keep in mind that all of the maps here are copies of the same initial unordered map, so I'm assuming their order is the same (although it is likely that it is not required by the standard, it would be interesting to know, let me check). — Qubit, Oct 18 '18 at 09:06
@Zulan According to https://stackoverflow.com/questions/45620007/order-of-unordered-map-changes-on-assignment, it seems it wasn't in C++11, however trying the same example with gcc and c++17 seems to give the same order, but I do agree that doesn't sound very safe. — Qubit, Oct 18 '18 at 09:09
You cannot rely on the order since it is not guaranteed. What happens is highly implementation defined. There is no guarantee that copying an an `unorderd_map` yields the same order. See also https://stackoverflow.com/questions/51592794/does-copy-of-unordered-map-will-have-exactly-same-buckets — Zulan, Oct 18 '18 at 09:18
@Zulan That's quite interesting, one would have hoped that the copy constructor, well, copied. But it is an unordered map so there really is no reason for it to do so. — Qubit, Oct 18 '18 at 09:30

OpenMP plus reduction on unordered_map

1 Answers1