4 ms·

As TFA mentions, > #1 trick: GNU grep is fast because it AVOIDS LOOKING AT EVERY INPUT BYTE. TFA is incredibly short, and will explain it much better than I c

• Arcuru 8y ago
  That doesn't avoid it needing to read the data off disk though. AFAIK even SSDs still only read in 4K chunks. As the other reply mentioned though, it's just that MacBook SSDs are that fast.
  • rujuladanh 8y ago
    All SSDs are that fast (and way faster). Nothing special on Macbook ones.
• saagarjha 8y ago
  > it AVOIDS LOOKING AT EVERY INPUT BYTE This would not help, since the backing storage doesn't provide support for this kind of resolution. It would end up reading in the entire file anyways, unless your input string is on the order of an actual block.
  • pathseeker 8y ago
    DMA would like a word with you
    • saagarjha 8y ago
      I'm still not seeing how this significantly changes things?
      • kortilla 8y ago
        Loading the file from disk into memory doesn’t require reads by the CPU. That’s significantly different than the cpu doing comparisons (or even reads) on each byte.
  • BeeOnRope 8y ago
    Sure it would help, not for the IO part, but the CPU-bound part of actually checking each character, which is apparently a much lower bound in this case.
    • saagarjha 8y ago
      Yeah, that's why the article talks about decreasing the amount of CPU work. From the context of disk IO though (which is what this thread seems to be about) this can't help.
• 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 ago
    This 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 ago
      It 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 ago
    It 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).