Immutable functional objects in highly mutable domain

Question

I'm currently learning functional programming in my spare time with Scala, and I have an idle newbie question.

I can see the elegance of having immutable objects when doing something like calculating a Haar wavelet transform - i.e. when the data itself being represented by the objects doesn't change.

But I saw a blog where someone had a small game as an example when demonstrating immutability. If a creature object recieved damage, it didn't change its state - it returned a new creature object with the new hitpoints and a new "aggro towards X" flag. But if we were to design something like a MMORPG, World of Warcraft say. A hundred players in a battleground... possibly thousands of attacks and buffing/debuffing spell effects affecting them in different ways. Is it still possible to design the system with completely immutable objects? To me it would seem like there would be a ginormous swarm of new instances each 'tick'. And to get the currently valid instance of objects, all clients would constantly have to go through some sort of central "gameworld" object, or?

Does functional programming scale for this, or is this a case of "best tool for best job, probably not immutable here"?

Answer 1

To me it would seem like there would be a ginormous swarm of new instances each 'tick'.

Indeed, that is the case. I have a Haskell application that reads a market data feed (about five million messages over the course of a six-hour trading day, for the data in which we're interested) and maintains "current state" for various things, such as the most recent bid and offer prices and quantities for the instruments, how well our model fits the market, etc. etc. It's rather frightening to simulate a run of this program against a recorded feed in profiling mode and watch it allocate and GC close to 288 TB of memory (or close to 50,000 times the size of my machine's RAM) in the first 500 seconds of its run. (The figure would be considerably higher without profiling, since profiling not only slows down the application, but also forces it all to run on one core, as well.)

But keep in mind, the garbage collector in pure language implementations is optimized for this sort of behavior. I'm quite happy with the overall speed of my application, and I think that it's fairly demanding, in that we have to parse several hundred messages per second from the market feed, do some fairly extensive calculations to build our model, and use that model to generate orders to go to the exchange as quickly as possible.

Answer 2

Typically in functional programming you won't have C++ style constructors. Then, even though conceptually you are creating objects all the time, it doesn't mean that the compiler has to make code to allocate a new object, because it can't affect the behaviour of the program. Since the data is immutable, the compiler can see what values you've just specified, and what has been passed into your functions.

Then, the compiler can create really tight compiled code that just calculates the fields in the specific objects when they are needed. How well this works depends on the quality of the compiler you use. However, clean functional programming code tells the compiler quite a lot more about your code than a C compiler for a similar program could assume, and so therefore a good compiler may generate better code than what you might expect.

So, at least in theory, there's no reason to be concerned; functional programming implementations can scale just as well as object oriented heap allocate implementations. In practice, you need to understand the quality of the language implementation you are working with.

Answer 3

An MMORPG is already an example of immutability. Since the game is distributed across servers and gamers' systems, there is absolutely not a central "gameworld" object. Thus, any object that gets sent over the wire is immutable — because it doesn't get changed by the receiver. Instead, a new object or message gets sent as a response, if there is one.

I've never written a distributed game so I don't know exactly how they're implemented, but I suspect that updates to objects are either computed locally or sent as diffs over the wire.

For example, you're playing Command & Conquer. Your mammoth tank is sitting in ready mode guarding your base. Your opponent approaches with a light tank to explore your base. Your mammoth tank shoots and hits your opponent's tank, causing damage.

This game is pretty simple, so I suspect a lot is computed locally whenever possible. Assume the two players' computers are initially in sync in terms of game state. Then your opponent clicks to move his light tank into your base. A message (immutable) is sent to you over the wire. Since the algorithm to move a tank is (probably) deterministic, your copy of Command & Conquer can move your opponent's tank on your screen, updating your game state (could be immutable or mutable). When the light tank comes in range of your mammoth tank, your tank fires. A random value is generated on the server (in this case, one computer is chosen arbitrarily as the server) to determine whether the shot hits your opponent or not. Assuming the tank was hit and an update to your opponent's tank must be made, only the diff — the fact that the tank's new armor level has decreased to 22% — is sent over the wire to sync the two players' games. This message is immutable.

Whether the object on either player's computer representing the tank is mutable or immutable is irrelevant; it can be implemented either way. Each player does not directly change the state of other gamers' game.

Answer 4

One point to note on immutability is that (if implemented correctly) it makes object creation relatively lightweight. If a field is immutable, then it can be shared between instances.

Answer 5

It's important to consider when designing a functional program that, like you state, Immutable objects will have some overhead. It's also important to remember that by having objects in your MMORPG program be immutable it will be inherently more scalable. So, the initial investment in equipment may be higher, but down the road as things expand you will be able to scale to your player base.

Another important thing to consider is that right now a the beefiest machines have 6 cores per cpu. Consider a dual cpu machine with 6 cores each. One of these 12 cores can be doing garbage collection and so the overhead from tearing down lots of objects can be offset by the application being easily scalable to those other 11 cores.

Also remember that not every object (and it's sub objects) need to be completely rebuilt on a copy. Any reference type that didn't change will only take a single reference assignment when an object is "copied".

Answer 6

Don't think of object creation at the wire level. For example, an optimized runtime for a functional language will probably be able to "cheat" when it comes to replacing an object and actual do mutation of the existing struct, if it knows nothing will reference the original and the new one replaces it completely. Think of Tail Recursion Optimization, but applied to object state.

Answer 7

I found a blog today that deals EXACTLY with the questions I raised in this post:

http://prog21.dadgum.com/23.html

Answer 8

Like pretty much every tool in programming, Immutable objects are powerful, but dangerous in the wrong situation. I think the game example is not a very good one or at least very contrived.

Eric Lippert has some interesting posts on the topic of immutability, and they're quite an interesting read.