8 ms·
Why GNU grep is Fast
- terinjokes 16y ago"The key to making programs fast is to make them do practically nothing. ;-)" In a prefect world, I would prefer many programs that did nothing and worked together, than a monolithic program that does anything (and even contains a kitchen sink!) but is slow. So come on fellow developers, let's make a bunch of nothing!
- tszming 16y agoThis is essentially the same as the "RISC patent" - a patent that essentially said "if you make something simpler, it'll go faster" Quoted from James Gosling, http://nighthacks.org/roller/jag/entry/quite_the_firestorm http://nighthacks.org/roller/jag/entry/quite_the_firestorm Also, kudo's to the 15 years maintainer of GNU grep.
- jonah 16y agoIsn't that a big part of the GNU mentality too? Lots of little programs that can be easily chained together.
- telemachos 16y agoLots of little programs that can be easily chained together. I think that's usually described as "the Unix philosophy." It's not limited to GNU (nor does it originate with GNU). See, for example, the Wikipedia article on "Unix philosophy"[1]: Doug McIlroy, the inventor of Unix pipes and one of the founders of the Unix tradition, summarized the philosophy as follows:[2] This is the Unix philosophy: Write programs that do one thing and do it well. Write programs to work together. Write programs to handle text streams, because that is a universal interface. This is usually abridged to "Write programs that do one thing and do it well". [1]http://en.wikipedia.org/wiki/Unix_philosophy#McIlroy:_A_Quarter_Century_of_Unix http://en.wikipedia.org/wiki/Unix_philosophy#McIlroy:_A_Quar... [2]http://www.faqs.org/docs/artu/ch01s06.html http://www.faqs.org/docs/artu/ch01s06.html
- jacquesm 16y agoThere is this strange wall between 'program' and 'subroutines' that at times feels completely artificial. Why shouldn't 'grep' be automatically available as a routine once programmed? I can see some of the charm of 'images' such as used by smalltalk.
- telemachos 16y agoI can see some of the charm of 'images' such as used by smalltalk. Or maybe the appeal of glue languages like Bash or (one style of) Perl. It is very nice to have the ability to treat arbitrary programs like libraries for your program. (Unfortunately, because of the GNU/BSD split - among other things - this style of programming is also completely brittle. One non-standard flag, and boom.)
- alextingle 16y ago'grep' is available once programmed. Just use popen(3). Until you naturally think this way, you will not understand the Unix philosophy.
- jacquesm 16y agoI (obviously) realize that you can do that. But that's not 'natural', that's an external process with a whole pile of start-up and shut-down overhead. Incidentally, some of the worst C code I've ever seen used piped unix shell commands all over the place, as if there is no penalty to doing this.
- Locke1689 16y agoThat's true. I think the tricky part is providing segregation where it's needed. That is, the problem is in supporting systems and programs which don't conform to the standard. Process segregation and scheduling is one way of solving this problem. Another is to simply enforce the design uniformly across the entire system. IIRC Plan9 does this slightly, but a better example may be a system which uses e.g., Haskell as the base language and simply requires all programs (modules) to be interfaced with the system with public facing symbols. A 'grep' IO monad may be an interesting way of linking and segregation.
- cperciva 16y agoAs telemachos says, that's the Unix philosophy. The GNU philosophy is to add options to programs until you run out of letters in the alphabet.
- koenigdavidmj 16y agoStop! Whoever crosseth the bridge of Death, must answer first these questions three, ere the other side he see! "What... is your name?" "Sir Brian of Bell." "What... is your quest?" "I seek the Holy Grail." "What... are four lowercase letters that are not legal flag arguments to the Berkeley UNIX version of `ls'?" "I, er.... AIIIEEEEEE!"
- jacquesm 16y agoBoyer-Moore is one of the examples that made me realize clearly that on the larger scale of programmer competence I'm nobody special. Some algorithms show such out-of-the-box thinking that it blows your mind. The most interesting thing is that most pattern matching algorithms up to then got slower with longer match strings, but Boyer-Moore actually got faster! To quote Majikthise: "Bloody hell, now that is what I call thinking."...
- cperciva 16y agoThe most interesting thing is that most pattern matching algorithms up to then got slower with longer match strings, but Boyer-Moore actually got faster! Another interesting bit of trivia: In the first chapter of my thesis I present a string matching algorithm with almost exactly the same asymptotic running time as BM -- but where BM performs exact matching using no precomputed index, my algorithm performs matching with mismatches using an index. With an index, of course, exact matching is O(log N) time -- in a peculiar way, the "cost" of inexact matching is one index worth of efficiency. [EDIT: On second thought, this last comment meaningful at all? I'm not sure, but it's almost 4AM so I'm not going to figure it out now.]
- jacquesm 16y agoIs your thesis online? I'd like to read that.
- cperciva 16y agoIs your thesis online? Yes, http://www.daemonology.net/papers/thesis.pdf http://www.daemonology.net/papers/thesis.pdf I'd like to read that. I recommend skipping the proofs. They're not very informative and the calculus gets rather tedious.
- jacquesm 16y agoThank you! > I recommend skipping the proofs. They're not very informative and the calculus gets rather tedious. And besides that is well over my head anyway, but I should be able to follow your main line of reasoning.
- frou_dh 16y agoThe Security Now podcast did an episode on the Boyer/Moore algorithm. Not the most information dense way to learn about it, but might be of interest. ( Starts at 34m10s -- http://twit.tv/sn203 http://twit.tv/sn203 )
- RiderOfGiraffes 16y agoThis: > The key to making programs fast is > to make them do practically nothing. > ;-) is a paraphrase of something I posted here a long time ago: > You can't make programs run faster, > you can only make them do less. While not entirely true (and Ph.D. theses have been written about the corners where it's wrong) it's an excellent start when you have to make a program run faster.
- vinutheraj 16y agoWhile not entirely true... One counter-example I can think of is that of Judy trees - http://judy.sourceforge.net/ http://judy.sourceforge.net/ which uses more instructions to try to keep the data in cache for as long as possible. A (CPU) cache-line fill is additional time required to do a read reference from RAM when a word is not found in cache. In today's computers the time for a cache-line fill is in the range of 50..2000 machine instructions. Therefore a cache-line fill should be avoided when fewer than 50 instructions can do the same job. More info at http://judy.sourceforge.net/doc/10minutes.htm http://judy.sourceforge.net/doc/10minutes.htm
- anamax 16y ago> One counter-example I can think of is that of Judy trees - http://judy.sourceforge.net/ http://judy.sourceforge.net/ which uses more instructions to try to keep the data in cache for as long as possible. It's not a counter-example. The cost of running a program includes the cost to access memory as well as the cost of executing instructions. It also includes the cost to access disk/flash.
- kragen 16y agoBTW, the HAT-trie is supposedly a speed improvement over Judy and all other known data structures for that problem. I don't yet understand it well enough to evaluate that claim.
- jacquesm 16y agoI have your comment taped over my monitor :)
- 16y ago
- ramki 16y agoi heard most of the editors use Boyer-Moore, somebody please confirm me. :(
- jakevoytko 16y agoI tested string searching algorithms a few years ago[0][1], and Brute Force was surprisingly performant, enough that picking a string searching algorithm becomes an engineering tradeoff. It found a sentence fragment at the end of Moby Dick within 8ms, 7 times slower than Boyer-Moore. But most of us aren't searching Moby Dick, but rather a HTTP header, some user input, or a paragraph of a document. Even long-winded users won't write Moby Dick into your <textarea>. Most languages and libraries use brute force for this reason - initializing and using Boyer-Moore may be slower than brute-forcing the text. Sometimes "practically nothing" is just a brute-force search. But Boyer-Moore is the perfect choice for Grep! The likely inputs on Unix are all huge: log files, entire directory trees, output pipes from loud programs, etc. The cost of initializing a small skip table is overwhelmed by the cost of I/O and the potential volume of text. It's not surprising that they've gone to some lengths to optimize the core inner loops and the I/O in that context. [0] http://www.jakevoytko.com/blog/2007/12/11/fun-with-string-searching/ http://www.jakevoytko.com/blog/2007/12/11/fun-with-string-se... I've declared bankruptcy on broken TeX and code examples... WordPress mangles them every few updates. [1] http://www.lysium.de/blog/index.php?/archives/201-Fun-With-String-Searching.html http://www.lysium.de/blog/index.php?/archives/201-Fun-With-S... A few improvements to the code in my post
- deleted 16y ago[deleted]
- jemfinch 16y agoThe fact that computers use instructions in our universe? Seriously, if you don't understand what he's basing his claim on, it's because you don't understand the Boyer-Moore algorithm. If you know how Boyer-Moore works, the reason is obvious. Instead of snarkily replying, why don't you take the same amount of time to read the wikipedia article on Boyer-Moore and see why brute force may be faster in some cases. (Since you've already shown yourself to be lazy, however, I'll explain it: Boyer-Moore constructs two alphabet-sized integer arrays based on the "needle" you're looking for; if your haystack is smaller than twice your alphabet size, and it frequently is, then Boyer-Moore is practically guaranteed to take more time than brute force.)
- 16y ago
- rntz 16y agoBoyer-Moore is a great algorithm, but it's for fixed-string searching. grep, in the general case, handles regular expression searching. Is there some way to extend Boyer-Moore to regular expressions that I'm unaware of? Or is GNU grep's use of Boyer-Moore limited to when the search string is just a literal?
- kscaldef 16y agoIn practice, most regular expressions contain some literal strings. You can use Boyer-Moore to anchor the match, then do a full regexp match from there.
- jimbokun 16y ago..and the classical answer to implementing full Regex is finite state automaton, correct? At least, there is a one to one correspondence. I'm curious, though, about what tricks are used in actual implementations to speed things up, and what modern Regex features necessitate climbing further up the Chomsky Hierarchy. (I seem to recall reading about features getting slipped into Regex engines that made them no longer finite state, but can't recall what they were, right now.)
- kscaldef 16y agoBack-references are the most common feature in regexp engines that make them non-regular.
- sharkbot 16y agohttp://en.wikipedia.org/wiki/Shift-or http://en.wikipedia.org/wiki/Shift-or Check out Shift-Or: used in agrep, and another example of a very clever algorithm. Rather than translating a non-deterministic finite state automata to a deterministic one, it uses the boolean operations of the hardware to simulate the NFA directly. Result: linear time regexp for patterns that have less than the bit-length of a machine's registers. I.e., 32 bytes on x86, 64 bytes on x86_64, etc.
- Jtsummers 16y ago
- jules 16y agoIs there a simple generalization of Boyer Moore to regular expressions? Can something be said about the optimality of string searching, for example by assuming a probability distribution of input texts?
- thaumaturgy 16y agoOne of the issues of Apple's Develop magazine a long time ago explained the Boyer-Moore, the Tuned Boyer-Moore, and the Self-Tuning Boyer-Moore, which is what I used for a C library I was working on at the time. If you think Boyer-Moore is a trip, check out Self-Tuning Boyer-Moore. There's actually a really good writeup on it at http://www.grouse.com.au/ggrep/string.html http://www.grouse.com.au/ggrep/string.html
- konad 16y agoPlan9 grep is competitive in my simple test, often faster. It is also immune from the pathological data that will kill GNU grep - see http://swtch.com/~rsc/regexp/ http://swtch.com/~rsc/regexp/ and the BUGS section of your local GNU grep #!/usr/local/plan9/bin/rc fn 9grep { /usr/local/plan9/bin/grep '2010-[0-9][0-9]-23 02:01:57' /home/maht/lighttpd.error.log > /dev/null } fn ggrep { /usr/bin/grep '2010-[0-9][0-9]-23 02:01:57' /home/maht/lighttpd.error.log > /dev/null } fn mgrep { /usr/bin/grep -mmap '2010-[0-9][0-9]-23 02:01:57' /home/maht/lighttpd.error.log > /dev/null } switch($1) { case -9 9grep case -g ggrep case -m mgrep case * ls -l /home/maht/lighttpd.error.log time /tmp/gtest -9 time /tmp/gtest -g time /tmp/gtest -m } /tmp/gtest -rw-r--r-- 1 www wheel 1113325534 Aug 23 18:51 /home/maht/lighttpd.error.log 23.67 real 3.88 user 3.74 sys 24.28 real 0.63 user 3.89 sys 23.09 real 0.56 user 3.87 sys
- kragen 16y agoIt looks like all three of your grep commands there are I/O-bound (where are you getting a machine with much less than a gig of RAM, but 50 megabytes per second of disk streaming? Is this an old server with a RAID?), but plan9 grep uses six times as many CPU cycles as the other greps. I wouldn't call that "competitive", even if system-call overheads does knock that crippling slowdown down to less than a factor of two. Also, what kind of kernel are you running there that would peg your CPU with a mere 300 megabytes per second of disk I/O? Is DMA disabled on your disk or something? Surely not, because there aren't any IDE PIO modes that are anywhere close to 50 megabytes per second.
- acqq 16y agoSpeaking as a guy who writes in assembly too, I'm not sure that much can be gained by BM at least on modern out-of-order processors. The cost of comparing every byte is low, and to skip a few bytes can cost more in additional instructions which can slow the pipeline than it would be by just searching through every byte for the first one. Other speedups (mmap) sound reasonable.
- powdahound 16y agoack (http://betterthangrep.com http://betterthangrep.com) is a great alternative to grep, although certainly slower as its written in Perl. Great for working with smaller files such as source code though.
- koenigdavidmj 16y agoIt's faster when you are trying to skip .svn directories, and certainly easier on the fingers.
- Qerub 16y agoEverybody should read the great post "The Treacherous Optimization" about `grep` at http://ridiculousfish.com/blog/archives/2006/05/30/old-age-and-treachery/ http://ridiculousfish.com/blog/archives/2006/05/30/old-age-a....