views:

271

answers:

4

Hello everyone,

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.

+2  A: 

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.

Nikolai N Fetissov
The OP doesn't ask about thread-safety, but actually make those procedures run in multiple threads.
KennyTM
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.
Andrew
@Andrew: just added a link to GCC extension.
Nikolai N Fetissov
You can, of course, manually partition the container and call `fill` on distinct ranges from multiple threads. That's manual, not automatic.
Nikolai N Fetissov
@Nikolai: Thanks, I just came across this link, too. Have you seen any info about MSVC implementation?
Andrew
+5  A: 

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)
Eugen Constantin Dinca
+1 I lost my bookmarks to these, thanks.
Nikolai N Fetissov
@Nikolai: The list is very incomplete and it's community wiki so feel free to add other implementations.
Eugen Constantin Dinca
what about the pros/cons of theese solutions?
f4
+1  A: 

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.

Thomas Matthews
A: 

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).

AshleysBrain