Trie vs Alternation

Benchmark created on December 14, 2025

Setup

const keywords = [
  'abstract', 'arguments', 'await', 'boolean', 'break', 'byte', 'case', 'catch',
  'char', 'class', 'const', 'continue', 'debugger', 'default', 'delete', 'do',
  'double', 'else', 'enum', 'eval', 'export', 'extends', 'false', 'final',
  'finally', 'float', 'for', 'function', 'goto', 'if', 'implements', 'import',
  'in', 'instanceof', 'int', 'interface', 'let', 'long', 'native', 'new',
  'null', 'package', 'private', 'protected', 'public', 'return', 'short', 'static',
  'super', 'switch', 'synchronized', 'this', 'throw', 'throws', 'transient', 'true',
  'try', 'typeof', 'var', 'void', 'volatile', 'while', 'with', 'yield'
];

const testText = 'function test() { const x = 0; let y = null; for (let i = 0; i < 10; i++) { if (true) return false; } }'.repeat(100);

// Current approach
const current = new RegExp('\\b(?:' + keywords.sort((a,b) => b.length - a.length).map(w => 
  w.split('').map(c => {
    const u = c.toUpperCase(), l = c.toLowerCase();
    return u === l ? RegExp.escape(c) : `[${RegExp.escape(u)}${RegExp.escape(l)}]`;
  }).join('')
).join('|') + ')\\b', 'g');

// Trie approach (simplified - hardcoded for these keywords)
const trie = new RegExp('\\b(?:[Aa](?:[Bb]stract|rguments|wait)|[Bb](?:oolean|reak|yte)|[Cc](?:a(?:se|tch)|har|lass|on(?:st|tinue))|[Dd](?:e(?:bugger|fault|lete)|o(?:uble)?)|[Ee](?:lse|num|val|x(?:port|tends))|[Ff](?:alse|inal(?:ly)?|loat|or|unction)|[Gg]oto|[Ii](?:f|mp(?:lements|ort)|n(?:stanceof|t(?:erface)?)?)|[Ll](?:et|ong)|[Nn](?:ative|ew|ull)|[Pp](?:ackage|r(?:ivate|otected)|ublic)|[Rr]eturn|[Ss](?:hort|tatic|u(?:per|per)|witch|ynchronized)|[Tt](?:h(?:is|row(?:s)?)|r(?:ansient|ue|y)|ypeof)|[Vv](?:ar|oid|olatile)|[Ww](?:hile|ith)|[Yy]ield)\\b', 'g');

Test runner

current.lastIndex = 0;
const m = [...testText.matchAll(current)];

trie.lastIndex = 0;
const m = [...testText.matchAll(trie)];

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published on December 14, 2025