Jump to content
  • Advertisement
Sign in to follow this  
Damocles

[C++] using openMP 'parallel for' directive with std::list - possible?

This topic is 3496 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Simple question - can it be done? Can I have some code like:
#pragma omp parallel for
for (list<Particle*>::iterator it = particles.begin(); it!=particles.end(); ++it)
{
// blah
}
The problem is that the openMP compiler spits the dummy saying that the for loop is improperly formed. It seems omp 'parallel for' directives will only work on for loops where the conditional test is less than (<), not different to (!=). That of course is less of a problem for integer or vector based loops, but it makes it impossible to use lists (because list iterators don't have a less-than operator so you cannot compile for loops that use less-then checks on list iterators). I understand why it requires less than tests - as the parallel threads might cause the counter variable to leap past the != test. So is there any worthwhile way to use std::list with openMP for loop optimizations?

Share this post


Link to post
Share on other sites
Advertisement
Linked lists can be processed in parallel, but MP likely doesn't deal with the problem.

Also 'list<Particle*>' is redundant, it introduces double indirection. The most you would ever need is list<Particle>.

But for particles, vector<Particle> would be ideal.

Share this post


Link to post
Share on other sites
Quote:

Also 'list<Particle*>' is redundant, it introduces double indirection. The most you would ever need is list<Particle>.

But for particles, vector<Particle> would be ideal


But if I used list<Particle> then every time I added a particle to the list, it would be copying the entire contents of the particle class each time. The whole reason I used list in the first place is for fast insertion/removal. By using Particle* I am adding another layer of indirection, but I'm removing the copy time for insertion/deletion. Using vector<particle> would be even worse, as removing a particle from early in the list would cause a huge amount of copying.

Unless I've misunderstood what you mean?

Share this post


Link to post
Share on other sites
Quote:
Original post by Damocles
But if I used list<Particle> then every time I added a particle to the list, it would be copying the entire contents of the particle class each time. The whole reason I used list in the first place is for fast insertion/removal. By using Particle* I am adding another layer of indirection, but I'm removing the copy time for insertion/deletion. Using vector<particle> would be even worse, as removing a particle from early in the list would cause a huge amount of copying.


The whole point of particle classes is that they're supposed to be fairly cheap to copy. It actually takes a fairly large structure for that copy overhead to become important, since handling list nodes takes a fair number of operations anyway, and because using the vector improves cache coherency.

I couldn't give you exact numbers, though. Profile and see.

Algorithmically speaking, yes, it's a bad idea to remove single elements from the middle (in general; from near the beginning in particular) of a std::vector. However, if you are removing several elements at once (which I would expect to the be the case for a particle system), the process can be optimized using std::remove_if() (which is O(size of container) regardless of how many elements are removed). If you don't care about the order of container contents (which may well also be the case, although some particles do care about drawing order), it may be optimized even more with std::partition().

Regardless, if you decide you want that level of indirection, don't manage it yourself; use one of the boost ptr_containers. I believe (haven't checked) that boost::ptr_list in particular is optimized to avoid the double indirection.

Share this post


Link to post
Share on other sites
Quote:
Original post by Damocles
Quote:

Also 'list<Particle*>' is redundant, it introduces double indirection. The most you would ever need is list<Particle>.

But for particles, vector<Particle> would be ideal


But if I used list<Particle> then every time I added a particle to the list, it would be copying the entire contents of the particle class each time. The whole reason I used list in the first place is for fast insertion/removal. By using Particle* I am adding another layer of indirection, but I'm removing the copy time for insertion/deletion.

Are you also considering the issues with allocating the particles; both your copy of the particle itself, and the node the list makes? If the cost of allocating the particle exceeds the cost of copying it, it will be more efficient to store it by value.
Quote:
Original post by Damocles
Using vector<particle> would be even worse, as removing a particle from early in the list would cause a huge amount of copying.

Unless I've misunderstood what you mean?

If you swap the particle to be removed with the last in the list, actually removing it from the list is as simple as removing the last element. Also, once the vector has grown to accommodate all particles, there will be no dynamic allocations anymore, where the linked list has to allocate and release the nodes as you insert and remove them.

Share this post


Link to post
Share on other sites
I'll have to profile it and see which system will work best for my setup. The main reason for choosing list over vector is because my particle classes are quite large (relatively speaking) with a fair bit of data in each. So I store pointers to the particles, not the particle class itself.

I'm not sure that swapping the vector positions so the particle is at the end then popping back would be faster than simply removing a node in an std::list. That is of course when the list is just pointers - it would be plenty faster if it was allocating all the data in the particle.

As for allocation - I use a memory pool of particles to avoid having to create particles at run time. As such, I assumed it would be best to simply store the pointer to each particle in the list, rather than copy the particle data into a vector node for each new particle.

Share this post


Link to post
Share on other sites
position (3 floats), rotation (3 floats), scale (2 floats), animation info (2 floats), movement info (6 floats), age info (2 floats), type/texture info (4 ints).

It's a general purpose particle class so that I can easily add new particle types without having to make lots of extra code. The downside is of course that it's pretty big for a particle class.

Share this post


Link to post
Share on other sites
Quote:
I'm not sure that swapping the vector positions so the particle is at the end then popping back would be faster than simply removing a node in an std::list. That is of course when the list is just pointers - it would be plenty faster if it was allocating all the data in the particle.

The speed gain of the vector has nothing to do with that.
It's that it is contiguous memory.

And by the way, a container of pointers is *always* wrong, period.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!