Comment by burntsushi | Hacker News Reader

Comment by burntsushi | Hacker News Reader

Parent Full thread

Yes, but there is an interesting clarification here. RE2 has used the "caching" approach documented in the Ruby bug ticket linked for quite some time (since its birth?): https://github.com/google/re2/blob/954656f47fe8fb505d4818da1...

It is mentioned only briefly in Cox's article on regex matching in the wild. Look for the word "bitstate": https://swtch.com/~rsc/regexp/regexp3.html

I didn't know Perl had implemented this trick too.

The paper[1] cited in the Ruby bug ticket was published very recently. When I first read the Ruby bug ticket, I immediately wondered how they sidestepped the memory use problem. The paper's abstract seems to suggest there is some technique for doing so, as it rebuffs the idea of doing "full" memoization. Alas, I do not have access the paper. (Which is fucking ridiculous.)

[1]: https://ieeexplore.ieee.org/abstract/document/9519427

OK, now that I have access to the paper, it does very briefly acknowledge RE2:

> while caching is used to accelerate backtracking in Perl and a rare path in RE2.

Although I wouldn't call it rare. It's probably used every time one wants capturing groups and the regex isn't one pass (pretty common) and the input isn't too big (like, say, a line in a log file).

The actual part of the paper that contains the key contribution (memoization but with less space) is fairly dense and I don't have the time right now to look more closely. But it looks like it might be applicable to RE2, Go's regexp package and Rust's regex crate. All three already use already use bounded backtracking (i.e., "full caching"), but if the space usage could be cut back, then it would increase the opportunity of using the bounded backtracker. Namely, all three put a bound on `size(regex) * size(haystack)`. If the search needs something bigger than that bound, then the backtracker isn't used. But if memory usage were instead much less than `size(regex) * size(haystack)`, then the backtracker could be used more often. (Which is a good thing since it's generally faster than a full Thompson NFA simulation.)

One of the authors mirrored the paper: https://fservant.github.io/papers/DavisServantLee-SelectiveM...

Thanks!

Reply on news.ycombinator.com