Am Fri, 15 Nov 2013 21:56:15 +0900 schrieb Mike Parker <aldac...@gmail.com>:
> On 11/15/2013 9:19 PM, Mikko Ronkainen wrote: > > > > If relevant, doubly-linked might work better? dcollections LinkList, or > > maybe DList? I'm asking mostly because I'd like the container to avoid > > memory allocations while in use. > > For a particle system, I would avoid lists. A list of particles needs to > be iterated every frame. A linked list is going to kill you as the > particle count increases. Since the particles will most like not be > contiguous in memory, you'll be thrashing your cache to hell and back. > > "Caches love linear access" is a quote to remember. When you need to do > frequent iteration of a list, your cache will love you if all of the > items are in a block of contiguous memory. So it's almost always better > to use an array for this sort of thing. Make your particle object a > struct and use a dynamic array of particles that you can grow as needed > or, if it makes sense, a fixed size static array. The point is that > arrays of structs will be lined up one next to the other in memory so > that you can make good use of the cache. Of course, the size of your > particle object also has a role to play here. > > Google for "linked list cache thrashing" or "cache-friendly data > structures" or some such for ideas. It is true, that these days you optimize for cache locality more than for anything else. How about this: - use an array - keep alive particles at the front and dead particles at the back - when an alive particle dies, you swap it with the last alive particle in the array and mark it as dead This way you always have a compact array from 0..aliveCount and don't need if-else to check for dead ones. (Which is otherwise another slowdown factor). -- Marco
