Multithreaded splitting a map into multiple sections

Question

Supposedly I have a large std::map<SomeType1, std::vector<SomeType2>> my_map, and I need to sort all vectors in the map. Currently I'm running in a single thread:

for (auto& item : my_map)
{
    std::sort(item.second.begin(), item.second.end(), &some_comparer);
}

Using the above code, my CPU is constantly idle around ~15%, so I think I can divide the map into smaller sections and sort each sections in seperate threads.

I'd like to ask, how can I divide a map? For example, I want to split it into 4 sections:

auto& section1 = my_map.divide(0, 0.25); // <~ how to apply this?
auto& section2 = my_map.divide(0.25, 0.5);
auto& section1 = my_map.divide(0.5, 0.75);
auto& section1 = my_map.divide(0.5, 1);

std::thread thread1([&section1] { sort_for_me_pls(section1); });
std::thread thread2([&section2] { sort_for_me_pls(section2); });
std::thread thread3([&section3] { sort_for_me_pls(section3); });
std::thread thread4([&section4] { sort_for_me_pls(section4); });
thread1.join();
thread2.join();
thread3.join();
thread4.join();

Why not simply sort the vectors in parallel, _i.e._, one vector per thread? There's a lot of hassle to divide the workload and then join it together (merge sort the segments etc). — Felix Glas, Feb 12 '18 at 19:11
@Snps I'd also like to learn how to sort vectors in parallel, but currently I don't how how to write a thread pool manager to handle threads. Could you please post the answer? — MiP, Feb 12 '18 at 19:14

score 3 · Accepted Answer · answered Feb 12 '18 at 19:21

Using C++17, sorting the vectors in parallel is as easy as:

for (auto& [key, value] : my_map) {
    std::sort(std::execution::par, std::begin(value), std::end(value), &some_comparer);
}

Unfortunately, I don't think there's any compilers that have implemented the parallel versions of the algorithms in the standard library as of this time. It will probably happen soon though (within the year?)

You could do it manually usig std::thread with something like this:

std::vector<std::thread> threads;

for (auto& [key, value] : my_map) {
    threads.emplace_back([&] {
        std::sort(std::begin(value), std::end(value), &some_comparer);
    });
}

for (auto&& t : threads) {
    t.join();
}

score 0 · Answer 2 · answered Feb 12 '18 at 19:26

You can refer to the first answer to this question (How to retrieve all keys (or values) from a std::map and put them into a vector?) to see how to get a vector of all the keys in a map. Once you do this, you can pass to the function each thread executes an iterator (or index) to begin at in the key vector and the number of keys it should handle. Then each thread can just sort all of the vectors associated with the keys in its portion of the key vector. The implementation is non-trivial so I will just leave that to your (for example what do you do if there is less than 4 keys, what if the number of keys is not evenly divisible by 4, etc.).

yenj · Answer 3 · 2018-02-12T22:44:59.883

Snps provided a nice answer to solve you actual problem. But since your question was about splitting a map into multiple pieces I think you should take a look at this answer to a similar (yet more generic) question. You should be able to apply this solution to your map or generalize it to work with any type of container. For example (split splits the c container into parts parts):

template <typename C>
using CItRange = boost::sub_range<const C>;

template <typename C>
std::vector<CItRange<C>> split(const C& c, size_t parts) {
   const size_t step = c.size() / parts;
   int remainder = c.size() % parts;
   std::vector<CItRange<C>> slices;
   auto it = begin(c);
   while(it != end(c)) {
      auto sliceBegin = it;
      size_t remainderSpread = remainder-- > 0 ? 1 : 0;
      std::advance(it, std::min(step + remainderSpread, (size_t)std::distance(it, end(c))));
      slices.push_back(CItRange<C>{sliceBegin, it});
   }

   return slices;
}

You can then use it like this:

std::map<int, std::vector<int>> myMap = {{1,{}}, {2,{}}, {3,{}}, {4,{}}, {5,{}}};

for(const auto& mapSlice : split(myMap, 2)) {
   ...
}

http://coliru.stacked-crooked.com/a/9d82fe79cc274dd7

Multithreaded splitting a map into multiple sections

3 Answers3