Skip grep, use awk
blog.jpalardy.com
blog.jpalardy.com
For example: GNU grep uses a heavily optimized implementation of the Boyer-Moore string search algorithm [1] which (it is claimed) requires just 3 (x86) cycles per byte of input. Boyer-Moore only searches for literal strings, but grep will extract the longest literal from the search regex (e.g. the string "foo" from the regex /foo(bar|baz)+/) and use Boyer-Moore to find candidate matches that are then verified using the regex engine.
So if you have a large corpus of text to search, grep is your friend. It can easily saturate your I/O bandwidth and perform an order of magnitude faster than typical "big data" platforms. [2]
[1] https://lists.freebsd.org/pipermail/freebsd-current/2010-Aug...
[2] https://aadrake.com/command-line-tools-can-be-235x-faster-th...
I also seem to recall the ripgrep author recently trying to optimise towards grep in another HN post.
Love ag ever since I discovered it, though you have to be careful every so often it doesn't look in a filetype that mattered.
If it does less work, and takes less time, then isn't that faster?
You need to be a touch careful with blanket statements, as this conclusion isn't quite what the data in my blog says. What it says is that ag is generally slower than GNU grep on large files, primarily because GNU grep's core search code is quite a bit more optimized than ag's. However, ag can outclass GNU grep when searching across entire directories primarily by culling the set of files that is searched, and also by parallelizing search if you want to exclude running GNU grep in a simple `find ... | xargs -P`-like command. (This is thesmallestcat's point.) This is why the first set of benchmarks in my blog don't actually benchmark GNU grep, because there is an impedance mismatch. Instead, ag/pt are benchmarked against `git grep`, where the comparison is quite a bit closer. (You'll want to check out the benchmarks on my local machine, which avoid penalizing ag for its use of memory maps.[1]) The second set of benchmarks basically swap out `git grep` for GNU grep and compare the tools on very large files.
ack isn't actually included in the benchmarks because it was incredibly slow when I tried it, although there may be something funny going on.[2] To be honest, it isn't terribly surprising to me, since every other tool is compiled down to native code.
The pt/sift story is interesting, and my current hypothesis is that the tools have received a misleading reputation for being fast. In particular, when using the tools with simple literals, it's likely that search will benefit from an AVX2 optimization when searching for the first byte. As soon as you start feeding more complex patterns (including case insensitivity), these tools slow down quite a bit because 1) the underlying regex engine needs more optimization work and 2) the literal analysis is lacking, which means the tools rely even more on the regex engine than other tools do.
The short summary of ripgrep is that it should outclass all the tools on all the benchmarks in my blog. I should update them at some point as ripgrep has gotten a bit faster since that blog post. Primarily, a parallel recursive directory iterator, which is present in sift, pt and ucg as well. Secondarily, its line counting has been sped up with more specialized SIMD routines. (I should hedge a bit here. It is possible to build patterns that a FSM-like engine will do very poorly on, but where a backtracking engine may not degrade as much. The prototypical example is large repetitions, e.g., `(foo){100}`. Of course, the reverse is true as well, since FSMs don't have exponential worst case time. Also, my benchmarks aren't quite exhaustive. For example, they don't benchmark GNU grep/ripgrep's `-f` flag for searching many regexes.)
[1] - https://github.com/BurntSushi/ripgrep/blob/master/benchsuite...
With respect to expanding repetitions on literals, that already works today. e.g.,
$ rg '(foo){100}' /dev/null --debug
...
DEBUG:grep::literals: required literal found: "foofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoo"
The truly eagle-eyed would notice that there are actually only 83 instances of `foo` in this string. In fact, literal detection is actually quite a tricky task on arbitrary regular expressions, and one must be careful to bound the number of and size of literals you produce. For example, the regex `\w+` matches an ~infinite number of literals, but `\w` is really just a normal character class, and some character classes are good to include in your literal analysis.The 83 comes from the fact that 83 times 3 = 249, which buts up against a hard-coded limit in the regex engine for literal detection: https://github.com/rust-lang/regex/blob/d894c631cb6c9a062c13...
In this case, the literal detector knows that the literal is a prefix. That means a prefix match must still be confirmed by entering the regex engine. If you pass a smaller literal, e.g., `(foo){4}`, then you'll see slightly different output:
DEBUG:grep::literals: literal prefixes detected: Literals { lits: [Complete(foofoofoofoo)], limit_size: 250, limit_class: 10 }
In this case, the regex compiler sees that a literal match corresponds to an overall match of the regex, and can therefore stay out of the regex engine entirely. The "completion" analysis doesn't stop at simple regexes either, for example, `(foo){2}|(ba[rz]){2}` yields: DEBUG:grep::literals: literal prefixes detected: Literals { lits: [Complete(foofoo), Complete(barbar), Complete(bazbar), Complete(barbaz), Complete(bazbaz)], limit_size: 250, limit_class: 10 }
This is important, because this particular pattern will probably wind up using a special SIMD multi-pattern matcher. Failing that, it will use the "advanced" version of Aho-Corasick, which is a DFA that is computed ahead-of-time without extra failure transitions (as opposed to the more general lazy DFA used by the regex engine).Literal detection is a big part of the secret sauce of ripgrep. Pretty much every single regex you feed to a tool like ripgrep will contain a literal somewhere, and this will greatly increase search speed when compared to tools that don't do literal extraction.
Of course, literal extraction has downsides. If your literal extractor picks out a prefix that is a very very common string in your haystack, then it would probably be better to just use the regex engine instead of ping-ponging back-and-forth between the prefix searcher and the regex engine. Of course, there are probably ways to detect and stop this ping-ponging, but I haven't invested much effort in that yet. Alas, the performance improvement in the common case (literals make things faster) seems to wind up being more beneficial for the general use case.
There is more in my blog post: http://blog.burntsushi.net/ripgrep/#literal-optimizations
The three biggest reasons to use grepalikes is not necessarily the time to execute the search, but
1) The reduced amount of typing. It's much faster to type "ack foo --ruby" than it is to type "find . -name '* .rb' | xargs grep foo"
2) Better filetype matching, because ack and ag check things beyond just file extensions. ack's --ruby flag checks for *.rb and Rakefile and "ruby" appearing in the shebang line, for example.
3) More features that grep doesn't include, like better highlighting and grouping, or full Perl regular expressions (in ack) and a ton of other features.
Here's a command line to find all the header files in your C source. It takes advantage of the ability to use Perl's regular expressions to specify output:
ack --cc '#include <(.+?)>' -H --output='$1' | sort -u
Here's an article I wrote a while ago on comparing the features of ack and ag. https://blog.newrelic.com/2015/01/28/grep-ack-ag/
Even though I created ack, I don't care which tool you use, so long as it suits your needs and makes you happy, but if all you're using your grep/ack/ag for is "grep -R function_name ." then you're only scratching the surface of what the tools can do for you.
The alias below sets perl to loop over STDIN splitting each line on more than one whitespace character and populate an array F. The -nE will then Evaluate an expression from the command line looping over the input line-by-line.
alias glorp='perl -aF"/\s+/" -nE'
So now we have the command `glorp` to play with which has more familiar syntax than awk and all of CPAN available to play with! $ [data is generated] | glorp '/Something/ and say $F[2]'
We have access to any Perl module by putting -MModule::Name=function after the command, the following will parse a JSON record per line and glorp out what we wanted: $ echo -e '{"hello":"world"}\n{"hello":"cat"}' | glorp 'say decode_json($_)->{hello};' -MJSON=decode_json
world
cat
Maybe you are used to using curl too. There is a nice web framework in Perl called Mojolicious (http://mojolicious.org) that provides a convenience module called 'ojo' for command line use. So grabbing the summary sentence from Wikipedia articles is as straight forward as below. Notice Mojolicious lets us use CSS selectors! $ echo -e 'grep\nawk\nperl' \
| glorp 'say g("wikipedia.org/wiki/$F[0]")->dom->at("#mw-content-text > div > p")->all_text' -MojoHowever, Ruby completely inherited this aspect of Perl and is another good candidate. It's just even old systems have a perl installed that will perform the awk like functionality.
https://code.google.com/archive/p/pyp/
"Pyp is a linux command line text manipulation tool similar to awk or sed, but which uses standard python string and list methods as well as custom functions evolved to generate fast results in an intense production environment."
Of course, you can do all of this in Python, just not as a one liner.
https://code.activestate.com/recipes/437932-pyline-a-grep-li...
alias glorp='ruby -ane '
$ [data is generated] | glorp ' ~ /Something/ and puts $F[2]'
Or: $ echo -e '{"hello":"world"}\n{"hello":"cat"}' | glorp 'puts JSON.load($_)["hello"] ' -rjson
(Of course Ruby got the -a autosplit-mode and the -n assumed 'while gets(); ... end' loop from Perl along with $_ and $F, so it's very intentional that they're similar) $ echo -e 'this\nis\na\nwhatever foo' | nip 'return /whatever/.test(line) && cols[1]' # fooI can think of two very strong reasons to prefer awk over perl:
* busybox implements awk, so its (usually) available even on embedded platforms
* awk syntax is way clearer than perl, anyone that has a few experience in C + shell can figure out what is being done with some googling
awk is also powerful enough to separate output to different files, accumulate inputs, etc. And if you need anything more complex, there are tons of other languages to choose from then (including perl).
I've switched to using it as my daily driver for text search and am incredibly happy with it.
[1]: https://github.com/BurntSushi/ripgrep
[2]: http://blog.burntsushi.net/ripgrep/
Edit: I confused awk with ag originally leading to this comment. Using ripgrep as a pre-filter to awk is still a ridiculous amount faster, especially on large trees, so while the OP's suggestion is cool I can't see myself reaching for it often.
Since this is an uncommon feature, I'd like to emphasize this. :-) In particular, ripgrep will automatically search UTF-16 encoded files via BOM sniffing. That means you can run ripgrep over a directory on Windows and be confident that it will correctly search both UTF-8 and UTF-16 encoded files automatically without having to think about it.
More generally, it supports all encodings found in the Encoding Standard[1]. However, only UTF-16 is automatically detected (where UTF-8 is the presumed default), so you'll need to explicitly specify `-E sjis` (for example) if you want to search Shift_JIS encoded files.
Also, I didn't really need to do much of anything to get this working. This is all thanks to @hsivonen's encoding_rs[2] crate, which is now (I think) in Firefox.
[1] - https://encoding.spec.whatwg.org/#concept-encoding-get
I was under the impression that ripgrep is a grep implementation that was incredibly optimised thanks to BurntSushi being a complete madman.
Simple: a lot of people use awk just as a grep.
> Pulling out a field from a line is what most people use awk for, but it's honestly the least interesting part of awk. In fact, if cut supported regular expressions for specifying the field and record separators people wouldn't be using awk for that purpose (because that's all that $n does).
There's nothing magical about awk's default FS. It's literally just /\s+/. If cut's -d was slightly more clever you wouldn't need to use awk.
some-cmd | sed -E '{ s/^\s+//g ; s/\s+/ /g }' | cut -f$nAlso, cut's output manipulation is surprising. '-f 2,1' is actually the same as '-f 1,2' - you can't change the order of printing.
I know there are other programs that can do the job, but it's a little frustrating when you can 'almost' get there with a chain of piped commands and a simple tool like cut, but have to fall back on a 'real' programming language to do just that extra bit of manipulation (awk, perl, whatever, and yes, I know the shell is a programming language but you get my point!)
some-cmd | sed -E 's/^\s+//;s/\s+/ /g' | cut -f$n
Rather than some-cmd | awk '{ print $n }'
;) Also I agree it's silly you can't change the field order.Apparently the code is in rust, which I know zero of. So, I didn't try building it either.
$ curl -LO 'https://github.com/BurntSushi/ripgrep/releases/download/0.5.2/ripgrep-0.5.2-x86_64-unknown-linux-musl.tar.gz'
$ tar xf ripgrep-0.5.2-*.tar.gz
$ cp ripgrep-0.5.2-*/rg $HOME/bin/rg
If you're not a fan of this approach (downloading random binaries and slapping them into your $HOME/bin), then your other choice is to build from source. I don't use Ubuntu, but install Rust[1] and then building ripgrep is easy: $ git clone git://github.com/BurntSushi/ripgrep
$ cd ripgrep
$ cargo build --release
$ ./target/release/rg -V
ripgrep 0.5.2
And yes, it would be great to get ripgrep packaged into Ubuntu.[2] There seems to be an up-to-date PPA here.[3][1] - https://www.rust-lang.org/en-US/install.html
awk '! /something/'
Doesn't it reproduce the same behaviour as the following? grep -v 'something'I had a loop operating on a text file like this:
while read line
do
echo "$line" | sed -e "s/A/X/" -e "s/B/Y/" -e "s/C/Z/"
...
Gradually, as I added more things to replace, I noticed severe slowdown. Things got fast again when I rewrote it as while read line
do
echo "$line" | sed -e "s/A/X/" | sed -e "s/B/Y/" | sed -e "s/C/Z/"
...
Turns out the later (multiple processes in parallel) helped with throughput. cat << EOF | sed -e 's/A/X/;s/B/Y/;s/C/Z/;'
A Brave Cow
Was Walking
Crows Were Airborne
All Was Well
EOF
or, cat << EOF > myfile
A Brave Cow
Was Walking
Crows Were Airborne
All Was Well
EOF
sed -e 's/A/X/;s/B/Y/;s/C/Z/;' < myfile
or (copy-pasted from shell for clarity), $ cat foo.sh
#!/bin/sh
sed -e 's/A/X/;s/B/Y/;s/C/Z/;'
$ cat << EOF | ./foo.sh
A
Brave
Cow
EOF
X
Yrave
Zow sed -e '' < /dev/stdin
into the script, but the solution is now much simpler and faster. $ cat myfile
foo foo
baz baz
$ cat foo.sh
#!/bin/sh
sed 's/^foo/bar/;s/^baz/foobar/'
$ ./foo.sh < myfile
bar foo
foobar baz
Depending on your expression, you may want to use -E to get POSIX ERE syntax.No, Perl regular expression are different than extended regular expressions that awk and "grep -E" use.
Sure, if I'm going to commit that to a script or shell function, I'll consider going back to refactor it and clean it up. But for quick-and-dirty exploration and prototyping, a long shell pipe is often the best modular way to compose a tool.
Protip: M-X-E will call up your one-liner into an editor session, from which you can save it directly to a permanent file. The number of locally-written tools which have originated in this fashion is ... probably embarassing to admit.
Blog - http://manasvigupta.github.io/2015/06/27/color-your-logs-and...
grep has tons of great option like
-F = fgrep; no regex - way faster
-v = as mentioned in the article
-o = print only matched input, not the entire line
-C = context, print lines before and after the match; can also be used partially with -A (after) and -B (before)
I used Python most of the time but still use Perl where it is appropriate.
They are available as a separate distributions on CPAN:
https://metacpan.org/pod/App::a2p
It looked something like
ps -ef| grep SomeDaemon | grep -v grep | grep -v perl | perl -e '<do something with the pid>'At some point I'll figure out a better alternative than this or pgrep which often misses processes.
psgrep () {
ps aux | sed -n '1p;/\<sed\>/d;/'"$1"'/p'
}
It's basically the same "grep -v grep" trick, but with pure sed. Also, the initial "1p" ensures that I still get the column headers from ps. kill -HUP $(pidof SomeDaemon)
and if it insists on running, I use: sudo kill -9 $(pidof SomeDaemon)
That's it, really. killall -HUP SomeDaemonThere is a killall on Solaris also which is very different but true to its name. You do not want to run it by accident.
yes, and xargs has a particularly useful argument -P that allows to do stuff in parallel and probably deserves more love :P
`pkill -v` is not verbose mode!
Remember pkill is next to pgrep...
Get-Process | Where-Object { $_.ProcessName -eq 'SomeDaemon' } | Stop-Process
Or at the command line:
ps | ? { $_.ProcessName -eq 'SomeDaemon' } | kill
My main point is that using perl and grep, (multiple thereof!) is nuts when you can do it all in perl.
Also crazy was using -ef (all processes) when the process of interest was using a known user. So ps -u <user> would be more appropriate.
Doing as much in Perl as possible, for portability, you'd do something like
ps -u <user>| perl -ane 'm/[S]omeDaemon/ && kill "SIGTERM", $F[1]'
-a means autosplit into fields, $F[0], F[1], etc so the pid is $F[1].See `perldoc -f kill` for the Perl function kill.
You can also do the `ps` from within Perl but I don't think you'd be gaining much in readability or portability.
pgrep -l 'reg.*ex" | xargs -L1 do-stuff
or just pkill if the idea is just to send a signal.
To gather particular process metrics, ps can be invoked with process ids (-p), with full control of its output (-o), grep is rarely needed.
do_something_with_pids $(ps -C SomeDaemon ho pid)
Though it's GNU procps.When benchmarking gawk, I've found using LANG=C and avoiding UTF-8 to make a substantial difference for pattern matching.
This is also true for grep and tr and sort - the unicode handling does impact speed quite a bit and I still don't understand why this here https://stackoverflow.com/q/20226851/772013 is not treated as a bug
Also grep -n is so much nicer than something like awk '{print NR "," $0}'
Finally, I think grep must be faster if only because grep doesn't line buffer by default, although you may --line-buffered.
$ [data is generated] | awk '!/something/'Depends on what you're after. 'grep ^[^#]' also gets rid of empty lines, as they don't have a first character to match.
find . -type f -name "*.cpp" -exec awk '/something/ {print FILENAME, NR, $0}' {} \+
Clearly grep wins this round!