7 ms·

Here's a thread on performance vs rg (ripgrep). https://github.com/BurntSushi/ripgrep/discussions/2597 https://github.com/BurntSushi/ripgrep/discussions/2597 di

by graphe 3y ago

Here's a thread on performance vs rg (ripgrep). https://github.com/BurntSushi/ripgrep/discussions/2597 https://github.com/BurntSushi/ripgrep/discussions/2597 didn't know about hypergrep either.

infocollector 3y ago
I think you should try it before you read these conflicting benchmarks from the authors: https://github.com/Genivia/ugrep-benchmarks https://github.com/Genivia/ugrep-benchmarks
ashvardanian 3y ago
Haven't benchmarked *grep implementations, but assuming those are just CLI wrappers around RegEx libraries, I'd expect the RegEx benchmarks to be broader and more representative. There, hyperscan is generally the king, which means hypergrep numbers are likely accurate: https://github.com/p-ranav/hypergrep?tab=readme-ov-file#directory-search-usr https://github.com/p-ranav/hypergrep?tab=readme-ov-file#dire... Disclaimer: I rarely use any *grep utilities, but often implement string libraries.
- burntsushi 3y ago
  I'm the author of ripgrep and its regex engine. Your claim is true to a first approximation. But greps are line oriented, and that means there are optimizations that can be done that are hard to do in a general regex library. You can read more about that here: https://blog.burntsushi.net/ripgrep/#anatomy-of-a-grep https://blog.burntsushi.net/ripgrep/#anatomy-of-a-grep (greps are more than simple CLI wrappers around a regex engine). If you read my commentary in the ripgrep discussion above, you'll note that it isn't just about the benchmarks themselves being accurate, but the model they represent. Nevertheless, I linked the hypergrep benchmarks not because of Hyperscan, but because they were done by someone who isn't the author of either ripgrep or ugrep. As for regex benchmarks, you'll want to check out rebar: https://github.com/BurntSushi/rebar https://github.com/BurntSushi/rebar You can see my full thoughts around benchmark design and philosophy if you read the rebar documentation. Be warned though, you'll need some time. There is a fork of ripgrep with Hyperscan support: https://sr.ht/~pierrenn/ripgrep/ https://sr.ht/~pierrenn/ripgrep/ Hyperscan also has some preculiarities on how it reports matches. You won't notice it in basic usage, but it will appear when using something like the -o/--only-matching flag. For example, Hyperscan will report matches of a, b and c for the regex \w+, where as a normal grep will just report a match of abc. (And this makes sense given the design and motivation for Hyperscan.) Hypergrep goes to some pain to paper over this, but IIRC the logic is not fully correct. I'm on mobile, otherwise I would link to the reddit thread where I had a convo about this with the hypergrep author.
  - haberman 3y ago
    > I'm on mobile, otherwise I would link to the reddit thread where I had a convo about this with the hypergrep author. From some searching I think you might mean this: https://www.reddit.com/r/cpp/comments/143d148/hypergrep_a_new_fastest_grep_to_search/ https://www.reddit.com/r/cpp/comments/143d148/hypergrep_a_ne...
    - burntsushi 3y ago
      Ah yup! I just posted a follow-up that links to that with an example (from a build of hypergrep off of latest master): https://news.ycombinator.com/item?id=38821321 https://news.ycombinator.com/item?id=38821321
- burntsushi 3y ago
  OK, now that I have hands on a keyboard, this is what I meant by Hyperscan's match semantics being "peculiar": $ echo 'foobar' | hg -o '\w{3}' 1:foobar $ echo 'foobar' | grep -E -n -o '\w{3}' 1:foo 1:bar Here's the aforementioned reddit thread: https://old.reddit.com/r/cpp/comments/143d148/hypergrep_a_new_fastest_grep_to_search/jn952bp/ https://old.reddit.com/r/cpp/comments/143d148/hypergrep_a_ne... I want to be clear that these are intended semantics as part of Hyperscan. It's not a bug with Hyperscan. But it is something you'll need to figure out how to deal with (whether that's papering over it somehow, although I'm not sure that's possible, or documenting it as a difference) if you're building a grep around Hyperscan.
  - kazinator 3y ago
    How about: use Hyperscan to round up all the lines that contain matches, and process those again with regex for the "-o" semantics.
    - burntsushi 3y ago
      You mean two different regex engines for the same search? That is perhaps conceptually fine, but in practice any two regex engines are likely to have differences that will make that strategy fall apart in some cases. (Perhaps unless those regex engines rigorously stick to a spec like POSIX or ecmascript. But that's not the case here. IIRC Hyperscan meticulously matches the behavior of a subset of PCRE2, but ripgrep's default engine is not PCRE2.) You could perhaps work around this by only applying it as an optimization when you know the pattern has identical semantics in both regex engines. But you would have to do the work to characterize them. I would rather just make the regex crate faster. If you look at the rebar benchmarks, it's not that far behind and is sometimes even faster. The case where Hyperscan really destroys everything else is for searches for many patterns. Hyperscan has other logistical issues. It is a beast to build. And its pattern compilation times can be large (again, see rebar). Hyperscan itself only supports x86-64, so one would probably want to actually use Vectorscan (a fork of Hyperscan that supports additional architectures).
  - cozzyd 3y ago
    is that an alias, or does hypergrep really use the same command name as mercurial?
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 ago
  1. 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.

by graphe 3y ago

Here's a thread on performance vs rg (ripgrep). https://github.com/BurntSushi/ripgrep/discussions/2597 https://github.com/BurntSushi/ripgrep/discussions/2597 didn't know about hypergrep either.

infocollector 3y ago

I think you should try it before you read these conflicting benchmarks from the authors: https://github.com/Genivia/ugrep-benchmarks https://github.com/Genivia/ugrep-benchmarks

ashvardanian 3y ago

Haven't benchmarked *grep implementations, but assuming those are just CLI wrappers around RegEx libraries, I'd expect the RegEx benchmarks to be broader and more representative. There, hyperscan is generally the king, which means hypergrep numbers are likely accurate: https://github.com/p-ranav/hypergrep?tab=readme-ov-file#directory-search-usr https://github.com/p-ranav/hypergrep?tab=readme-ov-file#dire... Disclaimer: I rarely use any *grep utilities, but often implement string libraries.

burntsushi 3y ago
I'm the author of ripgrep and its regex engine. Your claim is true to a first approximation. But greps are line oriented, and that means there are optimizations that can be done that are hard to do in a general regex library. You can read more about that here: https://blog.burntsushi.net/ripgrep/#anatomy-of-a-grep https://blog.burntsushi.net/ripgrep/#anatomy-of-a-grep (greps are more than simple CLI wrappers around a regex engine). If you read my commentary in the ripgrep discussion above, you'll note that it isn't just about the benchmarks themselves being accurate, but the model they represent. Nevertheless, I linked the hypergrep benchmarks not because of Hyperscan, but because they were done by someone who isn't the author of either ripgrep or ugrep. As for regex benchmarks, you'll want to check out rebar: https://github.com/BurntSushi/rebar https://github.com/BurntSushi/rebar You can see my full thoughts around benchmark design and philosophy if you read the rebar documentation. Be warned though, you'll need some time. There is a fork of ripgrep with Hyperscan support: https://sr.ht/~pierrenn/ripgrep/ https://sr.ht/~pierrenn/ripgrep/ Hyperscan also has some preculiarities on how it reports matches. You won't notice it in basic usage, but it will appear when using something like the -o/--only-matching flag. For example, Hyperscan will report matches of a, b and c for the regex \w+, where as a normal grep will just report a match of abc. (And this makes sense given the design and motivation for Hyperscan.) Hypergrep goes to some pain to paper over this, but IIRC the logic is not fully correct. I'm on mobile, otherwise I would link to the reddit thread where I had a convo about this with the hypergrep author.
- haberman 3y ago
  > I'm on mobile, otherwise I would link to the reddit thread where I had a convo about this with the hypergrep author. From some searching I think you might mean this: https://www.reddit.com/r/cpp/comments/143d148/hypergrep_a_new_fastest_grep_to_search/ https://www.reddit.com/r/cpp/comments/143d148/hypergrep_a_ne...
  - burntsushi 3y ago
    Ah yup! I just posted a follow-up that links to that with an example (from a build of hypergrep off of latest master): https://news.ycombinator.com/item?id=38821321 https://news.ycombinator.com/item?id=38821321
burntsushi 3y ago
OK, now that I have hands on a keyboard, this is what I meant by Hyperscan's match semantics being "peculiar": $ echo 'foobar' | hg -o '\w{3}' 1:foobar $ echo 'foobar' | grep -E -n -o '\w{3}' 1:foo 1:bar Here's the aforementioned reddit thread: https://old.reddit.com/r/cpp/comments/143d148/hypergrep_a_new_fastest_grep_to_search/jn952bp/ https://old.reddit.com/r/cpp/comments/143d148/hypergrep_a_ne... I want to be clear that these are intended semantics as part of Hyperscan. It's not a bug with Hyperscan. But it is something you'll need to figure out how to deal with (whether that's papering over it somehow, although I'm not sure that's possible, or documenting it as a difference) if you're building a grep around Hyperscan.
- kazinator 3y ago
  How about: use Hyperscan to round up all the lines that contain matches, and process those again with regex for the "-o" semantics.
  - burntsushi 3y ago
    You mean two different regex engines for the same search? That is perhaps conceptually fine, but in practice any two regex engines are likely to have differences that will make that strategy fall apart in some cases. (Perhaps unless those regex engines rigorously stick to a spec like POSIX or ecmascript. But that's not the case here. IIRC Hyperscan meticulously matches the behavior of a subset of PCRE2, but ripgrep's default engine is not PCRE2.) You could perhaps work around this by only applying it as an optimization when you know the pattern has identical semantics in both regex engines. But you would have to do the work to characterize them. I would rather just make the regex crate faster. If you look at the rebar benchmarks, it's not that far behind and is sometimes even faster. The case where Hyperscan really destroys everything else is for searches for many patterns. Hyperscan has other logistical issues. It is a beast to build. And its pattern compilation times can be large (again, see rebar). Hyperscan itself only supports x86-64, so one would probably want to actually use Vectorscan (a fork of Hyperscan that supports additional architectures).
- cozzyd 3y ago
  is that an alias, or does hypergrep really use the same command name as mercurial?

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 ago
1. 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.