Micromatch caching benchmark

micromatch-benchmark.js

/* eslint-disable no-console, import/no-extraneous-dependencies */

const micromatch = require('micromatch');

const NB_PAGES = 50 * 1000;
const NB_MATCHES = 2000;
const STAR_RATIO = 0.1;
const NEGATION_RATIO = 0.1;

const base = 'https://www.example.com';
const categories = ['products', 'news', 'articles'];

const makeId = () =>
  `${Math.random() < STAR_RATIO ? '*' : ''}${Math.floor(
    Math.random() * Math.max(NB_PAGES)
  )}${Math.random() < STAR_RATIO ? '*' : ''}`;
const makeMatchId = () => {
  const res = `${Math.floor(Math.random() * Math.max(NB_PAGES))}`.split('');
  while (Math.random() < STAR_RATIO) {
    const i = Math.floor(Math.random() * res.length);
    res[i] = '*';
  }
  return res.join('');
};
const makeCategory = () =>
  categories[Math.floor(Math.random() * categories.length)];
const makeUrl = () => `${base}/${makeCategory()}/${makeId()}`;
const makeMatchUrl = () =>
  `${
    Math.random() < NEGATION_RATIO ? '!' : ''
  }${base}/${makeCategory()}/${makeMatchId()}`;

const pages = [...new Array(NB_PAGES)].map(makeUrl);
const matches = [...new Array(NB_MATCHES)].map(makeMatchUrl);

// console.log(JSON.stringify(pages, null, 2));
// console.log(JSON.stringify(matches, null, 2));

function uniqArray(arr) {
  return arr.filter((e, i) => arr.indexOf(e) === i);
}

function compareArrays(_arr1, _arr2) {
  const arr1 = uniqArray(_arr1);
  const arr2 = uniqArray(_arr2);
  return (
    arr1.length === arr2.length &&
    arr1.every(elm1 => arr2.includes(elm1)) &&
    arr2.every(elm2 => arr1.includes(elm2))
  );
}

function benchmark({ compile = () => {}, run }) {
  const start = new Date();
  compile();
  const compileEnd = new Date();
  run();

  const runEnd = new Date();
  console.log(
    `Compilation: ${compileEnd - start}ms - Execution: ${runEnd -
      compileEnd}ms - Total: ${runEnd - start}ms`
  );
}

function createMemoizedMicromatchMatcher(_patterns = []) {
  const patterns = typeof _patterns === 'string' ? [_patterns] : _patterns;

  const positiveMatchers = [];
  const negativeMatchers = [];

  patterns.forEach(pattern => {
    // Patterns starting with `!` are negated
    if (pattern.charCodeAt(0) === 33) {
      negativeMatchers.push(micromatch.matcher(pattern.slice(1)));
    } else {
      positiveMatchers.push(micromatch.matcher(pattern));
    }
  });
  return function(str) {
    return (
      positiveMatchers.some(match => match(str)) &&
      !negativeMatchers.some(match => match(str))
    );
  };
}

let resMicromatchBase = [];
function benchmarkMicromatchBase() {
  console.log('Benchmarking micromatch base');
  benchmark({
    run: () => {
      resMicromatchBase = micromatch(pages, matches);
    },
  });
}

const resMicromatch = [];
function benchmarkMicromatch() {
  console.log('Benchmarking micromatch');
  let matcher;
  benchmark({
    compile: () => {
      matcher = createMemoizedMicromatchMatcher(matches);
    },
    run: () => {
      pages.forEach(url => {
        // const cond = micromatch(url, matches).length > 0
        const cond = matcher(url);
        if (cond) {
          resMicromatch.push(url);
        }
      });
    },
  });
}

const resRegExp = [];
function benchmarkRegExp() {
  console.log('Benchmarking RegExp');
  let positiveRegex;
  let negativeRegex;
  benchmark({
    compile: () => {
      const positivePatterns = [];
      const negativePatterns = [];
      matches.forEach(pattern => {
        if (pattern.charCodeAt(0) === 33) {
          negativePatterns.push(pattern);
        } else {
          positivePatterns.push(pattern);
        }
      });
      const positiveRegexSources = positivePatterns.map(
        pattern => micromatch.makeRe(pattern).source
      );
      const negativeRegexSources = negativePatterns.map(
        pattern => micromatch.makeRe(pattern.slice(1)).source
      );
      positiveRegex = new RegExp(`(${positiveRegexSources.join(')|(')})`);
      negativeRegex = new RegExp(`(${negativeRegexSources.join(')|(')})`);
    },
    run: () => {
      for (let i = 0; i < pages.length; ++i) {
        const url = pages[i];
        if (url.match(positiveRegex) && !url.match(negativeRegex)) {
          resRegExp.push(url);
        }
      }
    },
  });
}

console.log(`For NB_PAGES = ${NB_PAGES} - NB_MATCHES = ${NB_MATCHES}`);
console.log();

benchmarkMicromatchBase();
console.log(`${resMicromatchBase.length} elements`);
console.log();

benchmarkMicromatch();
console.log(
  `Correct results: ${compareArrays(resMicromatchBase, resMicromatch)}`
);
console.log();

benchmarkRegExp();
console.log(`Correct results: ${compareArrays(resMicromatchBase, resRegExp)}`);
console.log();

results.txt

For NB_PAGES = 50000 - NB_MATCHES = 2000

Benchmarking micromatch base
Compilation: 0ms - Execution: 9445ms - Total: 9445ms
9502 elements

Benchmarking micromatch
Compilation: 3ms - Execution: 5597ms - Total: 5600ms
Correct results: true

Benchmarking RegExp
Compilation: 431ms - Execution: 9340ms - Total: 9771ms
Correct results: true