1  /**
  2   * Copyright (c) Facebook, Inc. and its affiliates. All Rights Reserved.
  3   *
  4   * This source code is licensed under the MIT license found in the
  5   * LICENSE file in the root directory of this source tree.
  6   */
  7  
  8  // Make sure to run node with --expose-gc option!
  9  
 10  // The times are reliable if about 1% relative mean error if you run it:
 11  
 12  // * immediately after restart
 13  // * with 100% battery charge
 14  // * not connected to network
 15  
 16  /* eslint import/no-extraneous-dependencies: "off" */
 17  
 18  const Benchmark = require('benchmark');
 19  const diffBaseline = require('diff').diffLines;
 20  const diffImproved = require('../build/index.js').default;
 21  
 22  const testBaseline = (a, b) => {
 23    const benchmark = new Benchmark({
 24      fn() {
 25        diffBaseline(a, b);
 26      },
 27      name: 'baseline',
 28      onCycle() {
 29        global.gc(); // after run cycle
 30      },
 31      onStart() {
 32        global.gc(); // when benchmark starts
 33      },
 34    });
 35  
 36    benchmark.run({async: false});
 37  
 38    return benchmark.stats;
 39  };
 40  
 41  const testImproved = function (a, b) {
 42    const benchmark = new Benchmark({
 43      fn() {
 44        // Split string arguments to make fair comparison with baseline.
 45        const aItems = a.split('\n');
 46        const bItems = b.split('\n');
 47  
 48        const isCommon = (aIndex, bIndex) => aItems[aIndex] === bItems[bIndex];
 49  
 50        // This callback obviously does less than baseline `diff` package,
 51        // but avoiding double work and memory churn is the goal.
 52        // For example, `jest-diff` has had to split strings that `diff` joins.
 53        const foundSubsequence = () => {};
 54  
 55        diffImproved(aItems.length, bItems.length, isCommon, foundSubsequence);
 56      },
 57      name: 'improved',
 58      onCycle() {
 59        global.gc(); // after run cycle
 60      },
 61      onStart() {
 62        global.gc(); // when benchmark starts
 63      },
 64    });
 65  
 66    benchmark.run({async: false});
 67  
 68    return benchmark.stats;
 69  };
 70  
 71  const writeHeading2 = () => {
 72    console.log('## Benchmark time for `diff-sequences` versus `diff`\n');
 73    console.log('A ratio less than 1.0 means `diff-sequences` is faster.');
 74  };
 75  
 76  const writeHeading3 = n => {
 77    console.log(`\n### n = ${n}\n`);
 78    console.log('| name | % | ratio | improved | rme | baseline | rme |');
 79    console.log('| :--- | ---: | :--- | :--- | ---: | :--- | ---: |');
 80  };
 81  
 82  const writeRow = (name, percent, statsImproved, statsBaseline) => {
 83    const {mean: meanImproved, rme: rmeImproved} = statsImproved;
 84    const {mean: meanBaseline, rme: rmeBaseline} = statsBaseline;
 85    const ratio = meanImproved / meanBaseline;
 86  
 87    console.log(
 88      `| ${name} | ${percent}% | ${ratio.toFixed(
 89        4,
 90      )} | ${meanImproved.toExponential(4)} | ${rmeImproved.toFixed(
 91        2,
 92      )}% | ${meanBaseline.toExponential(4)} | ${rmeBaseline.toFixed(2)}% |`,
 93    );
 94  };
 95  
 96  const testDeleteInsert = (tenths, more, less) => {
 97    // For improved `diff-sequences` package, delete is often slower than insert.
 98    const statsDeleteImproved = testImproved(more, less);
 99    const statsDeleteBaseline = testBaseline(more, less);
100    writeRow('delete', tenths * 10, statsDeleteImproved, statsDeleteBaseline);
101  
102    // For baseline `diff` package, many insertions is serious perf problem.
103    // However, the benchmark package cannot accurately measure for large n.
104    const statsInsertBaseline = testBaseline(less, more);
105    const statsInsertImproved = testImproved(less, more);
106    writeRow('insert', tenths * 10, statsInsertImproved, statsInsertBaseline);
107  };
108  
109  const testChange = (tenths, expected, received) => {
110    const statsImproved = testImproved(expected, received);
111    const statsBaseline = testBaseline(expected, received);
112    writeRow('change', tenths * 10, statsImproved, statsBaseline);
113  };
114  
115  const getItems = (n, callback) => {
116    const items = [];
117  
118    for (let i = 0; i !== n; i += 1) {
119      const item = callback(i);
120      if (typeof item === 'string') {
121        items.push(item);
122      }
123    }
124  
125    return items.join('\n');
126  };
127  
128  // Simulate change of property name which is usually not same line.
129  // Expected: 0 1 2 3 4 5 6 7 8 9 and so on
130  // Received: 1 2 3 4 x0 5 6 7 8 9 and so on
131  const change2 = i => {
132    const j = i % 10;
133    return j === 4 ? `x${i - 4}` : j < 4 ? `${i + 1}` : `${i}`;
134  };
135  
136  const testLength = n => {
137    const all = getItems(n, i => `${i}`);
138  
139    writeHeading3(n);
140  
141    [2, 4, 8].forEach(tenth => {
142      testDeleteInsert(
143        tenth,
144        all,
145        getItems(n, i => i % 10 >= tenth && `${i}`),
146      );
147    });
148    testChange(
149      1,
150      all,
151      getItems(n, i => (i % 10 === 0 ? `x${i}` : `${i}`)),
152    );
153    testChange(2, all, getItems(n, change2));
154    testChange(
155      5,
156      all,
157      getItems(n, i => (i % 2 === 0 ? `x${i}` : `${i}`)),
158    );
159    testChange(
160      10,
161      all,
162      getItems(n, i => `x${i}`),
163    ); // simulate TDD
164  };
165  
166  writeHeading2();
167  
168  testLength(20);
169  testLength(200);
170  testLength(2000);