Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why GNU grep is fast (2010)

lists.freebsd.org

Post reply on HN
Print view View original

121–130 of 133 posts

Re: Why GNU grep is fast (2010)

#121

Post by agnokapathetic »

Myrmornis wrote: post #95

In case it helps anyone else, to install GNU grep on OSX using homebrew I did brew tap homebrew/dupes brew install --default-names homebrew/dupes/grep following http://www.heystephenwood.com/2013/09/install-gnu-grep-on-ma...

Be careful with:

  --default-names do not prepend 'g' to the binary
On OS X (a BSD derivative with BSD-grep), --default-names will put GNU grep in your path. A lot of things in OS X depend on BSD sed/awk/grep. Omitting --default-names links then GNU variants to ggrep/gsed/gawk.

Re: Why GNU grep is fast (2010)

#122

Post by evincarofautumn »

pestaa wrote: post #16

By this logic you can write really fast programs in Haskell, because it avoids computing unused values (and therefore complete calltrees). (Unfortunately, the management of such calltrees -- thunks -- often has higher cost than outright computing them in the first place.) I try hard, but I'm not smart enough to write programs that do nothing. :)

You can. A lazy algorithm will do no more reductions than an eager one, and it will usually do fewer. You just have to specify strictness. The compiler is pretty conservative about adding strictness because it has to preserve behaviour. But if you know something will be computed, e.g., a loop accumulator, then you can just tell the compiler so.

Re: Why GNU grep is fast (2010)

#123

Post by ceautery »

gjulianm wrote: post #77
bane wrote: post #45

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

Development time. Why invest time in such optimizations instead of other features when the app is fast enough? Time is not infinite and we need to prioritize what takes our development time.

I'd say time spent optimizing grep (GNU or otherwise) is always well spent. Saving a clock cycle or two per execution in my work's enterprise would translate into needing to lease less hardware, based just on how much grep is used. I imagine the same is true of all large Unix-y enterprises.

Re: Why GNU grep is fast (2010)

#124

Post by staz »

Danieru wrote: post #111
noonespecial wrote: post #79

Earlier quoted context omitted.

Returning 0 is technically doing something. It might not be something that you find useful but it is something.

On unix you'll find two programs which do this exact thing: `false` and `true`. False returns 1, and true returns 0. You might not believe that these are real programs but they are. You can find the binaries using `whereis`. For example on my linux install true is /bin/true. The command line is pretty awesome.

And here are the actual code source for them :

http://git.savannah.gnu.org/gitweb/?p=coreutils.git;a=blob_p...

/bin/true source is a bit longer than expected but /bin/false implementation is really interesting : http://git.savannah.gnu.org/gitweb/?p=coreutils.git;a=blob_p...

Re: Why GNU grep is fast (2010)

#125

Post by amit_m »

I wonder how much these tricks matter nowadays. Even if we ignore the time to read from disk, for simple algorithms that scan data linearly, it is often the case that the CPU is spending most of its time waiting for the data to be read from RAM.

Also, in modern x86 processors, an entire cache line (64 bytes) is read whenever a single byte is needed. So for strings smaller than 64, even algorithms that don't check every byte will read every byte from disk to RAM and from RAM to the processor cache.

Re: Why GNU grep is fast (2010)

#126

Post by colanderman »

amit_m wrote: post #125

I wonder how much these tricks matter nowadays. Even if we ignore the time to read from disk, for simple algorithms that scan data linearly, it is often the case that the CPU is spending most of its time waiting for the data to be read from RAM. Also, in modern x86 processors, an entire cache line (64 bytes) is read whenever a single byte is needed. So for strings smaller than 64, even algorithms that don't check eve…

Even if we ignore the time to read from disk, for simple algorithms that scan data linearly, it is often the case that the CPU is spending most of its time waiting for the data to be read from RAM.

Nope. Even DDR-3 can perform sequential transfers at speeds well exceeding one byte per CPU clock cycle.

And yes, you can ignore the time to read from disk. Think a SAN over a 10-gig link. That gets you close to byte-per-cycle territory as well. It takes on the order of a dozen cycles (more or less depending on architecture and algorithm) to perform one "step" of a search. So yes, these algorithms very much matter.

Also, in modern x86 processors, an entire cache line (64 bytes) is read whenever a single byte is needed. So for strings smaller than 64, even algorithms that don't check every byte will read every byte from disk to RAM and from RAM to the processor cache.

Yep. But this is not necessarily the bottleneck; see my above comments about the CPU.

Re: Why GNU grep is fast (2010)

#127

Post by disgruntledphd2 »

staz wrote: post #124
Danieru wrote: post #111

Earlier quoted context omitted.

On unix you'll find two programs which do this exact thing: `false` and `true`. False returns 1, and true returns 0. You might not believe that these are real programs but they are. You can find the binaries using `whereis`. For example on my linux install true is /bin/true. The command line is pretty awesome.

And here are the actual code source for them : http://git.savannah.gnu.org/gitweb/?p=coreutils.git;a=blob_p... /bin/true source is a bit longer than expected but /bin/false implementation is really interesting : http://git.savannah.gnu.org/gitweb/?p=coreutils.git;a=blob_p...

That is both hilarious and brilliant. The bin/false source code made me laugh out loud.

Re: Why GNU grep is fast (2010)

#128

Post by mtdewcmu »

tetha wrote: post #101
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…

Couldn't you speed up a small-alphabet search by considering pairs or triplets of characters so you have N^2 or N^3 glyphs instead of N characters (so, going from 4 characters to 16 cgaracters to 64 characters)?

I'm not sure exactly how your proposal might work, but, generally, the problem you would run into is that the group of characters can be shifted. So you'd end up having to compare every possible shift.

Re: Why GNU grep is fast (2010)

#129

Post by mtdewcmu »

staz wrote: post #124
Danieru wrote: post #111

Earlier quoted context omitted.

On unix you'll find two programs which do this exact thing: `false` and `true`. False returns 1, and true returns 0. You might not believe that these are real programs but they are. You can find the binaries using `whereis`. For example on my linux install true is /bin/true. The command line is pretty awesome.

And here are the actual code source for them : http://git.savannah.gnu.org/gitweb/?p=coreutils.git;a=blob_p... /bin/true source is a bit longer than expected but /bin/false implementation is really interesting : http://git.savannah.gnu.org/gitweb/?p=coreutils.git;a=blob_p...

true.c could be useful as a kind of helloworld -- a minimal example of the conventions followed by gnu command line programs.

Re: Why GNU grep is fast (2010)

#130

Post by rm445 »

mtdewcmu wrote: post #129
staz wrote: post #124

Earlier quoted context omitted.

And here are the actual code source for them : http://git.savannah.gnu.org/gitweb/?p=coreutils.git;a=blob_p... /bin/true source is a bit longer than expected but /bin/false implementation is really interesting : http://git.savannah.gnu.org/gitweb/?p=coreutils.git;a=blob_p...

true.c could be useful as a kind of helloworld -- a minimal example of the conventions followed by gnu command line programs.

GNU Hello exists for this purpose.
Post reply on HN