From: Tim X Date: 2007-04-12T20:45:06+09:00 Subject: Re: Slow ruby regexes Robert Klemme writes: > Subject: Re: Slow ruby regexes > > On 11.04.2007 22:51, MenTaLguY wrote: >> On Thu, 12 Apr 2007 03:27:04 +0900, "Robert Dober" wrote: >>> No it must be me who is confused, I thought that backtracking cannot >>> be avoided in regexs like e.g. %r{[a]*.*a} when trying for a greedy >>> match >> using a Ragel-ish notation, the NFA for /^a*.*a/ should look like this >> (after collapsing most of the epsilon transitions introduced by Thompson's >> Algorithm): >> start: ('' ->a_star | '' ->any_star), >> a_star: ('a' ->a_star | any ->any_star), >> any_star: (any ->any_star | 'a' =>final), >> final: (any ->final) >> >> Here, -> is a regular transition, and => is a labeled transition which sets a counter (initialized to -1) to the current input position if that is larger than the counter's current value. When we have explored all possible matches, the value of the counter will be the position of the last character in the (greedy) match. >> >>> The DFA of course could never backtrack but is there a DFA for this regex? >> >> Every NFA can be rewritten as a DFA. Each state in the resulting DFA corresponds to a superposition of states in the original NFA (again in pseudo-Ragel, where {a,b,c} denotes the superposition of NFA states a, b, and c): > > While this is true in theory there is a number of modern RX features that are > extremely difficult or impossible to do with a DFA. So as it stands now for > pratical purposes most modern RX engines are NFA or hybrids, sometimes (Perl) > with heavy optimizations to prevent certain ugly effects (see "Mastering > Regular Expressions" for details). > > Kind regards > To me, this is possibly a much more important point than just being concerned over raw performance. While NFA may be *a lot* better performing in the majority of cases, if we want to add in the exra power of backreferences and other 'nice' (possibly considered advanced) features, things begin to get a lot more complicated. Unfortunately, with complexity, we usually find higher levels of bugs in the final implementation. I'm not saying that things should be kept super simple just to ensure correctness at the cost of performance. However, we should consider complexity and correctness/maintainability of implementation as well as just pure performance. For me and possibly for many others, I find this particularly important as performance of regular expressions has never been a critical issue with any of the work I've had to use them for (to what extent this is just a reflection of the types of problems I deal with I don't know). In fact, everyone I've ever helped with sorting out performance problems with their regexp, it has turned out to be badly defined regexp that were the issue rather than poor performance of the engine/underlying algorithm. Maybe the real question we should be asking is "If ruby had a regexp engine which was 10, 100, 1000, 1000000 times faster, would that allow us to solve problems which we cannot solve now in any practicle way? In principal, I think having a regexp engine which possibly adopts the DFA/NFA algorithim if backreferences are not required and use a slower backtracking approach when they are is a good approach, but only if we can ensure a stable and correct implementation. Tim Tim -- tcross (at) rapttech dot com dot au