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

21–30 of 133 posts

Re: Why GNU grep is fast (2010)

#21

Post by bouk »

smackay wrote: post #20

In other words the correct choice of algorithm and data structure can dramatically simplify a problem and the amount of code and time needed to solve it. It also means that having tools where you can quickly apply different techniques, ahem, composable functions, that you can search for more efficient solutions with a lot less effort. That doesn't solve the smartness problem but it makes it a lot more tractable.

This is not just because of algorithm and data structure though, it's also very well implemented

Re: Why GNU grep is fast (2010)

#22

Post by pmiller2 »

This applies very well to optimization, too. There are only really two ways to optimize code:

1) make it do less

2) make it do more at a time.

The first corresponds to using more efficient algorithms and data structures. The second is parallelism.

Re: Why GNU grep is fast (2010)

#23

Post by nzp »

garethadams wrote: post #11
alan_cx wrote: post #9

Earlier quoted context omitted.

The article references an article published in 1991. Does that need stating too?

If this story was just a blogspam saying "Hey look I found this article from 1991 which is still relevant" then yes, because the story would be worth nothing by itself. But this story is actually an email (from 2010) written by the guy WHO ORIGINALLY WROTE GREP, making it a pretty damn interesting source in its own right. In that sense, the 1991 article is very much an aside. In conclusion, no.

> by the guy WHO ORIGINALLY WROTE GREP

Just a pedantic remark: He (Mike Haertel) originally wrote GNU grep. Grep, on the other hand, was originally written by Ken Thompson.

Re: Why GNU grep is fast (2010)

#24

Post by quizotic »

pmiller2 wrote: post #22

This applies very well to optimization, too. There are only really two ways to optimize code: 1) make it do less 2) make it do more at a time. The first corresponds to using more efficient algorithms and data structures. The second is parallelism.

> Make it do less.

Yes, but less in a particular way. It's important to skip processing stuff that can't matter in the end. In this example, skipping over bytes that can't matter because the end doesn't match. In DBMS, it's important to skip over records/columns/values that can't contribute to the answer.

The surprising realization in optimization is that procrastination is a virtue. Lazy beats eager.

Re: Why GNU grep is fast (2010)

#25

Post by ColinWright »

In case you're interested to see what older HN contributors had to say about this, here are some of the previous submissions, all of which have significant discussion:

https://news.ycombinator.com/item?id=1626305, 1193 days ago, 115 comments

https://news.ycombinator.com/item?id=2393587, 972 days ago, 68 comments

https://news.ycombinator.com/item?id=2860759, 842 days ago, 43 comments

( ionelm also pointed out a previous submission: https://news.ycombinator.com/item?id=6814153 )

Also worth mentioning is "The Treacherous Optimization" ( http://ridiculousfish.com/blog/posts/old-age-and-treachery.h... ), although previous submissions of that provoked no discussion at all.

https://news.ycombinator.com/item?id=1624402

https://news.ycombinator.com/item?id=5257874

ADDED IN EDIT: More rigorous searching has turned up substantial discussion of the Treacherous Optimization: https://news.ycombinator.com/item?id=1627367

Re: Why GNU grep is fast (2010)

#26

Post by shooper »

pmiller2 wrote: post #22

This applies very well to optimization, too. There are only really two ways to optimize code: 1) make it do less 2) make it do more at a time. The first corresponds to using more efficient algorithms and data structures. The second is parallelism.

It's not just make it do less but not to do something until it is really needed.

Re: Why GNU grep is fast (2010)

#28

Post by mseebach »

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 do that in any programming language by, well, not computing unused values.

Re: Why GNU grep is fast (2010)

#29

Post by mhurron »

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.

This is why I say I'm at my most efficient when I just don't do any work at all.

Re: Why GNU grep is fast (2010)

#30

Post by chii »

mseebach wrote: post #28
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 do that in any programming language by, well, not computing unused values.

That's like saying anyone can make money by just making money. It's a null statement!
Post reply on HN