什么是内部建模的数组这么快或者我做错了什么？

Question

我坐下来对我的实用程序库进行了一些性能优化：goodcore 当我注意到一些意外情况时：Array.indexOf（在节点 10.9 中）查找速度非常快，但并不总是 O(1) .

这是在我的笔记本电脑上找到 10k 大整数数组中的中间元素的部分测试的打印输出。

    Array::indexOf x 828,360,306 ops/sec ±1.25% (87 runs sampled)
    Arr.indexOfElement x 133,620,554 ops/sec ±0.87% (86 runs sampled)
    Arr.indexOfElement (no native) x 172,043 ops/sec ±0.92% (92 runs sampled)
    _.indexOf x 174,273 ops/sec ±0.87% (95 runs sampled)
Fastest is Array::indexOf

每秒 8 亿个 indexOf 很快！

通过缩小数组（200 个条目），它保持相同的数字。将数组增加到 1000k 会减慢到 1582 ops/sec

所以它可能在幕后保留一个哈希图，但不将键查找 space 扩展到某个数字之外，然后进行线性搜索？有谁知道是否是这种情况，那是多少？

或者我的代码有问题：

const SIZE = 10000;
let intArray10k = MocData.numericArray(SIZE, MocDataType.RandomInt, 0, 100000);
let intArray100 = MocData.numericArray(100, MocDataType.RandomInt, 0, 100000);
intArray10k[SIZE/2 - 1] = -1;

function complete(suite: Benchmark.Suite) {
    console.log(chalk.green('Fastest is ' + (suite.filter('fastest') as any).map('name') + "\n"));
}
function cycle(event: any) {
    console.log(chalk.grey("\t" + String(event.target)));
}
export const suites = [ 
    new Benchmark.Suite()
    .add('Array::indexOf', function () {
        intArray10k.indexOf(-1);
    })
    .add('Arr.indexOfElement', function () {
        Arr.indexOfElement(intArray10k, -1);
    })
    .add('Arr.indexOfElement (no native)', function () {
        Test.Env.forceNotNative = true;
        Arr.indexOfElement(intArray10k, -1);
        Test.Env.forceNotNative = false;
    })
    .add('_.indexOf', function () {
        _.indexOf(intArray10k, -1);
    })
    // add listeners
    .on('cycle', function (event: any) {
        cycle(event);
    })
    .on('complete', function () {
        complete(this);
    }),

编辑：感谢@jmrk 提醒您分配值以避免优化它。现在没有 100m 值，时间看起来更合理。仅供参考，高拼接值是由于我拼接并添加相同数量的值，以便保持数组大小。拼接函数好像没有做这个优化

    Array::indexOf x 162,893 ops/sec ±2.05% (87 runs sampled)
    Arr.indexOfElement x 171,492 ops/sec ±0.82% (91 runs sampled)
    Arr.indexOfElement (no native) x 165,929 ops/sec ±1.07% (91 runs sampled)
    _.indexOf x 169,678 ops/sec ±0.84% (92 runs sampled)

最快的是Arr.indexOfElement

    Array::slice x 130,022 ops/sec ±1.02% (91 runs sampled)
    Arr.slice x 131,115 ops/sec ±0.94% (91 runs sampled)
    Arr.shallowCopy x 130,130 ops/sec ±1.29% (89 runs sampled)
    Arr.slice (no native) x 52,057 ops/sec ±0.96% (91 runs sampled)
    Arr.shallowCopy (no native) x 59,676 ops/sec ±0.90% (92 runs sampled)
    _.slice x 60,078 ops/sec ±1.08% (94 runs sampled)

最快的是 Arr.slice,Array::slice,Arr.shallowCopy

    Array::reverse x 18,420 ops/sec ±1.18% (90 runs sampled)
    Arr.reverse x 133,600 ops/sec ±0.74% (92 runs sampled)
    _.reverse x 18,075 ops/sec ±1.83% (85 runs sampled)

最快的是Arr.reverse

    Array::filter x 7,749 ops/sec ±10.31% (88 runs sampled)
    Arr.filter x 11,752 ops/sec ±6.92% (88 runs sampled)
    _.filter x 5,939 ops/sec ±0.64% (93 runs sampled)

最快的是Arr.filter

    Array::forEach x 42,613 ops/sec ±34.98% (87 runs sampled)
    Arr.forEach x 126,806 ops/sec ±23.89% (91 runs sampled)
    _.forEach x 11,489 ops/sec ±1.23% (88 runs sampled)

最快的是Arr.forEach

    Array::map x 17,592 ops/sec ±18.32% (88 runs sampled)
    Arr.map x 39,564 ops/sec ±14.55% (88 runs sampled)
    _.map x 8,419 ops/sec ±1.34% (87 runs sampled)

最快的是Arr.map

    Array::reduce x 29,784 ops/sec ±29.35% (88 runs sampled)
    Arr.reduce x 63,781 ops/sec ±18.30% (86 runs sampled)
    _.reduce x 9,444 ops/sec ±2.25% (88 runs sampled)

最快的是Arr.reduce

    Array::splice x 914,209 ops/sec ±1.42% (90 runs sampled)
    Arr.splice x 4,777,243 ops/sec ±0.78% (91 runs sampled)
    Arr.splice (no native) x 5,111,231 ops/sec ±0.90% (88 runs sampled)

最快的是 Arr.splice（非本地）

    Array::splice(1) x 281,206 ops/sec ±10.53% (30 runs sampled)
    Arr.removeAt x 256,947 ops/sec ±1.23% (92 runs sampled)
    Arr.removeAt (no native) x 110,562 ops/sec ±1.03% (91 runs sampled)

最快的是 Array::splice(1),Arr.removeAt

    Array::find x 124,197 ops/sec ±32.06% (90 runs sampled)
    Arr.find x 159,169 ops/sec ±9.55% (92 runs sampled)
    _.find x 23,077 ops/sec ±1.12% (88 runs sampled)

最快的是Arr.find

Answer 1

这里是 V8 开发人员。当您看到每秒数亿次操作时，通常意味着优化编译器丢弃了测试代码，而您正在测量的只是一个空循环。您可以使用命令行标志 --print-opt-code 来检查。通常有效的解决方法是将结果分配给全局变量，如下所示：

var result;
function easily_misleading_microbenchmark() {
  result = intArray10k.indexOf(-1);
}
for (var i = 0; i < 1e6; i++) {
  easily_misleading_microbenchmark();
}

让编译器误以为结果是用来做某事的。

小心微基准测试，因为它们很容易误导您得出错误的结论！ :-)

一般来说，对于包含 n 个元素的数组，预计 Array.indexOf(value) 的复杂度为 O(n)。它永远不会是 O(1)。（如果你的测量结果是O(1)，那么你测量的任何东西都不是Array.indexOf()。）

什么是内部建模的数组这么快或者我做错了什么？

What are arrays modelled as internally to be this fast or what am I doing wrong?

arrays

performance

v8

node.js