Tuesday, September 1, 2009

Linked List Failure for Stardust

Stardust project homepage

This is my second attempt to try using a linked list for particle engine. The first attempt was for Emitter, and this time it's for Stardust.

Theoretically, a liked list data structure is the best choice for a particle engine. Linked lists are well-known for their efficient removal of arbitrary nodes from the list. There's no way knowing the dying order of particles in a particle list, hence no way knowing the order of particle removal from the list. It seems that using a linked list for a particle engine's particle list is a good idea, but after my experiments, it turned out not to be the case.

I've tried to use a linked list for Stardust's particle list, and then recompile some of my existing examples. The result showed that the performance didn't improve; actually, it's quite the opposite: the CPU consumption got even higher (approximately 5% higher than the original).

I'm pretty sure when the number of particles is large enough, linked lists shall yield far better performance than arrays, but for common particle effects and daily uses, the number is simply not that large, thus the result. I got the exact same result from the attempt to use linked lists for Emitter.

The original array version of Stardust makes use of object pools to improve performance; however, I encountered some difficulty in implementing object pools for the linked list version (yeah, I'm just an amateur programmer). I think the performance gained by using object pools compensate for not using linked lists. I'll just stick with arrays for Stardust, unless I somehow get motivated to make my third attempt to try linked lists for particle engines (this really is time-consuming).

If you are interested, I've saved a copy of the linked list version in the SVN repository. Click here to download the RAR archive.


noebef said...

Do you use regular Arrays oder Vectors? The vectors should boost the performance pretty much.

CJ Cat said...

Yes, I know. But I decided to make Stardust available to both Flash CS3 and CS4. That's why I used arrays instead of vectors.

Also, a friend of mine made a test on vectors, and the result showed that vector's performance advantage is only present when the element type is of "small" classes, such as the Number class. Using a vector typed to "large" classes like DisplayObject3D in Papervision3D, however, actually yields a worse performance than using arrays.