Hacker News Reader

Regular expressions are not Turing complete, yet a regular expression can have exponential complexity.

So the property "not Turing complete" does not give you anything practical.

A better approach is to have a scheduler which is fair, and which gives the compiler the cycles it deserves, even if it needs many of them.

View on HN

The only reason some regular expression engines take exponential time to match strings is because those implementations don't use regular expressions at all. Features like backreferences break them out of that class of languages. When you take the "regular" bit seriously you can guarantee linear time matching. See the engines used in Rust and Go.

First, it's not about the time spent compiling. And also not a scheduling problem.

Secondly, the eBPF constraints put the language even lower in the hierarchy than regular expressions.

Even lower than "proper" regular expressions, i.e. guaranteed linear time?

Yes, that's the intent.

The code is executed inline when filtering packets, instrumenting system calls and to prefilter kernel probes for user space. It has to be really fast, i.e. execute in a bounded amount of time.

Reply on news.ycombinator.com