Why GNU grep is fast (2010)

Post by tetha » Thu, Nov 28, 2013, 9:56 PM UTC

yelnatz wrote: post #60

I'm actually more familiar with the KMP algorithm than BM. So I looked it up to see what the difference was: The classic Boyer-Moore algorithm suffers from the phenomenon that it tends not to work so efficiently on small alphabets like DNA. The skip distance tends to stop growing with the pattern length because substrings re-occur frequently. By remembering more of what has already been matched, one can get larger sk…

Post by tetha » Thu, Nov 28, 2013, 10:04 PM UTC

bane wrote: post #45

The inverse is this...what is modern software doing that makes them so slow?

Post by mtdewcmu » Thu, Nov 28, 2013, 10:21 PM UTC

pmiller2 wrote: post #66

Someone wrote: post #65

Earlier quoted context omitted.

There is a third one, at low level: make it do something else. For example, programmer requests a multiplication, compiler generates a shift; programmer requests a division, compiler generates a multiplication; programmer specifies a switch, compiler generates a jump table.

I'd argue that's just a variation of doing less, in the same way that e.g. vectorization is a variation of parallelism.

Post by lelandbatey » Thu, Nov 28, 2013, 10:42 PM UTC

idupree wrote: post #90

tsm wrote: post #74

Earlier quoted context omitted.

$ touch foo $ chmod +x foo $ ./foo $ echo $? 0

For me, the trivial C program appears to run faster than the empty file: $ touch empty $ chmod +x empty $ time ./empty real 0m0.002s user 0m0.000s sys 0m0.000s $ echo "int main(){return 0;}" > trivial.c $ gcc trivial.c -o trivial $ time ./trivial real 0m0.001s user 0m0.000s sys 0m0.000s Timing results are consistent over several repetitions (provided everything's in cache from disk). Linux x86_64. `mov` takes ten tho…

    $ touch empty

    $ chmod +x empty 

    $ time ./empty 

        real    0m0.005s
        user    0m0.001s
        sys     0m0.001s

    $ echo "int main(){return 0;}" > trivial.c

    $ gcc trivial.c -o trivial

    $ time ./trivial

        real    0m0.002s
        user    0m0.001s
        sys     0m0.002s

Post by belorn » Thu, Nov 28, 2013, 11:36 PM UTC

jtmcmc wrote: post #88

MikeTaylor wrote: post #87

Impressive, but if the goal is for BSD to have a faster grep then clearly the solution is to use GNU grep instead of rolling their own redundant and inferior clone.

presumably GNU grep is GPL and incompatible with their BSD license