4 ms·

Obvious questions: 1. How do you extend Boyer-Moore to arbitrary regexps? 2. Does "not looking at every byte" really matter when the strings being searched fo

by sltkr 12y ago

Obvious questions: 1. How do you extend Boyer-Moore to arbitrary regexps? 2. Does "not looking at every byte" really matter when the strings being searched for are typically so short that you're gonna hit every cache line anyway?

kevinnk 12y ago
> Does "not looking at every byte" really matter when the strings being searched for are typically so short that you're gonna hit every cache line anyway? You're not skipping bytes of the search string, you're skipping bytes of the file being searched.
- pacificmint 12y ago
  Of course, but you can never skip more bytes than the search string is long.
  - aganders3 12y ago
    But you get to skip those few bites (potentially) very many times.
    - rcxdude 12y ago
      yes, but the point is that on modern CPUs checking those bytes is likely far from the bottleneck and thus skipping them saves you very little time, if any at all.
      - taeric 12y ago
        You might be surprised. Consider, counting to 2 million by 5 is significantly faster than counting by 1. Especially if you just go ahead and start some prefetching in the memory, I would expect that this can speed things up considerably. Edit: I should say I would still think things should be benchmarked to really know...
        justin66 12y ago
        (as mentioned by yan below) Ridiculous Fish did these sorts of benchmarks here: http://ridiculousfish.com/blog/posts/old-age-and-treachery.html http://ridiculousfish.com/blog/posts/old-age-and-treachery.h...
sophacles 12y ago
1. you find the fixed part of the regexps, do boyer-moore to fast filter the haystack, then do deeper NFA matching if the fixed bits are present. One example from later in that email thread: ^foo is the same as a fixed string search for \nfoo I presume there are ways you can bound your fixed searches, and have your NFA work "backwards" through the string after a boyer-moore hits. (or both backwards and forwards from fixed points, depending on where in the string the fixed bit is). 2. No not for some people's small file usage - But grep is used in many many cases on huge log files (and mail files/queues and so on) - there is a valid case for optimizing those uses. Production sysadmins deal with multiple GBs of logfiles regularly, and grep them a lot.
wongarsu 12y ago
>How do you extend Boyer-Moore to arbitrary regexps? As mentioned in the follow-up messages, some regexps can be translated to one or at least few fixed string searches (/^[Gg]rep/ is really a search for "\nGrep" or "\ngrep"). If you can't do that, your regexp may contain longish fixed strings that allow you to discard most lines via Boyer-Moore before you have to run the regexp engine. For the more general case, http://swtch.com/~rsc/regexp/ http://swtch.com/~rsc/regexp/ provides great links.
cbsmith 12y ago
1. You use lightgrep: https://github.com/jonstewart/liblightgrep https://github.com/jonstewart/liblightgrep

by sltkr 12y ago

kevinnk 12y ago

> Does "not looking at every byte" really matter when the strings being searched for are typically so short that you're gonna hit every cache line anyway? You're not skipping bytes of the search string, you're skipping bytes of the file being searched.

pacificmint 12y ago
Of course, but you can never skip more bytes than the search string is long.
- aganders3 12y ago
  But you get to skip those few bites (potentially) very many times.
  - rcxdude 12y ago
    yes, but the point is that on modern CPUs checking those bytes is likely far from the bottleneck and thus skipping them saves you very little time, if any at all.
    - taeric 12y ago
      You might be surprised. Consider, counting to 2 million by 5 is significantly faster than counting by 1. Especially if you just go ahead and start some prefetching in the memory, I would expect that this can speed things up considerably. Edit: I should say I would still think things should be benchmarked to really know...
      - justin66 12y ago
        (as mentioned by yan below) Ridiculous Fish did these sorts of benchmarks here: http://ridiculousfish.com/blog/posts/old-age-and-treachery.html http://ridiculousfish.com/blog/posts/old-age-and-treachery.h...

sophacles 12y ago

1. you find the fixed part of the regexps, do boyer-moore to fast filter the haystack, then do deeper NFA matching if the fixed bits are present. One example from later in that email thread: ^foo is the same as a fixed string search for \nfoo I presume there are ways you can bound your fixed searches, and have your NFA work "backwards" through the string after a boyer-moore hits. (or both backwards and forwards from fixed points, depending on where in the string the fixed bit is). 2. No not for some people's small file usage - But grep is used in many many cases on huge log files (and mail files/queues and so on) - there is a valid case for optimizing those uses. Production sysadmins deal with multiple GBs of logfiles regularly, and grep them a lot.

wongarsu 12y ago

>How do you extend Boyer-Moore to arbitrary regexps? As mentioned in the follow-up messages, some regexps can be translated to one or at least few fixed string searches (/^[Gg]rep/ is really a search for "\nGrep" or "\ngrep"). If you can't do that, your regexp may contain longish fixed strings that allow you to discard most lines via Boyer-Moore before you have to run the regexp engine. For the more general case, http://swtch.com/~rsc/regexp/ http://swtch.com/~rsc/regexp/ provides great links.

cbsmith 12y ago

1. You use lightgrep: https://github.com/jonstewart/liblightgrep https://github.com/jonstewart/liblightgrep