I have a 2d particle system which uses Allegro that works fine and does everything its supposed to, except I really can't have more than 1000 or so particles going at once, or else it begins to lag. I'm not really sure what the limit usually is for a 2d particle system, but 1000 seems kind of low. It might be how I'm storing the particles or something. It's the first particle system I've tried, so I might have made some stupid mistakes.

This could be for a number of reasons, but I can undoubtedly tell you it's something in the way you're updating or rendering your particles and not anything to do with Allegro (not that you implied that, just wanted to be clear).

How are you representing your particles in code? How do you update them? How do you render them? Posting some code here would help us determine what the probable bottlenecks are.

Here is the struct which represents a particle.

typedef struct{	//starting location	int xStart, yStart;	//location	int x, y;	//size	int width, height;	//starting x and y velocity	int startXVel, startYVel;	//x and y velocity	int xVel, yVel;	//how many ticks it will last	int lifespan;	//how many ticks have past since it was made	int age;	//color	int r, g, b;}Particle;

The particles are stored in a map like this.

map<int, Particle *> particles;

Here is part of the update function that updates and draws the particles.

for(int n = 0; n <= partAmount; n++){	//if the delay was reached, update the particle system	if(ticksTilUpdate <= 0)	{		particles[n]->x += particles[n]->xVel;		particles[n]->y += particles[n]->yVel;		particles[n]->xVel += gravityStrengthX;		particles[n]->yVel += gravityStrengthY;		particles[n]->age++;		//if the particle has reached its lifespan, reset it		if(particles[n]->age >= particles[n]->lifespan)		{			particles[n]->x = particles[n]->xStart;			particles[n]->y = particles[n]->yStart;			particles[n]->xVel = particles[n]->startXVel;			particles[n]->yVel = particles[n]->startYVel;			particles[n]->age = 0;		}		ticksTilUpdate == delay;	}	else {ticksTilUpdate--; maxLives--;}        if(partType == TYPE_IMAGE)		draw_sprite(CALGraphicsDriver::GetInst()->GetBufferBitmap(), partImage->GetData(), particles[n]->x, particles[n]->y);	if(partType == TYPE_CIRCLE)		circlefill(CALGraphicsDriver::GetInst()->GetBufferBitmap(), particles[n]->x, particles[n]->y, particles[n]->width/2,                 makecol(particles[n]->r, particles[n]->g, particles[n]->b));	if(partType == TYPE_RECT)		rectfill(CALGraphicsDriver::GetInst()->GetBufferBitmap(), particles[n]->x, particles[n]->y, particles[n]->x + particles[n]->width, 				particles[n]->y + particles[n]->height, makecol(particles[n]->r, particles[n]->g, particles[n]->b));	if(partType == TYPE_LINE)	         line(CALGraphicsDriver::GetInst()->GetBufferBitmap(), particles[n]->x, particles[n]->y, particles[n]->x + particles[n]->startXVel, 				particles[n]->y + particles[n]->startYVel, makecol(particles[n]->r, particles[n]->g, particles[n]->b));	if(partType == TYPE_PIXEL)		putpixel(CALGraphicsDriver::GetInst()->GetBufferBitmap(), particles[n]->x, particles[n]->y, makecol(particles[n]->r, particles[n]->g, particles[n]->b));

(Sorry that drawing code is kind of a mess, it didn't paste quite right)

The CALGraphicsDriver::GetInst()->GetBufferBitmap() part is just part of the graphics wrapper.

OK, first of all I think storing your particles in a map could be introducing some overhead. I think either a linked list or a vector is going to give better performance when iterating over large data sets (although I haven't actually benchmarked to see if this is true). Why, exactly, are you using a map to store the particles?

Secondly, it looks like you have a lot of redundant code in the for loop that could be causing a slow down.

For example:

CALGraphicsDriver::GetInst()->GetBufferBitmap() and partImage->GetData()

are called every time you go through the for loop. If you have a 1000 particles, that's 2000 unnecessary function calls. Why don't you simply call these functions once, outside of the for loop, and store them in variables that can be passed to the functions down below.

Also, I'm not sure if the methods you're calling from Allegro are really meant to be used in this way (I actually have no idea, just pointing it out as a possibility even though I already told you Allegro wouldn't be the problem :D, if someone who knows the Allegro API better then I could clear this up that would be great).

You're also doing a fair amount of if checks in the for loop which could lead to a high amount of branch mis-prediction, i.e. highly unoptimized machine code being generated by your compiler.

The main things I would work on however are making sure you only call GetBufferBitmap() and partImage->GetData() once, outside of the for loop and think about changing from using a map over to a linked list or vector.

The problem is your map. If you insist on using a map and not a vector or deque (which are what you should probably be using), don't iterate through it like that. Instead do:



That way, you aren't doing an O(log n) lookup each iteration, instead you're just doing an O(1) increment, which should really help your performance.

In all actuality though, std::vector or std::dequeu is the way to go, especially since your indices are from 0 to n.

i think map is usually for things that dont get created and deleted that often... because it has a lot of overhead in allocated memory...

using a vector, and maybe along with the Boost Memory Pool Allocator will speed up your process...

also, your code is really inefficient, so many repetitions... try to avoid the repetition, then your code will run a lot smoother i think :)

Thanks for the help. I did think of using an iterator for the loop, but never changed for some reason. I'll try to take out all the unecessary stuff. Also Morpheus011, you said "You're also doing a fair amount of if checks in the for loop which could lead to a high amount of branch mis-prediction", but don't those if checks have to be in the loop?

Thanks for the help. I did think of using an iterator for the loop, but never changed for some reason. I'll try to take out all the unecessary stuff. Also Morpheus011, you said "You're also doing a fair amount of if checks in the for loop which could lead to a high amount of branch mis-prediction", but don't those if checks have to be in the loop?

Quote:Original post by Grant1219
Thanks for the help. I did think of using an iterator for the loop, but never changed for some reason. I'll try to take out all the unecessary stuff. Also Morpheus011, you said "You're also doing a fair amount of if checks in the for loop which could lead to a high amount of branch mis-prediction", but don't those if checks have to be in the loop?

Tickstillupdate really looks like it shoudl be done Outside the particle iterator loop. Or is there a reason that ticks are updated once per particle as opposed to once per game cycle?