Mitigate memory consumption

[masklinn]

As can be seen from the comparison bench (1af15c1) the peak memory footprint of regex-filtered is much higher than that of FilteredRE2. It might not be the worst issue ever as 135MiB is probably not a deal-breaker (especially with the goal of using it in ua-parser/uap-python where we can hopefully get rid of the entire Python-side regex overhead)), but it's still an unfortunate amount compared to 45MiB.

I tried doing basic "obvious" optimisations like switching over to u32 ids as in re2, but that had essentially no effect, which makes sense after some back of the enveloppe calculations: the base dataset has ~600 regex, ~2000 entries and 3000 atoms, tops¹, so we're saving about 4B * 3000 = 12KiB in atom_to_entry, and maybe 20 bytes per entry in parents and regexps links if we're super optimistic for ~40KiB, that's out-the-ass but even if every entry had 600 regexps and 2000 parents (which is obviously impossible and way beyond the upper end) that'd still only be 2000 * 600 * 4 + 2000 * 2000 * 4 ~ 20MiB which falls well short of the observed difference.

After doing some comparisons between re2 and regex, it looks like a large part of the issue is likely due to compiled regexes taking a lot more memory in regex than in re2, an order of magnitude is routine.

What do? Possible avenues to investigate:

• switch to regex::bytes and disable unicode mode, this is not documented but it seems unlikely regexes.yaml regex need unicode semantics given JS regexes have basically none (afaik neither /u nor /v alter the way the basic \d, \w or \s character classes work, those are asci-only) that returns bytes data which is not great...

• convert bounded repetitions on the fly, they cause 10~100x increase in memory use compared to unbounded repetitions

  > echo -n ".+" | cargo r -qr -- -q
  7784 4838
  > echo -n ".{0,100}" | cargo r -qr -- -q
  140624 118326
  

  regexes.yaml has a bunch of them for redos mitigation purposes (ua-parser/uap-core@6e65445) but regex is not a backtracking engine so they make no difference, the biggest issue there is no strict equivalence, ua-parser/uap-core@6e65445 updated the unbounded repetition to anything from {0,20} to {1,300}... overall it's probably safe to drop anything with a 2-digit upper bound.

  NOTE: for simplicity can just remove the upper bound (rather than convert to * and +) as internally regex desugars * to {0,} and + to {1,}.

• this could also be applied to the character classes by splatting them to their ASCII definition:

  > echo -n "[0-9]+" | cargo r -qr -- -q
  10946 1322
  > echo -n "\d+" | cargo r -qr -- -q
  13496 8826
  > echo -n "[a-zA-Z0-9_]" | cargo r -qr -- -q
  6104 2660
  > echo -n "\w" | cargo r -qr -- -q
  80656 57486
  

  the effect is especially sensible with capture, like the extremely common capture of a bunch of numbers as part of a version spec:

  > echo -n "([0-9]+)" | cargo r -qr -- -q
  11330 1818
  > echo -n "(\d+)" | cargo r -qr -- -q
  46328 9994
  

  Of note: this is unnecessary for whitespace which apparently doesn't suffer from this issue, whether matched positively or negatively:

  > echo -n "\s" | cargo r -qr -- -q
  7040 4482
  > echo -n "[\f\n\r\t\v\u0020\u00a0\u1680\u2000-\u200a\u2028\u2029\u202f\u205f\u3000\ufeff]" | cargo r -qr -- -q
  7064 4642
  > echo -n "\S" | cargo r -qr -- -q
  8396 7646
  > echo -n "[^\f\n\r\t\v\u0020\u00a0\u1680\u2000-\u200a\u2028\u2029\u202f\u205f\u3000\ufeff]" | cargo r -qr -- -q
  9996 7914
  

  (all expanded character class definitions from https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Regular_expressions/Character_classes)

The latter two items would let us have our cake and eat it too, as well as reduce the explosion of atoms (and thus possibly their pruning, yielding better discriminatory power). The only drawback is we have to perform the conversion on the fly allocating a translated string from the borrow. So that makes building the extractors a bit more expensive but if it pans out it should significantly reduce memory consumption without affecting runtime costs (and possibly improving them).

Footnotes

1. IIRC, sadly while I noted it didn't work in a local file I didn't keep detailed notes on the parameters and (lack of) effect ↩