Enhancing the performance of games: a few ideas

[arthuro555]

Migrating away from Hashtable

Hashtable missuses an object as a map, whereas Map is more adapted, standard, properly typed, and most importantly performant. We should work towards replacing instances of Hashtable with Map, then ultimately fully remove it.

Refactor to remove gdjs.Variable

gdjs.Variable is most likely a performance hog. It allocates one variable for each javascript type per variable, is a full class with prototype etc. It must be very hard for javascript engines to optimize, as they cannot infer the shape of the data and generate performant data structures from them (e.g. it cannot optimize an array of numbers).

Instead of a class, we could use real javascript variables directly, replacing the methods with functional helpers. We would also have a different expression type for the intent of reading and the intent of writing.

For example, if

runtimeScene.variables = {
  GameState: "Playing",
  Image: {
    DataFromFS: [118, 214, 186, 48, 78, 63, 211, 133, 109, ...],
    Name: "arthuro.png"
  },
  Player: {
    Alive: true,
    HP: 70
  }
};

then the expression VariableString(GameState) would generate :

// from variabletools.ts
function getAsString(variable) {
  if(typeof variable !== "string") { ... }
  return variable;
}

// events code
getAsString(runtimeScene.variables.GameSate)

Variable(Player.HP) would generate

// from variabletools.ts
function getAsNumber(variable) {
  if(typeof variable !== "number") { ... }
  return variable;
}

// events code
getAsNumber(runtimeScene.variables.Player?.HP)

getAsNumber/getAsString/etc handle the case where variables.Player or Player.HP returns undefined. That way, we also ensure that expressions never create child variables if they do not exist too, which is a better behavior than creating empty variables.

The expression Image.DataFromFS used in a for loop event set to write the children to ImageBits[Variable(Image.Name)][0] would generate like this:

// events code
const arrayOrUndefined = runtimeScene.variables.Image?.DataFromFS;
function setChildContent(newValue) {
  const child1 = runtimeScene.variables;
  if(!child1.ImageBits) child1.ImageBits = {};
  const child2 = child1.ImageBits;
  const child3Name = getAsString(runtimeScene.variables.Image?.Name)
  if(!child2[child3Name]) child2[child3Name] = []; // Since `ImageBits[Variable(Image.Name)]` is then accessed with a number (`[0]`), we assume it is an array. An array can still be used as an object afterwards too, if the assumption was false.
  const child3 = child2[child3Name];
  child3[0] = newValue; // Since the expression was a number, we generate a bracket accessor instead of a dot accessor
}

if(arrayOrUndefined) {
  for(const i in arrayOrUndefined) {}
    setChildContent(arrayOrUndefined[i]);
    subevents(runtimeScene);
}

The set variable to boolean false with the variable Player.Alive would generate like this:

// from variabletools.ts
function setBoolean(variableSetter: (newValue: boolean) => void, newBooleanValue) {
  variableSetter(newBooleanValue);
}

// events code
function variableSetterExpression1010101(newValue) {
  const child1 = runtimeScene.variables;
  if(!child1.Player) child1.Player = {};
  child1.Alive = newValue;
}

setBoolean(variableSetterExpression1010101, false)

This should offer much more context to v8 and allow it to optimize variables much better, and to reduce the memory footprint of GDevelop games that use a lot of variables. This would also make tasks like loading an image from the internet/file system as an array to then insert it into the game much more performant and practical.

Using Typed Arrays for common number properties for cache locality

Some properties like x and y, height and width are commonly used together. Additionally, operations are often done with multiple instances of the same objects. We can optimize math heavy operation that use these a lot (e.g. collisions, behavior's movement calculus) by putting this data in contiguous memory (data oriented design) via typed arrays. Example pseudo code:

class ObjectNumericProperties {
  // We could also replace those with signed integer arrays for games with rounding pixels enabled
  // the shape of data is [object 1 x, object 1 y, object 2 x, object 2 y...]
  xandy = new Float32Array(30)
  handw = new Float32Array(30)
  // the shape of data is [object 1 angle, object 2 angle, ...]
  angle = new Float32Array(15)
  // etc for the other numerical properties like zOrder etc

  id = 0

  createObjectDataID() {
    // recycle IDs to not waste memory
    const newID = this.canRecycle ? this.recycleID() : this.id++;

    // resize the arrays if the ID is out of bounds. exponentially increase the new size each time as a resize is costly and we want to avoid these.
    this.resizeIfNecessary(newID);

    return newID;
  }
}

class RuntimeScene {
  objectsProperties = [];
  constructor(data) {
    for(const i in data.objectTypes) {
      // pesky JS in operator always returns strings instead of numbers, causing the array to deoptimize if we do not transform it insot a number
      const numericIndex = +i;
      this.objectProperties[i] = new ObjectNumericProperties();
    }
  }

  createObject(objectType) {
    return new RuntimeObject(this.objectProperties[this.getObjectTypeID(objectType)])
  }
}

class RuntimeObject {
  private objectProperties: ObjectNumericProperties;
  private objectDataID: number;
  constructor(objectProperties) {
    this.objectProperties = objectProperties;
    this.objectDataID = objectProperties.createObjectDataID();
  }

  get x() { return this.objectProperties.xandy[this.objectDataID*2]; }  
  set x(val) { this.objectProperties.xandy[this.objectDataID*2] = val; }
  get x() { return this.objectProperties.xandy[this.objectDataID*2 + 1]; }  
  set x(val) { this.objectProperties.xandy[this.objectDataID*2 + 1] = val; }

  get height() { return this.objectProperties.handw[this.objectDataID*2]; }  
  set height(val) { this.objectProperties.handw[this.objectDataID*2] = val; }
  get width() { return this.objectProperties.handw[this.objectDataID*2 + 1]; }  
  set width(val) { this.objectProperties.handw[this.objectDataID*2 + 1] = val; }

  get angle() { return this.objectProperties.angle[this.objectDataID]; }  
  set angle(val) { this.objectProperties.angle[this.objectDataID] = val; }
}

Using integer lists when doing object picking

It was established once I think by 4ian that object picking is especially slow in GDevelop.
Ideally, we could try and avoid copying the lists of objects at every event level, but I keep on turning the problem around and around and I cannot think of a good data structure for slowly filtering out objects more efficiently.

I am not sure if this optimization is worth it, due to the overhead of having to fetch the object in an array afterwards. I think mutating a number array like this is more efficient than an object array, and that an object array used as a lookup table rather than being constantly mutated would be faster, but that's just a hunch and I may be very very wrong.

So instead of using another data structure, what about optimizing the list to be more efficient?
We can use typed arrays again with the GDevelop object IDs (obj.id). We know IDs are unsigned integers, so we can use an Uint32 array. This introduces a technical limit of objects created throughout the lifetime of the game to 4,294,967,295. If we want to be on the safe side we could use an Uint64 which is truly a fully unrealistic limit to reach (18,446,744,073,709,551,615), but this would make us use BigInts, which are a hassle and less optimized...

Since typed arrays are fixed size and we do not want to resize them all the time for obvious perf reasons, we would use the first index to store the "length". This ensures that object picking array memory is never deallocated which would be bad for perf and not a memory leak: after all, if the array grew to be very big at a moment, we know that the game has the potential of reaching that amount of objects and must keep the array at that huge size for when it happens again without having to resize a lot again.

To get the object by ID

Example generated pseudo-code:

gdjs.SceneCode.GDSpwnPosObjects1= new Uint32Array(15);
gdjs.SceneCode.GDSpwnPosObjects2= new Uint32Array(15);
gdjs.SceneCode.GDSpwnPosObjects3= new Uint32Array(15);

gdjs.SceneCode.eventsList1 = function(runtimeScene) {
  // Resize the array if it cannot contain all IDs
  const objCount = runtimeScene.getObjectCount("SpwnPos");
  if(objCount > gdjs.SceneCode.GDSpwnPosObjects1.length) 
    gdjs.resizeTypedArray(gdjs.SceneCode, "GDSpwnPosObjects3", Math.ceil(objCount * 1.5));

  // RuntimeScene keeps track of the ID of objects for every object type present on the scene.
  // This list in RuntimeScene may also be an Uint32Array.
  // This methods fills the array starting from index 1, and set the index 0 to the amount of objects in the list.
  runtimeScene.getObjectsIDs("SpwnPos", gdjs.SceneCode.GDSpwnPosObjects1);

  gdjs.PlatformerCode.GDSpwnPosObjects2[0] = 0;
  for(let i = 1;i < gdjs.PlatformerCode.GDSpwnPosObjects1[0];++i) {
    if(gdjs.evtTools.myCondition(runtimeScene.getObjectByID( gdjs.PlatformerCode.GDSpwnPosObjects1[i]))) {
      gdjs.PlatformerCode.GDSpwnPosObjects2[++gdjs.PlatformerCode.GDSpwnPosObjects2[0]] 
        = gdjs.PlatformerCode.GDSpwnPosObjects1[i];
    }

    for(let i = 1;i < gdjs.PlatformerCode.GDSpwnPosObjects2[0];++i) {
      gdjs.evtTools.myAction(runtimeScene.getObjectByID( gdjs.PlatformerCode.GDSpwnPosObjects2[i]))
    }
  }
}

gdjs.SceneCode.func = function(runtimeScene) {
  runtimeScene.getOnceTriggers().startNewFrame();

  gdjs.SceneCode.GDSpwnPosObjects1[0] = 0;
  gdjs.SceneCode.GDSpwnPosObjects2[0] = 0;
  gdjs.SceneCode.GDSpwnPosObjects3[0] = 0;

  gdjs.SceneCode.eventsList1(runtimeScene);
}

// runtimescene.ts

class RuntimeScene {
  objectsTypesIDs = [];
  idToObject = [];
  constructor(data) {
    for(const i in data.objectTypes) {
      // pesky JS in operator always returns strings instead of numbers, causing the array to deoptimize if we do not transform it insot a number
      const numericIndex = +i;
      this.objectsTypesIDs[i] = [];
    }
  }

  createObject(objectName: string) {
    const obj = new RuntimeObject();

    // Add to the base objects lists
    const objectsList = this.objectTypesIDs[this.getObjectTypeID(objectName)];
    objectsList[0]++;
    if(objectsList[0] >= objectsList.length)
      gdjs.resizeTypedArray(this.objectTypesIDs, this.getObjectTypeID(objectName), Math.ceil(objectsList[0] * 1.5));
    objectsList[objectsList[0]] = obj.id;

    // Add to the object lookup table
    this.idToObject[obj.id] = obj;
  }

  getObjectByID(id: number) { return this.idToObject[id]; }

  getObjectsIDs(objectName: string, eventsObjectsList: Uint32Array) {
    const fullObjectsList = this.objectTypesIDs[this.getObjectTypeID(objectName)];
    for(let i = 0; i<fullObjectsLists[0];++i) eventsObjectsList[i]=fullObjectsLists[i];
  }
}

Use Rust WASM code for collisions

Parry is a notorious efficient collision-detection library made by the creators of Rapier, a notorious rust physics engine. WASM being especially good at number crunching jobs, and parry (& rapier) being designed for being compiled to WASM (as is seemingly the trend in rust land currently, apparently?), it would likely be much more performant than our JS solutions. This one would be relatively easy to test out:

1. Create a rust library that exposes the functions we need from parry (or rapier)
2. Compile it to wasm
3. Import it in GDJS
4. Try and replace collision handling code in polygon.ts with the wasm functions
5. Benchmark to see the difference

[4ian]

Thanks for opening this discussion!

A few things:

Migrating away from Hashtable

Probably using a Map is a good idea yes, at least internally.

Refactor to remove gdjs.Variable

I think that's a good idea overall.
Would be good to be 100% sure there is nothing we would miss by doing this?

Using Typed Arrays for common number properties for cache locality

Unsure if this is not a micro optimization, I would rather do this after improving the rest.

Using integer lists when doing object picking

As you said, I think there is optimization to be first done to even avoid copying list ("copy on write" optimizations, or this kind of stuff during code generation). For example, we already do something (search CanReuse in the codebase) so that the last action/condition of a list can iterate on a list without copying it because there won't be any change to it.

I'm tagging @D8H because he recently simplified a bit the code generation (removing global booleans in favor of more readable let declared variables), and we were discussing of any optimization that could be done.

Use Rust WASM code for collisions

This seems like a very nice library. From what I remember when I did a test the important points are:

• Collision solving is not the bottleneck. The bottleneck is iterating on too many objects, so the library should be integrated with a spatial structure holding objects.
• Calling into WASM may have some overhead (between the JS engine and the wasm) so it's another reason to avoid "micro optimising" only collision functions with wasm, and instead have the entire spatial structure holding objects.
• Ensure the library is not too big.
• Make it pluggable. I.e: have a naive implementation (written in JS, holds instances in an array, all "spatial" methods just return all objects) and the wasm implementation. It's easier to reason about, see the boundaries and benchmark the twos (you can just swap two lines of code and try with another implementation).
• Ensure it's actually faster :) From my experiment, some games might be slower because every instance moving had to call into the spatial data structure so that it's updated, which was costly.

I think though that we would already gain 80% of performance by having the collision methods (+ raycast + distance conditions) uses objects that would be hold in a spatial structure, R tree or even just a "dumb" grid (as the cost to update it is super super small).

[D8H]

Using integer lists when doing object picking

As you said, I think there is optimization to be first done to even avoid copying list ("copy on write" optimizations, or this kind of stuff during code generation). For example, we already do something (search CanReuse in the codebase) so that the last action/condition of a list can iterate on a list without copying it because there won't be any change to it.

I'm tagging @D8H because he recently simplified a bit the code generation (removing global booleans in favor of more readable let declared variables), and we were discussing of any optimization that could be done.

Picking lists are reused according to the type of the object parameter (and what the generated code does):

• "object" doesn't allow the function to modify the picking
• "objectList" allow to modify the picking

JS instructions with "objectList" are always modifying the picking list, but this is not the case for event functions. Events functions need an "objectList" because the iteration is done internally and not necessarily to actually modify the picking list. This means that some picking list copy could be avoided.

In event functions, the only instructions that have side effects on the caller picking lists are:

• object instance creation actions
• an action to change the picking list of the caller (Return objects from events based extensions #3163)
• JS events that use eventsFunctionContext.getObjectsLists()
• an instruction from an event-function that matches one of this 4 conditions (recursively)

Functions events could be analyzed during the code generation to add a "read-only" metadata on "objectList" parameters and allow a finer reuse of picking lists when extensions are used.

[Silver-Streak]

It was established once I think by 4ian that object picking is especially slow in GDevelop.

Just to chime in here, when we were doing Bunnymark comparison tests almost exactly a year ago , Object picking/sorting was the thing taking up the majority of render time.

To quote 4ian from that discussion:

The profiler here indicate that the rendering is just 25% of the time spent, the rest is on looping on all 
objects before events (applying forces, etc... though we have none here), then on events, than on all 
objects after events.

We could dive deeper using a JS profiler or just adding timing logs, but what we've learnt is that Pixi is 
not the bottleneck, but GDevelop objects handling is what is to be optimised to achieve more FPS.

This makes me think that object picking is definitely the place for the most optimization. Based off both Arthuro and D8H's comments above though, I'm not sure where you could first target improvements.