Optimizing performance when deleting objects

[tristanbob]

I have done some load-testing of GDevelop, including creating up to 1 million sprites. I know this should never be used in a game, but this process can help find performance problems and memory leaks. (See the project I used here: GDevelopApp/GDevelop-examples#544)

What I noticed is that deleting sprites takes a lot longer than creating them. We have two use cases to investigate:

1) Deleting objects in a running scene

How is this performed? The user uses the "delete object" action, which is defined
in Core\GDCore\Extensions\Builtin\BaseObjectExtension.cpp:

   obj.AddAction("Delete",
                _("Delete the object"),
                _("Delete the specified object."),
                _("Delete _PARAM0_"),
                _("Objects"),
                "res/actions/delete24.png",
                "res/actions/delete.png")

      .AddParameter("object", _("Object"))
      .AddCodeOnlyParameter("currentScene", "")
      .MarkAsSimple();

That "Delete" is defined in GDJS\GDJS\Extensions\Builtin\BaseObjectExtension.cpp

  objectActions["Delete"].SetFunctionName("deleteFromScene");

The deleteFromScene function is defined in GDJS\Runtime\runtimeobject.ts:

    /**
     * Remove an object from a scene.
     *
     * Do not change/redefine this method. Instead, redefine the onDestroyFromScene method.
     * @param instanceContainer The container owning the object.
     */
    deleteFromScene(instanceContainer: gdjs.RuntimeInstanceContainer): void {
      if (this._livingOnScene) {
        instanceContainer.markObjectForDeletion(this);
        this._livingOnScene = false;
      }
    }

markObjectForDeletion is in GDJS\Runtime\RuntimeInstanceContainer.ts

    /**
     * Must be called whenever an object must be removed from the container.
     * @param obj The object to be removed.
     */
    markObjectForDeletion(obj: gdjs.RuntimeObject) {
      // Add to the objects removed list.
      // The objects will be sent to the instances cache or really deleted from memory later.
      if (this._instancesRemoved.indexOf(obj) === -1) {
        this._instancesRemoved.push(obj);
      }

      // Delete from the living instances.
      if (this._instances.containsKey(obj.getName())) {
        const objId = obj.id;
        const allInstances = this._instances.get(obj.getName());
        for (let i = 0, len = allInstances.length; i < len; ++i) {
          if (allInstances[i].id == objId) {
            allInstances.splice(i, 1);
            this._allInstancesListIsUpToDate = false;
            break;
          }
        }
      }

      // Notify the object it was removed from the container
      obj.onDestroyFromScene(this);

      // Notify the global callbacks
      for (let j = 0; j < gdjs.callbacksObjectDeletedFromScene.length; ++j) {
        gdjs.callbacksObjectDeletedFromScene[j](this, obj);
      }
      return;
    }

This step performs several tasks, including:

• Removes the object from the allInstances array using allInstances.splice(i, 1); expression. This will removes one element at a time, and change the indexes of all items to the right of the selected object. This method has a time complexity of O(n).

If the order of elements in the array doesn't matter, we can improve the efficiency of the removal by swapping the element to remove with the last element, and then popping it off the end of the array. This method will have a time complexity of O(1). https://www.30secondsofcode.org/js/s/fast-remove-array-element/

• Adds the object to the instancesRemoved array. It seems that this array is used along with the instancesCache array to reuse objects. I'm not sure about the full implementation of this, so I can't try to identify performance optimizations.

GDJS\Runtime\runtimeobject.ts

    /**
     * Called when the object is destroyed (because it is removed from a scene or the scene
     * is being unloaded). If you redefine this function, **make sure to call the original method**
     * (`RuntimeObject.prototype.onDestroyFromScene.call(this, runtimeScene);`).
     *
     * @param instanceContainer The container owning the object.
     */
    onDestroyFromScene(instanceContainer: gdjs.RuntimeInstanceContainer): void {
      const theLayer = instanceContainer.getLayer(this.layer);
      const rendererObject = this.getRendererObject();
      if (rendererObject) {
        theLayer.getRenderer().removeRendererObject(rendererObject);
      }
      const rendererObject3D = this.get3DRendererObject();
      if (rendererObject3D) {
        theLayer.getRenderer().remove3DRendererObject(rendererObject3D);
      }
      for (let j = 0, lenj = this._behaviors.length; j < lenj; ++j) {
        this._behaviors[j].onDestroy();
      }
      this.destroyCallbacks.forEach((c) => c());
      this.clearEffects();
    }

2) Deleting objects when changing scenes

In theory, this should be faster because we don't care about existing object instances and can erase the entire structure. @D8H suggested this is being done in GDevelop/GDJS/Runtime/RuntimeInstanceContainer.ts, by assigning the instanceContainer array to an empty array [].

    /**
     * Clear any data structures to make sure memory is freed as soon as
     * possible.
     */
    _destroy() {
      // It should not be necessary to reset these variables, but this help
      // ensuring that all memory related to the container is released immediately.
      this._layers = new Hashtable();
      this._orderedLayers = [];
      this._objects = new Hashtable();
      this._instances = new Hashtable();
      this._instancesCache = new Hashtable();
      this._objectsCtor = new Hashtable();
      this._allInstancesList = [];
      this._instancesRemoved = [];
    }

However, I want to understand how that code gets executed when an event uses the "Change the Scene" action.
The "Change the scene" action is defined in: Core\GDCore\Extensions\Builtin\SceneExtension.cpp:

  extension
      .AddAction("Scene",
                 _("Change the scene"),
                 _("Stop this scene and start the specified one instead."),
                 _("Change to scene _PARAM1_"),
                 "",
                 "res/actions/replaceScene24.png",
                 "res/actions/replaceScene.png")
      .SetHelpPath("/interface/scene-editor/events")
      .AddCodeOnlyParameter("currentScene", "")
      .AddParameter("sceneName", _("Name of the new scene"))
      .AddParameter("yesorno", _("Stop any other paused scenes?"))
      .SetDefaultValue("true")
      .MarkAsAdvanced();

That scene function is defined in GDJS\GDJS\Extensions\Builtin\SceneExtension.cpp:

  GetAllActions()["Scene"].SetFunctionName(
      "gdjs.evtTools.runtimeScene.replaceScene");

That "replaceScene" function is defined in GDJS\Runtime\events-tools\runtimescenetools.ts:

      export const replaceScene = function (
        runtimeScene: gdjs.RuntimeScene,
        newSceneName: string,
        clearOthers: boolean
      ) {
        if (!runtimeScene.getGame().getSceneData(newSceneName)) {
          return;
        }
        runtimeScene
          .getScene()
          .requestChange(
            clearOthers
              ? gdjs.SceneChangeRequest.CLEAR_SCENES
              : gdjs.SceneChangeRequest.REPLACE_SCENE,
            newSceneName
          );
      };

requestChange and SceneChangeRequest are described in GDJS\Runtime\runtimescene.ts:

    /**
     * Request a scene change to be made. The change is handled externally (see gdjs.SceneStack)
     * thanks to getRequestedChange and getRequestedScene methods.
     * @param change One of RuntimeScene.CONTINUE|PUSH_SCENE|POP_SCENE|REPLACE_SCENE|CLEAR_SCENES|STOP_GAME.
     * @param sceneName The name of the new scene to launch, if applicable.
     */
    requestChange(change: SceneChangeRequest, sceneName?: string) {
      this._requestedChange = change;
      if (sceneName) this._requestedScene = sceneName;
    }

  //The flags to describe the change request by a scene:
  export enum SceneChangeRequest {
    CONTINUE,
    PUSH_SCENE,
    POP_SCENE,
    REPLACE_SCENE,
    CLEAR_SCENES,
    STOP_GAME,
  }

Now that a requestedChange has been set, I think it is handled by the step function in GDJS\Runtime\scenestack.ts:

    step(elapsedTime: float): boolean {
      if (this._stack.length === 0) {
        return false;
      }
      const currentScene = this._stack[this._stack.length - 1];
      if (currentScene.renderAndStep(elapsedTime)) {
        const request = currentScene.getRequestedChange();

        //Something special was requested by the current scene.
        if (request === gdjs.SceneChangeRequest.STOP_GAME) {
          this._runtimeGame.getRenderer().stopGame();
          return true;
        } else if (request === gdjs.SceneChangeRequest.POP_SCENE) {
          this.pop();
        } else if (request === gdjs.SceneChangeRequest.PUSH_SCENE) {
          this.push(currentScene.getRequestedScene());
        } else if (request === gdjs.SceneChangeRequest.REPLACE_SCENE) {
          this.replace(currentScene.getRequestedScene());
        } else if (request === gdjs.SceneChangeRequest.CLEAR_SCENES) {
          this.replace(currentScene.getRequestedScene(), true);
        } else {
          logger.error('Unrecognized change in scene stack: ' + request);
          return false;
        }
      }
      return true;
    }

Our requestedChange (replace) is performed in that same file:

    /**
     * Start the specified scene, replacing the one currently being played.
     * If `clear` is set to true, all running scenes are also removed from the stack of scenes.
     */
    replace(newSceneName: string, clear?: boolean): gdjs.RuntimeScene {
      if (!!clear) {
        // Unload all the scenes
        while (this._stack.length !== 0) {
          let scene = this._stack.pop();
          if (scene) {
            scene.unloadScene();
          }
        }
      } else {
        // Unload the current scene
        if (this._stack.length !== 0) {
          let scene = this._stack.pop();
          if (scene) {
            scene.unloadScene();
          }
        }
      }
      return this.push(newSceneName);
    }

The unloadScene function is defined in GDJS\Runtime\runtimescene.ts:

    /**
     * Called before a scene is removed from the stack of scenes
     * rendered on the screen.
     */
    unloadScene() {
      if (!this._isLoaded) {
        return;
      }
      if (this._profiler) {
        this.stopProfiler();
      }

      // Notify the global callbacks (which should not release resources yet,
      // as other callbacks might still refer to the objects/scene).
      for (let i = 0; i < gdjs.callbacksRuntimeSceneUnloading.length; ++i) {
        gdjs.callbacksRuntimeSceneUnloading[i](this);
      }

      // Notify the objects they are being destroyed
      const allInstancesList = this.getAdhocListOfAllInstances();
      for (let i = 0, len = allInstancesList.length; i < len; ++i) {
        const object = allInstancesList[i];
        object.onDestroyFromScene(this);
      }

      // Notify the renderer
      if (this._renderer) {
        this._renderer.onSceneUnloaded();
      }

      // Notify the global callbacks (after notifying objects and renderer, because
      // callbacks from extensions might want to free resources - which can't be done
      // safely before destroying objects and the renderer).
      for (let i = 0; i < gdjs.callbacksRuntimeSceneUnloaded.length; ++i) {
        gdjs.callbacksRuntimeSceneUnloaded[i](this);
      }

      this._destroy();

      this._isLoaded = false;
      this.onGameResolutionResized();
    }

The destroy function is defined right below that:

    _destroy() {
      // It should not be necessary to reset these variables, but this help
      // ensuring that all memory related to the RuntimeScene is released immediately.
      super._destroy();
      this._variables = new gdjs.VariablesContainer();
      this._initialBehaviorSharedData = new Hashtable();
      this._eventsFunction = null;
      this._lastId = 0;
      // @ts-ignore We are deleting the object
      this._onceTriggers = null;
    }

And finally, the super._destroy() function is what I listed at the start of this section.

Did I follow the code logic correctly?