#pragma omp parallel for
for (list<Particle*>::iterator it = particles.begin(); it!=particles.end(); ++it)
{
// blah
}
[C++] using openMP 'parallel for' directive with std::list - possible?
Author
Simple question - can it be done? Can I have some code like:
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.
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.
Author
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?
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.
Quote:Original post by DamoclesQuote:
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.
Author
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.
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.
Author
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
