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):
| program | 4,096 | 8,192 | 16,384 | 32,768 chars |
|---|---|---|---|---|
for (m of s.matchAll(/b/g)) c++ | 0.17 | 0.30 | 0.88 | 3.57 s (x4.1) |
s.replace(/b/g, function (m) { return 'c'; }) | 0.10 | 0.25 | 0.80 | 3.04 s (x3.8) |
s.replace(/b/g, 'c') (control) | 0.05 | 0.06 | 0.08 | 0.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.
replacewith a function builds the replacer'sstringargument withValue.strAlloc(self.arena, s)per match.- The
%RegExpStringIterator%'snext()callsregexpExecGeneric, which allocates a new string forexecon every call. The copy also drops the cell's cached ASCII flag, which the built-inexecuses 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.