3 ms·

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 y

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.

burntsushi 8y ago
It's really not a pity at all, considering that: 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. 3. Aho-Corasick is trivially portable.
- glangdale 8y ago
  Ha, there's a paper about FDR now. 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?
  - burntsushi 8y ago
    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.
    - glangdale 8y ago
      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.

burntsushi 8y ago

It's really not a pity at all, considering that: 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. 3. Aho-Corasick is trivially portable.

glangdale 8y ago
Ha, there's a paper about FDR now. 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?
- burntsushi 8y ago
  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.
  - glangdale 8y ago
    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.