5 ms·
rg uses a lot of memory in the OpenSubtitles test. 903M vs 29M for ugrep. Unlike the previous test, we are not told the size of the file being searched. Would
by 1vuio0pswjnm7 3y ago
rg uses a lot of memory in the OpenSubtitles test. 903M vs 29M for ugrep. Unlike the previous test, we are not told the size of the file being searched.
Would be interesting to see comparisons where memory is limited, i.e., where the file being searched will not fit entirely into memory.
Personally I'm interested in "grep -o" alternatives. The files I'm searching are text but may have few newlines. For example I use ired instead of grep -o. ired will give the offsets of all matches, e.g.,
echo /\"something\"|ired -n 1.htm
Quick and dirty script, not perfect:
#!/bin/sh
test $# -gt 0||echo "usage: echo string|${0##*/} file [blocksize] [seek] [match-no]"
{
read x;
x=$(echo /\""$x"\"|ired -n $1|sed -n ${4-1}p);
test "$x"||exit 1;
echo
printf s"$x"'\n's-${3-0}'\n'x$2'\n'|ired -n $1;
echo;
printf s"$x"'\n's-${3-0}'\n'X$2'\n'|ired -n $1;
echo;
echo w$(printf s"$x"'\n's-${3-0}'\n'X$2'\n'|ired -n $1)|ired -n /dev/stdout;
echo;
}
Another script I use loops through all the matches.
- 1vuio0pswjnm7 3y ago1. Retrieve test.json curl -i40A "" "https://api.crossref.org/works?query=unix&rows=1000" > test.json 2. Create shell script #!/bin/sh # usage: echo string|1.sh file [blocksize] [seek]" read x; x=$(echo -n $x|od -An -tx1|tr -d '\40'); echo /$x \ |ired -n $1 \ |sed "s/.*/s&@s-${3-0}@X$2/" \ |tr @ '\12' \ |ired -q -i /dev/stdin $1 \ |sed 's/.*/w&0a/' \ |ired -n /dev/stdout We can make the script slightly faster by using busybox #!/bin/sh # usage: echo string|1.sh file [blocksize] [seek]" read x; x=$(echo -n $x|busybox od -An -tx1|busybox tr -d '\40'); echo /$x \ |ired -n $1 \ |busybox sed "s/.*/s&@s-${3-0}@X$2/" \ |busybox tr @ '\12' \ |ired -q -i /dev/stdin $1 \ |busybox sed 's/.*/w&0a/' \ |ired -n /dev/stdout NB. If redirecting output to a file, replace /dev/stdout with the file name. ired is available on Void Linux https://ftp.lysator.liu.se/pub/voidlinux/static/ https://ftp.lysator.liu.se/pub/voidlinux/static/ xbps-query.static -Rs ired-0 xbps-install.static ired 3. Test grep v3.6, ripgrep v14.0.3 and shell script; busybox is v1.34.1 busybox time grep -Eo .{35}https:.{4} test.json; busybox time rg -o .{35}https:.{4} test.json; busybox time sh -c "echo https:|1.sh 45 35 test.json" We can make the script slower by using bash busybox time bash -c "echo https:|1.sh 45 35 test.json" Program size du -h /usr/bin/grep 216K/usr/bin/grep du -h /usr/bin/rg 5.7M/usr/bin/rg du -hc /usr/bin/ired /bin/dash /usr/bin/tr /usr/bin/sed /usr/bin/od 456K/bin/dash 40K/usr/bin/ired 56K/usr/bin/tr 68K/usr/bin/od 104K/usr/bin/sed 724Ktotal du -h /usr/bin/busybox /usr/bin/ired 772K/usr/bin/busybox 40K/usr/bin/ired 812Ktotal readelf -d /bin/dash /usr/bin/busybox File: /bin/dash There is no dynamic section in this file. File: /usr/bin/busybox There is no dynamic section in this file.
- burntsushi 3y agoOK, so I'll try your commands: $ busybox time grep -Eo .{35}https:.{4} test.json real 0m 0.15s user 0m 0.15s sys 0m 0.00s $ busybox time rg-14.0.3 -o .{35}https:.{4} test.json real 0m 0.00s user 0m 0.00s sys 0m 0.00s $ busybox time dash -c "echo https:|./1.sh test.json 45 35" real 0m 0.01s user 0m 0.01s sys 0m 0.00s $ busybox time bash -c "echo https:|./1.sh test.json 45 35" real 0m 0.00s user 0m 0.00s sys 0m 0.00s $ busybox time dash -c "echo https:|./busy-1.sh test.json 45 35" real 0m 0.00s user 0m 0.01s sys 0m 0.00s $ busybox time bash -c "echo https:|./busy-1.sh test.json 45 35" real 0m 0.01s user 0m 0.01s sys 0m 0.00s So grep -o takes 150ms, but both ripgrep and ired are seemingly instant. But if I use zsh's builtin `time` command with my own TIMEFMT[1], it gives me numbers greater than 0: $ time grep -Eo .{35}https:.{4} test.json real 0.324 user 0.317 sys 0.007 maxmem 16 MB faults 0 $ time rg-14.0.3 -o .{35}https:.{4} test.json real 0.008 user 0.003 sys 0.003 maxmem 16 MB faults 0 $ time dash -c "echo https:|./1.sh test.json 45 35" real 0.010 user 0.011 sys 0.007 maxmem 16 MB faults 0 $ time bash -c "echo https:|./1.sh test.json 45 35" real 0.011 user 0.014 sys 0.004 maxmem 16 MB faults 0 Would you look at that. ripgrep is faster! By a whole 2 milliseconds! WOW! OK, since I'm a software developer and thus apparently cannot understand the lowly needs of an "ordinary user," I'll hop over to my machine with a i5-7600, which was released 6 years ago. Is that ordinary enough, or still too super charged to do any meaningful comparison whatsoever? $ time grep -Eo .{35}https:.{4} test.json real 0.641 user 0.620 sys 0.017 maxmem 6 MB faults 0 $ time rg-14.0.3 -o .{35}https:.{4} test.json real 0.010 user 0.008 sys 0.000 maxmem 8 MB faults 0 $ time dash -c "echo https:|./1.sh test.json 45 35" real 0.011 user 0.009 sys 0.011 maxmem 6 MB faults 0 $ time bash -c "echo https:|./1.sh test.json 45 35" real 0.013 user 0.021 sys 0.003 maxmem 6 MB faults 0 (I ran the commands above each several times and took the minimum.) OK, so ripgrep is still 1ms faster even on "ordinary user" hardware. All right, so your other comment also shared another benchmark: $ time grep -Eo .{100}https:.{50} test.json real 1.777 user 1.772 sys 0.003 maxmem 6 MB faults 0 $ time rg-14.0.3 -o .{100}https:.{50} test.json real 0.013 user 0.006 sys 0.000 maxmem 8 MB faults 0 $ time rg-14.0.3 --color never -o .{100}https:.{50} test.json real 0.006 user 0.006 sys 0.000 maxmem 8 MB faults 0 $ time dash -c "echo https:|./1.sh test.json 156 100" real 0.015 user 0.024 sys 0.004 maxmem 7 MB faults 0 $ time bash -c "echo https:|./1.sh test.json 156 100" real 0.016 user 0.028 sys 0.000 maxmem 7 MB faults 0 (Notice that disabling color and line numbers for ripgrep improves its speed a fair bit. ired isn't doing either of those things, so it's only fair. GNU grep doesn't count line numbers by default and disabling color doesn't improve its perf here.) This one is more interesting because it exposes the fact that many regex engines have trouble dealing with bounded repeats. Something like `.{100}` for example is not executed particularly efficiently in most regex engines. And indeed, in ripgrep by default, `.` actually matches the UTF-8 encoding of any Unicode scalar value (so between 1 and 4 bytes) and not any arbitrary byte. You'd need to pass the `--no-unicode` flag or prefix your pattern with `(?-u)` to match any arbitrary byte. And indeed, even then, `.` doesn't match `\n`. So you might even want `(?s-u)`. But since this is a grep and *greps are line oriented*, you'd need to enable multi-line mode in ripgrep (GNU grep doesn't have this): $ time rg-14.0.3 -Uo '(?s-u).{100}https:.{50}' test.json real 0.057 user 0.041 sys 0.006 maxmem 8 MB faults 0 $ time rg-14.0.3 --color never -N -Uo '(?s-u).{100}https:.{50}' test.json real 0.042 user 0.041 sys 0.000 maxmem 8 MB faults 0 This actually runs slower, I believe, because it disables the line oriented optimizations that ripgrep uses. In this case, it isn't as good at detecting the `https:` literal and looking for that first. That's where `ired` can do (a lot) better, because it isn't line oriented and doesn't need to support arbitrary regex patterns. greps are. To complete this analysis, I'm going to do something that I realize is blasphemous to you and increase the input size by ten-fold. This will help us understand where time is being spent: $ time grep --color=never -Eo .{100}https:.{50} test.10x.json real 17.931 user 17.906 sys 0.017 maxmem 7 MB faults 0 $ time rg-14.0.3 --color never -N -o '.{100}https:.{50}' test.10x.json real 0.032 user 0.017 sys 0.010 maxmem 23 MB faults 0 $ time rg-14.0.3 --color always -N -o '.{100}https:.{50}' test.10x.json real 0.137 user 0.034 sys 0.019 maxmem 23 MB faults 0 $ time dash -c "echo https:|./1.sh test.10x.json 156 100" real 0.067 user 0.089 sys 0.069 maxmem 7 MB faults 0 I compared the profiles of `rg --color=never` and `rg --color=always`, and they look about the same to me. This suggests to me that color is slower simply because rendering it in my terminal emulator is slower. For grins, I also tried ugrep: $ time ugrep-4.4.1 --color=never -o '.{100}https:.{50}' test.10x.json real 6.003 user 5.977 sys 0.007 maxmem 6 MB faults 0 Owch. But not as bad as GNU grep. So with a bigger input, we can see that `rg -o` is about twice as fast as ired, even on "ordinary" hardware. And IMO, for inputs of the size you've provided, the difference is not meaningful. Going back to your original prompt: > Personally I'm interested in "grep -o" alternatives. It seems to me like `rg -o` is quite serviceable in that regard, and at the very least, substantially better than GNU grep. At this point, I wondered what ired did for substring search[2]. That immediately stuck out to me as something that looked wrong. Indeed: $ cat haystack ABAABAB $ echo -n BAB | od -An -tx1 | sed 's>^>/>;s/ //g' | ired -n haystack 0x4 $ echo -n ABAB | od -An -tx1 | sed 's>^>/>;s/ //g' | ired -n haystack $ rg -o ABAB haystack 1:ABAB So ired is a toy. One wonders how many search results you've missed over the years because of ired's feature "it's so minimal that it's wrong!" I mean sometimes tools have bugs. ripgrep has had bugs too. But this one has been in ired since 2009. What is it that you said? YIKES. Yeah. Seems appropriate. [1]: https://github.com/BurntSushi/dotfiles/blob/eace294fd80bfde13d9443c483d223d6a56cc3a2/.zshrc#L143 https://github.com/BurntSushi/dotfiles/blob/eace294fd80bfde1... [2]: https://github.com/radare/ired/blob/a1fa7904e6ad239dde950de5dc49a51be47e0c05/cmd.c#L111-L119 https://github.com/radare/ired/blob/a1fa7904e6ad239dde950de5...
- 1vuio0pswjnm7 3y agoripgrep is not for me.
- burntsushi 3y agoI never argued otherwise. Especially since you clearly don't mind false negatives. ;-)
- burntsushi 3y ago> rg uses a lot of memory in the OpenSubtitles test. 903M vs 29M for ugrep. Unlike the previous test, we are not told the size of the file being searched. Which test exactly? That's just likely because of memory maps futzing with the RSS data. Not actually more heap memory. Try with --no-mmap. I'm not sure I understand the rest of your comment about grep -o. Grep tools usually have a flag to print the offset of each match. EDIT: Now that I have hands on a keyboard, I'll demonstrate the mmap thing. First, ugrep: $ time ugrep-4.4.1 -c '\w+\s+Sherlock\s+Holmes\s+\w+' sixteenth.txt 72 real 22.115 user 22.015 sys 0.093 maxmem 30 MB faults 0 $ time ugrep-4.4.1 -c '\w+\s+Sherlock\s+Holmes\s+\w+' sixteenth.txt --mmap 72 real 21.776 user 21.749 sys 0.020 maxmem 802 MB faults 0 And now for ripgrep: $ time rg-14.0.3 -c '\w+\s+Sherlock\s+Holmes\s+\w+' opensubtitles/2018/en/sixteenth.txt 72 real 0.076 user 0.046 sys 0.030 maxmem 779 MB faults 0 $ time rg-14.0.3 -c '\w+\s+Sherlock\s+Holmes\s+\w+' opensubtitles/2018/en/sixteenth.txt --no-mmap 72 real 0.087 user 0.033 sys 0.053 maxmem 15 MB faults 0 It looks like the difference here is that ripgrep chooses to use a memory map by default here. I don't think it makes much of a difference here. If the file were bigger than available memory, then the OS would automatically handle paging.
- deleted 3y ago[deleted]
- 1vuio0pswjnm7 3y agotask: printing non-repeating patterns in relatively small files to the screen, optionally with some context context should be printed exactly as it appears in the file, i.e., newlines should be printed ired vs ripgrep, which one is better suited for this task one uses regular expressions, the other does not one is a 76k static binary that fits in 2MB L2 cache, the other is a 5.7MB dynamically-linked binary 2 shell scripts to demonstrate differences usage: echo pattern|1.sh [num chars before] [num chars after] 1. "1.sh" using 5.7MB binary, PCRE2 #!/bin/sh read x; case $# in :) ;;0)exec echo "usage: ${0##*/} file [num chars before] [num chars after]" ;;1)exec rg -uuu -no-unicode --block-buffered --color=never -NUo "$x" $1 esac case $# in 2|3)printf "((.)|(\\\\n)|(\\\\r)){"$2"}$x((.)|(\\\\n)|(\\\\r)){"${3-0}"}";esac \ |rg -f/dev/stdin -uuu --no-unicode --block-buffered --color=never -NUo $1 2. "2.sh" using 76k static binary, no regular expressions #!/bin/sh read x; len=${#x}; b=$(($2+$len)); case $# in 0)exec echo "usage ${0##*/} file [num chars before] [num chars after]" ;;2)b=$(($2+$len)) ;;3)b=$(($3+$2+$len)) esac echo "$x" > .x { printf /;ired -n -c X1 .x;} \ |ired -n $1 \ |sed "s/.*/s&@s-${2-0}@b$b@X/;" \ |tr @ '\12' \ |ired -n $1 \ |sed 's/.*/w&0a/' \ |ired -n /dev/stdout \ |sed -e '/^Invalid hexpair/d' generate test data: curl -4si0 -A "" https://www.google.com > test.html usage example: find the pattern "(" in test.html, display results to screen echo \(|1.sh test.html regex parse error: (?:() ^ error: unclosed group echo '[(]'|1.sh test.html echo \(|2.sh test.html cat .x observation: the task is simple but 1.sh may require more typing and knowledge of regular expressions observation: 2.sh does not require knowledge of PCRE; the pattern requires no extra chars, e.g., brackets usage example: find the pattern "(a" in test.html, display results to screen with 0 chars before and 3 chars after echo '[(]a'|1.sh test.html 0 3|sed -n l|less -N echo \(a|2.sh test.html 0 3|sed -n l|less -N observation: 1.sh does not include the newline after match #187; some workaround is required for 1.sh conclusion: for me, ripgrep is too large and complicated for this simple task involving relatively small files; it's overkill. it does not feel any faster than ired at the command line. in fact, it feels slower. like python or java, or other large rust/go binaries, there is a small initial delay, a jank. whereas ired feels very smooth.
- 1vuio0pswjnm7 3y ago
- 1vuio0pswjnm7 3y agoAbout grep -o. # stat -c %s file 6297285 # file file file: ASCII text, with very long lines (1545), with CRLF, LF line terminators Imagine file as a wall of text. 1. Printing byte offsets. # time grep -ob string file 0.03user 0.08system 0:00.22elapsed 52%CPU (0avgtext+0avgdata 1104maxresident)k 0inputs+0outputs (0major+86minor)pagefaults 0swaps # rg -V ripgrep 13.0.0 # time rg -ob string file 0.10user 0.17system 0:01.11elapsed 25%CPU (0avgtext+0avgdata 7804maxresident)k 0inputs+0outputs (0major+559minor)pagefaults 0swaps # time sh -c "echo -n string|od -An -tx1|sed 's>^>/>;s/ //g'|ired -n file" 0.03user 0.09system 0:00.18elapsed 67%CPU (0avgtext+0avgdata 720maxresident)k 0inputs+0outputs (0major+189minor)pagefaults 0swaps 2. Printing some "context" around the matched string. For example, add characters immediately preceding string. Baseline. # time grep -o string file 0.02user 0.07system 0:00.15elapsed 65%CPU (0avgtext+0avgdata 1068maxresident)k 0inputs+0outputs (0major+84minor)pagefaults 0swaps Add one character. # time grep -o .string file 0.21user 0.08system 0:00.36elapsed 83%CPU (0avgtext+0avgdata 1088maxresident)k 0inputs+0outputs (0major+87minor)pagefaults 0swaps Add another character. # time grep -o ..string file 0.29user 0.09system 0:00.46elapsed 82%CPU (0avgtext+0avgdata 1064maxresident)k 0inputs+0outputs (0major+88minor)pagefaults 0swaps # time rg -o ..string file 0.13user 0.13system 0:00.90elapsed 28%CPU (0avgtext+0avgdata 9012maxresident)k 0inputs+0outputs (0major+574minor)pagefaults 0swaps Yikes. Now let's try ired. Another shell script. This one will print all occurences of string. cat > 1.sh << eof #!/bin/sh # usage: echo string|1.sh file [blocksize] [seek]" read x; x=$(echo -n $x|xxd -p); echo /$x \ |ired -n $1 \ |sed "s/.*/s&@s-${3-0}@X$2/" \ |tr @ '\12' \ |ired -q -i /dev/stdin $1 \ |sed 's/.*/w&0a/' \ |ired -n /dev/stdout eof Baseline. # echo string|time sh 1.sh 6 0.11user 0.10system 0:00.17elapsed 127%CPU (0avgtext+0avgdata 772maxresident)k 0inputs+0outputs (0major+466minor)pagefaults 0swaps Add one character before string. # echo string|time sh 1.sh 7 1 0.12user 0.09system 0:00.16elapsed 131%CPU (0avgtext+0avgdata 740maxresident)k 0inputs+0outputs (0major+473minor)pagefaults 0swaps Add another. # echo string|time sh 1.sh 8 2 0.12user 0.11system 0:00.20elapsed 112%CPU (0avgtext+0avgdata 744maxresident)k 0inputs+0outputs (0major+461minor)pagefaults 0swaps Perhaps grep or ripgrep might be slightly faster at printing byte offsets. But ired is faster at printing matches with context. (NB. Context here means characters, not lines.) Try using ripgrep to print offsets for ired. #!/bin/sh read x; rg --no-mmap -ob $x $1 \ |cut -d: -f1 \ |sed "s/.*/s&@s-${3-0}@X$2/" \ |tr @ '\12' \ |ired -q -i /dev/stdin $1 \ |sed 's/.*/w&0a/' \ |ired -n /dev/stdout # time sh -c "echo string|1.sh file 8 2" 0.11user 0.06system 0:00.18elapsed 101%CPU (0avgtext+0avgdata 5972maxresident)k 0inputs+0outputs (0major+905minor)pagefaults 0swaps # stat -c %s /usr/bin/ired /usr/bin/grep /usr/bin/rg 37544 219248 5074800