2^23 项后 JSObject 的性能下降

Question

我无法理解下面的代码。在 2^23 (8,388,608) 项之后，其性能显着恶化。我以为这可能与 JSObject 的实现方式有关，但事实证明，如果我将字符串键更改为某种哈希值，性能实际上相当不错。

我想通过这个例子了解 V8 是如何工作的：

function foo() {
    const result = Object.create(null);
    for (let i = 0; i < 25_000_000; i += 1) {
        console.time(`Prop ${i}`);
        result[`prop_${i}`] = i + (Math.random() * 25_000_000);
        console.timeEnd(`Prop ${i}`);
    }
    return result;
}


const a = foo();

%DebugPrint(a);

console.log(a[`prop_24000000`]);
console.log(Object.keys(a).length);

运行它

$ node --allow-natives-syntax file.js

在 2^23 个项目之前记录的时间约为 0.001 毫秒，但之后，每次迭代会增加到大约 1.5 秒。

我也想对其进行分析，看看理论是否正确。如果您有任何理论，请告诉我如何分析它。

提前致谢！

Answer 1

V8 将对象存储在“类”中。通过以唯一的顺序插入唯一的键来形成类。几乎每次您向对象添加键时都会发生这种情况，它会分支并且您有一个新的类布局。如果您了解其他编程语言中的链接列表，这就是这些类在内存中的布局结构。

例如：

const obj = { a: 1 } // Class 1 Object
obj.b = 2; // Class 2 Object
// Here, obj's class is replaced by Class 2
// Class 2's memory structure is
// Keys: b
// Values: 2
// extends: Class 1 Object (pointer to the previous instantiation of Class 1)

// Class 1's memory structure:
// Keys: a
// Values: 1
// extends: nothing.

如果每次添加新键时都会发生此过程，您可以想象内存中的类数量。我不知道具体为什么插入时间超过 1.5 秒，但它可能与您使用的内存量有关，并且 V8 在添加另一个类之前对对象进行了某种分析，可以时间为 O(n)。由于指针压缩，V8 的内存也限制在 2-4GB 左右，因此在操作这么大的对象时也可以发挥很大的作用。

这就是 Map() 类存在的原因。类对于实际的 Hashmap 来说并不是什么东西。

当然，这包括许多简化和我的一些猜测。我鼓励您通过 V8 博客了解自己！

https://v8.dev/blog/fast-properties

https://v8.dev/blog/oilpan-pointer-compression

https://v8.dev/blog/fast-super