Hacker News Reader

Comment by sltkr | Hacker News Reader

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?

View on HN

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.

> 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.

Of course, but you can never skip more bytes than the search string is long.

But you get to skip those few bites (potentially) very many times.

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.

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...

(as mentioned by yan below) Ridiculous Fish did these sorts of benchmarks here: http://ridiculousfish.com/blog/posts/old-age-and-treachery.h...

>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/ provides great links.

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

Reply on news.ycombinator.com