Virtual iterators with parallel_for

[Alex_N_Intel]

Hi,

I'm trying to deploy multi-threading in a very large and mature software (~12 years old). The code is written in object oriented manner and the algorithms to be parallelized all use virtual iterators defined within the tool. Different implementations of some pure-virtual interface can use vectors, lists, hash-sets. All of them return virtual iterator with interface something like this:

template

class iterator

{

public:

virtual void first() = 0;

virtual void next() = 0;

virtual bool is_done() = 0;

virtual R current() = 0;

}

Implementation example:

template

class std_vector_iterator : public iterators

{

public:

void first() {m_curr_iter = m_container->begin();}

void next() { ++m_curr_iter;}

void end() { m_curr_iter = m_container ->end();}

bool is_done() const {return (m_curr_iter == m_container ->end());}

private:

std::vector* m_container;

}

The implementation inside uses STL iterators of different kinds.

Now, TBB interfaces don't accept those iterators, so I need to adjust the interfaces. I would also like the solution to benefit from the random-access property in case the iterators work on vector.

In high-level I see several options:

1. Copying the data into local vector before parallel work (trivial, but the size could be millions).

2. Writing a wrapper on top of the virtual iterators to comply with regular iterators interface (random access is out of the picture and scalability is damaged).

3. Adding virtual foreach function to the iterators and do the actual loop on the internal container (very complex code, and Im limited to expand the interface but not change them due to backward compatibility).

I suspect this problem is general for many legacy tools that try to use TBB. Is there any known BKM-s on this issue?

Regards,

Alex Nikonov

[Alexey-Kukanov]

Your virtual iterator interface is essentially a forward iterator. Unless you extend it somehow, you cannot benefit from random access to the underlying vector.

For #2, an STL-compliant wrapper would give you the ability to use the interface with parallel_do, but not parallel_for. You may build a range class to use with parallel_for, but due to lack of random access, it would be inefficient (possibly worse than parallel_do).

#3 seems to me a good, if not best, solution. It can use parallel_for with vectors and dequeusand parallel_do with containers that do not have random access. Given your implementation example, I do not see why it would require complex code, but of course I may not know all the details.