Simulator rewrite

[xoft]

The current implementation of physics simulators is less than satisfactory. I tried to make water flow upon chunk load (so that waterfalls work and undersea caverns fill with water), and the architecture simply overwhelms the server. One tick takes several seconds due to the simulators.

I've traced the main problem to be that the simulators look up each and every block through cWorld::GetBlock(), simply because they have to. That function has to lock the chunkmap, locate the correct chunk, ask it for block parameters... Just too much work per single block, considering that they may be thousands of blocks needing to update every tick.

Here's some profiling info from my tests:

Code:

cRedstoneSimulator::Simulate: 65089 torches, 0 repeaters, 56 blocks took 15072 ticks (15.07 sec)
cDelayedFluidSimulator::Simulate: 109 blocks took 63 ticks (0.06 sec)
cRedstoneSimulator::Simulate: 580 torches, 0 repeaters, 101 blocks took 31 ticks (0.03 sec)
cDelayedFluidSimulator::Simulate: 2911 blocks took 1781 ticks (1.78 sec)
cRedstoneSimulator::Simulate: 873 torches, 0 repeaters, 2301 blocks took 531 ticks (0.53 sec)
cDelayedFluidSimulator::Simulate: 1085 blocks took 172 ticks (0.17 sec)
cRedstoneSimulator::Simulate: 19261 torches, 0 repeaters, 10835 blocks took 7607 ticks (7.61 sec)
cDelayedFluidSimulator::Simulate: 69 blocks took 78 ticks (0.08 sec)
cRedstoneSimulator::Simulate: 91065 torches, 0 repeaters, 215 blocks took 2078 ticks (2.08 sec)
Generating chunk [16, 0, -26]
cDelayedFluidSimulator::Simulate: 201 blocks took 156 ticks (0.16 sec)
cRedstoneSimulator::Simulate: 2156 torches, 0 repeaters, 93 blocks took 1671 ticks (1.67 sec)
cChunkMap::WakeUpFluidSimulators took 16 ticks (0.02 sec)
cDelayedFluidSimulator::Simulate: 3381 blocks took 1843 ticks (1.84 sec)
cRedstoneSimulator::Simulate: 757 torches, 0 repeaters, 2163 blocks took 547 ticks (0.55 sec)
cDelayedFluidSimulator::Simulate: 1638 blocks took 344 ticks (0.34 sec)
cRedstoneSimulator::Simulate: 17328 torches, 0 repeaters, 10348 blocks took 2890 ticks (2.89 sec)
cDelayedFluidSimulator::Simulate: 172 blocks took 62 ticks (0.06 sec)
cRedstoneSimulator::Simulate: 84823 torches, 0 repeaters, 643 blocks took 1968 ticks (1.97 sec)
cDelayedFluidSimulator::Simulate: 187 blocks took 94 ticks (0.09 sec)
cRedstoneSimulator::Simulate: 5927 torches, 0 repeaters, 113 blocks took 156 ticks (0.16 sec)
cDelayedFluidSimulator::Simulate: 3136 blocks took 1640 ticks (1.64 sec)
cRedstoneSimulator::Simulate: 955 torches, 0 repeaters, 2080 blocks took 531 ticks (0.53 sec)
cDelayedFluidSimulator::Simulate: 1677 blocks took 344 ticks (0.34 sec)

Notice that the tick durations are totally unpredictable and completely degrade the server performance (>10s per some ticks!!!)

So how to improve this? I think the simulator should be called for each chunk individually, with the direct access to chunk's block data. That way, it won't have to do the lookups, it could even inspect (most) block neighbors without lookups, and it could process all blocks inside one chunk within one chunkmap-lock operation.
However, the current scheme of storing blocks for waking up would need to be somehow rewritten, too. Haven't gotten so far yet, will post updates as I make my mind up about it

[Taugeshtu]

You know what? I feel like there's something in the air, that calls us to EPICNESS

Also, I'm wondering, what would happen when simulator would requie neighbour chunk: let's not do chunk lookups for every block
I would recommend storing chunk's neighbours, so we could easily check their state and load them (if needed).

Anyway, good luck to you with that

[xoft]

If the simulator requires a neighbor chunk, it will still have to do a chunk lookup through cWorld. But that will be in so much fewer cases, that it's worth the effort.

I'm not sure storing 4 neighbors in each chunk and keep them in sync is worth the effort.

What I had in mind was a function signature:

Code:

cSomeSimulator::SimulateInChunk(const cChunkDef::BlockTypes & a_BlockTypes, const cChunkDef::BlockNibbles & a_BlockMetas, const BlockCoords & a_BlocksToSimulate, sSetBlockVector & a_BlocksToChangeOut);

So it will be able to directly read chunk data for the chunk, it will query cWorld for neighbors, if needed; it will have a per-chunk list of blocks to simulate and it will output a list of blocks that should change (so that cChunk can update heightmap, send the block changes to the client etc.)

EDIT: updated the function signature to take const references, where appropriate.

---

I have committed the simulator-waking to a new branch, /branches/wake_simulators_on_load. It's only for the curiosity, because it's actually useless, with those tick times.

[xoft]

You know what? That idea with storing chunk neighbors might not be as bad as it first seemed.

For current simulators, such as sand and floody fluid, it is not beneficial at all, none of these touch a neighbor more than 1 block away. For that reason, keeping the neighbors up to date would be too much work for almost no gain.

However, for redstone and in the future, for vanilla fluid simulators, this could become the real deal. These two need blocks up to 16 blocks away, for which the neighbor chunks make sense very much. Also this would further reduce the locking of the chunkmap - the simulators will tick inside the chunk's tick, having the chunkmap already locked, and accessing the neighbors as needed without locking at all.
For this to work, we'd need two things - chunk keeping track of their neighbors in a set of protected member fields / functions, and simulators being capable of ticking one chunk worth of data.
I'll start implementing the first one - chunk neighbors. Then I have no trouble converting old simulators to the new schema.
BUT! I'm afraid I won't have enough wits to rewrite the current redstone simulator to the one-chunk-worth idiom. So the only reasonable thing I can do for the time being, is disabling the redstone simulator, until someone boldly steps in and rewrites it, too.

[FakeTruth]

Why disable it? Will it become incompatible after you added neighbour info to the chunks?

[xoft]

not with the neighbors, but with the simulator rewrite. I want to change the simulator concept altogether, so at the very least the base class's function signatures will be different.

[NiLSPACE]

can you also change the firesimulator? becouse once you are on fire you stay on fire for ever until you relog.

[xoft]

I don't think that's handled in FireSimulator. Or at least it shouldn't be. In my opinion, FireSimulator should only be responsible for lighting stuff on fire, extinguishing fire after a certain time limit and burning things down; not for entity damage.

[xoft]

So I've started the rewrite, but it'll be difficult.
So far I have the chunk neighbors and their traversal, and I started changing the simulators so that they are synchronized with the tick thread and therefore can receive a direct cChunk pointer. That should already provide some speedup; although only marginal. But it'll be one hell of a debugging job to get it all right.

[keyboard]

Oh ok, cool. Then I guess I'll wait until there is a prototype so I can rewrite the redstone simulator.