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

61–70 of 133 posts

Re: Why GNU grep is fast (2010)

#61

Post by nostrademons »

mseebach wrote: post #43
chii wrote: post #30

Earlier quoted context omitted.

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

In the context of the comment I replied to, no, it's not. Haskell gives you some constructs that makes this easier but there exists no program whose Haskell implementations will run faster because of this, only programs that are easier to make fast.

The big advantage lazy evaluation has is composability. In an eager language, you have to explicitly code operations in a lazy fashion, which means that if you use a library, it will probably be eager. With Haskell you can be pretty sure that the runtime will evaluate only as much of the program as it needs to.

That said, the downside is that it then becomes very difficult to reason about the performance characteristics of your library, because its performance depends on how it's used. Simon Peyton-Jones is on record as saying that laziness is probably the wrong default for a language - the big benefit for Haskell was that it "kept them honest" wrt purity, but in a production system you probably want strictness.

Re: Why GNU grep is fast (2010)

#62

Post by pmiller2 »

eru wrote: post #15
TheAceOfHearts wrote: post #4

In case anyone is interested in checking it out, you can download the source here: ftp://mirrors.kernel.org/gnu/grep/

You will need some gnu common libraries. I tried building it from scratch recently, as a first step for implementing an extension idea, but didn't succeed. (If anyone is interested, I want to add more operators, like intersection or difference of regular languages.)

The shell, combined with grep already implements these intersection and difference operators. For intersection, all you have to do is pipe into a second grep [1]; for difference, you pipe into a second grep with -v [2].

[1] Intersection: grep regex1 file1 | grep regex2

[2] Difference: grep regex1 file1 | grep -v regex2

Re: Why GNU grep is fast (2010)

#64

Post by dredmorbius »

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.

The points of discarding data you don't need, not looking at stuff you don't need to look at, and minimizing the processing of the stuff you do look at are also highly valid.

I've seen 90% performance boosts in code where access to low-level data formats really wasn't possible. Though at times, using appropriate data structures / methods also helped markedly.

Re: Why GNU grep is fast (2010)

#65

Post by Someone »

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.

There is a third one, at low level: make it do something else.

For example, programmer requests a multiplication, compiler generates a shift; programmer requests a division, compiler generates a multiplication; programmer specifies a switch, compiler generates a jump table.

Re: Why GNU grep is fast (2010)

#66

Post by pmiller2 »

Someone wrote: post #65
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.

There is a third one, at low level: make it do something else. For example, programmer requests a multiplication, compiler generates a shift; programmer requests a division, compiler generates a multiplication; programmer specifies a switch, compiler generates a jump table.

I'd argue that's just a variation of doing less, in the same way that e.g. vectorization is a variation of parallelism.

Re: Why GNU grep is fast (2010)

#67

Post by AlisdairO »

ColinWright wrote: post #59
gitaarik wrote: post #54

Earlier quoted context omitted.

hey hey hey, if you want hacker news to stay fast you should't make it do too much!

The systems I wrote were independent of HN and didn't slow it down. I got significant grief for them and pulled them. Standard "wisdom" for start-ups includes "If you're not embarrassed by your first product then you didn't launch early enough," and "Try the minimal viable product before investing too much time." I both launched early, and made sure the "product" was absolutely minimal. It got slated by the people it…

I wouldn't be surprised if that was because people misinterpreted it as complaining about reposting, which is a contentious topic on HN.

Re: Why GNU grep is fast (2010)

#69

Post by gruseom »

stcredzero wrote: post #44

That's also a Forth way of looking at optimization. Also reminds me of Kent Beck's quip when he was asked to optimize Chrysler's C3 system. He asked for validated sets of input and output. The programmers on site said the the system wasn't producing correct results yet. His response: In that case, I can make this real fast!

I recall nearly the same story about Jerry Weinberg:

Engineers: Oh your system can only do a thousand cards a minute? Ours can do ten thousand.

Weinberg: Yeah but your system doesn't work! If mine doesn't have to work I can do a million cards a minute.

I thought I got it from one of Weinberg's books.

Re: Why GNU grep is fast (2010)

#70

Post by michaelsbradley »

The author of The Silver Searcher[1] has some blog posts about his efforts at optimizing his own grep-like tool.

There's nothing wrong with good ole grep, but on boxen I spend any significant time on, I always install ag. The integration with Emacs provided by ag.el[2] is awesome too!

[1] https://github.com/ggreer/the_silver_searcher#how-is-it-so-f...

[2] https://github.com/Wilfred/ag.el

Post reply on HN