In Screeps, is CPU limit enforced in a way that allows CPU limit robust code to be written?

Question

In Screeps, each player's usage of CPU is limited, but the documentation for this feature doesn't make the way this is enforced sufficiently clear for writing CPU limit robust code. I've considered the following four possibilities:

---

1. The player's cycle is never interrupted.

At one extreme, the player's memory deserialize, main script execution, and memory re-serialize are never interrupted, and exceeding the CPU limit simply means that the player's cycle will be skipped on subsequent ticks until the CPU debt is repaid. CPU limit robust code isn't strictly necessary in this case, but it would still be useful to detect when the player's cycle is skipped and possibly start doing things more efficiently. This can easily be achieved using code like this:

module.exports.loop = function()
{
  var skippedTicks = 0;

  if ( 'time' in Memory )
  {
    skippedTicks = Game.time - Memory.time - 1;
  }

  // Main body of loop goes here, and possibly uses skippedTicks to try to do
  // things more efficiently.

  Memory.time = Game.time;
};

This way of managing players' CPU usage is vulnerable to abuse by infinite loops, and I'm almost certain that this is not the behaviour of Screeps.

2. The player's cycle is atomic.

The next possibility is that the player's cycle is atomic. If the CPU limit is exceeded, the player's cycle is interrupted, but neither the scheduled game state changes nor the changes to Memory are committed. It becomes more important to improve efficiency when an interrupted cycle is detected, because ignoring it means that the player's script will be unable to change game state or Memory. However, detecting interrupted cycles is still simple:

module.exports.loop = function()
{
  var failedTicks = 0;

  if ( 'time' in Memory )
  {
    failedTicks = Game.time - Memory.time - 1;

    // N failed ticks means the result of this calculation failed to commit N times.
    Memory.workQuota /= Math.pow( 2, failedTicks );
  }

  // Main body of loop goes here, and uses Memory.workQuota to limit the number
  // of active game objects to process.

  Memory.time = Game.time;
}

2.5. Changes to Memory are atomic but changes to Game objects are not.

EDIT: This possibility occurred to me after reading the documentation for the RawMemory object. If the script is interrupted, any game state changes already scheduled are committed, but no changes to Memory are committed. This makes sense, given the functionality provided by RawMemory, because if the script is interrupted before a custom Memory serialize is run, the default JSON serialize is run, which would make custom Memory serialization more complicated: the custom deserialization would need to capable of handling the default JSON in addition to whatever format the custom serialize wrote.

3. JavaScript statements are atomic.

Another possibility is that the player's cycle isn't atomic but JavaScript statements are. When the player's cycle is interrupted for exceeding the CPU limit, incomplete game state changes and Memory changes are committed, but with careful coding - a statement that makes a Screeps API call must assign the result of the call to a Memory key - the game state changes and Memory changes won't be inconsistent with each other. Writing fully CPU limit robust code for this case seems complicated - it's not a problem that I've solved yet, and I'd want to be sure that this is the true behaviour of Screeps before attempting it.

4. Nothing is atomic.

At the other extreme, not even single statements are atomic: a statement assigning the result of a Screeps API call to a key in Memory could be interrupted between the completion of the call and the assigning of the result, and both the incomplete game state changes and the incomplete memory changes (which are now inconsistent with each other) are committed. In this case, possibilities for writing CPU limit robust code are very limited. For example, although the presence of the value written to Memory by the following statement would indicate beyond doubt that the Screeps API call completed, its absence would not indicate beyond doubt that the call did not complete:

Memory.callResults[ Game.time ][ creep.name ] = creep.move( TOP );

---

Does anyone know which of these is the behaviour of Screeps? Or is it something else that I haven't considered? The following quote from the documentation:

The CPU limit 100 means that after 100 ms execution of your script will be terminated even if it has not accomplished some work yet.

hints that it could be case 3 or case 4, but not very convincingly.

On the other hand, the result of an experiment in simulation mode with a single creep, the following main loop, and selecting 'Terminate' in the dialog for a non-responding script:

module.exports.loop = function()
{
  var failedTicks = 0;

  if ( 'time' in Memory )
  {
    var failedTicks = Game.time - Memory.time - 1;

    console.log( '' + failedTicks + ' failed ticks.' );
  }

  for ( var creepName in Game.creeps )
  {
    var creep = Game.creeps[ creepName ];

    creep.move( TOP );
  }

  if ( failedTicks < 3 )
  {
    // This intentional infinite loop was initially commented out, and
    // uncommented after Memory.time had been successfully initialized.

    while ( true )
    {
    }
  }

  Memory.time = Game.time;
};

was that the creep only moved on ticks where the infinite loop was skipped because failedTicks reached its threshold value. This points towards case 2, but isn't conclusive because CPU limit in simulation mode is different from online - it appears to be infinite unless terminated using the dialog's 'Terminate' button.

Answer 1

Case 4 by default, but modifiable to case 2.5

As nehegeb and dwurf suspected, and experiments with a private server have confirmed, the default behaviour is case 4. Changes to both game state and Memory that occurred before the interruption are committed.

However, the running of the default JSON serialize by the server main loop is controlled by the existence of an undocumented key '_parsed' in RawMemory; the key's value is a reference to Memory. Deleting the key at the start of the script's main loop and restoring it at the end has the effect of making the whole set of Memory changes made by the script's main loop atomic i.e. case 2.5:

module.exports.loop = function()
{
  // Run the default JSON deserialize. This also creates a key '_parsed' in
  // RawMemory - that '_parsed' key and Memory refer to the same object, and the
  // existence of the '_parsed' key tells the server main loop to run the
  // default JSON serialize.
  Memory;

  // Disable the default JSON serialize by deleting the key that tells the
  // server main loop to run it.
  delete RawMemory._parsed;

  ...

  // An example of code that would be wrong without a way to make it CPU limit
  // robust:

  mySpawn.memory.queue.push('harvester');
  // If the script is interrupted here, myRoom.memory.harvesterCreepsQueued is
  // no longer an accurate count of the number of 'harvester's in
  // mySpawn.memory.queue.
  myRoom.memory.harvesterCreepsQueued++;

  ...

  // Re-enable the default JSON serialize by restoring the key that tells the
  // server main loop to run it.
  RawMemory._parsed = Memory;
};

Answer 2

It is not #1 or #2. I'm betting it's #4, it would make the most sense to monitor CPU usage external to the main loop and kill it whenever the limit is reached. #3 would require complicated code in the screeps server to perform "statement-level" transactions. There is no CPU limit in the simulator, as you've discovered.

Most players solve this problem by simply putting critical code early in their main loop, e.g. tower code comes first, then spawn code, then creep movement/work. This also protects against uncaught exceptions in your code as your most critical functions will (hopefully) already have executed. This is a poor solution for CPU limit though, in my observation it appears as though your code is skipped every 2nd tick once you've used all the CPU in your bucket and are constantly hitting your regular limit.

I don't have a CPU issue right now (I have a subscription), but I would solve this by putting CPU-intensive code near the end and, if possible, only executing it when you have plenty of CPU in your bucket and you are nowhere near your 500 CPU per-tick limit. It also helps to have larger creeps, it's common for either pathfinding or even just movement (0.2 per move) to take up a fair chunk of CPU and larger creeps means fewer creeps.

Answer 3

One of the ingame 'tips of the day' says:

TIP OF THE DAY: If CPU limit raises, your script will execute only partially.

Therefore i would say, it's most likely #4!
Just like dwurf says, the following approach to script layout should do the trick in most cases:

Most players solve this problem by simply putting critical code early in their main loop, e.g. tower code comes first, then spawn code, then creep movement/work. [...]