recycling particles

[jerome]

Hi,

 

I just start learning about particles, reading the wiki, all your posts and funky demos, guys, and the doc/code.

As I can see in many playground demos that people overwrite for their own needs the Emitter.updateFunction(), I dig a little in the TS genuine code (though I'm not a TS coder, it is very readable)

 

https://github.com/BabylonJS/Babylon.js/blob/master/Babylon/Particles/babylon.particleSystem.ts#L138

 

L138 : recycling

The particle age is its recycling criterium.

So the recycled particles are removed from the particles array and added to the stock array for later use (re-emission, etc).

 

To remove a particle from the particles array, the javascript (unless it is overwritten in typescript) splice() function is used.

 

As far as I know, this function returns a new js array.

 

So this means, the GC will be called to free the former array allocated memory. 

We can think this little detail is not that important.. but we are here within an updateFunction() intended to be called each frame, maybe for each particle, aren't we ?

Maybe on powerful computers, we'll even never notice this GC behavior.

 

I know (for having read much about this topic) that in 2D html5 games, spliced array (and other js functions which dynamically create new objects) are avoided as much as possible in the render loop.

 

A workaround could be to sort() the particles array and then have for example living particles from 0 to deathIndex-1 and dead particles from deadIndex to particles.length with this deathIndex managed in the Emitter.

The sort() function returns the same array ... sorted. No memory free/allocation, so no GC calls.

I don't know if sorting a almost pre-sorted big array is quicker (*) than a GC call therefore. And sorting not scalar type objects with sort() is not that easy in javascript either.

 

Or manually to sort the array by setting living and dead particles at choosen indexes (see next post)

 

Or maybe to have a new array object with a new splice()-like method as the DK's new array-object used for matrices computation.

Such an object could then be used anywhere else in the code so the memory allocation would be thus mastered everywhere in BJS (concerning js arrays at least).

 

I understand it is a deep re-implementation and seems quite expensive regarding the expected benefit.

 

So... I don't know

 

(was just my humble indecisive opinion so far)

 

 

(*) : the real question is not about the speed but about the predictibily :

if you consume, say, 2 micro-seconds each frame to sort your array (or do something smarter), you master how and when it happens

if you rely only on the GC, it can trigger whenever it "wants" and can use as much time as it needs 

[jerome]

here's an old article about a recycling particle system with no array.splice() call : http://buildnewgames.com/particle-systems/

 

please go down right to the  "How the Particle Pool Works" part to read a better explanation than mine.

 

I personaly like this implementation : simple, light and kiss

[GameMonetize]

Hum that's interesting...we need to do more testing but definitely I add that to my backlog (unless you want to experiment it and propose a PR?)

[jerome]

added to my backlog : learn quickly some TS and how to PR  ... so I'll be able to propose all this stuff by myself instead of writting endless posts

[GameMonetize]

I did a small test that seems to work well:

                    if (particle.age >= particle.lifeTime) { // Recycle by swapping with last particle                        var lastParticle = particles.pop();                        if (lastParticle !== particle) {                            lastParticle.copyTo(particle);                            this._stockParticles.push(lastParticle);                        }                        index--;                        continue;                    }

[jerome]

This looks very smart !

 

I guess what you intend to to though I don't understand everything as I didn't even know this copyTo() method..!

 

 pop() doesn't create any new array what is a good thing, but only changes the array length. I guess the initial allocated memory isn't removed by the GC as the array reference  is unchanged and as the array may still grow back again later. Not sure.

 

When you push() new particles into the array somewhere else, some new memory will be allocated : a push doesn't reuse array "free" indexes like empty or null positions, even at the start of the array : [null, null, "toto", null].push("titi") => [null, null, "toto", null, "titi"]

 

So I think, not sure as I'm not a js expert, the object array will keep a more or less fixed size as it will vary between empty and initial array length but the underlying allocated memory could grow with no limit...

 

depending on the pop() behavior :

if pop() doesn't free the array memory for further uses, the allocated memory will grow every push() call,

if pop() removes the pop-element memory, we face the GC problem again.

 

Am I wrong ?

In my humble indecisive opinion, an array with an at once fixed length would be more convinient regarding to GC concerns.

 

Does copyTo() allocate new memory ?

 

I need some time to make tests in the playground with big amount of short live particles (to force push/pop) on an old computer so the GC will be significant against the animation.

[GameMonetize]

copyTo does not allocate new memory and just do a copy on a per property basis

 

I did test about GC with pop() and GC is not triggered at all so I'm assuming browsers are smart enough to reuse memory

 

The problem with particleSystem is that active particles count can vary a lot and having a fixed sized array would not be really useful as we may have to grow it frequently. Obviously we can create a big one once and for all but this will lead to the following problem:

- Memory waste (mainly on low end devices / phones)

- A lot of copy between memory where pop and push are heavily optimized by browsers

 

But obviously if you want to give a try a find a better way, I will be more than happy to integrate your change

[jerome]

Oki, I'll check for a elegant way to do it... if I succeed :-q

 

Yours, with pop() and no splice(), is really really smart (*) and involves only a minor change in the BJS code.

So it seems to be so far the very best way 

 

The case with so many short living particles increasing the memory consumption to a significant point (or triggering too much the GC) is maybe purely hypothetical as many other allocation or computation problems should occur before in the code considering the JS VM capacities.

So, ok, I stop splitting hairs 

 

In other terms, once we get rid of the splice() method or other new object creation methods within the render loop, the job is done !

 

A general good practice would be to pre-allocate or create everything whatever the level of abstraction/representation, low or high, (pooling all that stuff if needed) before entering the render loop.

 

 

 

 

(*) my humble decided opinion, this time.

[jerome]

mmmhh...

I thought back to your solution.

I think I am wrong about the risk of infinite memory allocation upon push() calls : 

 

if the pop() doesn't trigger the GC, as it seems to do, this means the array memory is kept allocated for further use, despite the array js object length  property decreases.

the push() would so be considered as that "further use" as it will increase back the array length. I guess the js array implementation is smart enough to re-use the previously allocated memory if present, before allocating new blocks.

 

So your pop()/push() ( or no-splice() ) solution seems to be really the very right one with no-fixed length arrays !

 

 

The one I was thinking about was like this of the link article : a single fixed length array with as well living and dead particles. But it had the disadvantages of the fixed size array and needed a complete re-implementation of BJS particle life management.

So let's forget it.

[fenomas]

Hi,

 

Just chiming in to say that DK's proposed "push/pop" change should definitely be made!

 

I noticed that "splice" in ParticleSystem and came here to suggest it. 

 

FYI Jerome: the problem with splice() is not memory, but performance - when you remove an item from the middle of the array, all subsequent items have to move up a spot. So the larger the array is, the longer it takes to splice a value.

[jerome]

You are right...

but both, my captain !

splice() instantiate a new object also : the spliced element array. Even if you don't use it.

So the GC needs then to free this allocated unused memory.

It usually don't matter... except in a 60 fps loop

[fenomas]

Sure in principle, but O(1) << O(n). Creating an array that will immediately get destroyed isn't free, but it's so cheap that it could be justified by cleaner code, etc. But calling splice even once can be expensive, if the array is large.

 

More importantly, I've just realized that the "pop/push" fix is already done! I bumped this thread thinking it was not implemented yet - I must have been looking at an old version. Sorry about that, nothing to see here...