Switch entity tiles to use *mutable* arrays

[byorgey]

Right now we store the world as a triple: a collection of immutable terrain tiles, a collection of immutable entity tiles, and a map specifying which cells have been updated from their original entity values. However, there is no good reason that we can't just use mutable arrays for entity tiles. Running the game already takes place in a monad; we just have to make sure that it supports the mutable array operations. This should hopefully make the implementation simpler and speed up the game as well.

[twitu]

I was looking into this and I can use a boxed mutable array like STArray could work here. The other options namely - IOArray and StorableArray do not really appear to fit this use case.

I'll also look into benchmarking the performance difference from making this change.

[byorgey]

STArray seems the cleanest conceptually, though it means we will have to thread the s parameter through everything. But IOArray seems like it could work too?

[twitu]

I'm looking into this issue again after the fused-effects system as added. This change appears to be simultaneously easier and more difficult to implement.

I've tried this out using IOArray first. So lookupEntity is now an IO operation.

lookupEntity :: forall t e. Coords -> World t e -> IO (Maybe e)
lookupEntity i (World f t m) = case cachedTile of
  Just entity -> return entity
  Nothing -> do
    findTile <- mapM (`unsafeRead` tileIndex i) entityTileArray
    return $ findTile ? genTile
 where
  cachedTile = M.lookup i m
  genTile = snd (f i)
  entityTileArray = snd <$> M.lookup (tileCoords i) t

But I can't seem to get lookupEntityM to work.

lookupEntityM :: forall t e sig m. (Has (State (World t e)) sig m, Has (Lift IO) sig m, IArray U.UArray t) => Coords -> m (Maybe e)
lookupEntityM c = do
  modify @(World t e) $ loadCell c
  sendM $ lookupEntity c <$> get @(World t e)

The main addition to the current lookupEntityM is adding lifted IO effect. But there does not appear to be any direct trigger for IO in effects. And sendM which I think is supposed to do the job is not working.

[polux]

We may have no choice for performance reasons, but I think we shouldn't take the decision of making the game state mutable lightly. Once we do that we close the door to things like:

• undo
• more generally: time travelling/rewind
• replays / movies
• diffing two successive game states (for debugging purposes for instance)
• easy checking of temporal logic formulas or invariants on a game trace, because producing a game trace wouldn't be trivial anymore

All these things can be done by snapshoting the world, but it will be more cumbersome. My (limited) experience is that when something is persistent you are more inclined to experiment with features like these.

One thing we could do is turn world modification an effect and have two interpreters: a pure slow one, and a mutable fast one. This is reminiscent of the discussion about how to represent the store in https://github.com/byorgey/swarm/issues/150#issuecomment-946973170.

[xsebek]

I have myself avoided mutable state in Haskell so far as the pure data-structures offered pretty good performance - I am not sure that this is the bottleneck. The cons presented by @polux also make me less excited for this change.

If we can spare the time and effort, I would really like to see if we could not get good enough performance with an IntMap replacing the changed cells Map. We could use V2 Int32 indexing instead and fit the whole coordinate into one Int for efficient search and I am sure most players would still fit inside the smaller world. :slightly_smiling_face:

In any case it would be nice to have benchmarks running bigger robot programs to see what the improvements are. I imagine the scenarios to test could be:

• path enumeration
  • we could send robots from base in path determined by an int
  • number 0 is noop otherwise shift by 2 bits - 00..11 is direction to go
  • only tests blocked queries of World, no cell changes
• creating a lot of seed robots
  • the program would teleport seed robots to random X cells
  • after some time they are all self-destructed and we have X entity changes
• BFS from base
  • the robots would create&place say a 1 on each tile they visit
  • could be parametrized with distance from base
  • tests the updates and queries of World

[xsebek]

Also maybe this could be significantly improved with saving&loading the world (#50) - we could put the loaded world into the immutable array and thus empty the changed Map entirely.

[twitu]

I agree with @polux's comments above that mutable arrays will certainly push a lot of interesting ideas out. Since the main reason for mutable arrays for performance I thought of trying out the changes to at least benchmark the performance difference.

I've take a stab at it in #278 using IO arrays and my conclusion is that IO is truly messy and it leaks everywhere. Currently the branch is not building because I've stopped at a couple of major roadblocks.

The changes to the World module itself are relatively small. It's just that the logic becomes much more imperative. However the main challenges that occur because of this are -

• The whole of loadRegion becomes IO because it involves loading the entity array. So by usage loadRegion -> loadCell -> lookupEntity and lookupTerrain also become IO. This still contained with World module so it's fine.
• This however affects View module very much. View is generated by "looking up" all the tiles and entities in a world, so everything gets polluted with IO. Not only does it make the some of the nested structures very difficult to write. But it also uses a monad for Context and so to deal with the two monadic contexts now needs effects where there was none.
• A few other pure functions like changeWorld' also need to be changed in Step module. The top level functions probably don't need change since it is already using the IO effect.

Overall even as an experiment using IO Array has turned out to be very hairy and is still not building. I might have better luck with ST Array. I'm open to suggestions if there's a better way to implement it.

[byorgey]

I'm going to close this --- I think we're all agreed that adding mutable state is not a great direction to go in. Definitely still open to experimenting with other ways to get better performance, e.g. the suggestion to try IntMap for coordinates.