4 ms·

This appears to be the same algorithm used by ripgrep (https://github.com/BurntSushi/ripgrep https://github.com/BurntSushi/ripgrep) for searching when SIMD/AVX

This appears to be the same algorithm used by ripgrep (https://github.com/BurntSushi/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.

Bohp3oow 8y ago
Teddy seems to be just one small specialized chunk of hyperscan.
burntsushi 8y ago
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. :-)
- glangdale 8y ago
  Imma keep telling you until you grab my merge logic. :-)
lambda 8y ago
Yes, ripgrep (or specifically, the Rust regex crate) takes inspiration from Hyperscan for its SIMD matching. https://github.com/rust-lang/regex/commit/203c509df9e1dcba61eaa60ba9c09be9ca0c4b25 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.
- glangdale 8y ago
  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.

4 ms·

This appears to be the same algorithm used by ripgrep (https://github.com/BurntSushi/ripgrep https://github.com/BurntSushi/ripgrep) for searching when SIMD/AVX

by hlieberman 8y ago

Bohp3oow 8y ago
Teddy seems to be just one small specialized chunk of hyperscan.
burntsushi 8y ago
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. :-)
- glangdale 8y ago
  Imma keep telling you until you grab my merge logic. :-)
lambda 8y ago
Yes, ripgrep (or specifically, the Rust regex crate) takes inspiration from Hyperscan for its SIMD matching. https://github.com/rust-lang/regex/commit/203c509df9e1dcba61eaa60ba9c09be9ca0c4b25 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.
- glangdale 8y ago
  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.