From: Paolo Bonzini <paolo.bonzini@gmail.com>
Date: Wed, 17 Jun 2009 11:02:11 GMT
Subject: Re: git diff looping?
Message-ID: <4A38CD33.9020402@gmail.com>
In-Reply-To: <20090617102332.GA32353@coredump.intra.peff.net>

>   system,  orig:   0.22s
>   system, paolo:   0.22s
>   system,   ".":   0.15s
>   compat,  orig: 150.88s
>   compat, paolo:   0.43s
>   compat,   ".":   0.15s
> 
> Besides the exponential behavior on the original regex, it is still
> about twice as slow as the system one.

The reason is that the glibc regex is a DFA-based matcher.  It is much 
slower on regexes with backreferences, but otherwise it is faster.

>   1. Replace the builtin diff.java.xfuncname pattern with what Paolo
>      suggested (though I haven't verified its correctness beyond a
>      cursory look at the results).

I checked it a bit harder, but still it is not easy to check because of 
the false positives in the original regex.  I'm pretty sure it's correct 
  though; I find it even easier to read (though longer) than the 
original one.

>      I haven't looked at how large or how portable the glibc
>      implementation is.

Decently portable, but I don't think it's worth it.  Users that write 
regexes so complex should know of the exponential behavior, I think.

Paolo