traverse stl containers in parallel

General OpenMP discussion

traverse stl containers in parallel

Postby holomorph » Mon Apr 21, 2008 5:06 am

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
holomorph
 

Re: traverse stl containers in parallel

Postby ejd » Mon Apr 21, 2008 5:21 am

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.
ejd
 
Posts: 1025
Joined: Wed Jan 16, 2008 7:21 am

Re: traverse stl containers in parallel

Postby holomorph » Mon Apr 21, 2008 5:55 am

ejd wrote: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.
holomorph
 

Re: traverse stl containers in parallel

Postby ejd » Mon Apr 21, 2008 7:03 am

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.
ejd
 
Posts: 1025
Joined: Wed Jan 16, 2008 7:21 am

Re: traverse stl containers in parallel

Postby holomorph » Mon Apr 21, 2008 7:41 am

ejd wrote: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
holomorph
 

Re: traverse stl containers in parallel

Postby ejd » Mon Apr 21, 2008 8:26 am

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.
ejd
 
Posts: 1025
Joined: Wed Jan 16, 2008 7:21 am

Re: traverse stl containers in parallel

Postby holomorph » Mon Apr 21, 2008 11:26 pm

ejd wrote: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
 

Re: traverse stl containers in parallel

Postby holomorph » Sat Aug 16, 2008 10:59 pm

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.
holomorph
 


Return to Using OpenMP

Who is online

Users browsing this forum: Yahoo [Bot] and 7 guests

cron