Why GNU grep is fast

http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html#

by shawndumas • 15 years ago

329 68 15 years ago

lists.freebsd.org

RiderOfGiraffes5• 15 years ago

Dup: http://news.ycombinator.com/item?id=1626305

Many, many, many comments there.

hartror• 15 years ago

Less than a year old. HN really needs to alert you to dupes when you submit . . or does it? I know it doesn't allow you to post a dupe for a cool off period after it has been posted . . .

jonknee• 15 years ago

There is a dupe checker, but only for exact matches (which if there is one instead of getting a warning it automatically lodges an upvote of that link on your behalf). The OP of this thread appended a # to the end of the URL to bypass the filter.

duck• 15 years ago

No cool off period (although that is a good idea). I just submitted a good read and it head already been posted 616 days ago, and thus no one will see it.

yan• 15 years ago

Obligatory post by ridiculous_fish on grep's speed optimizations: http://ridiculousfish.com/blog/archives/2006/05/30/old-age-a...

RiderOfGiraffes5• 15 years ago

And the HN discussion: http://news.ycombinator.com/item?id=1627367

aidenn0• 15 years ago

Interestingly enough, awk is many times faster for an inverted grep (grep -v) than grep is. Get a large file and test yourself!

grep -v regex awk '$0 !~ /regex/ {print}'

This is possibly due largely to this not helping in that case:

GNU grep AVOIDS BREAKING THE INPUT INTO LINES.

awk is very fast at breaking the input into lines (that's what it spends most of the day doing!). I don't understand why it's so much slower though. (I had a 100+MB log file that I was searching when I discovered this).

sliverstorm• 15 years ago

Odds are grep is not super optimized for the -v case...

jrockway• 15 years ago

The key to making programs fast is to make them do practically nothing.

This is the Ultimate Truth of optimizing computer programs, and it seems so few people understand it.

"Why can't you make Python faster!?" Because Python does a lot of stuff without you asking.

StavrosK2• 15 years ago

It might be the Ultimate Truth, but it also begs the question. Of course you need to make programs do less, the question is how you actually do it...

j_baker• 15 years ago

He didn't say it was the Complete Ultimate Truth, did he?

JeanPierre• 15 years ago

I have to disagree, and I could actually use Boyer-Moore as an example on this:

Split the string you're searching into four roughly equal pieces, with an overlap so that potential matches is guaranteed to be found. Then do a Boyer-Moore on those in parallel. E.g. if you look after FOO, you'd have to split the string like this (pipes are the start/end of the piece exclusive, i.e. piece 1 does not contain the last O)

    piece 1 here|
  ...7890abcdeFOOghijk
             |piece 2 here

Now, what we know is that in the worst cases, this would require more operations: The O may be detected by piece 1, and it will check if the character in front is an O as well. Piece 2 will also check the same O, so there's redundant computation going on. However, this is theoretically faster (I'd guess it is practically faster for large files) even though this requires more operations.

xpaulbettsx• 15 years ago

Another way of putting this was from an nVidia developer deck I once read: the fastest triangle you can render is the one you don't render at all.

crasshopper4• 15 years ago

I thought the Ultimate Truth of optimizing computer programs was: Premature optimization is the root of all evil.

nostrademons• 15 years ago

If you're doing it right, then by the time you've decided to optimize, it's no longer premature.

gaius• 15 years ago

http://www.jwz.org/doc/easter-eggs.html

Mozilla is not big because it's full of useless crap. Mozilla is big because your needs are big. Your needs are big because the Internet is big. There are lots of small, lean web browsers out there that, incidentally, do almost nothing useful

crasshopper4• 15 years ago

Which browsers? uzbl? midori? seamonkey? lynx?

DarkShikari3• 15 years ago

- Roll your own unbuffered input using raw system calls.

A small toy project I wrote last year was a modification of GNU grep that did the opposite -- it aggressively prefetched ahead of the file it was currently reading. This helped performance dramatically on fragmented data (e.g. tons of small files).

For most typical greps (at least of files as opposed to standard input), "grep" is likely disk-bound, not CPU-bound.

(Note: I mean literal prefetch, not actually reading the file from disk. This is important because file input is a blocking operation in UNIX -- the thread blocks when read() is called and can only be resumed when the read is complete, unlike the case of output. This prevents the filesystem from reordering or merging multiple reads unless they come simultaneously from different threads. This is why reads are often slower than writes on typical data.)

electrum• 15 years ago

How did that compare to --mmap?

angusgr2• 15 years ago

Wow, I didn't realise grep had a separate --mmap option. Interesting.

I don't think it would make much difference in the parent's case of many, small, fragmented files because if you're mmapping each file in turn and it's not cached, it still needs to be loaded from disk - it just happens in a page fault instead of the read() call.

Possibly if you mmapped all of the files and then used madvise() or something to prefetch in front of where you are in the list of files. Maybe grep does that, I don't know?

I guess the case where that technique would help is actually when you have a combination of (a) many files, (b) a computationally expensive pattern match (even just -i is a measurable hit) and (c) largeish files.

Because on many small files and a simple match, the disk I/O is still going to be the major component - even if you prefetch you still can't get around needing to load all the file contents from disk.

dasht4• 15 years ago

"mmap" is not a general solution for grep. It's nice when it can be used but grep must be able to grep files much to large to reasonably mmap and various kinds of streams.

dasht4• 15 years ago

Regarding this bit: "Roll your own unbuffered input using raw system calls. / A small toy project I wrote last year was a modification of GNU grep that did the opposite -- it aggressively prefetched ahead of the file it was currently reading. "

I think you mis-understood. "Roll your own unbuffered input [....]" does not mean "do not read ahead" it means "do not use stdio". Stdio buffers have a lot of overhead (relatively speaking) in support of features that grep does not need.

ecaron• 15 years ago

This is discussed best in the opening chapter of O'Reilly's Beautiful Code: http://oreilly.com/catalog/9780596510046. Google Books has a readable snippet of the section at http://bit.ly/g34QRh, but I highly recommend buying the book because it is a great read.

gorset3• 15 years ago

The other day I was actually surprised over how slow gnu grep was. I wanted to count how many lines in a log file contained a domain. Using grep -c <domain> <file> took 25 seconds for 1.7GB log file, whilst agrep only took 5 seconds.

novas0x2a• 15 years ago

One thing to check: what is your current locale? GNU grep is much, much slower when it's multibyte-aware, even if you're searching for an ascii string. Try repeating your test with LC_ALL=C grep (don't forget to take the filecache into account).

You can check the current values of your locale with `locale`.

ssp• 15 years ago

That's also the case for sort. If you often sort huge ASCII files, doing it in LC_ALL=C is a huge win.

gorset3• 15 years ago

Nice! That fixed it. Now it's 3 seconds.

I'm still surprised why it's so much slower with UTF-8, though. I guess gnu grep is naively converting back and forth between representations? There's nothing in UTF-8 that should prevent it from doing this efficiently. Even with complex patterns, it possible to search through the file in about the same time as a simple pattern. E.g. aspell can build a FSA where each transition is O(1), making the search time more or less independent of the search pattern.

nprincigalli• 15 years ago

Check out ack, tailored for programmers: http://betterthangrep.com/

TallGuyShort• 15 years ago

For vi users, I recommend this plugin: https://github.com/mileszs/ack.vim. I like it better than simply replacing grep with ack. This has made me a lot more productive, as I can do complex searches MUCH faster!

arnemart• 15 years ago

Textmate users should absolutely check out AckMate (https://github.com/protocool/AckMate), which runs circles around "find in project".

wazoox2• 15 years ago

Generally speaking, matching regexpes using perl instead of grep is often a win :

    perl -p -e 'm/regexp/' somefile

chaosfox• 15 years ago

That will print the whole file regardless, I think you meant:

       perl -ne 'print if /regex/' file

juiceandjuice3• 15 years ago

I have some serious love for mmap.

I don't know how many people's code I've optimized by eliminating:

FILE *f;

f = open("file.dat","r")

f.read(...)

and replacing it with mmap'd I/O

dasht4• 15 years ago

What if the input is not from a regular file?

jules2• 15 years ago

In which cases is mmap faster?

juiceandjuice3• 15 years ago

data analysis, i.e. reading in large files, but overall it's pretty fast anyways. Furthermore, you don't read the whole file into memory so your program only uses a small amount of memory while running. I'd work with grad students reading in 1-2GB of data to analyze it and allocating that all to a process, and they'd wonder why their system would slow down.

The best thing about it is that the OS does the caching. So, say I analyze a file, I run a program with 4 arguments that maps a file to memory. Next time it runs, the file is still in memory so it doesn't bother re-reading the original file. (Try doing a recursive grep on directory, then try it again right after)

minimax• 15 years ago

What language could you possibly be using here? The first line looks like C, but then in C on most systems, open returns an int (a file descriptor). Maybe you wrote open() but you meant fopen()? An easy mistake, but then how are we to interpret the syntax in the 3rd line? f.read(...)? What is this I don't even.

> I don't know how many people's code I've optimized...

I'm gonna venture a guess of 0 on this one.

juiceandjuice3• 15 years ago

haha, I just realized this... I meant C, but I think I've been screwing around in python so much lately that I kind of did that naturally on accident.

dasht4• 15 years ago

Mike has only given part of the answer there. GNU grep obviously is very I/O tuned. And GNU grep optimizes the special cases of constant strings and of regexps that (more or less) start with a constant string -- but there's more!

GNU grep is also fast for most commonly encountered non-constant-string regexps (even those that don't start with a constant string) because its regexp engine avoids backtracking by doing an on-the-fly conversion (of many patterns) to a DFA. These extra cases are algorithmically neat and when you want them, you're glad they're there -- but they are less sexy in benchmarks because the most common use case in the real world, by far, is a search for a constant string.

pedrocr3• 15 years ago

How far could you go in a discussion like this before BSD grep could reasonably be considered a derived work of GNU grep?

The discussion is going deeply into how GNU grep is implemented so it's clearly not a clean-room reverse engineering kind of situation. On the other hand nothing is being discussed that could be subject of copyright as only ideas and algorithms are put forth and no code is shown. How careful do you have to be to be sure?

redthrowaway3• 15 years ago

I'm assuming you're asking when BSD grep has to be released under the GPL? As the BSD license is slightly more restrictive than the GPL, I imagine that the GPL would have to be adopted if there was significant code usage, which there doesn't appear to be in this case.

jallmann• 15 years ago

> As the BSD license is slightly more restrictive than the GPL

Other way around.

pedrocr3• 15 years ago

The case where code is used would make it clear cut that you need to GPL it. You can relicense BSD (without advertisement clause) to GPL but not the other way around.

My doubt is at what point would you need to GPL it even though you haven't actually reused any code, just described the GPL code to someone who then reimplemented it into the BSD grep. This case still seems pretty benign as only general algorithms and approaches are shared but it made me consider where the line might be.

petermin• 15 years ago

Thank you very much for sharing this!!!

crasshopper4• 15 years ago

This makes me wonder: how is greplin so fast? And how come gmail search is slow?

(Yeah, I could ask somewhere else ... but this is HN, I bet someone looking at this Just Knows.)

terrapinbear• 15 years ago

Unrolling that inner loop in the Boyer-Moore algo is called "Duff's Device".

Why GNU grep is fast

Related Stories