CODEWITHSUNDEEP
c++multithreadingc++11collectionsstd
Iter Ator
Iter Ator

Reputation: 9334

How to process std containers with threads?

I have a collection (currently an std::list<MyClass*> but it can be a std::map<int, MyClass*> also) named my_objects which contains pointers to MyClass instances.

At the moment, I process the array like this:

for(std::list<MyClass*>::iterator iterator = my_objects.begin(), end = my_objects.end(); iterator != end; ++iterator) {

    (*iterator)->someFunction();
    // ...

}

someFunction may change some of the properties of the current element, and may read some of the other elements properties. But there is no property, which is changed, and read by an another instance. So the result is the same regardless of the order of iteration.

I would like to rewrite this loop, to use four std::thread, and process the first quarter of elements with the first thread, the second quarter with the thread, etc...

Is it possible to jump inside of the collection, and start the iteration there? Is it the recommended method to process a collection like this? If not, how should this be done?

Upvotes: 0

Views: 212

Answers (3)

Sven Nilsson
Sven Nilsson

Reputation: 1879

The recommended method is to use an atomic counter to acquire unique objects for each thread to process. The thread function for each thread looks similar to this (pseudo code):

std::atomic<int> atomic_ctr(0);

void threadfunc() {
  list_iterator iter = list.begin();
  int current_list_pos=0;
  int next_pos;
  while((next_pos = atomic_ctr++) < list.size()) {
    while (current_list_pos < next_pos) {
      ++iter;
      ++current_list_pos;
    }
    iter->func();
  }
}

Upvotes: 1

Sam Varshavchik
Sam Varshavchik

Reputation: 118445

For starters, modern C++ code uses range iteration:

for (const auto &ptr:my_objects)
{
    ptr->someFunction();
}

Cleaner, less typing, avoids common iteration pitfalls.

Now, as far as partitioning a std::list, there is no std::list method that returns an initial iterator somewhere in the middle of the list. With std::vector's random access iterators this is trivial, but this is not what a std::list is for. So, if you want to change your container to a std::vector, this becomes a no-brainer.

However, it's not really hard to iterate over the entire list, but only process each nth element:

size_t p=0;

for (const auto &ptr:my_objects)
{
    if (p == 0)
        ptr->someFunction();
    p = (p+1) % 4;
}

So now, this thread invokes someFunction() for every fourth element in the list, and one-fourth of all elements in the list.

So, all that's needed here are four threads iterating here, with the only difference is that the first thread's initial value of p is set to 0, as shown; the second thread's initial value of p is set to 1; and, of course, the third and the fourth's thread initial value of p set to 2 and 3.

This will neatly divide the list into four equal parts, with list elements assigned to one of the four threads for processing.

Upvotes: 3

Daniel
Daniel

Reputation: 1447

In the simplest case, you can create a worker object (to be called inside a thread) such that you construct it with a reference to your container and additionally the range (element index or iterators) that it is supposed to change.

If there truly are no dependencies to the parts of the data that are changed by your workers, this should work, even if it is a hack.

Otherwise, you will have to create a kind of wrapper object around your container that implements a locking mechanism for reading and writing of specific elements (I would suggest boost::upgrade_lock).

Your threaded worker objects would then need to talk to this (shared) object for read and write access to your container.

Upvotes: 0

Related Questions