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.

Pacer

C++14 may add some parallel algorithm support, here are some papers that were submitted, keep in mind many of these will not be added – Acrolith

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)

Detonate

@Nikolai: The list is very incomplete and it's community wiki so feel free to add other implementations. – Detonate

what about the pros/cons of theese solutions? – Month

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.

Horseradish

Answer 3

Current C++ standards don't talk about threads at all, so no. Here is more or less original statement about STL thread safety.

Edit:

Look at one common (GCC) implementation of std::fill:

template<typename _ForwardIter, typename _Tp>
  void
  fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __value)
  {
      for ( ; __first != __last; ++__first)
          *__first = __value; 
  }

It's obvious that it's not safe for parallel execution (which would require specialized implementation.)

And here is GCC extension for Parallel Mode.

Destine

The OP doesn't ask about thread-safety, but actually make those procedures run in multiple threads. – Deidradeidre

for me it seems that executing this code concurrently should not be an issue because everything is independent or I am getting this wrong? My question is not thread safety of container memory access but acceleration of a fill/transform loop. – Pacer

@Andrew: just added a link to GCC extension. – Destine

You can, of course, manually partition the container and call fill on distinct ranges from multiple threads. That's manual, not automatic. – Destine

Thanks, I just came across this link, too. Have you seen any info about MSVC implementation? – Pacer

Answer 4

Visual Studio 2010 provides the Parallel Patterns Library which has STL style algorithms which execute in parallel. Of course, this is Microsoft-specific to VS2010 (and up, I guess).

Greyback

It may be interessting for future readers, that PPL's interface is nowadays a subset of Intel's TBB. – Graniah