执行时间与process.hrtime()返回的结果大相径庭。

I'm having trouble explaining why my performance test return significantly different results on 2 different types of run.

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

Steps to reproduce issue:

步骤来复制问题:

1. Get the code from gist: https://gist.github.com/AVAVT/83685bfe5280efc7278465f90657b9ea
2. 从gist获得代码:https://gist.github.com/avt/83685bfe5280efc7278465f90657b9ea
3. Run node practice1.generator
4. 运行节点practice1.generator
5. Run node practice1.performance-test
6. 运行节点practice1.performance-test

practice1.generator should generate a test-data.json file, and log some searching algorithm execution time into the console. After that, practice1.performance-test reads from test-data.json, and perform the exact same evaluation function on that same data.

practice1。生成器应该生成一个测试数据。json文件，并将一些搜索算法执行时间记录到控制台。在那之后,practice1。性能测试从测试数据读取。json，并在相同的数据上执行完全相同的评估功能。

The output on my machine is consistently similar to this:

我的机器上的输出始终类似如下:

> 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

Note the difference in execution time in the case of indexOf and binary search comparing to the other algorithms.

注意索引和二进制搜索与其他算法在执行时间上的差异。

If I repeatedly run node practice1.generator or node practice1.performance-test, the result is quite consistent though.

如果我反复运行node practice1。practice1生成器或节点。性能测试，结果是相当一致的。

Now this is so troubling, I can't find a way to figure out which result is credible, and why such differences occur. Is it caused by a difference between the generated test array vs JSON.parse-d test array; or is it caused by process.hrtime(); or is it some unknown reason I couldn't even fathom?

这实在是太麻烦了，我找不到一种方法来找出哪一种结果是可信的，为什么会出现这种差异。它是由生成的测试数组与JSON之间的差异引起的吗?parse-d测试数组;还是由process.hrtime()引起的;或者是我无法理解的未知原因?

---

Update: I have traced the cause of the indexOf case to be because of JSON.parse. Inside practice1.generator, the tests array is the original generated array; while in practice1.performance-test the array is read from the json file and is probably different from the original array somehow.

更新:我已经跟踪了导致indexOf case的原因是由于JSON.parse。practice1内部。生成器，测试数组是原始生成的数组;而在practice1。性能测试从json文件中读取数组，并且可能与原始数组有某种不同。

If within practice1.generator I instead JSON.parse() a new array from the string:

如果practice1之内。生成器I而不是JSON.parse()从字符串中创建一个新数组:

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

performanceUtil.performanceTest(tests2);

The execution time of indexOf is now consistent on both files.

索引的执行时间在两个文件上都是一致的。

> 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

So at least I know indexOf run better on the original array and worse on a JSON.parse-d array. Still I only know the reason, no clue why.

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

The Binary search execution time remain different on 2 files, consistently taking ~1.7ms in practice1.generator (even when using a JSON.parse-d object) and ~2.3ms in practice1.performance-test.

在两个文件上，二进制搜索执行时间保持不同，在实践1中始终保持在1.7ms左右。生成器(即使使用JSON)。(解析-d对象)和~2.3ms在实践1.性能测试。

---

Below is the same code as in the gist, provided for future reference purpose.

下面是与主旨相同的代码，供以后参考。

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

2 个解决方案

#1

As you have already noticed, the performance difference leads to the comparison: generated array vs JSON.parsed. What we have in both cases: same arrays with same numbers? So the look up performance must be the same? No.

正如您已经注意到的，性能差异导致了比较:生成的数组与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.

每个Javascript引擎都有不同的数据类型结构来表示相同的值(数字、对象、数组等)。在大多数情况下，优化器试图找出使用的最佳数据类型。并且通常还会生成一些附加的元数据信息，比如隐藏的clases或数组的标记。

There are several very nice articles about the data types:

关于数据类型有几篇很好的文章:

• v8-perf/data-types
• v8-perf /数据类型
• v8 performance tips
• v8性能技巧

So why arrays created by JSON.parse are slow? The parser, when creating values, doesn't properly optimize the data structures, and as the result we get untagged arrays with boxed doubles. But we can optimize the arrays afterwards with Array.from and in your case, same as the generated arrays, you get smi arrays with smi numbers. Here is an example based on your sample.

为什么是JSON创建的数组。解析慢吗?在创建值时，解析器不能正确地优化数据结构，因此，我们会得到带有盒式双打的未标记数组。但是我们可以使用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)]));

Run it with node --allow-natives-syntax test.js

使用node -allow-native -syntax test.js运行它

#2

OK...first of all lets talk about testing strategy...

好吧……首先我们谈谈测试策略……

Running this tests several times gives incredible different results fluctuating a lot for each point... see results here

多次运行这个测试会给你带来难以置信的不同结果。看到结果

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

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

After test update (running 100 tests in a row and calculating average) I score that the main difference in execution times are:

在测试更新(连续运行100个测试并计算平均值)之后，我的评分主要区别在于:

• the indexOf and for loops are working better in GENERATOR scenario
• indexOf和for循环在生成器场景中工作得更好
• the binary search and interpolation search are working better in JSON-parse scenario
• 二进制搜索和插值搜索在json解析场景中工作得更好。

Please look at the google doc before...

请先看看谷歌doc。

OK.. Great... This thing is much more easier to explain... basicly we trapped into situation when RANDOM memory access(binary, interpolation search) and CONSECUTIVE memory access(indexOf, for) give different results

好吧. .伟大的……这件事更容易解释……一般情况下，当随机内存访问(二进制、插值搜索)和连续内存访问(indexOf, for)给出不同的结果时，我们会陷入这种情况

---

Hmmm. Lets go deeper inside the memory management model of NodeJS

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

First of all NodeJS has several array representations, I actually know only two - numberArray, objectArray(means array that can include value of any type)

首先，NodeJS有几个数组表示，实际上我只知道两个数字数组，objectArray(表示数组包含任何类型的值)

Lets look at GENERATOR scenario:

让我们看看生成器场景:

During initial array creation NodeJS is ABLE to detect that your array contains only numbers, as array starting from only numbers, and nothing of other type is added to it. This results in using simple memory allocation strategy, just raw row of integers going one by one in memory...

在初始数组创建期间，NodeJS能够检测到数组只包含数字，因为数组仅从数字开始，并且不添加任何其他类型的数据。这导致使用简单的内存分配策略，即在内存中逐个执行原始的整数行……

Array is represented as array of raw numbers in memory, most likely only memory paging table has an effect here

数组表示为内存中原始数字的数组，很可能只有内存分页表在这里有影响

This fact clearly explains why CONSECUTIVE memory access works better in this case.

这一事实清楚地解释了为什么在这种情况下，连续内存访问更有效。

Lets look at JSON-parse scenario:

让我们看看JSON-parse场景:

During the JSON parsing structure of JSON is unpredictable(NodeJS uses a stream JSON parser(99.99% confidence)), every value is tracted as most cozy for JSON parsing, so...

在JSON解析结构不可预测的过程中(NodeJS使用流JSON解析器(99.99%的信心))，每个值都被认为是最适合JSON解析的，所以……

Array is represented as array of references to the numbers in memory, just because while parsing JSON this solution is more productive in most cases (and nobody cares (devil) )

数组表示为对内存中的数字的引用数组，这是因为在解析JSON时，这个解决方案在大多数情况下效率更高(而且没人在乎)

As far as we allocating memory in heap by small chunks memory gets filled in more fluid way

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

Also in this model RANDOM memory access gives better results, because NodeJS engine has no options - to optimize access time it creates good either prefix tree either hash map which gives constant access time in RANDOM memory access scenarios

此外，在这个模型中，随机内存访问会得到更好的结果，因为NodeJS引擎没有选择——为了优化访问时间，它创建了一个好的前缀树或哈希映射，在随机内存访问场景中，哈希映射提供恒定的访问时间

And this is quite good explanation why JSON-parse scenario wins during binary, interpolation search

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