Friday, August 3, 2012

magic intervals

It is desirable to have large numbers of entities processed per-frame on multiple threads and fibers in a balanced manner. This can be achieved by creating a manager to schedule updates across a frame in small slices to keep resources from being contended too aggressively.

We can use (abuse?) random initial sleep intervals to achieve this behavior intrinsically, without the need for any management processing. Consider a group of game entities, which all sleep for one second (t) and then perform their update. We can imagine all the threads/fibers running at the same time causing a spike in our resource consumption at that point.

If we perform a sleep of a random interval between 0..t for the first update, we can effectively distribute the updates across subsequent frames, without any further management.

explanatory graph of explaining

Our normal behavior in the top frame is imbalanced and spikes each frame as all the entities wake up for processing simultaneously. Using our random first sleep, we shuffle the processing order across the frame. We can see in the sorted view how this would give us well-distributed updates across the frame.

The caveats for this are that a large enough number of entities is required to balance out the updates evenly. The method should be indifferent to variable-length sleep intervals (variable-length sleep would inevitably end up distributed like this anyway).

It's a trick only applicable in certain cases, but the required code change is very localized (a sleep() during init()) and can work nicely for game entities/enemies.

No comments:

Post a Comment