执行时间 process.hrtime() return 截然不同的结果

Question

我无法解释为什么我的性能测试 return 在 2 种不同类型的运行上有显着不同的结果。

重现问题的步骤：

从要点获取代码： https://gist.github.com/AVAVT/83685bfe5280efc7278465f90657b9ea
运行 node practice1.generator
运行 node practice1.performance-test

practice1.generator 应该生成一个 test-data.json 文件，并将一些搜索算法执行时间记录到控制台中。之后，practice1.performance-test 从 test-data.json 读取，并对相同的数据执行完全相同的评估函数。

我的机器上的输出一直与此类似：

> node practice1.generator
Generate time: 9,307,061,368 nanoseconds
Total time using indexOf             : 7,005,750 nanoseconds
Total time using for loop            : 7,463,967 nanoseconds
Total time using binary search       : 1,741,822 nanoseconds
Total time using interpolation search: 915,532 nanoseconds

> node practice1.performance-test
Total time using indexOf             : 11,574,993 nanoseconds
Total time using for loop            : 8,765,902 nanoseconds
Total time using binary search       : 2,365,598 nanoseconds
Total time using interpolation search: 771,005 nanoseconds

请注意 indexOf 和 binary search 与其他算法相比执行时间的差异。

如果我重复运行node practice1.generator或node practice1.performance-test，结果还是比较一致的

现在这太麻烦了，我找不到办法弄清楚哪个结果是可信的，以及为什么会出现这种差异。它是由生成的测试数组与 JSON.parse-d 测试数组之间的差异引起的吗？还是process.hrtime()造成的；还是我什至无法理解的一些未知原因？

更新：我追踪到 indexOf 案例的原因是因为 JSON.parse。在practice1.generator里面，tests数组就是原来生成的数组；而在 practice1.performance-test 中，数组是从 json 文件中读取的，并且可能以某种方式与原始数组不同。

如果在 practice1.generator 内，我改为 JSON.parse() 来自字符串的新数组：

var tests2 = JSON.parse(JSON.stringify(tests));

performanceUtil.performanceTest(tests2);

indexOf 的执行时间现在在两个文件上是一致的。

> node practice1.generator
Generate time: 9,026,080,466 nanoseconds
Total time using indexOf             : 11,016,420 nanoseconds
Total time using for loop            : 8,534,540 nanoseconds
Total time using binary search       : 1,586,780 nanoseconds
Total time using interpolation search: 742,460 nanoseconds

> node practice1.performance-test
Total time using indexOf             : 11,423,556 nanoseconds
Total time using for loop            : 8,509,602 nanoseconds
Total time using binary search       : 2,303,099 nanoseconds
Total time using interpolation search: 718,723 nanoseconds

所以至少我知道 indexOf 运行在原始数组上更好，而在 JSON.parse-d 数组上更差。 还是只知道原因，不知道为什么。

二进制搜索执行时间在 2 个文件上保持不同，在 practice1.generator 中始终花费约 1.7 毫秒（即使使用 JSON.parse-d 对象) 和 practice1.performance-test.

中的 ~2.3ms

下面是与要点中相同的代码，以供将来参考。

性能-utils.js:

'use strict';

const performanceTest = function(tests){
  var tindexOf = process.hrtime();
  tests.forEach(testcase => {
    var result = testcase.input.indexOf(testcase.target);

    if(result !== testcase.output) console.log("Errr", result, testcase.output);
  });
  tindexOf = process.hrtime(tindexOf);

  var tmanual = process.hrtime();
  tests.forEach(testcase => {
    const arrLen = testcase.input.length;
    var result = -1;
    for(var i=0;i<arrLen;i++){
      if(testcase.input[i] === testcase.target){
        result = i;
        break;
      }
    }

    if(result !== testcase.output) console.log("Errr", result, testcase.output);
  });
  tmanual = process.hrtime(tmanual);

  var tbinary = process.hrtime();
  tests.forEach(testcase => {
    var max = testcase.input.length-1;
    var min = 0;
    var check, num;
    var result = -1;

    while(max => min){
      check = Math.floor((max+min)/2);
      num = testcase.input[check];

      if(num === testcase.target){
        result = check;
        break;
      }
      else if(num > testcase.target) max = check-1;
      else min = check+1;
    }

    if(result !== testcase.output) console.log("Errr", result, testcase.output);
  });
  tbinary = process.hrtime(tbinary);


  var tinterpolation = process.hrtime();
  tests.forEach(testcase => {
    var max = testcase.input.length-1;
    var min = 0;
    var result = -1;
    var check, num;

    while(max > min && testcase.target >= testcase.input[min] && testcase.target <= testcase.input[max]){
      check = min +  Math.round((max-min) * (testcase.target - testcase.input[min]) / (testcase.input[max]-testcase.input[min]));
      num = testcase.input[check];

      if(num === testcase.target){
        result = check;
        break;
      }
      else if(testcase.target > num) min = check + 1;
      else max = check - 1;
    }

    if(result === -1 && testcase.input[max] == testcase.target) result = max;

    if(result !== testcase.output) console.log("Errr", result, testcase.output);
  });
  tinterpolation = process.hrtime(tinterpolation);

  console.log(`Total time using indexOf             : ${(tindexOf[0] * 1e9 + tindexOf[1]).toString().replace(/\B(?=(\d{3})+(?!\d))/g, ",")} nanoseconds`);
  console.log(`Total time using for loop            : ${(tmanual[0] * 1e9 + tmanual[1]).toString().replace(/\B(?=(\d{3})+(?!\d))/g, ",")} nanoseconds`);
  console.log(`Total time using binary search       : ${(tbinary[0] * 1e9 + tbinary[1]).toString().replace(/\B(?=(\d{3})+(?!\d))/g, ",")} nanoseconds`);
  console.log(`Total time using interpolation search: ${(tinterpolation[0] * 1e9 + tinterpolation[1]).toString().replace(/\B(?=(\d{3})+(?!\d))/g, ",")} nanoseconds`);
}

module.exports = { performanceTest }

practice1.generator.js:

'use strict';

require('util');
const performanceUtil = require('./performance-utils');
const fs = require('fs');
const path = require('path');
const outputFilePath = path.join(__dirname, process.argv[3] || 'test-data.json');

const AMOUNT_TO_GENERATE = parseInt(process.argv[2] || 1000);

// Make sure ARRAY_LENGTH_MAX < (MAX_NUMBER - MIN_NUMBER)
const ARRAY_LENGTH_MIN = 10000;
const ARRAY_LENGTH_MAX = 18000;
const MIN_NUMBER = -10000;
const MAX_NUMBER = 10000;

const candidates = Array.from(Array(MAX_NUMBER - MIN_NUMBER + 1), (item, index) => MIN_NUMBER + index);

function createNewTestcase(){
  var input = candidates.slice();
  const lengthToGenerate = Math.floor(Math.random()*(ARRAY_LENGTH_MAX - ARRAY_LENGTH_MIN + 1)) + ARRAY_LENGTH_MIN;

  while(input.length > lengthToGenerate){
    input.splice(Math.floor(Math.random()*input.length), 1);
  }

  const notfound = input.length === lengthToGenerate ?
    input.splice(Math.floor(Math.random()*input.length), 1)[0] : MIN_NUMBER-1;

  const output = Math.floor(Math.random()*(input.length+1)) - 1;
  const target = output === -1 ? notfound : input[output];

  return {
    input,
    target,
    output
  };
}

var tgen = process.hrtime();

var tests = [];
while(tests.length < AMOUNT_TO_GENERATE){
  tests.push(createNewTestcase());
}

fs.writeFileSync(outputFilePath, JSON.stringify(tests));
var tgen = process.hrtime(tgen);
console.log(`Generate time: ${(tgen[0] * 1e9 + tgen[1]).toString().replace(/\B(?=(\d{3})+(?!\d))/g, ",")} nanoseconds`);

performanceUtil.performanceTest(tests);

practice1.performance-test.js:

'use strict';

require('util');
const performanceUtil = require('./performance-utils');
const fs = require('fs');
const path = require('path');
const outputFilePath = path.join(__dirname, process.argv[2] || 'test-data.json');

var tests = JSON.parse(fs.readFileSync(outputFilePath));
performanceUtil.performanceTest(tests);

Answer 1

正如您已经注意到的，性能差异导致比较：generated array 与 JSON.parsed。在这两种情况下我们都有什么：具有相同数字的相同数组？那么查找性能必须相同吗？没有。

Every Javascript engine has various data type structures for representing same values(numbers, objects, arrays, etc). In most cases optimizer tries to find out the best data type to use. And also often generates some additional meta information, like hidden clases or tags for arrays.

有几篇关于数据类型的非常好的文章：

那么为什么 JSON.parse 创建的数组很慢？解析器在创建值时没有正确优化数据结构，结果我们得到 untagged 数组和 boxed 双精度数。但是我们可以在之后使用 Array.from 优化数组，在你的情况下，与生成的数组一样，你会得到 smi 数组和 smi 数字。这是一个基于您的示例的示例。

const fs = require('fs');
const path = require('path');
const outputFilePath = path.join(__dirname, process.argv[2] || 'test-data.json');

let tests = JSON.parse(fs.readFileSync(outputFilePath));

// for this demo we take only the first items array
var arrSlow = tests[0].input;
// `slice` copies array as-is
var arrSlow2 = tests[0].input.slice();
// array is copied and optimized
var arrFast = Array.from(tests[0].input);

console.log(%HasFastSmiElements(arrFast), %HasFastSmiElements(arrSlow), %HasFastSmiElements(arrSlow2));
//> true, false, false
console.log(%HasFastObjectElements(arrFast), %HasFastObjectElements(arrSlow), %HasFastObjectElements(arrSlow2));
//> false, true, true
console.log(%HasFastDoubleElements(arrFast), %HasFastDoubleElements(arrSlow), %HasFastDoubleElements(arrSlow2));
//> false, false, false

// small numbers and unboxed doubles in action
console.log(%HasFastDoubleElements([Math.pow(2, 31)]));
console.log(%HasFastSmiElements([Math.pow(2, 30)]));

运行它与 node --allow-natives-syntax test.js

Answer 2

OK...首先让我们谈谈测试策略...

运行这个测试多次给出了令人难以置信的不同结果，每个点都波动很大......在这里查看结果

https://docs.google.com/spreadsheets/d/1Z95GtT85BljpNda4l-usPjNTA5lJtUmmcY7BVB8fFGQ/edit?usp=sharing

测试更新后（运行连续 100 次测试并计算平均值）我认为执行时间的主要差异是：

indexOf 和 for 循环在 GENERATOR 场景中运行得更好
二进制搜索和插值搜索在 JSON-parse 场景中工作得更好

请先查看 google 文档...

好的..太好了...这件事更容易解释...基本上我们陷入了随机内存访问（二进制，插值搜索）和连续内存访问(indexOf, for) 给出不同的结果

嗯。让我们深入了解 NodeJS 的内存管理模型

首先NodeJS有几种数组表示法，我其实只知道两种- numberArray，objectArray（表示可以包含任何类型值的数组）

让我们看看 GENERATOR 场景：

在初始数组创建期间，NodeJS ABLE 检测您的数组只包含数字，因为数组仅从数字开始，什么都没有其他类型的添加到它。这导致使用简单的内存分配策略，只有原始的整数行在内存中一个一个地移动...

数组在内存中表示为array of raw numbers，很可能只有memory paging table在这里起作用

这个事实清楚地解释了为什么 CONSECUTIVE 内存访问 在这种情况下效果更好。

让我们看看JSON-解析场景：

在 JSON 的解析结构中 JSON 是不可预测的（NodeJS 使用流 JSON 解析器（99.99% 置信度）），每个值都被认为是最适合 JSON 正在解析，所以...

数组在内存中表示为 array of references to the numbers，只是因为在解析 JSON 时，此解决方案在大多数情况下效率更高（没人关心（魔鬼））

就我们在堆中按小块分配内存而言，内存会以更流畅的方式填充

同样在这个模型中 RANDOM 内存访问 给出了更好的结果，因为 NodeJS 引擎没有选项 - 为了优化访问时间，它创造了很好的 prefix tree either hash map 提供了持续访问随机内存访问场景

中的时间

这很好地解释了为什么 JSON-parse 场景在二进制插值搜索中获胜

执行时间 process.hrtime() return 截然不同的结果

Execution time with process.hrtime() return vastly different result

javascript

execution-time

node.js

ecmascript-6