Hacker News Reader

Comment by roninkoi | Hacker News Reader

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

View on HN

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.

(For those unaware, burntsushi is the author of ripgrep)

source?

(edit: was supposed to be a pun)

This should suffice? https://github.com/BurntSushi/ripgrep

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.

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.

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.

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.

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!

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

Especially ripgrep! All hail ripgrep!

I will never go back to not using it.

Reply on news.ycombinator.com