JavaScript链表引起垃圾回收问题

Question

我已经在JavaScript中实现了以下链表数据结构:

```html

我已经在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;

我这样使用它来更新动画列表：

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

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

node.remove()这行代码会导致我的游戏明显卡顿，我怀疑它在触发垃圾回收。讽刺的是，如果我注释掉node.remove()这行代码并允许链表无限增长，游戏就可以平稳运行。

动画不断地添加和移除。我在动画的update函数中添加了一些日志记录：

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

你可以看到，在迭代链表的过程中，每秒钟会多次进行操作，偶尔会删除一个节点。

如何在不影响性能的情况下实现O(1)的链表删除？

- Maros

---

使用链表的目的是什么？不能只使用数组或对象吗？ - Michał Perłakowski

然后您可以使用一个对象。 - Michał Perłakowski

不要对数据进行解引用，从而导致GC压力。将对象放入另一个数组中，并在下一个创建的对象中使用它，假设它们保持相同的数据模式和大小。如果不是这样，那么您只需要保存数据，直到有一个时间，当GC的影响对应用程序没有影响时再释放。 - Blindman67

@Gothdo 你的意思是我应该将这些动画存储为对象中的键值对，然后使用delete关键字删除它们吗？@Blindman67 那是个好主意。所以这个链表抽象因为GC而变得无意义？ - Maros

你也可以考虑使用 Set。 - Michał Perłakowski

Answer 1

node.remove() 这一行会导致我的游戏出现明显的卡顿。我怀疑它触发了垃圾回收。

不是的。卡顿是因为每次 update 调用只更新了很少的动画。

你的问题是老生常谈的“迭代过程中删除”问题。在你的情况下，它并不会触发稀有的边缘情况错误，而只是停止了迭代：

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;
}

哎呀，简单的解决方法是在产生 yield 前缓存下一个要迭代的节点：

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

（或类似内容），但当下一个节点被删除时，它仍然会失败。更好的方法可能是省略这些行。

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

从节点的remove方法中删除，以便在删除期间保持引用不变。这不会影响GC。

---

另一个解决方案是完全放弃链表-除非您经常在列表中间添加/删除节点在迭代外，否则它过于复杂。在迭代期间过滤旧动画很简单，可以使用一个老式（内存高效的？）Array来完成，甚至可以就地进行：

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;
    });
}

你可以通过在i===j时不重新赋值来优化filter。

- Bergi

---

啊，好发现。我目前正在使用您的简单修复程序来缓存下一个节点。 - Maros