4 ms·
"GNU grep is fast because it AVOIDS LOOKING AT EVERY INPUT BYTE" Somewhat confusing since it has to look at every byte to find the newlines. They are using a
by tyingq 8y ago
"GNU grep is fast because it AVOIDS LOOKING AT EVERY INPUT BYTE"
Somewhat confusing since it has to look at every byte to find the newlines. They are using a pretty specific definition of "look".
- tribaal 8y agoThis is why the linked article specifically says it does not look for newlines: > Moreover, GNU grep AVOIDS BREAKING THE INPUT INTO LINES. Looking for newlines would slow grep down by a factor of several times, because to find the newlines it would have to look at every byte!
- deleted 8y ago[deleted]
- dllthomas 8y ago... until you ask for line numbers.
- tyingq 8y agoIt can't avoid breaking the output into lines, though, so it probably looks for newlines after a match is found. I assume the Boyer Moore preprocessor reads a lot of bytes also. Not disputing it's more efficient, but there's no magic. It avoids reading some bytes when and if it can.
- dllthomas 8y ago> It can't avoid breaking the output into lines It can whenever you don't ask for line numbers, can't it? > It probably looks for newlines after a match is found Probably, yeah. Counting number of newlines in a range, without caring just where they fall, can probably be pretty darned fast with vector instructions. Idk if that's worth the additional pass, though.
- BeeOnRope 8y agoIt doesn't need to look for newlines. That is looking for ^ABCD is not harder than looking for ABCD. The set of matches for the former is a subset of the latter, so if you have some fast way of doing the latter you have a fast way of doing the former (with an additional check for the preceding newline). Another way of looking at is just considering the ^ another character (plus one-off special handling for start of file).