# RegExp.prototype.exec alternative that doesn't allocate a new object on every execution

**URL:** <https://es.discourse.group/t/regexp-prototype-exec-alternative-that-doesnt-allocate-a-new-object-on-every-execution/215>\
**Category:** 💡 Ideas\
**Created:** [February 9, 2020, 8:29am UTC](https://es.discourse.group/t/regexp-prototype-exec-alternative-that-doesnt-allocate-a-new-object-on-every-execution/215 "2020-02-09T08:29:52Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![pygy](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/pygy/32/231_2.png) [@pygy](https://es.discourse.group/u/pygy)\
**Post date:** [February 9, 2020, 8:29am UTC](https://es.discourse.group/t/regexp-prototype-exec-alternative-that-doesnt-allocate-a-new-object-on-every-execution/215/1 "2020-02-09T08:29:52Z")

</div>

A common pattern when parsing is to use a global RegExp as lexer, and loop while the value returned by `lexer.exec(source)` isn't null.

This is efficient as far as parsing goes, but it allocates an array on every iteration which isn't optimal.

Proposed alternatives (assume `RegExp.success` is a symbol):

```javascript
const result = []
while (lexer.exec(input, result) && result[RegExp.success]) {
  // parse here
}

```

```javascript
const result = []
const into = {result}
while (lexer.exec(input, into) && result[RegExp.success]) {
  // parse here
}

```

In both cases, `exec` would blank the previous results before matching.

Another possibility:

```javascript
const result = lexer.result
while (lexer.execInResult(input) && result[RegExp.success]) {
  // do the parsing here
}

```

...where `result` would be an object with non-configurable getters into the actual results.

---

<div class="post-metadata">

**Author:** ![claudiameadows](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/claudiameadows/32/126_2.png) [@claudiameadows](https://es.discourse.group/u/claudiameadows)\
**Post date:** [February 9, 2020, 10:40pm UTC](https://es.discourse.group/t/regexp-prototype-exec-alternative-that-doesnt-allocate-a-new-object-on-every-execution/215/2 "2020-02-09T22:40:40Z")

</div>

The GC cost here is fairly minimal - 90% of the time spent is just string processing, and the object is likely pooled in and reused from the nursery in subsequent iterations anyways since it's never retained on subsequent calls. It's also not nearly large enough for most GCs to promote it immediately.

Personally, `.matchAll(...)` is more useful than this, since it just becomes a simple `for` loop. It may seem heavier, but it's really not. And in my experience, when GC allocation actually matters, you've already stopped using regexps and so almost 100% of allocations are already explicit.

---

<div class="post-metadata">

**Author:** ![pygy](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/pygy/32/231_2.png) [@pygy](https://es.discourse.group/u/pygy)\
**Post date:** [February 9, 2020, 11:40pm UTC](https://es.discourse.group/t/regexp-prototype-exec-alternative-that-doesnt-allocate-a-new-object-on-every-execution/215/3 "2020-02-09T23:40:53Z")

</div>

`.matchAll()` is far less flexible. You can't switch lexers mid-stream (e.g. when matching RegExps, one for character sets vs one for the rest of the source).

Also, you can't beat native code that relies on SIMD operations with JS.

It's not just GC, re-using the same object improves cache locality.

---

<div class="post-metadata">

**Author:** ![ljharb](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/ljharb/32/8_2.png) [@ljharb](https://es.discourse.group/u/ljharb)\
**Post date:** [February 10, 2020, 12:01am UTC](https://es.discourse.group/t/regexp-prototype-exec-alternative-that-doesnt-allocate-a-new-object-on-every-execution/215/4 "2020-02-10T00:01:00Z")

</div>

What SIMD operations with JS? SIMD was withdrawn, and is only intended to be available via WASM.

---

<div class="post-metadata">

**Author:** ![pygy](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/pygy/32/231_2.png) [@pygy](https://es.discourse.group/u/pygy)\
**Post date:** [February 10, 2020, 12:33am UTC](https://es.discourse.group/t/regexp-prototype-exec-alternative-that-doesnt-allocate-a-new-object-on-every-execution/215/5 "2020-02-10T00:33:36Z")

</div>

Let's rephrase that, it was indeed ambiguous:

"Also, with JS, you can't beat native code that relies on SIMD operations."

---

<div class="post-metadata">

**Author:** ![claudiameadows](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/claudiameadows/32/126_2.png) [@claudiameadows](https://es.discourse.group/u/claudiameadows)\
**Post date:** [February 10, 2020, 9:33am UTC](https://es.discourse.group/t/regexp-prototype-exec-alternative-that-doesnt-allocate-a-new-object-on-every-execution/215/6 "2020-02-10T09:33:08Z")

</div>

> [@pygy](#):
>
> Also, you can't beat native code that relies on SIMD operations with JS.

The speedup you'd get from vectorization is minimal compared to not allocating hundreds to thousands of small string slices you don't need. 😉

> [@pygy](#):
>
> It's not just GC, re-using the same object improves cache locality.

If you use character codes, you get that naturally, but the moment you do a string traversal, you've just thrown all that effort away because the cache is now optimizing for that. Oh, and string allocation disrupts that further. So pretty much all your hopes and dreams for that are destroyed before it returns to JS and it's then all a wash and you're back to square one.

You have a similar issue with `String.fromCharCode`, but it's a lot easier to recover from that when all you have are raw integers and occasional booleans with almost no garbage.

---

<div class="post-metadata">

**Author:** ![pygy](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/pygy/32/231_2.png) [@pygy](https://es.discourse.group/u/pygy)\
**Post date:** [February 10, 2020, 11:56am UTC](https://es.discourse.group/t/regexp-prototype-exec-alternative-that-doesnt-allocate-a-new-object-on-every-execution/215/7 "2020-02-10T11:56:29Z")

</div>

The small string slices are not necessarily useless.

Also, by having a dedicated `result` object with getters, you could defer the creation of the slices (indeed, often `result[0]` isn't useful when you're after the captures in disjunction arms). Most of the captures will be `undefined`. Assuming you don't need some of the lexemes, rather than capturing them, you can create empty captures at the end of the disjunction arm.

It's also a code size/runtime trade off, and a readbility tradeoff. I'm trying to get the best possible perf out of the RegExp engine while keeping readable parsers.

---

<div class="post-metadata">

**Author:** ![claudiameadows](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/claudiameadows/32/126_2.png) [@claudiameadows](https://es.discourse.group/u/claudiameadows)\
**Post date:** [February 10, 2020, 4:37pm UTC](https://es.discourse.group/t/regexp-prototype-exec-alternative-that-doesnt-allocate-a-new-object-on-every-execution/215/8 "2020-02-10T16:37:43Z")

</div>

1. The memory has to exist to cache the result in either way.
2. The array would in practice likely be generated as a complete step anyways, and the engine will allocate an extra backing array for it even if it's not exposed directly - that way it can index the array (which is faster to access) to access and cache individual groups.
3. What kills performance is the memory indirection more so than just the allocations. GC allocators are efficient, and they can reallocate stuff in the nursery with as few as a couple instructions in some cases. But try reading any of those generated strings and you will see performance falter quick. **Edit:** To summarize: the allocations are death by a thousand papercuts. The indirections are death by a hundred thousand deep knife wounds.

Also, you only normally get about a 1.5-2x speedup using SSE4 on x86 regexp implementations - not an 8-16x (16- or 8-bit lanes) speedup. Sounds like a lot, but you can't parallelize parsing very well in the general case - it's inherently a serial action and vectorization only helps so much.

---

<div class="post-metadata">

**Author:** ![pygy](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/pygy/32/231_2.png) [@pygy](https://es.discourse.group/u/pygy)\
**Post date:** [February 10, 2020, 8:04pm UTC](https://es.discourse.group/t/regexp-prototype-exec-alternative-that-doesnt-allocate-a-new-object-on-every-execution/215/9 "2020-02-10T20:04:46Z")

</div>

You don't get what I mean.

> ... and the engine will allocate an extra backing array for it even if it's not exposed directly ...

It has to do it once, assuming this API:

```javascript
const result = lexer.result
while (lexer.execInResult(input) && result[RegExp.success]) {}

```

or zero times, assuming this API

```javascript
const result = []
while (lexer.exec(input, result) && result[RegExp.success])

```

... since in that case the allocation happens once, in client code.

The current API returns fresh arrays for each step in the loop. Even if the array is recycled, unless the very same array is immediately recycled, both the matcher and the client code end up with a result at a different memory address from invocation to invocation. With my proposed API, the result is stable for the whole loop.

I haven't looked, but I'd be surprised if a function with the `lexer.execInto(input, result)` signature doesn't already exist in every engine out there wrapped by `RegExp.prototype.exec()` which provides the fresh array when called.

Edit: Rather than discussing this abstractly, I'm going to try and implement said API in the various engines and see if it does bring better perf. The proof will be in the pudding...

Specifically, I'll give it a stab in SpiderMonkey and JavaScriptCore; building v8 on a Mac requires  
one to remove the CLI tools so that XCode takes precedence and I don't want to mess up my dev setup. Both SM and V8 use irregexp under the hood, so I expect similar gains, if any, from the approach I suggest.

---

<div class="post-metadata">

**Author:** ![claudiameadows](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/claudiameadows/32/126_2.png) [@claudiameadows](https://es.discourse.group/u/claudiameadows)\
**Post date:** [August 31, 2024, 7:11am UTC](https://es.discourse.group/t/regexp-prototype-exec-alternative-that-doesnt-allocate-a-new-object-on-every-execution/215/10 "2024-08-31T07:11:23Z")

</div>

Resurrecting this old thread because I like the idea more and more. With groups, there's even more allocation, so it's even more useful to cache now (it's no longer just a couple allocations).

As for the API, I feel `nextResult = re.exec(input, prevResult)` would be better. It glides in naturally, and it doesn't even need polyfilled first before you can start using it in many cases.