Motivation for this change

I use the micromatch library to support processing include/exclude glob patterns for file search in the GitHub Repositories extension for VS Code, which integrates with github.dev to allow users to browse repos without cloning them locally. I recently received a report that file search in a github.dev repo was not working for a user, tracked as microsoft/vscode-remote-repositories-github#156. It turned out that it was working, but was just taking a very long time.

By adding some timestamped log statements to the micromatch library code, I isolated the bottleneck to this block of code in the micromatch.not function:

In my case, items contained 5mil elements, and matches contained 42k elements. This resulted in the library spending almost 9 minutes in micromatch.not. 99.2% of that time was spent in the block of code above.

Here's an example of the logging I added in micromatch.not:

const postProcess = Date.now();
console.log(`[ MICROMATCH.NOT] Got ${matches.length} matches and ${items.length} items, postprocessing...`);

for (let item of items) {
  if (!matches.includes(item)) {
    result.add(item);
  }
}
console.log(` [ MICROMATCH.NOT] Done postprocessing in ${Date.now() - postProcess} ms, got ${result.size} results`);

And here are the numbers when run on the inputs mentioned above:

[ MICROMATCH] Done processing 42478 matches
[ MICROMATCH.NOT] Got 42478 matches and 5453280 items, postprocessing...
 [ MICROMATCH.NOT] Done postprocessing in 522035 ms, got 54902 results
[ GLOBFILTER] Done processing micromatch in 525728ms

Impact of this change

With the change in this PR, this cuts the postprocessing time on my machine from 525728ms to 924ms, yielding an approximately 500x speedup in the postprocessing step. Overall, the time spent in the micromatch.not function goes from 525728ms to 4687ms, which is approximately a 100x improvement for consumers of the micromatch.not function:

  let matches = new Set(micromatch(list, patterns, { ...options, onResult }));

  for (let item of items) {
    if (!matches.has(item)) {
      result.add(item);
    }
  }

[ MICROMATCH] Done processing 42478 matches
[ MICROMATCH.NOT] Got 42478 matches and 5453280 items, postprocessing...
 [ MICROMATCH.NOT] Done postprocessing in 924 ms, got 54902 results
[ GLOBFILTER] Done processing micromatch.not in 4687ms