In Search of Lost Time: GNU Grep 3.7 released with fix for 'extreme performance degradation'
- Reference: 1629116468
- News link: https://www.theregister.co.uk/2021/08/16/gnu_grep_37/
- Source link:
This search tool, which looks for character patterns in files, is a core utility on Linux and other Unix-like operating systems. In November last year, a user [1]noted : "I have a use case where I run grep with a large number of search patterns on a large text file. It works well with grep-3.3, but with grep-3.4 it quickly burned through GBs of memory and almost locked up my system due to swapping ... even with just 30,000 patterns it exceeds the limit of 5GB."
By contrast, grep 3.3 used "just a few 100MB."
[2]
Grep maintainer Jim Meyering took a look and identified a bug that "triggers excessive hash collisions ... that made the new pattern-preprocessing phase take O(N^2) time for N patterns."
[3]
[4]
In the announcement for [5]version 3.7 , Meyering said that an example use (below) now takes "seconds, not days." : | grep -Ff
The bug only shows up in cases where "too many patterns hashed to too few buckets."
Grep is normally remarkably fast and a much better experience than, for example, the agony of attempting to search a large directory for a string in Windows Explorer.
[6]Debian 11 formally debuts and hits the Bullseye
[7]Elementary OS 6 Odin released on a 'pay what you want' basis
[8]Zorin OS 16 Pro arrives complete with optional 'Windows 11' desktop
[9]Russian Arm SoC now shipping in Russian PCs running Russian Linux
In 2010, GNU grep author Mike Haertel [10]posted about "why GNU grep is fast."
Haertel said that it avoids looking at every input byte by skipping ahead "whenever it finds a non-matching character," avoids copying data, and executes "fewer than 3 x86 instructions executed for each input byte it actually looks at."
The current documentation [11]explains the algorithms used (Boyer-Moore and Aho-Corasick) and acknowledges that while normally efficient, "it can be quite slow in some cases."
[12]
Certain regular expressions can result in "using an algorithm that is exponential in the worst case." Case-insensitive searches and multi-byte characters can also slow it down.
Those in search of a faster grep may want to look at [13]ripgrep , written in Rust primarily by Andrew Gallant, and which according to [14]his tests is generally faster than grep, for reasons including always-on Unicode support.
Grep normally works well though and in the event of performance issues it might be worth checking out version 3.7. That said, it takes a while for new versions of grep to filter through to distros: the version in our Windows Subsystem for Linux, for example, is 2.25.
[15]
Hat-tip to Michael Larabel at Phoronix who [16]spotted the fix.®
Get our [17]Tech Resources
[1] https://debbugs.gnu.org/cgi/bugreport.cgi?bug=44754
[2] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_software/oses&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=2&c=2YRqLtp-g3mp08uefu7Cs6AAAAII&t=ct%3Dns%26unitnum%3D2%26raptor%3Dcondor%26pos%3Dtop%26test%3D0
[3] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_software/oses&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=4&c=44YRqLtp-g3mp08uefu7Cs6AAAAII&t=ct%3Dns%26unitnum%3D4%26raptor%3Dfalcon%26pos%3Dmid%26test%3D0
[4] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_software/oses&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=3&c=33YRqLtp-g3mp08uefu7Cs6AAAAII&t=ct%3Dns%26unitnum%3D3%26raptor%3Deagle%26pos%3Dmid%26test%3D0
[5] https://savannah.gnu.org/forum/forum.php?forum_id=10037
[6] https://www.theregister.com/2021/08/16/debian_11_bullseye_released/
[7] https://www.theregister.com/2021/08/12/elementary_os_6_odin/
[8] https://www.theregister.com/2021/08/10/zorin_os_16_pro/
[9] https://www.theregister.com/2021/08/10/baikall_iru_arm_pcs/
[10] https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html
[11] https://wildebeest1p.gnu.org/software/grep/manual/html_node/Performance.html#Performance
[12] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_software/oses&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=4&c=44YRqLtp-g3mp08uefu7Cs6AAAAII&t=ct%3Dns%26unitnum%3D4%26raptor%3Dfalcon%26pos%3Dmid%26test%3D0
[13] https://github.com/BurntSushi/ripgrep
[14] https://blog.burntsushi.net/ripgrep/
[15] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_software/oses&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=3&c=33YRqLtp-g3mp08uefu7Cs6AAAAII&t=ct%3Dns%26unitnum%3D3%26raptor%3Deagle%26pos%3Dmid%26test%3D0
[16] https://www.phoronix.com/scan.php?page=news_item&px=GNU-Grep-3.7
[17] https://whitepapers.theregister.com/
I've always got by with fgrep
RTFM
fgrep is the same as grep -F , as used in Meyering's example in the article.
grep, sed & awk
With a touch of shell scripting they're all you'll ever need to quickly solve most everyday problems.
Re: grep, sed & awk
I would add cut, join, comm, diff and sort, with the occasional tr and tail, pulled together by a good understanding of some of the more obscure parts of ksh/bash.
The tradditional UNIX tool set contains just so many obscure, but often very useful commands if you know them.
It was all just so easy when you could grab the permuted index for the man pages, and just read through to see what commands were there, and then go and read the actual man pages. The GNU Info documentation, even if it were complete, which is isn't, is just not as easy to browse.
Re: grep, sed & awk
There are some useful modern tools to add to Peter G's list, particularly [1]gron which converts JSON into a 'one value per line with a full path' format making it easily grep-able.
[1] https://tompaton.com/blog/cached/github.com/tomnomnom/gron.html
Re: grep, sed & awk
You forgot cat and tail.
Re: grep, sed & awk
Hrmm. grep yes. I am less sure of sed and awk.
Little Jonny the sysadmin had a problem. Little Jonny thought he could solve it with sed and awk. Little Jonny had three problems.
More seriously, I find sed and awk fine for simple substitutions and variable outputs from a string but not after that.,
Re: grep, sed & awk
You would be surprised how many silicon chip designs have required sed & awk to get them into the fab over the years. Just sayin'.
Re: grep, sed & awk
Including Tetris... (a friend and old colleague wrote this): https://github.com/csBlueChip/BAShTris
Absolute insanity!
Interesting...
Enjoyed the link to the "why is gnu grep fast" mailing list...
I'd vote for ack as a good replacement