3 ms·

I've spent years benchmarking against various AC implementations; typically in Snort. They're usually stupidly huge and slow. Rabin-Karp needs a fair bit of he

I've spent years benchmarking against various AC implementations; typically in Snort. They're usually stupidly huge and slow. Rabin-Karp needs a fair bit of help to work; I mention it as a starting point. As a core matching technique it isn't much more fancy than "put your stuff in a hash table". Handling strings of different length is in fact hard but using multiple tables is viable. It scales a lot better than Aho-Corasick in that you can engineer the size of the hash tables and anticipate performance. Conversely, AC just develops a huge 'root cloud' when the pattern sets get big - increasingly, you're always in a prefix of something. It tends to benchmark well (sorta, kinda) especially if you feed it input that doesn't look much like what you're trying to match. You then just bounce around a couple shallow states that get to be resident in L1 and you look pretty smart. Also, in Rabin-Karp or fancy variants, every access is independent of every other, a property that you can only dream of in AC as you pootle from state to state making reads that depend on what you did last. "FDR" works on a different principle - it is 'bucketed SIMD shift-or with super-characters' (see the paper). I have a third matcher in the wings based on PEXT, which I must finish up. Honestly I don't care what people do. Arguably a good deal of the money we made from Hyperscan in its closed-source era came from selling a 'regex' matcher came from just doing the simplistic case of multiple literal matching. Our Rabin-Karp thingy (multiple hash tables with different lengths and strides) was called "hlm" (originally, "Vomitsauce"), took a few pages of code, wasn't that conceptually complex, and probably by itself (sans regex) netted a few hundred thousand a year (we eventually replaced it with FDR). This is borderline ridiculous; making money of a big complex regex matcher seemed well-deserved, but making money off a simplistic task like this seemed like picking up bills of the ground. What frustrates me is that people don't generally look beyond one solution, don't innovate, and don't care that they aren't innovating or reading the literature. Apparently algorithm design is a parlor trick for getting into Google, not a thing that one might actually do.

burntsushi 8y ago
> Honestly I don't care what people do. You can't have it both ways. You clearly care to some extent. Whatever though. Clearly we disagree on how to approach this stuff. I realize you probably don't intend this, but you really come off as belittling others for not being as smart as you. It's not cool. > Conversely, AC just develops a huge 'root cloud' when the pattern sets get big - increasingly, you're always in a prefix of something. It tends to benchmark well (sorta, kinda) especially if you feed it input that doesn't look much like what you're trying to match. You then just bounce around a couple shallow states that get to be resident in L1 and you look pretty smart. The OP constructed a benchmark from exactly the task they are trying to do and did algorithm development until they got a better result. That seems like exactly the right way to approach this. Not everyone is in a position to make an extra few hundred thousand dollars by switching from AC to Vomitsauce. That's all I'm trying to do too. It's going to take a _long_ time for the field to collectively catch up to Hyperscan. It'll take me years, if I keep on my current path.
- glangdale 8y ago
  I think the field should pass Hyperscan, not catch up to it. There are a number of things about HS that I'm increasingly uneasy about. As for the rest I'm done. I don't think I can adequately explain my irritation at the general state of discourse about the things I worked on for 12+ years without coming off in all sorts of ways I don't really intend. Suffice to say I've seen things you people wouldn't believe, strawmen comparison implementations on fire off the shoulder of Orion, etc. :-) I will try to write up my new string matcher at some point, in a less convoluted context than Hyperscan. HS, from sheer complexity, makes almost all algorithms more or less undiscoverable - it's hard to avoid having some busy-body subsystem jump in front of the simple demo you're trying to do.
  - burntsushi 8y ago
    > I think the field should pass Hyperscan, not catch up to it. There are a number of things about HS that I'm increasingly uneasy about. Right. I meant it as a short-hand way of saying, "it will take a while for the field to catch up to the battle tested knowledge you've accumulated, of which, some is expressed inside Hyperscan." :-)

burntsushi 8y ago

> Honestly I don't care what people do. You can't have it both ways. You clearly care to some extent. Whatever though. Clearly we disagree on how to approach this stuff. I realize you probably don't intend this, but you really come off as belittling others for not being as smart as you. It's not cool. > Conversely, AC just develops a huge 'root cloud' when the pattern sets get big - increasingly, you're always in a prefix of something. It tends to benchmark well (sorta, kinda) especially if you feed it input that doesn't look much like what you're trying to match. You then just bounce around a couple shallow states that get to be resident in L1 and you look pretty smart. The OP constructed a benchmark from exactly the task they are trying to do and did algorithm development until they got a better result. That seems like exactly the right way to approach this. Not everyone is in a position to make an extra few hundred thousand dollars by switching from AC to Vomitsauce. That's all I'm trying to do too. It's going to take a _long_ time for the field to collectively catch up to Hyperscan. It'll take me years, if I keep on my current path.

glangdale 8y ago
I think the field should pass Hyperscan, not catch up to it. There are a number of things about HS that I'm increasingly uneasy about. As for the rest I'm done. I don't think I can adequately explain my irritation at the general state of discourse about the things I worked on for 12+ years without coming off in all sorts of ways I don't really intend. Suffice to say I've seen things you people wouldn't believe, strawmen comparison implementations on fire off the shoulder of Orion, etc. :-) I will try to write up my new string matcher at some point, in a less convoluted context than Hyperscan. HS, from sheer complexity, makes almost all algorithms more or less undiscoverable - it's hard to avoid having some busy-body subsystem jump in front of the simple demo you're trying to do.
- burntsushi 8y ago
  > I think the field should pass Hyperscan, not catch up to it. There are a number of things about HS that I'm increasingly uneasy about. Right. I meant it as a short-hand way of saying, "it will take a while for the field to catch up to the battle tested knowledge you've accumulated, of which, some is expressed inside Hyperscan." :-)