It's a pity that Aho-Corasick always seems to be the starting point for this kind of work, because it's as slow as a wet week and/or the tables are huge (pick your poison).
To do this right you need a fast prefilter and a reasonable fast string match. Our string matcher in Hyperscan blew AC away on size and speed, typically. Unfortunately, I never had a chance to build its successor. But AC is a disaster of one dependent load after another and is mediocre at best in terms of performance.
1. There is no write up of the Hyperscan algorithm of which you speak. I wrote up a part of Teddy, but I still don't understand the full algorithm. Hyperscan's code takes serious effort to understand. I spent days staring at Teddy and I still didn't get everything.
2. Aho-Corasick is reasonably simple to implement and does fairly decently for a large number of tasks.
The fact that AC is portable and simple and that everyone feels good about themselves as a result of implementing a classical-sounding algorithm (why AC and not Rabin-Karp? who knows?) is why is keeps cropping up, like kudzu. It's still either (a) huge, (b) slow, (c) both and (d) a poor fit for modern architectures - it has a way of turning the problem into a latency problem for whichever level of memory its structures fit into (rather than a throughput problem).
It's a solution. Big deal. There are half-a-dozen better ones just floating around in the literate, but this shitty one seems to be the one people fixate on. Maybe it's because Aho and Corasick sort earlier in the dictionary than Rabin and Karp?
It's been a while since I looked into Rabin Karp, but I remember there being two issues: 1) it really wants all of its patterns to be the same length and 2) it doesn't scale to a large number of patterns. Aho-Corasick has its own issues at scale, but only to the extent that your proportion of memory reads that hit cache decreases. But honestly, I've never implemented it in anger.
I'll have to take a closer look at FDR. I thought it was for single pattern search, not multi pattern search.
I don't really understand why you're being so bombastic about this. AC has a number of nice qualities, as I mentioned above. We don't need to resort to bullshit about how it's only used because it makes people feel good about themselves. That's not a good way to win people over to your cause.
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.
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.
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.
> 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." :-)
To do this right you need a fast prefilter and a reasonable fast string match. Our string matcher in Hyperscan blew AC away on size and speed, typically. Unfortunately, I never had a chance to build its successor. But AC is a disaster of one dependent load after another and is mediocre at best in terms of performance.