traverse stl containers in parallel

[holomorph]

Hello OpenMP-Users!

I am trying to parallelize an existing seriell programm with openmp. Thereby I encountered a severe problem while traversing stl-containers.
Following example seems to slow down my code heavily, when executed within a parallel region.

for (iter = vector.begin(); iter!=vector.end();iter++)
{
iter->doanything(...);
}

If I use random access on the vector instead I do not have these problems.

for (int iter = 0; iter < vector.size(); iter++)
{
vector[iter].doanything(...);
}

It seems like in the first variant is only executed serially, reaping all the benefits of parallel execution. But i cannot imagine why ?
And is there any way to circumvent this problem without having to change all the iterator-loops within my serial program?

Thanks for your help,
Christian

[ejd]

You need to give me a little more information on what compiler you are using and how exactly you are running this loop. From what you have shown below it is hard to say much. The one thing that I will note, is that in the second loop you have declared iter and so it is private, while in the first loop iter is declared elsewhere and may be private or shared. This could make a big difference.

[holomorph]

You need to give me a little more information on what compiler you are using and how exactly you are running this loop. From what you have shown below it is hard to say much. The one thing that I will note, is that in the second loop you have declared iter and so it is private, while in the first loop iter is declared elsewhere and may be private or shared. This could make a big difference.

Yes, thats right.

- I am using microsoft visual c++ (2005) on windows

- I will explain in more detail the way i run this loop. I tested following two loops on a quadro core intel machine. The first loop has a speedup of nearly 4, as expected, whereas the second loop executes more than 10 times slower(!) than the serial code.


1.) this works fine!

vector< double > vec;
for (int k=0;k<100000;k++)
vec.push_back(0.0);

#pragma omp parallel for
for (int i=0; i<4; i++)
{
for (int index=0;index<vec.size();index++)
{
//do ntothing
}
}


2.) this is very slow!

vector< double > vec;
for (int k=0;k<100000;k++)
vec.push_back(0.0);

#pragma omp parallel for
for (int i=0; i<4; i++)
{
vector< double >::const_iterator iter;
for (iter=vec.begin();iter!=vec.end();iter++)
{
//do nothing
}
}

So, the vector is shared, while the index-variable or the iterator are private to each thread. I do not even have to access the iterator, like iter->..., as i have implied in my previous post. It is enough to just traverse the container.

[ejd]

Your code looks reasonable and I tried it using a couple of compilers others than Microsoft and architectures other than Intel. I don't see the large variation you are describing. Unfortunately I don't have any idea why the Microsoft compiler/runtime would have this problem. Maybe someone else reading this might have an idea. The only other thing that I can suggest, is that you ask this question on one of Microsoft's forums.

[holomorph]

Your code looks reasonable and I tried it using a couple of compilers others than Microsoft and architectures other than Intel. I don't see the large variation you are describing.

Thanks for your help and thanks for that information. I will try if this problem still exists when using an intel compiler. Perhaps, if not, i will consider using this compiler instead of microsoft`s.

I would be glad if someone could confirm my problems? It seems strange to me that I cannot find any ressources to this topic, since this should be a common problem for all Visual Studio users runnning code in parallel.

Best wishes,
Christian

[ejd]

I just tried it using an Intel compiler and an Intel 2 chip (not 2 core) system and I don't see the variation you described there either. Unfortunately I don't have access to a Microsoft compiler or a quad-core Intel chip at this time to try it on those. Good luck in finding out more info and if you do, please feel free to post it here so the rest of us will know.

[holomorph]

I just tried it using an Intel compiler and an Intel 2 chip (not 2 core) system and I don't see the variation you described there either.

Hm, this is very strange. I couldn't find a solution but i verified that the same problem also exists using the intel c++ compiler. So, it seems not to be only a problem with microsofts implementations.

[holomorph]

Hello again,
i just wanted to state that the problem actually does not really exist. The slowdown was caused by wrong compiler settings, which should only be sensible for debug-mode. With common compiler settings the speedup is as expected, although i am still surprised that traversing a stl container with bi-directional iterators is much slower than using random access iterators [..]. But there is no problem with multithreading.