página - Lista enlazada de JavaScript que provoca la recolección de basura

formas de agregar javascript en html

Question

Implementé la siguiente estructura de datos de la lista vinculada en JavaScript:

class Node {
  constructor(data, list) {
    this.data = data;
    this.list = list;
    this.prev = null;
    this.next = null;
  }

  remove() {
    if (this.prev) {
      this.prev.next = this.next;
    } else {
      this.list.start = this.next;
    }

    if (this.next) {
      this.next.prev = this.prev;
    } else {
      this.list.end = this.prev;
    }

    this.next = null;
    this.prev = null;
    this.list.length -= 1;
  }
}

class LinkedList {
  constructor() {
    this.end = null;
    this.start = null;
    this.length = 0;
  }

  append(data) {
    const node = new Node(data, this);

    if (!this.start) {
      this.start = node;
    }

    if (this.end) {
      node.prev = this.end;
      this.end.next = node;
    }

    this.end = node;
    this.length += 1;

    return data;
  }

  remove() {
    if (this.end) {
      return this.end.remove();
    }
  }

  *[Symbol.iterator]() {
    let current = this.start;
    while (current) {
      yield current;
      current = current.next;
    }
  }
}

module.exports = LinkedList;

Lo uso así para actualizar una lista de animaciones:

static update(timeDelta) {
  for (let node of this.animations) {
    const animation = node.data;

    if (animation.animating) {
      animation.update(timeDelta);
    } else {
      node.remove();
    }
  }
}

La línea node.remove() causa un retraso muy notable en mi juego. Sospecho que está desencadenando la recolección de basura. Perversamente, si hago un comentario sobre la línea node.remove() y node.remove() que la lista enlazada crezca para siempre, el juego funciona sin problemas.

Las animaciones se agregan y eliminan constantemente. Agregué un poco de registro en la función de update la animación:

start iterating linked list
removing
ms elapsed:  0.45499999999992724
end iterating
start iterating linked list
removing
ms elapsed:  0.455000000000382
end iterating
start iterating linked list
removing
ms elapsed:  0.13000000000010914
end iterating
start iterating linked list
(13) updating
ms elapsed:  2.200000000000273
end iterating

Puede ver que la lista vinculada se itera muchas veces por segundo con un nodo ocasional que se elimina.

¿Cómo puedo lograr la eliminación O (1) de mi lista sin realmente causar una desaceleración en el rendimiento?

Answer 1

La línea node.remove() causa un retraso muy notable en mi juego. Sospecho que está desencadenando la recolección de basura.

Nop. El retraso viene del hecho de que cada llamada de update actualiza solo unas pocas animaciones.

Su problema es el viejo y famoso problema de "eliminar durante la iteración". En su caso, no desencadena errores de casos extremos, simplemente detiene la iteración:

while (current) {
  yield current;
  // after yielding, in the `update` function, we have
  //    node = current
  // and most importantly
  //    node.remove()
  // which assigns (with `this` being `node`)
  //    this.next = null;
  // then the iteration is resumed
  current = current.next;
}

Oops. La solución simple es almacenar en caché el siguiente nodo que se iterará antes de ceder:

let next = this.start;
while (next) {
  const current = next;
  next = current.next;
  yield current;
}

(o algo así), pero por supuesto todavía falla cuando se elimina el siguiente nodo. Un mejor enfoque podría ser omitir las líneas

this.next = null;
this.prev = null;

desde el método remove del nodo, para que las referencias permanezcan intactas durante la eliminación. Esto no afectará a GC.

Otra solución sería eliminar por completo la lista enlazada; se trata de una nueva configuración, a menos que agregue / elimine nodos con frecuencia en el medio de la lista fuera de una iteración . Filtrar antiguas animaciones durante una iteración es simple, se puede hacer con una buena Array antigua (¿eficiente desde el punto de vista de la memoria?), Incluso en el lugar:

function filter(array, callback) {
    var i=0, j=0;
    while (j < array.length) {
        if (callback(array[j]))
            array[i++] = array[j++];
        else
            array[i] = array[j++];
    }
    array.length = i;
}
function update(timeDelta) {
    filter(animations, animation => {
        var keep = animation.animating;
        if (keep) animation.update(timeDelta);
        return keep;
    });
}

(es posible que pueda optimizar el filter al no reasignar cuando i===j )