3 ms·

That might help, but I think it goes in the wrong direction - The proper way to implement a regex matcher if you are worried about performance against arbitrary

That might help, but I think it goes in the wrong direction - The proper way to implement a regex matcher if you are worried about performance against arbitrary patterns is to build a Finite State Machine. It's not as simple of code and involves knowing some computer science theory, but results in a matcher with better time complexity guarantees.

ridiculous_fish 4y ago
Finite state machines also have their cliffs, in particular bounded repetition. Rust's FA-based regex will explode with /.{12345}/, while v8's backtracking engine handles it no problem.
- burntsushi 4y ago
  Yes, but please be careful here. The cliffs are categorically different. The cliffs of a finite state machine are still bounded to O(m * n), where m ~ len(regex) and n ~ len(haystack). The cliffs of a backtracker are exponential and difficult to predict. The repetition operator provokes the cliff because it represents short-hand syntax for easily increasing `m` to very large sizes. Indeed, by default, '.{12345}' will fail to compile because it blows the default limit. That only works because, as I said, the cliffs for finite automata based regex engines are far more predictable.
hddqsb 4y ago
[Note: This comment tree is about the Redis code, which uses glob-style patterns rather than regex. So in this comment and in my grandparent comment, "*" means "any string" rather than "zero or more of the previous pattern".] An NFA / DFA would be a perfectly valid way to implement an efficient matcher, but it's not the only way. For example, memoization (https://news.ycombinator.com/item?id=32434412#32436442 https://news.ycombinator.com/item?id=32434412#32436442) can be easily shown to have time complexity O(P * T) where P = len(pattern) and T = len(text), which is the same as a basic NFA implementation. In the case of the Redis code, my proposed fix requires much less code and memory than memoization or an NFA, and has time complexity O(P * T). It's slightly harder to prove this bound; here is a sketch of the proof: Matching against a pattern fragment that does not contain "*" takes O(len(pattern_fragment)). When a call to stringmatchlen() encounters a wildcard, it may recurse O(T) times (and then it returns). Each recursive call can be classified either "leaf" (if there is a match failure before the next wildcard) or "full" (if the match reaches the next wildcard). The insight I described leads to at most one "full" call at each level of the recursion (i.e. for each wildcard in the pattern). So for a particular pattern fragment, the number of "leaf" calls that process it is O(T). Hence the overall time complexity is O(P * T).
- burntsushi 4y ago
  See also: https://github.com/google/re2/blob/main/re2/bitstate.cc https://github.com/google/re2/blob/main/re2/bitstate.cc Although its space complexity is P*T, which limits its use to small regexes/haystacks. It sounds like your claim is that your technique achieves a smaller space bound?
  - hddqsb 4y ago
    Yes. My proposed fix takes O(P * T) time and O(1) memory (but it only supports glob-style wildcards; it doesn't support repetition of specific characters / character classes / sub-patterns).
    - burntsushi 4y ago
      Ah gotya. An important clarification indeed. Thanka for that!
      - deleted 4y ago
        [deleted]

ridiculous_fish 4y ago

Finite state machines also have their cliffs, in particular bounded repetition. Rust's FA-based regex will explode with /.{12345}/, while v8's backtracking engine handles it no problem.

burntsushi 4y ago
Yes, but please be careful here. The cliffs are categorically different. The cliffs of a finite state machine are still bounded to O(m * n), where m ~ len(regex) and n ~ len(haystack). The cliffs of a backtracker are exponential and difficult to predict. The repetition operator provokes the cliff because it represents short-hand syntax for easily increasing `m` to very large sizes. Indeed, by default, '.{12345}' will fail to compile because it blows the default limit. That only works because, as I said, the cliffs for finite automata based regex engines are far more predictable.

hddqsb 4y ago

[Note: This comment tree is about the Redis code, which uses glob-style patterns rather than regex. So in this comment and in my grandparent comment, "*" means "any string" rather than "zero or more of the previous pattern".] An NFA / DFA would be a perfectly valid way to implement an efficient matcher, but it's not the only way. For example, memoization (https://news.ycombinator.com/item?id=32434412#32436442 https://news.ycombinator.com/item?id=32434412#32436442) can be easily shown to have time complexity O(P * T) where P = len(pattern) and T = len(text), which is the same as a basic NFA implementation. In the case of the Redis code, my proposed fix requires much less code and memory than memoization or an NFA, and has time complexity O(P * T). It's slightly harder to prove this bound; here is a sketch of the proof: Matching against a pattern fragment that does not contain "*" takes O(len(pattern_fragment)). When a call to stringmatchlen() encounters a wildcard, it may recurse O(T) times (and then it returns). Each recursive call can be classified either "leaf" (if there is a match failure before the next wildcard) or "full" (if the match reaches the next wildcard). The insight I described leads to at most one "full" call at each level of the recursion (i.e. for each wildcard in the pattern). So for a particular pattern fragment, the number of "leaf" calls that process it is O(T). Hence the overall time complexity is O(P * T).

burntsushi 4y ago
See also: https://github.com/google/re2/blob/main/re2/bitstate.cc https://github.com/google/re2/blob/main/re2/bitstate.cc Although its space complexity is P*T, which limits its use to small regexes/haystacks. It sounds like your claim is that your technique achieves a smaller space bound?
- hddqsb 4y ago
  Yes. My proposed fix takes O(P * T) time and O(1) memory (but it only supports glob-style wildcards; it doesn't support repetition of specific characters / character classes / sub-patterns).
  - burntsushi 4y ago
    Ah gotya. An important clarification indeed. Thanka for that!
    - deleted 4y ago
      [deleted]