在 Javascript 中使用弱引用查找 table

Question

我有一个树结构，其中的元素是动态添加和删除的。这些元素是从网络动态加载的。我想要实现的是查找 table 将元素的 id 映射到树中的实际元素。现在，使用简单的 Map 或 Object 时的问题是它持有对树元素的强引用，这会在一段时间后使内存膨胀。由于 node >= 14.6.0 和 Chrome >= 84 supposedly support WeakRef's 我想我可以制作一个 Map 将 WeakRefs 保存到我的树元素然后简单地 deref() 并查看元素是否仍然存在大约。我试图对此进行测试，但它似乎不起作用。我的最小测试如下所示：

const lookup = new Map();
let element = new Object({id:"someid", data: {}});

lookup.set(element.id, new WeakRef(element));
console.dir(lookup.get("someid").deref());
// as expected output is { id: 'someid', data: {} }

element = null;
console.log(element);
// as expected output is null

// simply calling global.gc() didn't work
// so i made this loop which allocates mem *and* calls global.gc() to
// force garbage collection
// problem: infinite loop because deref always returns the dereferenced
// value which should have gone since element was set to null

while (lookup.get("someid").deref()) {
  const a = new Array(1000);
  // enabled with --expose-gc in node
  global.gc();
}

console.dir(lookup.get("someid").deref());

正如上面评论中所写，问题是循环永远不会结束因为 deref 调用总是 returns 一个值，尽管元素是 var 被设置为空。

我是不是漏掉了什么？如果不是，这就是它应该如何工作，我怎样才能实现拥有弱引用映射的目标（WeakMap 不是这里的一个选项，因为我将有一个 O(n) 成本来查找一个元素 id)?.

Answer 1

我认为您的代码运行良好（当然，while 循环和 global.gc() 除外）。如果您运行 Chrome 中的这个测试页面，并且等待一段时间，最终它会在控制台中记录许多 WeakRef 确实已被垃圾收集：https://output.jsbin.com/momelej

Answer 2

这里真正的问题是调用 global.gc() 不会运行完整的 GC 通过。在我下面的测试中，只有当我允许 10 秒的空闲时间时，我才得到完整的 GC。

以下是对您的特定代码的一些观察。如果我在 GC 中添加一个 await delay(5000) 暂停，那么您的对象在 while 循环之前仍未被 GC。但是，如果我添加两个 await delay(5000) 语句或一个 await delay(10000) 语句，它会在 while 循环之前进行 GC。因此，GC 显然对时间敏感，调用 global.gc() 显然不是完整的运行 GC。例如，这是您的代码版本，其中 weakref 已被 GC 处理！

function delay(t, v) {
    return new Promise(resolve => {
        setTimeout(resolve, t, v);
    });
}

async function run() {

    const lookup = new Map();
    let element = new Object({ id: "someid", data: {} });

    lookup.set(element.id, new WeakRef(element));
    console.dir(lookup.get("someid").deref());
    // as expected output is { id: 'someid', data: {} }

    element = null;
    await delay(10000);
    console.log(element);
    // as expected output is null

    // if above is delay(5000), then it logs "in while loop"
    // if above is delay(10000), then it does NOT log "in while loop"
    // so the amount of time is important to allow the GC to do its thing
     
    while (lookup.get("someid").deref()) {
        console.log("in while loop");
        break;
    }

    console.dir(lookup.get("someid").deref());
}

run();

在我发现您的代码会延迟 GC 之前，我开始运行一个实验，看看 WeakRef 是否有效。这是显示的代码（具有允许完整 GC 的正确延迟），WeakRef 确实在节点 v14.15 中工作。

这是我的测试代码：

// to make memory usage output easier to read
function addCommas(str) {
    var parts = (str + "").split("."),
        main = parts[0],
        len = main.length,
        output = "",
        i = len - 1;

    while (i >= 0) {
        output = main.charAt(i) + output;
        if ((len - i) % 3 === 0 && i > 0) {
            output = "," + output;
        }
        --i;
    }
    // put decimal part back
    if (parts.length > 1) {
        output += "." + parts[1];
    }
    return output;
}

function delay(t, v) {
    return new Promise(resolve => {
        setTimeout(resolve, t, v);
    });
}

function logUsage() {
    let usage = process.memoryUsage();
    console.log(`heapUsed: ${addCommas(usage.heapUsed)}`);
}

const numElements = 10000;
const lenArrays = 10000;

async function run() {

    const cache = new Map();
    const holding = [];

    function checkItem(n) {
        let item = cache.get(n).deref();
        console.log(item);
    }

    // fill all the arrays and the cache
    // and put everything into the holding array too
    let arr, element;
    for (let i = 0; i < numElements; i++) {
        arr = new Array(lenArrays);
        arr.fill(i);
        element = { id: i, data: arr };

        // temporarily hold onto each element by putting a
        // full reference (not a weakRef) into an array
        holding.push(element);

        // add a weakRef to the Map
        cache.set(i, new WeakRef(element));
    }
    // clean up locals we don't need any more
    element = array = null;

    // should have a big Map holding lots of data
    // all items should still be available
    checkItem(numElements - 1);
    logUsage();

    await delay(5000);
    logUsage();

    // make whole holding array contents eligible for GC
    holding.length = 0;

    // pause for GC, then see if items are available
    // and what memory usage is
    await delay(5000);
    checkItem(0);
    checkItem(1);
    checkItem(numElements - 1);

    // count how many items are still in the Map
    let cnt = 0;
    for (const [index, item] of cache) {
        if (item.deref()) {
            ++cnt;
            console.log(`Index item ${index} still in cache`);
        }
    }
    console.log(`There are ${cnt} items that haven't be GCed in the map`);
    logUsage();
}

run();

而且，我得到的输出是这样的：

{
  id: 9999,
  data: [
    9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999,
    9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999,
    9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999,
    9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999,
    9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999,
    9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999,
    9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999,
    9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999,
    9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999,
    9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999,
    ... 9900 more items
  ]
}
heapUsed: 806,706,120
heapUsed: 806,679,456
undefined
undefined
undefined
There are 0 items that haven't be GCed in the map
heapUsed: 3,412,144

输出中的两行 undefined 和最后一个 heapUsed 表明包装在 weakRef 引用中的对象确实得到了 GC。

因此，在经过足够长的时间延迟且解释器无事可做后，仅具有 weakRef 的数据似乎已被 GC 处理。我还不知道为什么你的例子没有显示，除了我的经验表明仅仅调用 global.gc() 并不一定会像一个真正的空闲解释器那样做所有相同的 GC。所以，我建议你插入一个合法的暂停（就像我在我的例子中所做的那样），看看你是否最终恢复了记忆。

P.S。我发布了 this other question 关于我在处理此答案时发现的 GC 异常。

Answer 3

Am I missing something here?

是的：您缺少链接到的 documentation 中的注释，例如：

If your code has just created a WeakRef for a target object, or has gotten a target object from a WeakRef's deref method, that target object will not be reclaimed until the end of the current JavaScript job (including any promise reaction jobs that run at the end of a script job). That is, you can only "see" an object get reclaimed between turns of the event loop.

当然还有：

Avoid where possible
Correct use of WeakRef takes careful thought, and it's best avoided if possible. It's also important to avoid relying on any specific behaviors not guaranteed by the specification. When, how, and whether garbage collection occurs is down to the implementation of any given JavaScript engine.

也就是说，实现您的目标是完全可能的；您的测试用例太简单了（根据上面引用的注释）无法显示。这是一个固定版本：

const lookup = new Map();

(function () {
  let element = { id: "someid", data: {} };
  lookup.set(element.id, new WeakRef(element));
  element = null;

  console.log(lookup.get("someid").deref());

  setTimeout(() => {
    global.gc();
    console.log(lookup.get("someid").deref());
  }, 0);
})();

在 Javascript 中使用弱引用查找 table

Lookup table with weak references in Javascript

javascript

node.js

lookup

weak-references

lookup-tables