Trying to beat V8's regex engine with just JS
177 views
Skip to first unread message
Peter Martischka
Dec 15, 2020, 8:23:35 AM12/15/20
to v8-users
Hello v8-users!
In the past I often had a regex as bottleneck in my projects, rewriting them manually to JS often helped. So I recently thought, could I write something that generates the fitting JS for a given regex? Out of that came RECO - https://github.com/Pita/reco . Unfortunately the generated code can't get quite as fast yet. It still takes about 2-3 times in benchmarks compared to the built in regex engine. But it can match all sorts of complicated regex patterns. In manual attempts to rewrite a regex I could often beat the built-in time.
I would appreciate very much help in making the generated code faster and make it beat the built-in matcher every time. Any help is appreciated, thank you :)
In the past I often had a regex as bottleneck in my projects, rewriting them manually to JS often helped. So I recently thought, could I write something that generates the fitting JS for a given regex? Out of that came RECO - https://github.com/Pita/reco . Unfortunately the generated code can't get quite as fast yet. It still takes about 2-3 times in benchmarks compared to the built in regex engine. But it can match all sorts of complicated regex patterns. In manual attempts to rewrite a regex I could often beat the built-in time.
I would appreciate very much help in making the generated code faster and make it beat the built-in matcher every time. Any help is appreciated, thank you :)
Peter
J Decker
Dec 17, 2020, 11:37:45 PM12/17/20
to v8-users
Ben Noordhuis
Dec 20, 2020, 6:45:45 AM12/20/20
to v8-users
On Fri, Dec 18, 2020 at 5:37 AM J Decker <d3c...@gmail.com> wrote:
>
> https://swtch.com/~rsc/regexp/regexp1.html ?
That page describes linear-time regular expressions but JS-compatible
regex engines must also support exponential-time backtracking.
As an interesting aside: V8 recently grew a
--enable-experimental-regexp-engine flag that enables /pattern/l ('l'
for 'linear time'), see
https://bugs.chromium.org/p/v8/issues/detail?id=10765 for details. I'm
pretty excited about it, it blocks off a whole class of catastrophic
backtracking bugs.
>
> https://swtch.com/~rsc/regexp/regexp1.html ?
That page describes linear-time regular expressions but JS-compatible
regex engines must also support exponential-time backtracking.
As an interesting aside: V8 recently grew a
--enable-experimental-regexp-engine flag that enables /pattern/l ('l'
for 'linear time'), see
https://bugs.chromium.org/p/v8/issues/detail?id=10765 for details. I'm
pretty excited about it, it blocks off a whole class of catastrophic
backtracking bugs.
Reply all
Reply to author
Forward
0 new messages