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

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

重现问题的步骤:

从gist获取代码:
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.7ms(即使使用JSON.parse -d对象也是如此)，在practice1.performance-test中花费约2.3ms。

以下是与要点相同的代码，以供将来引用。

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);

最佳答案

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



关于数据类型，有几篇非常不错的文章:

v8-perf/data-types

v8 performance tips

那么，为什么JSON.parse创建的数组很慢？解析器在创建值时无法正确优化数据结构，结果我们得到的untagged数组为boxed double。但是，我们之后可以使用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运行它