使用process.hrtime()的执行时间会返回截然不同的结果

Question

我无法解释为什么我的性能测试会在两种不同类型的运行中返回显着不同的结果.

重现问题的步骤:

1. 从gist获取代码:https: //gist.github.com/AVAVT/83685bfe5280efc7278465f90657b9ea
2. 跑 node practice1.generator
3. 跑 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.generatorI中而不是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个文件上保持不同,一直占用~1.7ms practice1.generator(即使使用JSON.parse-d对象)和~2.3ms practice1.performance-test.

---

以下是与要点中相同的代码,供将来参考.

/*
 * performance-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 arrayvs JSON.parsed。在这两种情况下我们得到了什么：具有相同数字的相同数组？那么查找性能一定是相同的吗？不。

每个 Javascript 引擎都有不同的数据类型结构来表示相同的值（数字、对象、数组等）。在大多数情况下，优化器会尝试找出要使用的最佳数据类型。并且还经常生成一些附加的元信息，例如数组的hidden clases或tags。

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

• v8-性能/数据类型
• v8 性能技巧

那么为什么创建的数组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