7 ms·

One reason that Perl regex is relatively slow is because it isn't actually regular: it can't be implemented using DFAs or NFAs.

by User23 7y ago

gigatexal 7y ago
DFA/NFAs?
- supergauntlet 7y ago
  https://en.wikipedia.org/wiki/Deterministic_finite_automaton https://en.wikipedia.org/wiki/Deterministic_finite_automaton https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton https://en.wikipedia.org/wiki/Nondeterministic_finite_automa... Said another way: a state machine. True regular languages can be defined by a simple state machine, which is relatively much faster than the extended regular-like language that perl exposes.
- hexspeaker 7y ago
  Deterministic Finite Automaton. It's a concept from automata theory which is a concept from theory of computation. Implementations of DFA's are how libraries like google's re2 or golang's regex are implemented. They're not as powerful as regex libs built with a non-regular language model but that's by design. Fun trivia: DFAs and NFAs are computationally equivalent. Any NFA can be converted into an equivalent DFA. https://en.wikipedia.org/wiki/Deterministic_finite_automaton https://en.wikipedia.org/wiki/Deterministic_finite_automaton
  - JoelMcCracken 7y ago
    I always found the algorithm to convert a NFA to an equivalent DFA to be pretty cool.
    - hinkley 7y ago
      Hold up. I've seen this conversation play out probably half a dozen times over the last few years and it just occurred to me... If you can convert a nondeterministic automata to a deterministic one, doesn't that mean they are all deterministic?
      - kazinator 7y ago
        "Nondeterministic" in automata is a very specialized word that doesn't refer to anything like a random process in a stochastic universe. It's a representation for state machines in which state transitions are apparently ambiguous: a given state in the NFA can, for exactly the same input, go into multiple other states. This is a very convenient representation for pattern matching. The way the ambiguity resolves itself is not through randomness, but by the understanding that the machine is in all of the possible states at the same time. Then, in a concrete implementation in a programming language, we represent that situation by using a set of states as the run-time state. E.g. when the input symbol b is received, some NFA machine goes from state { 0, 3, 5 } to { 1, 3, 7, 8 }; i.e. it is in NFA states 0, 3 and 5, which transition to 1, 3, 7, 8 when b is seen. NFA graphs can be executed directly by an NFA simulator which calculates these transitions on the fly. We can also statically figure out all the state sets there can be and their transitions.Then we re-label these sets as the simple states of a deterministic automaton. E.g. { 0, 3, 5 } is dubbed S0, { 1, 3, 7, 8} is dubbed S1. There is a transition from S0 to S1 on b. We can work through all the possible transitions, ferret out all the subsets and their transitions to build a simple machine. That is the "subset construction".
      - hexspeaker 7y ago
        Yes for regular languages but not for higher level ones. For example, deterministic context-free is a subset of context-free. For languages that are turing complete, the question is less about ability to compute and more about the speed at which something can be computed. This is an unsolved problem known as P vs. NP. https://en.wikipedia.org/wiki/P_versus_NP_problem https://en.wikipedia.org/wiki/P_versus_NP_problem
  - crispyambulance 7y ago
    > ...not as powerful as regex libs built with a non-regular language... I've wondered about that, but I can't think of a realistic example where that would really matter. Is there something that perl regex's can do, in non-crazy everyday use-cases, that can't be done by something like re2?
    - blaisio 7y ago
      Backreferences and look around. I don't think it's proven that they can't be added on to an automata based regular expression engine. Nobody has figured it out yet though.
      - Drup 7y ago
        Actually, it's been proved for ... longer than PERL exists ? The various features in PERL allow you to emulate context-free languages. There is a proof somewhere, but it's trivial to see you can use backreferences to parse languages with well-nested parens. Languages of well-nested parens are known to be non-regular, and thus impossible to write with regular expressions. Also note that knowing if an arbitrary context-free language is regular is undecidable. That doesn't mean you can't try to optimize down some PERL grammar to a regex, but your optimization will never be complete.
        setr 7y ago
        >Also note that knowing if an arbitrary context-free language is regular is undecidable. That doesn't mean you can't try to optimize down some PERL grammar to a regex, but your optimization will never be complete. Are you reffering to the programming language or PCRE? I would expect PCRE to be a simple superset of the regex grammar, and thus the optimization is complete and trivial: the appearance of any PCRE constructs denies the use of the DFA engine; otherwise, use the DFA. I don’t see how you could ever optimize out eg a backreference (converting to some equivalent regex) without already having parsed the subject text and determining it to be unnecessary. In which case, I don’t see how the inability to determine regularity of a context-free grammar is relevant (if you’re referring to the context-free nature of PCRE’s grammar, its not clear to me why you should care where the regex input grammar itself is regular/context-free, and why you’d want to convert PCRE to a regular grammar; optimizing a regex search shouldn’t care about the grammar defining the search)
  - hinkley 7y ago
    They are powerful in the sense that they are specialized to a task and perform it much better.
fwip 7y ago
Here is some further reading on the topic that I found useful. https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
apetresc 7y ago
Sure, but it must be relatively simple to identify, pre-compilation, if the regex is regular or not; there's only certain constructions that break regularity. Why couldn't Perl's engine fall back to a more optimized regular-language-only implementation for those cases, if it has such a big impact on performance?
- ben509 7y ago
  Theoretically, a regular expression can be expressed in constant space, and that's profoundly limiting, so anything that requires so much as a stack is not a regex. That includes basic things like capture groups. That doesn't mean you can't use automata in a regex-plus implementation, though. I can't find the paper, but I think there is a hybrid engine that tries to get the best of both worlds; constant space where possible and using additional space to provide more features.
  - chaosite 7y ago
    You can implement capture groups with no problem using automata (see re2). You might have meant to say that you can't use backreferences.
- rurban 7y ago
  It can, and it's one of my explicit goals to do so. But the biggest problem is perl's horrible code in regcomp and regexec. (based on Henry Spencer's old code). It mostly does state transitions via goto or setjmp/longjmp. The initial regex scanner did 2 passes, so it would have been trivial to detect NFA illegal backtracking with zero cost. With a cleanly written codebase it would be much easier. my re::engine::PCRE2 replacement is much faster, can do everything and even has less bugs than perl5 regex updates. But it's still not production ready, and full replacement would still be huge work. Now it's just via hooks. Which are slow, because most of the work is done twice.
chaosfox 7y ago
see also, Perl Regular Expression Matching is NP-Hard: https://perl.plover.com/NPC/ https://perl.plover.com/NPC/
joosters 7y ago
It's also possible that they might be including perl's startup time in that measurement? Their comments about 'parallelising' 'by using ampersand' make me concerned about the methodology involved.

One reason that Perl regex is relatively slow is because it isn't actually regular: it can't be implemented using DFAs or NFAs.

by User23 7y ago

One reason that Perl regex is relatively slow is because it isn't actually regular: it can't be implemented using DFAs or NFAs.

gigatexal 7y ago

DFA/NFAs?

supergauntlet 7y ago
https://en.wikipedia.org/wiki/Deterministic_finite_automaton https://en.wikipedia.org/wiki/Deterministic_finite_automaton https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton https://en.wikipedia.org/wiki/Nondeterministic_finite_automa... Said another way: a state machine. True regular languages can be defined by a simple state machine, which is relatively much faster than the extended regular-like language that perl exposes.
hexspeaker 7y ago
Deterministic Finite Automaton. It's a concept from automata theory which is a concept from theory of computation. Implementations of DFA's are how libraries like google's re2 or golang's regex are implemented. They're not as powerful as regex libs built with a non-regular language model but that's by design. Fun trivia: DFAs and NFAs are computationally equivalent. Any NFA can be converted into an equivalent DFA. https://en.wikipedia.org/wiki/Deterministic_finite_automaton https://en.wikipedia.org/wiki/Deterministic_finite_automaton
- JoelMcCracken 7y ago
  I always found the algorithm to convert a NFA to an equivalent DFA to be pretty cool.
  - hinkley 7y ago
    Hold up. I've seen this conversation play out probably half a dozen times over the last few years and it just occurred to me... If you can convert a nondeterministic automata to a deterministic one, doesn't that mean they are all deterministic?
    - kazinator 7y ago
      "Nondeterministic" in automata is a very specialized word that doesn't refer to anything like a random process in a stochastic universe. It's a representation for state machines in which state transitions are apparently ambiguous: a given state in the NFA can, for exactly the same input, go into multiple other states. This is a very convenient representation for pattern matching. The way the ambiguity resolves itself is not through randomness, but by the understanding that the machine is in all of the possible states at the same time. Then, in a concrete implementation in a programming language, we represent that situation by using a set of states as the run-time state. E.g. when the input symbol b is received, some NFA machine goes from state { 0, 3, 5 } to { 1, 3, 7, 8 }; i.e. it is in NFA states 0, 3 and 5, which transition to 1, 3, 7, 8 when b is seen. NFA graphs can be executed directly by an NFA simulator which calculates these transitions on the fly. We can also statically figure out all the state sets there can be and their transitions.Then we re-label these sets as the simple states of a deterministic automaton. E.g. { 0, 3, 5 } is dubbed S0, { 1, 3, 7, 8} is dubbed S1. There is a transition from S0 to S1 on b. We can work through all the possible transitions, ferret out all the subsets and their transitions to build a simple machine. That is the "subset construction".
    - hexspeaker 7y ago
      Yes for regular languages but not for higher level ones. For example, deterministic context-free is a subset of context-free. For languages that are turing complete, the question is less about ability to compute and more about the speed at which something can be computed. This is an unsolved problem known as P vs. NP. https://en.wikipedia.org/wiki/P_versus_NP_problem https://en.wikipedia.org/wiki/P_versus_NP_problem
- crispyambulance 7y ago
  > ...not as powerful as regex libs built with a non-regular language... I've wondered about that, but I can't think of a realistic example where that would really matter. Is there something that perl regex's can do, in non-crazy everyday use-cases, that can't be done by something like re2?
  - blaisio 7y ago
    Backreferences and look around. I don't think it's proven that they can't be added on to an automata based regular expression engine. Nobody has figured it out yet though.
    - Drup 7y ago
      Actually, it's been proved for ... longer than PERL exists ? The various features in PERL allow you to emulate context-free languages. There is a proof somewhere, but it's trivial to see you can use backreferences to parse languages with well-nested parens. Languages of well-nested parens are known to be non-regular, and thus impossible to write with regular expressions. Also note that knowing if an arbitrary context-free language is regular is undecidable. That doesn't mean you can't try to optimize down some PERL grammar to a regex, but your optimization will never be complete.
      - setr 7y ago
        >Also note that knowing if an arbitrary context-free language is regular is undecidable. That doesn't mean you can't try to optimize down some PERL grammar to a regex, but your optimization will never be complete. Are you reffering to the programming language or PCRE? I would expect PCRE to be a simple superset of the regex grammar, and thus the optimization is complete and trivial: the appearance of any PCRE constructs denies the use of the DFA engine; otherwise, use the DFA. I don’t see how you could ever optimize out eg a backreference (converting to some equivalent regex) without already having parsed the subject text and determining it to be unnecessary. In which case, I don’t see how the inability to determine regularity of a context-free grammar is relevant (if you’re referring to the context-free nature of PCRE’s grammar, its not clear to me why you should care where the regex input grammar itself is regular/context-free, and why you’d want to convert PCRE to a regular grammar; optimizing a regex search shouldn’t care about the grammar defining the search)
- hinkley 7y ago
  They are powerful in the sense that they are specialized to a task and perform it much better.

fwip 7y ago

Here is some further reading on the topic that I found useful. https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html

apetresc 7y ago

Sure, but it must be relatively simple to identify, pre-compilation, if the regex is regular or not; there's only certain constructions that break regularity. Why couldn't Perl's engine fall back to a more optimized regular-language-only implementation for those cases, if it has such a big impact on performance?

ben509 7y ago
Theoretically, a regular expression can be expressed in constant space, and that's profoundly limiting, so anything that requires so much as a stack is not a regex. That includes basic things like capture groups. That doesn't mean you can't use automata in a regex-plus implementation, though. I can't find the paper, but I think there is a hybrid engine that tries to get the best of both worlds; constant space where possible and using additional space to provide more features.
- chaosite 7y ago
  You can implement capture groups with no problem using automata (see re2). You might have meant to say that you can't use backreferences.
rurban 7y ago
It can, and it's one of my explicit goals to do so. But the biggest problem is perl's horrible code in regcomp and regexec. (based on Henry Spencer's old code). It mostly does state transitions via goto or setjmp/longjmp. The initial regex scanner did 2 passes, so it would have been trivial to detect NFA illegal backtracking with zero cost. With a cleanly written codebase it would be much easier. my re::engine::PCRE2 replacement is much faster, can do everything and even has less bugs than perl5 regex updates. But it's still not production ready, and full replacement would still be huge work. Now it's just via hooks. Which are slow, because most of the work is done twice.

chaosfox 7y ago

see also, Perl Regular Expression Matching is NP-Hard: https://perl.plover.com/NPC/ https://perl.plover.com/NPC/

joosters 7y ago

It's also possible that they might be including perl's startup time in that measurement? Their comments about 'parallelising' 'by using ampersand' make me concerned about the methodology involved.