2 ms·

I feel like this is like describing GCC or Clang as "a bunch of ideas taped together". That is more or less true but also fails to capture a pretty big achieve

by chubot 5y ago

I feel like this is like describing GCC or Clang as "a bunch of ideas taped together". That is more or less true but also fails to capture a pretty big achievement. Or same with v8 and SpiderMonkey. They have a bunch of different optimization techniques tuned for specific workloads. That is, regexes are a rich enough language now, with enough different use cases, that I think it will be true for any future implementation. --- I think the articles themselves are great, but they're also pretty dense, and I wish there was a version for regex users, not implementers. It seems like people still have a lot of problems with the backtracking regex vs. regular language distinction in practice.

glangdale 5y ago
GCC and Clang have phases that communicate synergistically. If I'm working on instruction scheduling, I can get the benefits of an upstream pass that did code motion. Conversely, if I'm working on a backend for x86, I can both share benefit of the front-end generic optimizations with an ARM backend [ edit: and not be concerned about what's going on in the other backend as well ] By contrast, both Hyperscan and RE2 have a tendency to just throw different, well understood techniques at the problem of matching regular expressions, without necessarily getting much decomposition of the problem. Hyperscan goes further but at great expense and complexity - and many of the decisions we made are very "one size fits all". One of the consequences of this is that the regex vs regular language distinction you speak of tends to pop up aggressively and annoyingly, even when there are perfectly good possibilities for a solution that integrates automata and back-tracking based matching. RE2 handles this by taping back-tracking to a automata-based approach, and Hyperscan doesn't solve this at all (unless you count Chimera, which tapes libpcre to Hyperscan). Users probably shouldn't have to know about the underlying engine, but the other problem of the idiosyncratic nature of all of our 'taping' jobs is that each system has weird corners that users can wind up suddenly finding out about (and often can't really control). My dream library would allow users to indicate which tradeoffs they want (potentially telling them to "go away" when they ask for the impossible or unimplemented; e.g. "I want fully general backreferences, streaming and fixed-sized stream state").
- chubot 5y ago
  Hm decomposing the problem and integrating automata and backtracking sound interesting. Although I'll say you can't claim that the RE2 articles aren't the gold standard if you haven't worked on or published this yet! :) (as code or prose) Many things may have changed since they were written, but as far as I can tell they haven't been demonstrated in a friendly way, i.e. with the short example code in those articles.

by chubot 5y ago

glangdale 5y ago

GCC and Clang have phases that communicate synergistically. If I'm working on instruction scheduling, I can get the benefits of an upstream pass that did code motion. Conversely, if I'm working on a backend for x86, I can both share benefit of the front-end generic optimizations with an ARM backend [ edit: and not be concerned about what's going on in the other backend as well ] By contrast, both Hyperscan and RE2 have a tendency to just throw different, well understood techniques at the problem of matching regular expressions, without necessarily getting much decomposition of the problem. Hyperscan goes further but at great expense and complexity - and many of the decisions we made are very "one size fits all". One of the consequences of this is that the regex vs regular language distinction you speak of tends to pop up aggressively and annoyingly, even when there are perfectly good possibilities for a solution that integrates automata and back-tracking based matching. RE2 handles this by taping back-tracking to a automata-based approach, and Hyperscan doesn't solve this at all (unless you count Chimera, which tapes libpcre to Hyperscan). Users probably shouldn't have to know about the underlying engine, but the other problem of the idiosyncratic nature of all of our 'taping' jobs is that each system has weird corners that users can wind up suddenly finding out about (and often can't really control). My dream library would allow users to indicate which tradeoffs they want (potentially telling them to "go away" when they ask for the impossible or unimplemented; e.g. "I want fully general backreferences, streaming and fixed-sized stream state").

chubot 5y ago
Hm decomposing the problem and integrating automata and backtracking sound interesting. Although I'll say you can't claim that the RE2 articles aren't the gold standard if you haven't worked on or published this yet! :) (as code or prose) Many things may have changed since they were written, but as far as I can tell they haven't been demonstrated in a friendly way, i.e. with the short example code in those articles.