4 ms·

Regexes can be fast and simple, but sometimes it’s faster and simpler to use normal string search. I recently replaced a regex with two finds for 10x speedup.

secondcoming 2y ago
Well if people spend time learning arcane regex syntax it'd be a shame to not use them! But yes, you're right. Sometimes simple finds are sufficient.
cies 2y ago
Or write a parser! In most cases the parser will not be shorter (code) than the regex, but it will most certainly be simpler (cognitively; it's hard to understand all that regexes do, they're close to magic) and more testable (you can test the parts of the parser, like the number parser or the string parser, individually), and often faster too.
- cies 2y ago
  https://stackoverflow.com/questions/11905506/regular-expression-vs-string-parsing https://stackoverflow.com/questions/11905506/regular-express...
hyperpape 2y ago
There's pretty wide variety in the performance of regular expressions between different languages, and efficient implementations will often recognize when your regular expression has a literal suffix/prefix, and optimize accordingly. That doesn't help you if you're stuck using a library that doesn't perform those optimizations, but it means you need to be careful about importing your assumptions about regex performance from one language to another. See also: https://github.com/burntSushi/rebar https://github.com/burntSushi/rebar
zeckalpha 2y ago
Sounds like the regex library was not implemented as Russ describes... a linear find should be equivalent to a well implemented regex search for a specific string of characters.
- adrianN 2y ago
  It’s re2…
- burntsushi 2y ago
  The GP doesn't really provide enough details to tell the difference between 1) the programmer did something wrong, or 2) the regex engine is missing optimizations or 3) the GP has a use case that is actually difficult to optimize for in the generality of the regex engine. Any one of these 3 things could be true. It's possible more than one is true simultaneously! > a linear find should be equivalent to a well implemented regex search for a specific string of characters This is only true theoretically. If your regex engine is just a DFA scan that does char-at-a-time matching, then any "well implemented" substring search algorithm is going to blow it out of the water because it likely uses SIMD. Of course, many regex engines (including RE2), detect literals in the regex and use SIMD to scan for it. So while "DFA scan that does char-a-time matching" is a fine semantic model to have (to a first approximation) for a finite automata based regex engine, the model breaks down pretty quickly for reasoning about performance in general.
- andrewla 2y ago
  Depending on the type of string search this is not completely true. A naive string search is O(kn) (where k is the length of the search string) which is actually slower than the O(n) that a DFA can get. But KMP and similar algorithms can do better; they can get performance approaching O(n/k) for many cases by not even looking at every character of the input string.
  - hyperpape 2y ago
    In practice, it's apparently often better to avoid these techniques and just use SIMD operations to search. You look at every byte, so it's O(n) but the overhead of more complicated approaches isn't worth it. See this comment from burntsushi: https://lobste.rs/s/ycydmd/why_gnu_grep_is_fast_2010#c_gpim7s https://lobste.rs/s/ycydmd/why_gnu_grep_is_fast_2010#c_gpim7....
    - MattPalmer1086 2y ago

secondcoming 2y ago

Well if people spend time learning arcane regex syntax it'd be a shame to not use them! But yes, you're right. Sometimes simple finds are sufficient.

cies 2y ago

Or write a parser! In most cases the parser will not be shorter (code) than the regex, but it will most certainly be simpler (cognitively; it's hard to understand all that regexes do, they're close to magic) and more testable (you can test the parts of the parser, like the number parser or the string parser, individually), and often faster too.

cies 2y ago
https://stackoverflow.com/questions/11905506/regular-expression-vs-string-parsing https://stackoverflow.com/questions/11905506/regular-express...

hyperpape 2y ago

There's pretty wide variety in the performance of regular expressions between different languages, and efficient implementations will often recognize when your regular expression has a literal suffix/prefix, and optimize accordingly. That doesn't help you if you're stuck using a library that doesn't perform those optimizations, but it means you need to be careful about importing your assumptions about regex performance from one language to another. See also: https://github.com/burntSushi/rebar https://github.com/burntSushi/rebar

zeckalpha 2y ago

Sounds like the regex library was not implemented as Russ describes... a linear find should be equivalent to a well implemented regex search for a specific string of characters.

adrianN 2y ago
It’s re2…
burntsushi 2y ago
The GP doesn't really provide enough details to tell the difference between 1) the programmer did something wrong, or 2) the regex engine is missing optimizations or 3) the GP has a use case that is actually difficult to optimize for in the generality of the regex engine. Any one of these 3 things could be true. It's possible more than one is true simultaneously! > a linear find should be equivalent to a well implemented regex search for a specific string of characters This is only true theoretically. If your regex engine is just a DFA scan that does char-at-a-time matching, then any "well implemented" substring search algorithm is going to blow it out of the water because it likely uses SIMD. Of course, many regex engines (including RE2), detect literals in the regex and use SIMD to scan for it. So while "DFA scan that does char-a-time matching" is a fine semantic model to have (to a first approximation) for a finite automata based regex engine, the model breaks down pretty quickly for reasoning about performance in general.
andrewla 2y ago
Depending on the type of string search this is not completely true. A naive string search is O(kn) (where k is the length of the search string) which is actually slower than the O(n) that a DFA can get. But KMP and similar algorithms can do better; they can get performance approaching O(n/k) for many cases by not even looking at every character of the input string.
- hyperpape 2y ago
  In practice, it's apparently often better to avoid these techniques and just use SIMD operations to search. You look at every byte, so it's O(n) but the overhead of more complicated approaches isn't worth it. See this comment from burntsushi: https://lobste.rs/s/ycydmd/why_gnu_grep_is_fast_2010#c_gpim7s https://lobste.rs/s/ycydmd/why_gnu_grep_is_fast_2010#c_gpim7....
  - MattPalmer1086 2y ago