Friday, May 21, 2010

Stardust v1.1 with Fast Array Splicing



Stardust project homepage

The initial release of Stardust Particle Engine version 1.1 is now available (yep, no more betas). The major difference of the current revision from the previous one is the use of fast-splicing arrays (I made up this name, because I don't know if there's a formal or correct name for it).

Before Stardust employs linked-lists as default internal particle collections, ordinary arrays are used. Arrays are known to be fast to traverse and sort; however, arrays are also notoriously known to be ultra-slow when it comes to splicing large arrays. This is why I switched to linked-lists, which can perform much faster splicing operations by simple node-link manipulation.

I've come back to arrays and use a new method to perform splicing, and this turns the tables again. Now Stardust uses fast-splicing arrays as internal particle collections.

So, what are fast-splicing arrays anyway? Well, they're are no different from ordinary arrays except that they perform splicing quite differently. As any programmer familiar with ordinary array splicing knows, ordinary splicing first creates a new array of the size one-cell-smaller than the original one, and then copies the original elements, except for the spliced out one, into the new array. This is very CPU-consuming when dealing with large arrays, since a new large array is created every time a large array is to be spliced, not to mention the fact that rapid splicing is a fundamental nature of particle engines.

The figure below illustrates the splicing process for ordinary arrays.



Fast-splicing arrays do the job differently. Each of them always keeps the last cell empty, to allow iterators to tell whether they have reached the "tail" of the array, and it double its size when the last empty cell is to be used. Also, each array keeps track of the index of the last occupied cell. When a particle is to be removed from a cell, the last particle is then moved to the now-empty cell, and then the index indicator is decremented, i.e. moved left. No new arrays are ever created for splicing.

The order of the array has been disrupted you say? As long as no mutual action is in place, the order of the array is of no significance. Even if mutual actions are involved, requiring the particles to be sorted according to their x-coordinates, the emitter sorts the array automatically before further processing in this case, so the order is still not problem.



This splicing approach is even faster than linked-list splicing, since it only involves two assignment operations and one integer decrement operation, as opposed to four assignment operations for linked-lists (or maybe more...argh, you do the math).

Moreover, arrays are faster for adding particles, because they simply assign references to their cells, and, on the other hand, linked-lists have to create new nodes to hold references to particles added and subsequent nodes.

I think I don't have to say anything more about the sorting operations. Arrays are the fastest, 'nuff said.

Here's a table that compares the performance of particle adding, traversal, splicing, and sorting operations for different particle containers. I believe that you can clearly understand why I prefer fast-splicing arrays over linked-lists.

3 comments:

katopz@sleepydesign.com said...

may i've live demo up and running for this test please? yeah, you know me kinda lazy to create one ;)

CJ Cat said...

The performance test demo is included in the "test" folder in the SVN trunk.

katopz@sleepydesign.com said...

nice! thx! :D