STL algorithms and concurrent programming

Question

Can any of STL algorithms/container operations like std::fill, std::transform be executed in parallel if I enable OpenMP for my compiler? I am working with MSVC 2008 at the moment. Or maybe there are other ways to make it concurrent?

Thanks.

Answer 1

There are a number of projects that aim at having parallel STL type libraries:

1. OpenMP Multi-Threaded Template Library
2. libstdc++ parallel
3. HPC++ Parallel Standard Template Library
4. Parallel Patterns Library (shamelessly borrowed from AshleysBrain's answer)

Answer 2

To guarantee std::transform and std::fill to be parallel-safe, you will have to write your own version. The common implementation of these functions is for sequential execution.

Let us take std::fill as a simple example. In converting to parallel, you will need to break up the function into smaller functions that can be executed asynchronously without any inter-dependencies. For example, one sub-function could fill the first half and the second sub-function could fill the second half. The parent function would have to delegate (fork) the two sub-functions, and wait for them to finish (join).

The bigger question is whether or not the overhead spent in run-time preparation for parallel execution can make up for the actual parallel execution time. Large fills would have a higher justification than smaller fills.

Perhaps a better idea is to make thread-safe versions of these functions and have the threads execute in parallel, rather than splitting up the functions.

Before splitting things into multiple threads, first try optimizing in reference to the data. Search the web for Data Oriented Design. Articles have shown that by optimizing execution to reduce processor cache misses, a program can run significantly faster.