Exposing re2::FilteredRE2

[uhop]

Apparently re2::FilteredRE2 (see filtered_re2.h and filtered_re2.cc greatly improves the performance on large strings when multiple regular expressions should be matched. But it requires providing a 3rd-party case-insensitive sub-string search engine.

It would be nice to expose this functionality in a way compatible with RE2 and RE2.Set.

[uhop]

It looks like there are two possible tasks to accomplish before starting the implementation:

1. Select a reasonable search engine. It can be an existing high-performance implementation or we can implement a well-known algorithm ourselves.
2. Write a series of tests to see what kind of benefits we are talking about. Confirm that it is worth implementing.

[wrmedford]

I do wonder if a library that exposes vectorscan bindings would be better for this goal? I'd need to see how it behaves with WASM runtimes though.

[uhop]

My 2 cents.

On WASM

See https://github.com/uhop/node-re2/wiki/Notes-on-building-alternatives

In general I was less than impressed with WASM mostly because it doesn't support strings (should be coded as an array of numbers) and everything should be marshalled/copied to/from WASM. Obviously it is a problem with large strings due to an associated performance hit.

My understanding that future versions of WASM will try to solve these problems. The last time I checked they didn't.

To be fair the implementation of node-re2 suffers from similar problems, e.g, converting JS strings to UTF-8 and back, which requires copying. But not to such degree.

In general I would love to stop all this "pre-build 44 different versions of the binary" nonsense and ship WASM. It'll cover other runtimes automatically: Bun, Deno, browsers. But I don't believe we are there yet. Obviously I could be wrong.

On other regexp engines

While there are several interesting regexp engines, we need to answer three questions:

1. Is it faster than the native regexp?
2. Is it safe to use on user input?
3. Does it provide extensions/additions worth using even with negative 1 and/or 2?

The first question is about a significant improvement, not 2-3% faster. Otherwise people are not going to bother. Ironically, I started this project when Node used PCRE internally and RE2 was just faster in general. But at some point (I am guessing) they started to JIT regular expressions (still using a naive PCRE algorithms), so the speed became not an issue for most use cases.

But naive algorithms meant that more complex expressions + bad people on internet and unsanitized input from the wild meant ReDoS. So you are going to use RE2 when you are scraping internet and deal with any kind of user-generated input. So far I didn't see faster alternatives to RE2 in the safety department.

Alternative engines

There are quite a few interesting alternatives, which can be used for text parsing with regular expressions. Some of them:

• Intel Hyperscan — you already mentioned Vectorscan, which is based on it.
• Oniguruma
• TRE — very interesting fuzzy search.

Another obvious development is #199 — I am waiting for it to be absorbed by google/re2 so it'll be automatically available to us (predicated on the change not affecting other cases negatively speed-wise).

So far TRE looks interesting because of its unusual functionality. The rest are subject to evaluating.

[uhop]

As to what search engines to use for FilteredRE2: it is a classic computer science algorithmic problem and it is a well-documented area. The best place to start is https://en.wikipedia.org/wiki/String-searching_algorithm

I bet there are multiple existing C/C++ implementations and wouldn't be difficult to implement something similar.

[wes-matsec]

Yea, you might find that on AVX-512 supporting processors, that vectorscan's perf uplift is significantly higher than 2-3%.

Their kernels beat RE2 by about 50% wall clock on most cases from what I've tried and it provides richer output than re2::FilteredRE2 would due to providing an annotated offset of where all matches were. I can't give too many details but that's the path I'm exploring within my job. If there were an open source alternative I might be able to help with it and transition our stack to using that.

My point on WASM was just making sure that vectorscan would be usable in the browser, not that it would be the only shippable artifact. I think you're actually likely going to want to ship more individual binaries with vectorscan compared to RE2 because it has kernel optimizations per processor arch. There is a bit of a blowup there for a generally consumable vectorscan unfortunately (and partially why it potentially makes more sense as a client compiled library or an internal library where you're aware of a constrained set of processor architectures you need to support).