Optimal Immutable Data Structure for Highly Dynamic Particle System

Question

Trying to see if immutability is a good fit for highly dynamic objects like game entities (that constantly are moving around and changing) or particle systems, each which might have thousands or millions of objects moving around. Wondering if it's even theoretically possible.

I would like to know how to create a high performance immutable data structure for this scenario.

Typically you have a mutable array that you might push to the GPU to do parallel operations on it to get max performance. I'm wondering though if there are any functional / persistent data storage / immutable solutions to this problem that have the same or close to the same performance.

Specifically, it seems like with an immutable solution, you would run out of memory fast by constantly appending to the immutable data structure. Seems like you would have to limit the amount of history/versioning on the data structure, which means only limited immutability. Second, it seems like the overhead of creating these new objects would be too much, though perhaps there is a low-level data structure with pointers or something that you could use that would make this negligible.

Answer 1

Immutable data structures are best suited for systems where

• the majority of data managed by an application stays unchanged (or can be modeled in a way so it stays unchanged)

• the changes to the data can be applied or modeled as a sequence of small differences to the previous states

I did not implement a dynamic particle system by myself in the past, but from what I know about these systems is: they don't fit into that category. In a particle system, the vast amount of data like the particle positions or velocity is fully changed from one iteration in the main loop to the next.

Using some "immutable array" for representing the particle states and using a GPU to process it would only lead to a solution where this operation is not applied "in place", but the result is created as new array. When the next step is to throw away the original array from the former processing cycle, there will be no benefit from immutability - doing such an operation in-place will be at least as fast and at least twice as memory efficient than using an intermediate result array.

Answer 2

Here's some immutable data that is constantly moving around.

Ryu always did know how to follow through. As you can see here, just because the data is immutable doesn't mean nothing at all changes.

Specifically, it seems like with an immutable solution, you would run out of memory fast by constantly appending to the immutable data structure. Seems like you would have to limit the amount of history/versioning on the data structure, which means only limited immutability.

That's a resource concern which for the most part can be abstracted away. You can record every request to change state immutably and make state into something you calculate by replaying all of those state change requests. If doing that compactly isn't enough you can always record state at certain points and push previous requests off to long term storage. How often is a tuning variable. Oh and you can record those states, immutably.

Second, it seems like the overhead of creating these new objects would be too much, though perhaps there is a low-level data structure with pointers or something that you could use that would make this negligible.

This is fine as long as your constructors don't do silly things. Stick to validating and setting attributes. That way the cost of creating new objects will be no more then that with a little pointer addition thrown in. Never optimize based on what something "seems like". Test and be sure.

Answer 3

Actually, I think that GPU processing already is example of immutable particle simulation.

This is because in GPU, the data that you put in, in form of texture, is not changed, but new data, in form of texture, is output. One texture is read-only, while second is write-only. And once the output texture is written, it is not changed. At the same, after reading is finished, the read-only texture becomes obsolete and can be re-used.

So next step, texture that was created is used as input and texture that was read from is used for output.

But this really only works if every reference to the particles is switched to the new version. But I don't see reason why any code would keep reference to obsolete data. So the key point here is to make sure every reference gets updated to new version and memory reuse becomes possible and efficient.

Answer 4

One of the challenges of particle systems even for mutable data structures, especially ones where there is no foreseeable upper bound to the number of particles, is that they have the tricky requirement of often being very performance-critical for sequential access (which often implies some memory contiguity and practically requires it to some degree if GPU is involved) while simultaneously wanting to remove from middle of the container as well as insert to it repeatedly as particles are born and die.

One of the common solutions I see to this problem in my industry to get some contiguity and still maintain constant-time insertions and removals when index invalidation would be a PITA is to use the analogical equivalent of a free list. Store the particles in contiguous blocks with, say, memory allocated for 64+ particles in a block. If a memory chunk for a particle is unused, treat it as a list node and push it to the top of a stack (which just involves manipulating some pointers). When inserting, pop a free node from the stack and utilize the pointer to that as memory for the particle (if the stack is empty, allocate a new block to store 64+ more particles and push those chunks to the free stack). When removing/freeing a particle, treat the pointer to it as a free node and push it to the stack. That's the basic concept and you can get more elaborate than this and free the blocks when empty and so forth.

If you get to this point, it's actually not so much more work to turn this into a persistent data structure utilizing garbage collection or ref counting with something like shared pointer or reference to shallow copy blocks, like so:

And I actually tried this for a particle system to compare performance using a PDS representation with 4 million particles (though the GIF looks like crap and doesn't communicate the original FPS whatsoever):

And what I found was that with my original mutable structure where I was mutating that structure directly, I got around 300 FPS. With my PDS version which outputted a whole new instance of the structure with each frame, the frame rates dropped to 120 FPS.

However, keep in mind that simulation is uber simple. It's doing trivial work to rasterize the particles in CPU and the force applied on them is a dirt simple sort of "follow the mouse click" thing. So I was mostly just stress testing the differences between mutating an existing data structure and outputting a brand new version each frame, and 40% of the original FPS isn't as bad as it sounds. The proportional differences between the two would shrink considerably if my particle simulation was considerably more complicated with, say, particle collision detection.

So I've actually found it quite reasonable as far as performance with the best PDS implementation I could come up with, which wasn't even optimized that much. I'm not sure what features I could get out of this being an immutable PDS and haven't applied it in production (though I do use a PDS now for meshes with tremendous benefits). Originally I just tried using particles as a stress test for this kind of chunky, ref-counting block idea to see if I could apply it in other places than particle*.

I didn't actually intend to use the data structure with particles so much as just enjoying benchmarking data structures of this sort with a simple particle sim. It's some weird old habit I have because I like to get a sense of performance more in terms of "frame rates" in some context than just like how much time it takes to do N insertions to a data structure which isn't quite as clear to me about its impact on FPS when applied in a bigger picture. It's also my personal defensive measure not to get too tunnel-visioned optimizing the structure outside of something at least slightly more resembling a real-world application.

Most people focus on the benefits of immutability in terms of reasoning about correctness and thread safety which I did get to some degree, but in my case a lot of the enormous practical benefits I found more immediately with immutability, and specifically persistent data structures, is how cheap they are to copy around and create modified copies. That makes undoing and exception-safety and non-destructive editing and things of this sort trivial to implement, since I can just cheaply copy the old version and create a new modified copy with only the relevant parts that changed requiring a deep copy and then swap it back with the old version on anything resembling an undo/rollback/non-destructive reevaluation.

The difficulty with particles given that highly dynamic nature is that probably every single particle in the data structure would want to be touched every frame, and so we might still end up deep copying the entire thing every frame either way. It might be useful in this case to not store a complete particle in one PDS but have parallel ones which store different fields, like one dedicated to just particle positions and velocity, another for colder fields like particle sizes and life times, things of this sort. This way the data that needs to be output per frame that's different from the previous might shrink a bit.

One Use Case

I was trying to think of a practical use case for that kind of immutable rep above (which I didn't really intend to be used for particles, I just used particles to quickly test it out), and one I could imagine if we can relax the "highly dynamic" requirements is like a particle painting software.

Like the user might spray and spread particles around on a canvas designed to sort of simulate real media, and instead of working with pixels or vectors they're actually working with a boatload of particles, millions and millions of them, that have velocity and so forth, and the particles stop moving after a while and settle down but the user might then grab a tool to smear and just start smearing the paint particles all over the place again. And the user might zoom in so, so close that he's just playing around with a few particles.

In that case it's rather dynamic but not every single particle is moving every single frame, so that sort of immutable rep might be a fairly efficient way to store the user's undos in a way that minimizes memory usage, since it'd only require the bulk of the memory for the particles that actually moved in the new versions of the PDS generated from the time the user's undo was captured.

And the particles might have like a bit of depth and shading/lighting to them to allow for some impasto effects.

That's kind of a fun idea. I might go code it over some weekend just for a fun little paint software.