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.