4 ms·

String search algorithms can cleverly skip forward when they don't find a match. They can skip forward more for longer "needle" strings. That said grep is pre

by jlebar 7y ago

String search algorithms can cleverly skip forward when they don't find a match. They can skip forward more for longer "needle" strings. That said grep is pretty fast period, so probably doesn't make a huge difference in practice, especially if you're IO-bound, which is common.

jandrese 7y ago
The caveat being if you're Unicode aware then many of the old skipahead strategies don't work as well and have to be rolled back or disabled.
- burntsushi 7y ago
  That's not true. They work just fine. Typically, substring search algorithms are implemented at the encoding level, e.g., on UTF-8 directly. If you just treat that as an alphabet of size 256, then algorithms like Boyer-Moore work out of the box. But the skip-ahead stuff isn't the most important thing nowadays. The key is staying in the fast vectorized skip loop as long as possible.
  - jandrese 7y ago
    I noticed severe slowdowns when passing in the /u flag on my regexes, even with big fixed ASCII strings in the middle of the patterns. They were taking 10 times as long to complete.
    - burntsushi 7y ago
      That doesn't imply that things like Boyer-Moore suddenly stop being effective. Without more details (which regex engine? what regex? what corpus? which programming language?) it's impossible to state the cause, but it could be as simple as the regex engine not being smart enough to use a literal searcher in that case.
      - JetSpiegel 7y ago
        Since you don't want to toot your own horn, and you saved me many hours of not waiting for searches, I'll link to ripgrep here https://github.com/BurntSushi/ripgrep https://github.com/BurntSushi/ripgrep