parallel_for Iteration over STL Containers

[AJ13]

If I only want read-only access to members, is it possible to simply iterate over an STL container, say std::set, using parallel_for ? Would I have to write wrapper functions to permit this? Could someone provide a short snippet of how it could be done?

Thanks,

AJ

[Alexey-Kukanov]

parallel_for utilizes the idea of recursive splitting the overall iteration space in half. Thus, random access iterators (e.g. std::vector::iterator) could be efficiently used with parallel_for via blocked_range:

// assuming all necessary TBB headers are included
typedef std::vector MyVector;
class MyParallelForBody {
    // class definition here
};
MyVector vec(1024);

// assuming function scope
tbb::parallel_for(
    tbb::blocked_range<:ITERATOR>(vec.begin(), vec.end()),
    MyParallelForBody(), tbb::auto_partitioner() );

Ageneral forward iterator can be inherently serial, like in lists: one can not access an element in the middle until all previous elements are traversed. TBB's blocked range will not work with such an iterator. A custom version of Range for parallel_for is possible, but hardly ever can be efficient. You might find parallel_while suiting your needs, especially if the time of processing greatly exceeds iteration overhead. You would need to write a wrapper putting the[ begin(), end() ) iteration space into a Stream interface required by parallel_while; it could look like this:

class Stream {
    typedef std::list MyList;
    MyList::iterator my_iter;
    const MyList& my_list;
public:
    Stream( const MyList& _list )
    : my_list(_list), my_iter(_list.begin()) {}
    bool pop_if_present( MyObject& item ) {
        bool result = (it!=my_list.end());
        if( result ){
            item = *my_iter;
            my_iter++;
        }
        return result;
    }
}

[AJ13]

Okay, we talked about read-only access (I think, unless the previous post applied to write access to), and now some time later I have to ask about write access only to an std::vector. Although, maybe some specifics on other containers would help (since the thread topic is for STL containers).

It was suggested to me that iterating over a std::vector with parallel_for might be problematic, in the case that the std::vector changes size (the memory location of the whole vector may change).

So, if I know that my vector will not change size during iteration, is it safe with an std::vector to write to different elements concurrently? Basically, suppose I have a recusive algorithm using parallel_for, and I want to use std::vector. I know that the ranges will not overlap, so is it possible to just change entries directly using references to the single vector in memory?

I know that concurrent_vector will solve these problems, and I'm going to look at it in more detail. However, I'm attempting to use STL containers where possible since they will be more efficient. The trick is, knowing what container can be used where safely.


Thanks,

AJ Guillon

[Anton_M_Intel]

Sure, you can write std::vector unless it changes size concurrently with the parallel_for call.

Likewise std::vector, the tbb::concurrent_vector doesn't actuallyprovide per-item locking mechanism yet (like tbb::concurrent_hash_map do). It is user responsibility to use vector's items without data-races. Instead, the concurrent_vector provides ability to grow concurrently.