ReviewOS

zig-utils/zig-js

RegExp: matchAll and replace with a function copy the whole input per match (quadratic)

#971
Closed glennmichael123 opened this 10 days ago ·
10 days ago

Found in the post-#933 survey and re-executed today on a Debug build of main, timed externally. Each program runs over the ASCII subject 'ab '.repeat(N / 3):

program4,0968,19216,38432,768 chars
for (m of s.matchAll(/b/g)) c++0.170.300.883.57 s (x4.1)
s.replace(/b/g, function (m) { return 'c'; })0.100.250.803.04 s (x3.8)
s.replace(/b/g, 'c') (control)0.050.060.080.16 s

node runs each in milliseconds. The survey measured peak memory as quadratic too: 238 MB for matchAll at 32k.

Cause: both loops hand the whole input to user-visible code as a fresh copy on every match.

  • replace with a function builds the replacer's string argument with Value.strAlloc(self.arena, s) per match.
  • The %RegExpStringIterator%'s next() calls regexpExecGeneric, which allocates a new string for exec on every call. The copy also drops the cell's cached ASCII flag, which the built-in exec uses for O(1) index conversion.

The generic match, replace and split loops, used when exec is overridden or subclassed, copy the same way.

A string has no identity, so passing the same value on every call is unobservable. Fix: a value-taking regexpExecGenericValue, one rooted string value per loop shared by exec and the replacer, and matchAll's next() passing its stored __str directly.

Non-ASCII subjects keep a separate O(n) cost per exec (UTF-16 to byte conversion without the ASCII shortcut). That is a larger change, left out of this issue.

10 days ago

Taking this; fix written, gating now.

10 days ago

Fixed in ad1ca10. Every exec loop now reuses one input string instead of copying it per match: matchAll's next(), the replacer's string argument, and the generic match/replace/split paths behind a user-defined exec.

Debug, median of 3, in seconds, on 'ab '.repeat(N/3):

program4k8k16k32k64k131k
matchAll, before0.120.280.843.1611.60–
matchAll, after0.070.100.150.240.440.80
replace(fn), before0.110.250.792.9311.40–
replace(fn), after0.060.080.100.160.260.46
replace('c') control0.070.070.090.140.220.38

A runtime case with 8 checks is pinned, and node passes all of them. The corpus is identical, with 0 flips. Non-ASCII subjects still pay a separate per-exec conversion cost, which is not in this change.

Sign in to comment on this issue.