Re:How we made Haskell search strings as fast as Rust
by burntsushi on Thursday March 14, 2019 @06:59AM
(#19388093)
I thought FDR was for single literals only?
One of the hurdles for using the algorithms from Hyperscan is that it's not always clear when particular algorithms are used and in what conditions. I have the same problem in my regex library, but Hyperscan takes it to another level because it's so much more sophisticated. :)
Re:How we made Haskell search strings as fast as Rust
by glangdale on Thursday March 14, 2019 @07:08AM
(#19388137)
(see other response)
FDR is for > literals than Teddy. It's Noodle that's for single literals. Hard to imagine how you could get confused given that the names we chose are so transparent. :-)
Re:How we made Haskell search strings as fast as Rust
by burntsushi on Thursday March 14, 2019 @08:18AM
(#19388526)
Hah. I've only made it halfway through your paper so far. Excited to read the rest. :)
AC sucks. It's simple enough, but it's always going to be either slow or big - sometimes both. I'd say that's a source of frustration to me, but it's not really, as we made a lot of money selling string matching to customers back when Hyperscan was closed-source. It's so much easier to sell string matching than regex matching as regexes are full of surprises, but strings are quite tractable.
I'm not delighted with where we left string matching in Hyperscan - "FDR" was wheezing under load in a bunch of ways, and I had some better things in the pipeline. But it still should generally murder AC barring some corner cases.
Unfortunately, Hyperscan has moved away from having a pure-play literal matcher in it (what remains is really more of a specialist 1- to 8-char literal matcher), which I regard as a semi-mistake (so there may be more corner cases than there used to be).