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

91–100 of 133 posts

Re: Why GNU grep is fast (2010)

#91

Post by _delirium »

FreakLegion wrote: post #85
_delirium wrote: post #72

Does this still work in Unicode? It seems like it'd cause the Boyer-Moore lookup tables to blow up in size.

You can use Unicode code points for the shift table(s -- the Horspool variant has only one table) but make them sparse, that way the tables only contain characters that exist in the pattern. Hash tables make for easy lookups, but with a bit blob of a few hundred kB you can also use a bitmask. Of course, you can also just reduce the Unicode pattern to bytes, so your alphabet is never larger than 256. This will run slo…

> Of course, you can also just reduce the Unicode pattern to bytes

Ah, right. I was under the impression this was unsafe, since you could end up with spurious byte matches that are not on character boundaries. But it seems the keyword is "self synchronizing", and UTF-8 (but not UTF-16) is safe to do byte-oriented searching on.

Re: Why GNU grep is fast (2010)

#92

Post by tfb »

pmiller2 wrote: post #58
pacala wrote: post #46

Earlier quoted context omitted.

I wholly agree that it's worth investing in finding the best solution. However, in my experience I found that having concrete code to work with is invaluable . The magic bullet for me is to slap something concrete together, then aggressively refactor / cut the crap out of it. In some sense, building software is like sculpture. You've got this amorphous block of half baked ideas, and you need to turn it somehow into a…

I call that "sketching in code." I've gotten in some trouble in interviews for "starting to write code right away," so it's a habit I'm having to fight at the moment, but I find having something in code (that I'm fully willing to throw away) really helps. It's like Fred Brooks said: ...plan to throw one away; you will, anyhow.

I agree. It helps to have something tangible and to refactor later. I think the main issue that some people (myself included of course) have with that is refactoring too late. You never want to build something big on top of sketchy code. I've done this a few times myself to try to meet a deadline, and it's really bit me in the ass. We're talking weeks maybe months down the drain.

"Sketching in code" is a great analogy. Similar to how you'd trim off the rough edges in a sketched drawing, I've found myself cutting a lot of cruft when refactoring.

Re: Why GNU grep is fast (2010)

#93

Post by wpietri »

levosmetalo wrote: post #18
zamalek wrote: post #12

I don't know who to attribute the quote to, but there is one the goes something along the lines of: "The fastest method to execute is an empty method."

> "The fastest method to execute is an empty method." The fastest method to execute is an empty method that was never called. The fastest method to execute is an empty method that was never called and never written. The fastest method to execute is an empty method that was never called and never written and never planned.

One of the things I like best about Lean-derived software development methods is that they maximize the amount of work not done.

Re: Why GNU grep is fast (2010)

#98

Post by lubomir »

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…

This page [1] nicely demonstrates differences between KMP and BM.

[1]: http://www.cs.utexas.edu/users/moore/best-ideas/string-searc...

Re: Why GNU grep is fast (2010)

#99

Post by bnegreve »

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…

Before the system can execute any one of these programs, it has fork the bash process, call exec to load the new binary in the process memory, load the standard library and map it to the adress space, open stdin / stdout, run the program, close stdin / stdout, wait for the process termination ...

Comparing to all this, a move instruction in userland won't really make a difference.

Edit: List on system calls required to execute trivial.c (on my Linux):

execve, brk, access, mmap, access, open, open, open, open, open, stat, open, stat, open, stat, open, stat, open, fstat, mmap, close, access, open, read, fstat, mmap, mprotect, mmap, mmap, close, mmap, mmap, mmap, arch_prctl, mprotect, mprotect, munmap, exit_group

Re: Why GNU grep is fast (2010)

#100

Post by mtdewcmu »

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…

I have a book called Flexible Pattern Matching in Strings[1], which covers all the algorithms that might go into a modern, state-of-the-art grep, with practical advice on performance (N.B.: Boyer-Moore is no longer state-of-the-art). The publication year is 2002.

[1] http://www.dcc.uchile.cl/~gnavarro/FPMbook/

Post reply on HN