1

I am trying to parallelize operations over a large vector of objects in C++. I have written parallel programs in Java before, but I have just started using C++.

The current code uses an iterator over the vector. What would be the fastest way to parallelize this? My current thoughts are...

  1. Using the .size() function and using a forloop through the vector. However, I am worried about the runtime of the .size() function, is it O(N) or O(1)? Also would forloops be slower than using an iterator?

  2. Somehow splitting the vector, and create iterators for the new vectors in parallel? If so, what would be a good method of splitting the vector with a fast runtime?

Or is there some faster way to do this?

user262476
  • 27
  • 4
  • size is constant time. using a for loop should be no different from using an iterator as far as time complexity is concerned. but using iterators or a for-each loop is preferred to the traditional for loop. I am not sure what it is that you are trying to do with splitting. Are u asking us how we can split a vector in C++? Or is it just a programatical split for the threads? Vectors support random access iterators. So you can have iterators at different points and hand them out to different threads for parallel processing. Be careful with anything that could invalidate the iterators though. – MS Srikkanth Apr 03 '14 at 19:27

4 Answers4

2

However, I am worried about the runtime of the .size() function, is it O(N) or O(1)?

vector<...>::size() is O(1).

Also would forloops be slower than using an iterator?

In most cases, I doubt it. In some cases, an algorithm which takes iterators may be optimized based on the value type of the iterator. Benchmark it.

Somehow splitting the vector, and create iterators for the new vectors in parallel? If so, what would be a good method of splitting the vector with a fast runtime?

Vector iterators are random access. It is a very cheap operation to just find the distance from begin to end (O(1)), and split it in half.

auto begin = v.begin();
auto end = v.end();
auto mid = begin + (end - begin)/2;
algorithm(begin, mid);
algorithm(mid, end);
Benjamin Lindley
  • 101,917
  • 9
  • 204
  • 274
  • If additional splitting is needed, then review the advance and distance methods: [Iterator library](http://en.cppreference.com/w/cpp/iterator), [std::advance](http://en.cppreference.com/w/cpp/iterator/advance), [std::distance](http://en.cppreference.com/w/cpp/iterator/distance). – CPlusPlus OOA and D Apr 03 '14 at 19:31
0

If the vector isn't modified by iterators I'd divide vector onto N parts and gave every thread its piece of vector, after that, if needed one thread summarizes results of all others.

INait
  • 181
  • 6
0

look into boost threads. I find them very intuitive

Kim Kardashian
  • 81
  • 2
  • 8
0

I believe this answer is relevant: https://stackoverflow.com/a/2547725/1524700 Depending on your platform I would also add Intel Threading Building Blocks to the list.

Community
  • 1
  • 1
Andrey
  • 1,561
  • 9
  • 12