4 ms·
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 in
by the8472 10y ago
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.
- amelius 10y agoRegular 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.
- the8472 10y agoFirst, 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.
- andrewflnr 10y agoEven lower than "proper" regular expressions, i.e. guaranteed linear time?
- the8472 10y agoYes, 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.
- tmerr 10y agoThe 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.