[HN Gopher] Why GNU grep is fast (2010)
___________________________________________________________________
Why GNU grep is fast (2010)
Author : pcr910303
Score : 140 points
Date : 2022-07-24 13:46 UTC (9 hours ago)
(HTM) web link (lists.freebsd.org)
(TXT) w3m dump (lists.freebsd.org)
| xonix wrote:
| Btw, the GNU awk is also considerably faster (due to bytecode)
| than awk bundled with BSD & Mac (usually, "one true awk").
| tyingq wrote:
| Depends on the task...sometimes nawk ("one true awk") is faster
| than gawk. Mawk is almost always faster than either.
|
| An older, but good article on that:
| https://brenocon.com/blog/2009/09/dont-mawk-awk-the-fastest-...
| compiler-guy wrote:
| A CS professor of mine said, "You can't make a computer run
| faster; you can only make it do less."
|
| That's not entirely true these days due to things like thermal
| throttling, but it's still a great way to think about
| performance.
| hahnchen wrote:
| If it does less, then it won't thermal throttle.
| cmarschner wrote:
| grep still runs a regex processor though, which I think by
| default is a deterministic finite-state machine. I had the
| impression that even when only fixed strings are used one would
| still need to use -F to get to full speed. For fixed strings
| Boyer-Moore is the obvious choice.
| epage wrote:
| See also https://blog.burntsushi.net/ripgrep which contrasts
| ripgrep with GNU grep and others (from 2016)
| heywoodlh wrote:
| Ripgrep has always been interesting to me as I don't ever find
| myself bothered by the speeds of GNU grep, even when working
| with large files. Additionally, grep is a standard utility
| included on most Unix-like OS-es so it is not super risky to
| write a script that relies on grep -- in contrast to writing a
| script that relies on a not-usually-installed-by-default tool
| like ripgrep. For me, I just don't have issues with grep!
|
| I'd love to hear people's experiences on how grep wasn't
| adequate and why they use ripgrep instead.
|
| (This is not a criticism of Ripgrep: I'm glad it exists and
| that other people find it useful.)
| copperroof wrote:
| On the filesizes I was working with (log files) both silver
| surfer and GNU grep would lock up and crash. Ripgrep handled
| the same thing in _seconds_. The difference in speed is
| staggering you may not think the speed bothers you, but I
| can't go back after installing ripgrep. Its the difference
| between my mind wandering waiting for a search to complete,
| versus instantly seeing the results and not losing a train of
| thought.
| ydant wrote:
| For me the big advantage of ripgrep is it defaults to
| searching recursively so I can just do "rg term".
|
| And the plugins support, which enables something like
| ripgrep-all, which can then search PDFs, etc.
|
| If I'm scripting, though, I try to stick to common
| denominator grep.
| heywoodlh wrote:
| Ah, that makes sense. I'm glad you brought that up because
| I didn't even notice that I'm just used to adding -R to my
| grep commands when I need recursive searching.
|
| I can totally see how that would be a small, but impactful
| difference.
| adrian_b wrote:
| Whenever you normally use some programs with other
| options than their defaults, it is simpler to define
| aliases for those programs.
|
| There are many common programs that I never use with
| their standard default options (which are very bad, IMO),
| e.g. cp, mv, ln, rm, rsync, date and many others, so I
| always define aliases for them, which include those
| options that I want to use by default.
|
| So for grep, the recursive search should be included in
| the grep alias. There is no need for a new program in
| order to have this feature.
| mjochim wrote:
| > Whenever you normally use some programs with other
| options than their defaults, it is simpler to define
| aliases for those programs.
|
| I don't buy into this. These aliases tend to come at the
| cost, or at least the risk, that your workflow breaks
| when you are at another computer or working on a shell on
| some server that doesn't have this alias. That's why I
| like additional aliases, like l for ls, but with your
| favorite options. But I dislike aliases that change
| default behavior - and often in an intransparent way.
| jraph wrote:
| This, and also it ignores irrelevant files. It has sane
| defaults but you can tweak this with a .rgignore file,
| which is like .gitignore but for rg. By the way, it will
| use .gitignore files in a git directory.
|
| That means that by default, it will take a lot less time
| and won't ruin your terminal when lines of some generated
| files (especially minified ones that are all on one line)
| match your search.
|
| This is the main reason I use ripgrep.
| js2 wrote:
| > By the way, it will use .gitignore files in a git
| directory.
|
| If I'm in a repo, I'm using `git grep`.
|
| That makes `rg` a mostly redundant tool for me since it's
| optimized for searching source code. I can't really use
| it as a general purpose replacement for grep since if it
| doesn't find anything I'm left wondering whether what I'm
| searching is not really there or whether `rg` just didn't
| bother to check. Even with `--no-ignore --all`, I'm still
| not sure whether it searches everything. It's one of
| those tools that I find is too clever for my own good.
|
| So when `git grep` doesn't cover my use case, my fall
| back is `find | grep` which contains no magic and I know
| exactly what it's searching.
| heywoodlh wrote:
| Whoa, I didn't even know about `git grep`. Sure enough,
| `man git-grep` has a bunch of relevant info! Thanks for
| sharing this.
|
| I feel like there are a billion features in git (like
| this) that I don't know about.
| masklinn wrote:
| > It has sane defaults but you can tweak this with a
| .rgignore file, which is like .gitignore but for rg. By
| the way, it will use .gitignore files in a git directory.
|
| Fwiw there's also a << .ignore >> semi-standard which
| works with several tools, and not just greps e.g. fd also
| respects it by default.
| atwood22 wrote:
| Do you know about "git grep"? It's like grep but only
| greps files tracked by git. Very useful.
| pletnes wrote:
| This. Also you can do stuff like <<rg --python
| myvariable>> to search python files only. Neat for multi-
| language directory trees. (Works with many other
| languages.)
| staticassertion wrote:
| Have you worked in a monorepo? There can be 100kloc or more,
| easily, as well as tens or hundreds of gigabytes for build
| artifacts/ compilation artifacts, etc that you'll want to
| skip over.
|
| For scripts I'll still use grep sometimes for the portability
| reason, naturally.
| heywoodlh wrote:
| I have not worked in a monorepo. But that seems to be a
| great place to use `ripgrep`.
| staticassertion wrote:
| That's probably the #2 thing for me. The other is that I
| have a `~/workspace` where I put all of my projects and
| sometimes I ripgrep through there.
| marcinreal wrote:
| It doesn't even have to be a monorepo to see the speed
| difference. In Emacs I frequently invoke a thing where it
| searches my codebase as I type. With ripgrep, the results
| update almost instantaneously. ag, the silver searcher,
| is the second fastest thing I've used, but there would be
| a noticeable lag in updating the results as I typed, even
| for smaller repos.
| jrockway wrote:
| What's the emacs thing? I use deadgrep but your thing
| sounds better.
| wantoncl wrote:
| Unicode support. It might have been the Windows ports of grep
| that were the problem, but ripgrep shines with Unicode files.
| And it handles a mix of Unicode and ASCII files without
| issue.
|
| And I totally agree that having grep installed everywhere and
| it's pretty fast enough. But I had a few ripgrep searches
| that were genuinely eyeblink fast. Like my finger hadn't
| fully lifted off the enter key and it was done. On 10K+ plus
| files, about 1 GB, with 1.5M+ LOC. And the default folder
| recursion and .gitignore handling is a plus.
| Twirrim wrote:
| ripgrep absolutely tears through some large monoorepos we
| have at work, far faster than GNU grep.
|
| I imagine the performance difference is even more startling
| for anyone on a Mac who hasn't replaced BSD grep with GNU
| grep (install the gnu tools from homebrew and alias "grep" to
| "ggrep", the performance difference is huge).
| Macha wrote:
| I find I'm installing third party CLI tools anyway, for xsv
| and jq as the real irreplacable but not yet standard Unix
| tools. Once I'm having to do that, stuff like ripgrep, fzf or
| fdfind get added for having a nice UI, even if they wouldn't
| cross the essential threshold otherwise.
| 1vuio0pswjnm7 wrote:
| I have not felt the need to use ripgrep either. If there was
| some set of directories and files that I had to search
| recursively and grep was not fast enough, then I would find a
| way to reduce the size/number of directories and files that I
| am searching. That is not always an easy problem to solve,
| but I believe it is the problem most worthy of solving. To
| me, size matters. Small has its advantages.
|
| I use computers with resource constraints.^1 I have grep in
| multicall/crunched binaries. To use ripgrep I would have to
| make include it as a separate binary. Is there a solution
| similar to crunchgen for making crunched Rust binaries.
|
| I am not sure if the "ripgrep" name is a joke or the author
| is serious. Assuming the later, I am content to wait for the
| BSD and Linux projects I use to switch from C to Rust and
| from BSD/GNU grep to ripgrep, at which point I would imagine
| it will simply be called "grep". For portability.
|
| 1. This may be why I have less need for ripgrep. I try to
| keep things small. Keeping things small routinely has the
| deirable side effect of making things relatively fast.
| s17n wrote:
| Yeah, it's actually an interesting case study in performance
| optimization - GNU grep puts all this effort into optimizing
| the performance characteristics of the system calls it uses
| based on deep kernel knowledge, but ripgrep is orders of
| magnitude faster for many users via the simple trick of
| "completely ignore a lot of files by default"
| ape4 wrote:
| Sounds like both techniques could be used together.
| ducktective wrote:
| > simple trick of "completely ignore a lot of files by
|
| The author of rg wrote a blog post about this. According to
| what I recall, he did performance comparisons on _same_
| limitations and scope. So it 's not like in that benchmark,
| the difference would be due to an obvious fact as this.
| dist1ll wrote:
| That's not really what's happening in the article. If you
| read through the single file benchmark, you'll see several
| clever algorithmic improvements (like rarest byte guessing,
| building a set of variants for Unicode-aware multiple pattern
| matching, etc...).
|
| The author literally concedes that the .gitignore feature was
| not done for performance, and actually carries a significant
| overhead in large directory trees. For the sake of
| comparability, the study was controlled for the .gitignore
| overhead.
| [deleted]
| tlb wrote:
| I'd forgotten to upgrade grep on my latest Macbook. In a large
| source code repo, looking for a fixed string with no wildcards:
|
| osx grep -r: real 2m37.786s user 2m27.034s
| sys 0m3.958s
|
| ggrep -r: real 0m12.842s user 0m5.754s
| sys 0m2.825s
|
| which is the difference between something I'd avoid and something
| I'll use.
| mpweiher wrote:
| Did you try setting the locale for OSX grep?
| LC_CTYPE=C
|
| https://news.ycombinator.com/item?id=4841168
| potatoalienof13 wrote:
| Did you make sure to clear the filesystem cache between each
| run?
| tlb wrote:
| The cache was warm for both measurements, which is more
| typical of my dev environment.
| torstenvl wrote:
| Related: https://ridiculousfish.com/blog/posts/old-age-and-
| treachery....
| ijidak wrote:
| Love his summary.
|
| > The key to making programs fast is to make them do practically
| nothing. ;-)
|
| It is a great way to think about performance.
|
| Is there any way that I can write code such that I avoid this
| work altogether...?
| hyperpape wrote:
| This is a good article, but note that some recent implementations
| skip the whole Boyer-Moore machinery and don't seem to suffer for
| it
| https://lobste.rs/s/ycydmd/why_gnu_grep_is_fast_2010#c_gpim7....
| Minor self-promotion, I grabbed that link from my page on string-
| matching, https://justinblank.com/notebooks/stringmatching.html.
___________________________________________________________________
(page generated 2022-07-24 23:00 UTC)