String multi search benchmark

README.md

Takeaways:

• indexOf & includes are a lot faster than regexes for this test set
• aho-corasick implementation ( https://github.com/BrunoRB/ahocorasick ) could be optimized, but the baseline performance is very slow, relative to primitives

 ✓ shared/secretScanning/scan.bench.ts 18972ms
     name                      hz     min     max    mean     p75     p99    p995    p999     rme   samples
   · regex match     6,506,410.47  0.0000  0.9696  0.0002  0.0002  0.0002  0.0002  0.0004  ±0.36%   6506411
   · regex test      7,752,708.05  0.0000  0.0453  0.0001  0.0001  0.0002  0.0002  0.0002  ±0.03%   7752709
   · indexOf loop   20,244,797.80  0.0000  0.1915  0.0000  0.0000  0.0000  0.0001  0.0001  ±1.00%  20244798
   · includes loop  19,030,936.66  0.0000  0.1259  0.0001  0.0000  0.0001  0.0001  0.0001  ±1.00%  19030937
   · corasick              621.73  1.5707  4.1978  1.6084  1.6097  1.7468  1.7919  4.1978  ±0.56%       622

string-multi-search.ts

import { bench } from "vitest";
import Fs from "node:fs";

class AhoCorasick {
  constructor(keywords: string[]) {
    this._buildTables(keywords);
  }

  _buildTables(keywords: string[]) {
    var gotoFn = {
      0: {},
    };
    var output = {};

    var state = 0;
    keywords.forEach(function (word) {
      var curr = 0;
      for (var i = 0; i < word.length; i++) {
        var l = word[i];
        if (gotoFn[curr] && l in gotoFn[curr]) {
          curr = gotoFn[curr][l];
        } else {
          state++;
          gotoFn[curr][l] = state;
          gotoFn[state] = {};
          curr = state;
          output[state] = [];
        }
      }

      output[curr].push(word);
    });

    var failure = {};
    var xs = [];

    // f(s) = 0 for all states of depth 1 (the ones from which the 0 state can transition to)
    for (var l in gotoFn[0]) {
      state = gotoFn[0][l];
      failure[state] = 0;
      xs.push(state);
    }

    while (xs.length) {
      var r = xs.shift();
      // for each symbol a such that g(r, a) = s
      for (var l in gotoFn[r]) {
        var s = gotoFn[r][l];
        xs.push(s);

        // set state = f(r)
        state = failure[r];
        while (state > 0 && !(l in gotoFn[state])) {
          state = failure[state];
        }

        if (l in gotoFn[state]) {
          var fs = gotoFn[state][l];
          failure[s] = fs;
          output[s] = output[s].concat(output[fs]);
        } else {
          failure[s] = 0;
        }
      }
    }

    this.gotoFn = gotoFn;
    this.output = output;
    this.failure = failure;
  }

  search(string: string) {
    var state = 0;
    var results = [];
    for (var i = 0; i < string.length; i++) {
      var l = string[i];
      while (state > 0 && !(l in this.gotoFn[state])) {
        state = this.failure[state];
      }
      if (!(l in this.gotoFn[state])) {
        continue;
      }

      state = this.gotoFn[state][l];

      if (this.output[state].length) {
        var foundStrs = this.output[state];
        results.push([i, foundStrs]);
      }
    }

    return results;
  }
}

const schema = Fs.readFileSync("./shared/schema.ts", "utf8");
const searchWords = ["hello", "hi", "index", "nothing", "string"];
const searchRegex = new RegExp(`(${searchWords.join("|")})`);
const corasick = new AhoCorasick(searchWords);

bench(
  "regex match",
  () => {
    schema.match(searchRegex);
  },
  { time: 1000 }
);

bench(
  "regex test",
  () => {
    searchRegex.test(schema);
  },
  { time: 1000 }
);

bench(
  "indexOf loop",
  () => {
    let found = true;
    for (let word of searchWords) {
      if (schema.indexOf(word) !== -1) found = true;
    }
  },
  { time: 1000 }
);

bench(
  "includes loop",
  () => {
    let found = true;
    for (let word of searchWords) {
      if (schema.includes(word)) found = true;
    }
  },
  { time: 1000 }
);

bench(
  "corasick",
  () => {
    corasick.search(schema);
  },
  { time: 1000 }
);