4 ms·

What surprised me the most is how fast grepping is. It can search more bytes from memory than iterations in a simple for loop?

taldo 3y ago
Probably a pretty bad test of the _actual_ speed of grep. A more realistic test would have printable characters and frequent newlines. I wouldn't be surprised if all those bytes were just taking a fast-path shortcut somewhere.
- dan-robertson 3y ago
  Grep is fast. Like obviously in this case you’re ‘just’ measuring how fast you can read from a pipe, but there are plenty of ways grep could have been implemented that would have been slower. Generally, I think grep will convert queries into a form that can be searched for reasonably efficiently (eg KMP for longer strings (bit of a guess – not sure how good it is on modern hardware), obviously no backtracking for regular expressions.
  - burntsushi 3y ago
    I don't think KMP has been used in any practical substring implementation in ages. At least I'm not aware of one. I believe GNU grep uses Boyer-Moore, but that's not really the key here. The key is using memchr in BM's skip loop.
- SnowflakeOnIce 3y ago
  Depending on many factors (like details of the patterns used and the input), some regex engines (like Hyperscan) can match tens of gigabytes per second per core. Shockingly fast!
Night_Thastus 3y ago
Especially ripgrep! All hail ripgrep! I will never go back to not using it.
burntsushi 3y ago
It provided the easiest possible case to grep: a simple literal. So all grep needs to do is substring search. And in turn it's accelerated by use of memchr. And that in turn it's written in assembly using AVX2 vector instructions, courtesy of GNU libc.
- littlestymaar 3y ago
  (For those unaware, burntsushi is the author of ripgrep)
  - xeonmc 3y ago
    source? (edit: was supposed to be a pun)
    - paraselene_ 3y ago
      This should suffice? https://github.com/BurntSushi/ripgrep https://github.com/BurntSushi/ripgrep
- deleted 3y ago
  [deleted]
slyall 3y ago
The loki logging software takes advantage of how fast grepping is. Instead of have a big index that lets you locate the exact line you are looking for it has a much small index of tags. The tags ( something like env=prod, app=auth ) will narrow things down to say 1% of the data in the time period. The software then just greps though a few Gigabytes to find the exact lines you are after.
nathants 3y ago
grep is the beginning, not the end. it’s a great performance baseline to meet, and then beat[1]. computers are insanely fast! the startups using grep on aws are undercutting those doing slower things on aws. i wonder why aws architects never talk about grep. 1. https://github.com/nathants/bsv https://github.com/nathants/bsv

taldo 3y ago

Probably a pretty bad test of the _actual_ speed of grep. A more realistic test would have printable characters and frequent newlines. I wouldn't be surprised if all those bytes were just taking a fast-path shortcut somewhere.

dan-robertson 3y ago
Grep is fast. Like obviously in this case you’re ‘just’ measuring how fast you can read from a pipe, but there are plenty of ways grep could have been implemented that would have been slower. Generally, I think grep will convert queries into a form that can be searched for reasonably efficiently (eg KMP for longer strings (bit of a guess – not sure how good it is on modern hardware), obviously no backtracking for regular expressions.
- burntsushi 3y ago
  I don't think KMP has been used in any practical substring implementation in ages. At least I'm not aware of one. I believe GNU grep uses Boyer-Moore, but that's not really the key here. The key is using memchr in BM's skip loop.
SnowflakeOnIce 3y ago
Depending on many factors (like details of the patterns used and the input), some regex engines (like Hyperscan) can match tens of gigabytes per second per core. Shockingly fast!

Night_Thastus 3y ago

Especially ripgrep! All hail ripgrep! I will never go back to not using it.

burntsushi 3y ago

It provided the easiest possible case to grep: a simple literal. So all grep needs to do is substring search. And in turn it's accelerated by use of memchr. And that in turn it's written in assembly using AVX2 vector instructions, courtesy of GNU libc.

littlestymaar 3y ago
(For those unaware, burntsushi is the author of ripgrep)
- xeonmc 3y ago
  source? (edit: was supposed to be a pun)
  - paraselene_ 3y ago
    This should suffice? https://github.com/BurntSushi/ripgrep https://github.com/BurntSushi/ripgrep
deleted 3y ago
[deleted]

slyall 3y ago

The loki logging software takes advantage of how fast grepping is. Instead of have a big index that lets you locate the exact line you are looking for it has a much small index of tags. The tags ( something like env=prod, app=auth ) will narrow things down to say 1% of the data in the time period. The software then just greps though a few Gigabytes to find the exact lines you are after.

nathants 3y ago

grep is the beginning, not the end. it’s a great performance baseline to meet, and then beat[1]. computers are insanely fast! the startups using grep on aws are undercutting those doing slower things on aws. i wonder why aws architects never talk about grep. 1. https://github.com/nathants/bsv https://github.com/nathants/bsv