Iteration as array but still accessible by a key

Question

I'm writing my own game engine for simple 2D game and want to iterate children, but for some reason I would like to access each item by a key.

Maybe anybody know any good solutions to my problems below?

Problem #1

I can't use Object.keys and for-in, because simple array iteration has 5x performance boost. Performance critical.

Problem #2

I would like to add/remove children easily by passing child object to function: scene.add(child); scene.remove(child);

Solution #1?

I can create data structure with both children array and object. Use add/remove methods to fill both array and object in same time. Of course in a case of changing children property, you will break the stuff, but it is not my case, you have to use add/remove.

Real example

Rendering. Each shader program has children array.

_render(...args) {
    const [gl, scene, camera] = args;
    const { childrenByShaderProgram } = scene;
    const dt = 0;

    gl.clearColor(0, 0, 0, 1);
    gl.clear(gl.COLOR_BUFFER_BIT);

    camera.updateViewMatrix();

    scene.beforeUpdate(dt);

    Object.keys(childrenByShaderProgram).forEach(uuid => {
      const children = childrenByShaderProgram[uuid];
      const sp = children[0].shaderProgram;

      // Per shader program rendering.
      this._useShaderProgram(gl, sp);

      // Update view matrix uniform value.
      sp.updateUniform('u_v', camera.viewMatrix);

      for (let j = 0, len = children.length; j < len; j += 1) {
        const child = children[j];

        // Update attributes and uniforms values.
        scene.updateEachChild(child, dt);

        // Apply changes by binding uniforms and attributes.
        sp.bindUniforms(gl);
        sp.bindAttributes(gl);

        // tbd @andytyurin texture implementation should be here.
        gl.drawArrays(gl.TRIANGLE_STRIP, 0, Math.floor(child.vertices.length / 2));
      }
    });

    scene.afterUpdate(dt);

    window.requestAnimationFrame(() => this._render(...args));
  }

Next will be harder... scene.js

export class Scene {
  constructor() {
    this.childrenByShaderProgram = {};
  }

  add(child) {
    const { children } = child;

    if (children && children.legnth) {
      // Container object.
      for (let i = 0, l = children.length; i < l; i += 1) {
        const nestedChild = children[0];
        const nestedChildren = nestedChild.children;

        // Children recursion.
        if (nestedChildren && nestedChildren.length) {
          this.add(nestedChild);
        } else {
          this._addChild(nestedChild);
        }
      }
    } else {
      this._addChild(child);
    }
  }

  remove(child) {
    const { children } = child;

    if (children && children.legnth) {
      // Container object.
      for (let i = 0, l = children.length; i < l; i += 1) {
        const nestedChild = children[0];
        const nestedChildren = nestedChild.children;

        // Children recursion.
        if (nestedChildren && nestedChildren.length) {
          this.remove(nestedChild);
        } else {
          this._removeChild(nestedChild);
        }
      }
    } else {
      this._removeChild(child);
    }
  }

  _addChild(child) {
    const spUuid = child.shaderProgram.uuid;

    if (child.renderingIdx) {
      throw new Error(
        'Could not add child as it is already added to the scene'
      );
    }

    this.childrenByShaderProgram[spUuid] =
      this.childrenByShaderProgram[spUuid] || [];

    child.renderingIdx = this.childrenByShaderProgram[spUuid].length;
    this.childrenByShaderProgram[spUuid].push(child);
  }

  _removeChild(child) {
    const spUuid = child.shaderProgram.uuid;
    const { renderingIdx } = child;

    if (!renderingIdx) {
      throw new Error(
        'Could not remove child which has not been added to the scene'
      );
    }

    const shaderProgramChildren = this.childrenByShaderProgram[spUuid];
    const lenMinusOne = shaderProgramChildren.length - 1;

    if (renderingIdx === 0) {
      this.childrenByShaderProgram[spUuid] = shaderProgramChildren.slice(1);
    } else if (renderingIdx === lenMinusOne) {
      this.childrenByShaderProgram[spUuid] = shaderProgramChildren.slice(
        0,
        lenMinusOne
      );
    } else {
      this.childrenByShaderProgram[spUuid] = [
        ...shaderProgramChildren.slice(0, renderingIdx),
        ...shaderProgramChildren.slice(renderingIdx + 1)
      ];
    }
  }

  beforeUpdate(children, dt) {}

  updateEachChild(child, dt) {
    // Make appropriate calculations of matrices.
    child.update();
  }

  afterUpdate(children, dt) {}
}

export default Scene;

In example I'm using renderingIdx to remove child faster from array, but I don't want to keep any properties inside each of my child. So as alternative I can keep children in two variants as key-value and Array. It will give same performance while rendering and same performance of adding and removing children from/to scene.

Thank you!

Answer 1

The solution you came up with is the way to go. To keep track of the keys, it might be good to write a wrapper class:

class LookupArray {
 constructor(key, ...entries) {
  this.key = key;
  this.array = [];
  this.hash = {};
  this.push(...entries);
  }
  push(...entries) {
   for(const entry of entries) {
     this.hash[entry[this.key]] = entry;
     this.array.push(entry);
    }
   return entry.length;
  }
  get(id) {
  return this.hash[id] || this.array[id];
  }
}

So one can do:

const lookup = new LookupArray("length", "abcd", "defghi");
console.log(
  lookup.get(0), // "abcd"
  lookup.get(4), // "abcd"
);

for(const entry of lookup.array)
  console.log(entry);

---

But i guess you can achieve similar performance with less memory through Object.entries as outlined in the comments.