Why GNU grep is fast
lists.freebsd.org
lists.freebsd.org
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.
You can only make it do less.
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
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
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.)
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.
It doesn't do that, and that's the first method I used in my hack.
fadvise() works just as well though, I think.
Fair enough. :) If you feel like sharing then I'm very curious as to what the additional methods were.
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.
Many, many, many comments there.
It isn't an easy problem to solve, working out if two URLs are equivalent, but the RFC goes some way to solving it which picks up easy things like adding a #.
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).
perl -p -e 'm/regexp/' somefile perl -ne 'print if /regex/' fileYou can check the current values of your locale with `locale`.
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.
Edit: Granted, since I'm using -c, it has to look at all the bytes to find all the newlines.
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
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)
> I don't know how many people's code I've optimized...
I'm gonna venture a guess of 0 on this one.
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.
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?
Other way around.
From the point of view of the FSF, the BSD license is more restrictive, as it grants fewer freedoms to users. From the BSD point of view, GPL grants fewer freedoms to developers, and is thus more restrictive.
In the context of the question asked, I was approaching it from the POV of the GPL's authors, given that the question was whether the BSD code would have to adopt the GPL license. I apologize for my inarticulateness.
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.
When LWN does a description of how the VM or scheduler works they are effectively describing the code. But maybe that's the same as a research paper on algorithms where reimplementation is clearly possible. Maybe for it to be a derived work you'd have to describe the code so exactly you'd be effectively translating it in whole to another form.
(Yeah, I could ask somewhere else ... but this is HN, I bet someone looking at this Just Knows.)