Hacker News Reader

Comment by hlieberman | Hacker News Reader

This appears to be the same algorithm used by ripgrep (https://github.com/BurntSushi/ripgrep) for searching when SIMD/AVX is enabled. Specifically, it uses the algorithm Teddy from the library that’s derived from this paper.

View on HN

ripgrep author here. Yes, the Teddy algorithm was originally extracted from Hyperscan. But this is a teeny tiny piece of Hyperscan. And AFAIK, ripgrep's implementation (which is actually in the underlying regex library) doesn't carry over the full Teddy algorithm. Or so I've been told. :-)

Imma keep telling you until you grab my merge logic. :-)

Yes, ripgrep (or specifically, the Rust regex crate) takes inspiration from Hyperscan for its SIMD matching.

https://github.com/rust-lang/regex/commit/203c509df9e1dcba61...

Both libraries also rely on a number of techniques from existing published research.

Hyperscan is ruthlessly optimized for x86 platforms, but has dropped support for non-x86 platforms. Rust's regex crate is designed more as a general purpose, portable regular expression implementation, suitable for wide scale use.

I like 'ruthlessly'. It sounds very butch, especially applying to an activity largely carried out by seated, balding men hunched over terminals in an office.

Rust regex is suited to wide scale use. By comparison to Hyperscan, it is not suited to the kind of large scale cases that Hyperscan handles, but it's well done.

Many of Hyperscan techniques are sui generis, not published. Hopefully some of that will be rectified over time.

Teddy seems to be just one small specialized chunk of hyperscan.

Reply on news.ycombinator.com