Hacker News Reader

Comment by the8472 | Hacker News Reader

It very much is necessary. Take the linux kernel's eBPF interpreter for example. Since the code runs in kernel scope and in many critical places (system call interception, network processing) it's important that the code executes within a bounded amount of time.

I think its restrictions are that it only allows forward jumps and a limited amount of instructions.

View on HN

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.

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