Hi,
after
Mindless released Golems on the forums here, he posted his ideas about what to include in a savestate, what to compress, ...
I got inspired to investigate Lix rewinding performance. Over several evenings, I've finished the following three improvements:
- Savestate only the mutable half of the world
- Choose graphical frames of hatches/exits/... only when drawing
- Refactor away from overuse of shared pointer to world
1. Mutable Half: The world in Lix consists of terrain, players, their lix, hatches, exits, traps, ..., and I used to keep everything in savestates. But some parts of the world never change: Water never changes. Fire hazards never change. An exit has some state (e.g., ownership, the
red player gets points) but this state never changes during play. The initial value of the overtime never changes.
I've separated the world into a mutable half (land, lix, triggered traps, ...) and an immutable half (hatches, exits, water, ...). I copy only the mutable half into savestates. When I load a savestate, I attach the loaded mutable half to the existing immutable half, and that's the new world. This makes the savestates smaller in memory and reduces allocations. Each gadget (hatch, exit, trap, ...) is a heap-allocated class object. To track one in a savestate, we must deep-copy it, and it helps when we only have to save some of the gadgets, not all.
The name "half" is euphemistic. The mutable half is still the lion's share with the uncompressed land bitmap, the physics map, ..., and I didn't look into compression.
2. Graphical Frames: Ostensibly, exits still change over time because they animate. This animation has no bearing on physics, which is a strong argument to keep the exit in the immutable half of the world. But if the exit never changes, it can't keep track of its current animation frame.
The solution: During drawing, I tell the exit the current tick (physics update number) and the exit computes its animation frame from first principles. The drawing method ferries the arguments the to the exit.
Instead of incrementing the frame each tick and resetting the frame after reaching the end, we compute the modulus
tick % animationLength. Naively, taking the modulus of integers is slower than adding and comparing integers. But there are performance benefits: We track less state in the exit now, which makes the exit smaller in memory by itself, and it makes all savestates smaller because exits can now be in the immutable half of the world.
Most importantly, non-drawing physics updates don't have to compute animation frames for exits anymore. When we aren't going to draw the results of some physics updates, we've saved many virtual method calls: One virtual call per gadget per update.
After all, we have our direst need for performance during singleplayer rewinding, during networked games with many players, and during mass replay verification. All three cases compute several (or all) physics updates behind the scenes. E.g., rewinding loads a savestate that is older than the target tick, then updates physics
forward from the savestate until we're at the target tick.
3. Ditch Shared Pointer: A shared pointer to the world means two levels of indirection:
- Usercode holds a shared pointer by value.
- Each shared pointer points to the single reference-counting storage.
- The reference-counting storage points points to the payload.
Compare this with unique resource handling (one indirection) or putting the world struct by value inside your world-handling code (direct access for the holder, and still one indirection for other parts of the physics).
In 2016, when I wrote D Lix, I chose the shared pointer for all holdings of worlds (the current world and for the savestated worlds) because I wanted easy savestating. The same world could appear several times in the savestating cache. I used the same type (shared pointer to world struct) everywhere. The problem was in the
current world, which was also a shared pointer to a world struct. All physics that referenced the world (instead of, e.g., only the lix at hand) had to dereference the shared world pointer many times over.
Solution: Now, I hold the current world by value. After all, the world struct is less than 300 bytes; there is a lot of indirection in the world by itself already.
Sidetracking: I've also removed the shared pointers from the savestating cache. That wasn't necessary to change; it wouldn't have mattered for performance here. For now, I've resorted to manual management of copying/disposing between the current world and the savestates. To do what I really wanted, I need move semantics. D supports C++03-style RAII, but not yet the value-type-based rule-of-five resource handling that became popular with C++11. I want to write my program in the mathematical union of all the programming languages.
Overall BenefitMass replay verification is
3.5 percent faster. The 1077 replays from the replay collection take 18.9 seconds on my Intel i5-6600 3.30 GHz. Before, in the stable Lix 0.10.24, they took 19.6 seconds.
It can't be from the smaller savestates because mass replay verification doesn't generate savestates. It must be either from holding the current world by value or from from skipping graphical frame calculations and avoiding their virtual calls. I can't tell which of the two improvements it is, I have only measured all three optimizations together.
During singleplayer, I've kept the full
60 fps more often during hard rewinds when Lix 0.10.24 would dent to 55 or 50 fps. This is hard to quantify because it depends on the level. It's also hard to guess which of the three optimizations played the biggest role here. The bottom line is: The benefit is at least measurable during graphical play.
We'll see if and how much it helps in practice, after I release this in Lix 0.10.25.
-- Simon
