Using persistent data structures to streamline complex/combinatorial software systems (e.g. games) #

Writing this article as - equally - a thing I’d like other people to be more aware of AND a reminder to myself on the benefits/tradeoffs this kind of design brings about.

What for #

To start with, we’ll use a game system as an example (in Python), as those are straightforward to imagine and can easily explode in various complex functionalities interacting with each other, all impacting system state in different ways - and plenty enough ways all of this can go wrong.

If you’ve never written a game the concept is relatively simple, a continuous loop runs (oftentimes literally a while True: ... kind of loop) and takes user inputs, changes game state based off those inputs, and ultimately it renders game elements onto a screen. Rinse, repeat.

Now, the complexity isn’t there right at the beginning, it usually takes a bit before you start hitting various obstacles due to complexity and then it almost instantly becomes exponentially more difficult to do anything just because of plain combinatorial explosion of conditions you have to deal with.

If you know what that means you can skip the next section but sadly way too many people make their living producing/selling software without having a grasp on how these things plays out.

Brief intro to combinatorial explosions #

Best demonstrated through sequence-of-operations examples, like the other in which one would bake a cake, put clothes on, or visit nodes in a network of some kind, travel through a given number of cities.

Sometimes the order matters, which admittedly reduces some of the numbers, but still - sometimes the order doesn’t matter.

Let’s say you’re given 3 interconnected cities (city A, city B, and city C) and you have to visit all of them, you have 6 possible combinations of events that can occur:

you get the picture.

but what if there were 4 cities? 24 combinations.

5 cities? 120 combinations.

6? 720 combinations.

7? 5,040 combinations.

8? 40,320 combinations.

9? 362,880 combinations.

10? 3,628,800 combinations.

11? 39,916,800 combinations.

By 20 cities the number of combinations balloons into quintillions.

https://en.wikipedia.org/wiki/Factorial

The pains of combinatorial explosions #

And this is ultimately the bane of complex, “feature rich” systems when they’re not done right.

The initial phases of development are relatively manageable but as things are piled on you end up with 2!, 3!, 4! … 10! (or more) interconnected features which impact each other resulting in 3,628,800 potential combinations of system states you will ultimately end up having to deal with when something goes wrong.

This has always been a problem and no amount of trickery nor more labor can help.

And the problem is exacerbated by people making decisions without having an understanding of how any of this works.

Taming the beast #

It’s a hard sell convincing others of the benefits but when you’re engineering your own systems for experiments or hobbies you can do yourself a favor and make use of persistent data structures in order to “shift-left” the design that has an impact on potential combinatorial explosions, simultaneously putting bottlenecks on your designs and keeping scope creep somewhat manageable.

To start with, I’ll describe persistent data structures themselves (and immutable data structures).

Persistent vs immutable data structures #

An immutable data structure is a data structure whose state cannot be modified after you first create it.

For example a Python list is mutable but a tuple is immutable:

>>> _mutable: list[int] = [1, 2, 3]
>>> _immutable: tuple[int] = (1, 2, 3)
>>> _mutable[0]
1
>>> _immutable[0]
1
>>> _mutable[0] = 5
>>> _mutable[0]
5
>>> _immutable[0] = 5
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment

however immutability is only a part of it.

The other part is persistence.

A persistent data structure is usually (but doesn’t have to be) immutable, and its primary purpose is to internally preserve a previous version of itself.

So imagine if we actually could reassign that tuple’s first value (at index 0) to 5 but without modifying the actual tuple.

This can be done manually of course, and it would look something like this:

>>> _immutable: tuple[int] = (1, 2, 3)
>>> _temporary: list[int] = list(_immutable)
>>> _temporary[0] = 5
>>> _immutable_v2: tuple[int] = tuple(_temporary)
>>> _immutable[0]
1
>>> _immutable_v2[0]
5
>>> _immutable is _immutable_v2
False

and now you have one version of _immutable, the original, and you have another version with its first value set to something else.

Wait, you might ask now…

What would be the point? #

The point is the intention to always prevent mutability downstream, providing data integrity.

If you can know for a fact that you have passed an immutable data structure through a 15-calls deep call stack you can look at the 13th, 14th, 15th call and be almost certain that the data is still the same and that it’s almost certain it hadn’t changed anywhere in between.

That makes debugging and even design itself much simpler.

Mutation is technically possible but not intended, YMMV but if you wrote code that’s got a 15 calls deep call stack and you’re passing an immutable data structure through it all (for some reason) other programmers working with the code will generally try not to mess with the data structure when changing code anywhere in between.

And the cloning? Why multiple versions? #

If for some reason you decide that somewhere in the middle of the aforementioned call stack the data structure has to change after all but only this once and it should remain immutable/unchangeable for the rest of the call stack - you can do that.

So you have this guarantee so to say that the data you’re dealing with is always the same but simultaneously you have this specific point in your code where you unmistakably decide that you need an alternate/specialized/slightly-different version of that immutable data structure.

A chokepoint.

Is it just ceremony? #

No.

If you happen to be one of the people who write nicely encapsulated, isolated, TESTABLE, code, you can immediately see potential benefits of this.

If your 15-calls-deep call stack has to make a side effect of some kind, you can use persistent data structures for most if not all data that is operated on in the 15 calls.

Pass values into functions/methods, get a new versions of those values back.

Now you have variables holding both pre-evaluation state and the post-evaluation state.

What for, you ask?

A common scenario I see is you have a variable holding some complex state and you pass that state to 3 different functions, and any one of them can make changes based on some constantly-changing factors.

Combinations of (notice the phrase I’m using here) these factors might have an impact on how any of the other functions work, commonly causing bugs and side effects which you have to spend time chasing down, mapping out, figuring out, fixing, refixing, etc.

And the more factors you end up introducing (we all know this is a given) the quicker your unmanageable combinatorial explosion becomes a problem.

Sounds like a lot of work #

but it isn’t.

Pyrsistent is one of my favorite Python libraries these days, I’ve decided to try it out on an RPG game (via Pygame) and the productivity boost of just not having to worry about all the various changes to complex game states alone had me go from someone who was (honestly) afraid of even attempting to write game code to someone who can almost precisely estimate whether a game design is sane enough to implement or not.

When your starting point is (almost) always with persistent data structures you can exactly tell how much effort it will be to (re)write the code needed to make something happen.

And Pyrsistent makes the aforementioned versioning/cloning of immutable data structures much easier. Instead of all the assigning/reassigning dance you can do this:

>>> from pyrsistent import PVector, v as vec
>>> _immutable: PVector[int] = vec(1, 2, 3)
>>> _immutable_v2 = _immutable.set(0, 5)
>>> _immutable[0]
1
>>> _immutable_v2[0]
5
>>> _immutable is _immutable_v2
False

Memory usage implications and structural sharing #

And the best part?

You’re not actually duplicating all the data when you do this with Pyrsistent, as Pyrsistent data structures (such as PVector) rely on structural sharing to maintain performance and memory efficiency.

Under the hood a PVector isn’t really creating an entirely new copy of itself with all the data, but instead it relies on structural sharing and path copying which I won’t get into now, the gist of it is that _immutable and _immutable_v2 reuse the same memory for the same data that they hold, so 2 and 3 are the exact same memory used by both, only the 1 is pointed at by _immutable and the 5 is pointed at _immutable_v2.

This same principle applies to any of the many supported data types and the full list is here.

Of course there are a couple of performance drawbacks despite of this however once you ground a less-than-optimal version of your system with persistent data structures, optimizing and refactoring where necessary lets you both have your cake and eat it as well.

Game example of combinatorial explosion tamed by persistent data structures #

A real life example I can detail here from my game experiment with Pyrsistent and which could help drive the point home is speculative collision detection.

See collision detection usually starts simple then you introduce new things one after another which usually impact each other and movement overall and you have to keep track of everything and sometimes a player can’t move there usually, unless it’s a special edge case, however be careful to take this factor into account and so on and so forth.

Persistent data structures made this all linear for me.

I ignore collision detection and just move the player to where they want to go.

Then I take a look at where the player moved, check the various sets of conditions and reassign the state back to pre-movement if the movement is illegal.

The same principles applies to most types of player actions, the code is simple and just lets you do things and returns new state, but after you do something and you weren’t supposed to, the state is set back.

That way no matter how many different mechanics there are your movement code never has to worry about collision, your collision code never has to worry about player actions, your player actions code never has to worry about the environment, and ultimately your environment code never has to worry about any of the other factors.

The final benefit I can mention is that (although I can’t say for sure and this is subjective) I think the amount of code you have to write is drastically reduced. Things end up neatly segregated but they’re always straightforward and compact.

Does this relate to functional programming? #

Yes but it’s intertwined, I’m writing OOP game code, it’s just that more often than not my instance of e.g. Player class inherits from PClass and its method calls return a new version of self instead of quietly mutating its own internal state.

What about lenses? #

Yes making use of lenses does make sense however I am yet to get to that point - I leverage persistent data structures as chokepoints at which you have to deliberately decide what you’re doing and nested mass-reassignment that lenses does is a bit contrary to this goal.

I’ll probably write about it when I try it out.

Implications for thread safe, lock free, concurrent, and parallel processing #

I mean do I even need to get started on this?

If you’re at all familiar with parallel processing you can easily imagine just how much simpler it nows become to take the collision detection from the above example and evaluate each and every collision check on a separate CPU core.

If your checks are not interdependent you could check if the player had walked into a wall on core #2 and check if the player had stepped on another player’s toes on core #3 and so on and so forth.

No locks, no semaphores, no mutexes.

Forget about CPU cores!

You want to distribute a massive real time system across multiple servers?

You could check if the player had walked into a wall on server #2 and check if the player had stepped on another player’s toes on server #3 and so on and so forth.

[Next: XMPP as an authentication method, ejabberd as an identity and authentication service]