Re: git diff looping?

Jeff King [off-list ref] writes:

I can reproduce the problem on Solaris 8 using git v1.6.3. It seems to
be caused by a horribly slow system regex implementation; it really
chokes on the regex we use to find the "funcname" line for java files.

Hmm.  Is running under LC_ALL=C LANG=C _with_ the slow system regex help?

I tried building against the code in compat/regex; it completes in a
reasonable amount of time, though it is still noticeably slow. With
system regex, the diff given above doesn't complete in less than 90
seconds (at which I get bored and kill it). With compat/regex, it
completes in about 2.2 seconds. Disabling the xfuncname, it completes in
0.14 seconds.

In this particular case it is clear that a good way to fix the problem is
to replace Solaris's dumb regex implemention with what comes in compat/,
but I at the same time have to wonder if that funcname pattern for java
can somehow be simplified, so that it does not to require so sophisticated
implementation of regexp?

On Tue, Jun 16, 2009 at 09:51:24AM -0700, Junio C Hamano wrote:

quoted

I can reproduce the problem on Solaris 8 using git v1.6.3. It seems to
be caused by a horribly slow system regex implementation; it really
chokes on the regex we use to find the "funcname" line for java files.

Hmm.  Is running under LC_ALL=C LANG=C _with_ the slow system regex help?

No, it remains extremely slow (it is possible that it _is_ faster,
though, but I never managed to run either case to completion; they are
both clearly orders of magnitude off of acceptable).

In this particular case it is clear that a good way to fix the problem is
to replace Solaris's dumb regex implemention with what comes in compat/,
but I at the same time have to wonder if that funcname pattern for java
can somehow be simplified, so that it does not to require so sophisticated
implementation of regexp?

That may be a possibility. The default pattern is actually two regexes
(one is a "do not match this" and the other is "match this"). The
problematic one seems to be (and that is a space and a tab between the
brackets):

  ^[      ]*(([   ]*[A-Za-z_][A-Za-z_0-9]*){2,}[  ]*\([^;]*)$

which I determined by setting diff.java.xfuncname just to that (and it
remains slow). Whereas setting it to:

  ^[     ]*(catch|do|for|if|instanceof|new|return|switch|throw|while)

completes in about 5 seconds of CPU time (in the actual pattern it is
negated, but that shouldn't matter as we do the negation ourselves).

Now that being said, 5 seconds is still embarrassingly bad. Watch this
(with the solaris system regex):

  $ git config diff.java.xfuncname '^[ 	]*(catch|do|for|if|instanceof|new|return|switch|throw|while)'
  $ time git diff v0.4.0 >/dev/null
  real    0m5.869s
  user    0m4.720s
  sys     0m0.200s

  $ git config diff.java.xfuncname foo
  $ time git diff v0.4.0 >/dev/null
  real    0m1.895s
  user    0m0.980s
  sys     0m0.210s

So besides learning that this machine is horribly slow, we can see that
running that relatively simple regex takes almost 4 seconds, compared to
a little over 1 second to do the entire rest of the diff. I am inclined
to say that regex performance like that is so bad that we shouldn't care
about optimizing for it, and just use something else.

Bear in mind that the same engine will be used for "grep", too. So you
aren't really doing "git grep" users any favors by linking against such
an awful library.

Really, that performance is so bad that I'm beginning to wonder if I am
somehow measuring something wrong. How could they ship something so
crappy through so many versions?

-Peff

The Solaris 10 server here isn't set up to build git.  git/Makefile
isn't compatible with /usr/ccs/bin/make. Is it desired to have a
Makefile that's portable to the Sun tools?

I was going to test Jeff's patch, but I probably won't install GNU
make on this machine unless I find I more compelling need to build git
on Solaris.

If it would help folks out, I'd be willing to try to create a Makefile
patch that works with the Sun tools, but I don't currently have a
Linux machine that I can easily use to verify compatibility.


On Tue, Jun 16, 2009 at 9:51 AM, Junio C Hamano[off-list ref] wrote:

Jeff King [off-list ref] writes:

quoted

I can reproduce the problem on Solaris 8 using git v1.6.3. It seems to
be caused by a horribly slow system regex implementation; it really
chokes on the regex we use to find the "funcname" line for java files.

Hmm.  Is running under LC_ALL=C LANG=C _with_ the slow system regex help?

quoted

I tried building against the code in compat/regex; it completes in a
reasonable amount of time, though it is still noticeably slow. With
system regex, the diff given above doesn't complete in less than 90
seconds (at which I get bored and kill it). With compat/regex, it
completes in about 2.2 seconds. Disabling the xfuncname, it completes in
0.14 seconds.

In this particular case it is clear that a good way to fix the problem is
to replace Solaris's dumb regex implemention with what comes in compat/,
but I at the same time have to wonder if that funcname pattern for java
can somehow be simplified, so that it does not to require so sophisticated
implementation of regexp?

On Tue, Jun 16, 2009 at 10:16:39AM -0700, John Bito wrote:

The Solaris 10 server here isn't set up to build git.  git/Makefile
isn't compatible with /usr/ccs/bin/make. Is it desired to have a
Makefile that's portable to the Sun tools?

No, the Makefile is hopelessly GNU, and that is intentional: the subset
of make that is portable means there are a lot of things you just can't
do. I think it was decided long ago that it wasn't worth trying to
support non-gmake.

-Peff

Jeff King wrote:

On Tue, Jun 16, 2009 at 09:51:24AM -0700, Junio C Hamano wrote:

quoted

quoted

I can reproduce the problem on Solaris 8 using git v1.6.3. It seems to
be caused by a horribly slow system regex implementation; it really
chokes on the regex we use to find the "funcname" line for java files.

Hmm.  Is running under LC_ALL=C LANG=C _with_ the slow system regex help?

No, it remains extremely slow (it is possible that it _is_ faster,
though, but I never managed to run either case to completion; they are
both clearly orders of magnitude off of acceptable).

I haven't tried setting LC_ALL, LANG, but this Solaris regex is MANY orders
of magnitude slower.  I've been running your example diff on the egit
repository for 2 hours and it still hasn't finished.  The compat/regex
version finished in 3 seconds.  Solaris 10 x86.

-brandon

I believe the issue is that Solaris implements 'extended' regular
expressions only in regcomp/regexec.  The implementation of
regcmp/regex seems to be from SysV and supports only 'basic' regular
expressions.

On Tue, Jun 16, 2009 at 10:35 AM, Brandon Casey[off-list ref] wrote:

Jeff King wrote:

quoted

On Tue, Jun 16, 2009 at 09:51:24AM -0700, Junio C Hamano wrote:

quoted

quoted

I can reproduce the problem on Solaris 8 using git v1.6.3. It seems to
be caused by a horribly slow system regex implementation; it really
chokes on the regex we use to find the "funcname" line for java files.

Hmm.  Is running under LC_ALL=C LANG=C _with_ the slow system regex help?

No, it remains extremely slow (it is possible that it _is_ faster,
though, but I never managed to run either case to completion; they are
both clearly orders of magnitude off of acceptable).

I haven't tried setting LC_ALL, LANG, but this Solaris regex is MANY orders
of magnitude slower.  I've been running your example diff on the egit
repository for 2 hours and it still hasn't finished.  The compat/regex
version finished in 3 seconds.  Solaris 10 x86.

-brandon

On Tue, Jun 16, 2009 at 10:39:39AM -0700, John Bito wrote:

I believe the issue is that Solaris implements 'extended' regular
expressions only in regcomp/regexec.  The implementation of
regcmp/regex seems to be from SysV and supports only 'basic' regular
expressions.

The regexps in question end up being compiled by regcomp (see
xdiff-interface.c:xdiff_set_find_func), so I don't think that is the
issue.

-Peff

Brandon Casey wrote:

Jeff King wrote:

quoted

On Tue, Jun 16, 2009 at 09:51:24AM -0700, Junio C Hamano wrote:

quoted

quoted

I can reproduce the problem on Solaris 8 using git v1.6.3. It seems to
be caused by a horribly slow system regex implementation; it really
chokes on the regex we use to find the "funcname" line for java files.

Hmm.  Is running under LC_ALL=C LANG=C _with_ the slow system regex help?

No, it remains extremely slow (it is possible that it _is_ faster,
though, but I never managed to run either case to completion; they are
both clearly orders of magnitude off of acceptable).

I haven't tried setting LC_ALL, LANG, but this Solaris regex is MANY orders
of magnitude slower.  I've been running your example diff on the egit
repository for 2 hours and it still hasn't finished.  The compat/regex
version finished in 3 seconds.  Solaris 10 x86.

Ok, I don't think this call is going to finish.  'git diff v0.4.0' on
Solaris 10 x86 using the native regex library.  It has been running now
for over 4.5 hours.

If you're interested in a data point from another non-gnu regex library,
I ran the same test on a mips IRIX6.5.  It took 19.5 secs, and this is
not a young machine.  It takes 4 secs when diff.java.xfuncname is set
to 'foo'.

-brandon

Really, that performance is so bad that I'm beginning to wonder if I am
somehow measuring something wrong. How could they ship something so
crappy through so many versions?

Because without some care in the matcher, the regex can be exponential. 
This happens because you can backtrack arbitrarily from [A-Za-z_0-9]* 
into [A-Za-z_] and ironically it also causes the regex not to work as 
intended; for example "catch(" can match the complex part of the regex 
(e.g. the first repetition can be "c" and the second can be "atch".

We can make it faster and more correct at the expense of additional 
complication.

Starting from:

^[ \t]*(([ \t]*[A-Za-z_][A-Za-z_0-9]*){2,}[ \t]*\([^;]*)$

we have to:

1) move [ \t] at the end of the repeated subexpression so that it 
removes the need for the [ \t] after

^[ \t]*(([A-Za-z_][A-Za-z_0-9]*[ \t]*){2,}\([^;]*)$

2) make sure that at least one space/tab is eaten on all but the last 
occurrence of the repeated subexpression.  To this end the LHS of {2,} 
is duplicated, once with [ \t]+ and once with [ \t]*.  The repetition 
itself becomes a + since the last occurrence is now separately handled:

^[ \t]*(([A-Za-z_][A-Za-z_0-9]*[ \t]+)+[A-Za-z_][A-Za-z_0-9]*
[ \t]*\([^;]*)$

Paolo

On Wed, Jun 17, 2009 at 10:46:21AM +0200, Paolo Bonzini wrote:

2) make sure that at least one space/tab is eaten on all but the last  
occurrence of the repeated subexpression.  To this end the LHS of {2,} is 
duplicated, once with [ \t]+ and once with [ \t]*.  The repetition itself 
becomes a + since the last occurrence is now separately handled:

^[ \t]*(([A-Za-z_][A-Za-z_0-9]*[ \t]+)+[A-Za-z_][A-Za-z_0-9]*
[ \t]*\([^;]*)$

Thanks, I can confirm that this is _much_ faster. Here are some timings
from my Solaris 8 box for the "git diff v0.4.0" case using the system
and compat engines, and using three regexes: the original that git is
using now, an updated one with your regex above[1] replacing the second
line of the stock pattern, and a baseline regex of "." which should take
virtually no time at all.

  system,  orig: infinite
  system, paolo:   2.5s
  system,   ".":   0.6s
  compat,  orig: 288.0s
  compat, paolo:   1.5s
  compat,   ".":   0.6s

So it goes from infinite to 2.5s. Which still spends 3 times as long
matching funcname regexes as it does actually calculating the diff. The
compat library is a little better, but still chokes pretty badly on the
original regex.

Let's compare compat to the glibc implementation on my Debian box:

  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.

So I think there are three possible optimizations worth considering:

  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). This is easy to do, and will help
     people with crappy system regex libraries and people on
     compat/regex/ (right now just mingw) a _lot_. The downside is that
     it's a little harder to read the regex, but not terribly so.

  2. Recommend NO_REGEX for people with slow system regex libraries.
     This is also easy to do, and will help people even if we do (1) for
     two reasons:

       a. we process user-defined regexes through diff.*.xfuncname
          patterns, as well as through "git grep"; so we are protecting
          against poor performance when they give us a complex regex

       b. even on more reasonable regexps like Paolo's, we seem to get a
          2:1 speedup over the Solaris system library

  3. Replace compat/regex with something faster. It still produces
     exponential behavior in complex cases where glibc does not, and it
     seems to be about 1/3 as fast on Paolo's regex.

     I haven't looked at how large or how portable the glibc
     implementation is. Another alternative is that we could provide a
     simple compat/ as now, and have better support for linking against
     an external library like pcre, if it is available.

-Peff

[1] Note if you are cutting and pasting Paolo's regex into the C code,
    the "\(" needs to be "\\(", which I screwed up in my initial
    timings. :)

  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

Jeff King wrote:

  3. Replace compat/regex with something faster. It still produces
     exponential behavior in complex cases where glibc does not, and it
     seems to be about 1/3 as fast on Paolo's regex.

     I haven't looked at how large or how portable the glibc
     implementation is. Another alternative is that we could provide a
     simple compat/ as now, and have better support for linking against
     an external library like pcre, if it is available.

The glibc implementation is quite large. Cutting the library-specific
cruft it still sits at about 10k LOC.

Using PCRE is a no-go, as it uses perl-compatible regexes even for the
posix-compatible API, as per pcreposix(3):

       When  PCRE  is  called  via these functions, it is only the API that is
       POSIX-like in style. The syntax and semantics of  the  regular  expres-
       sions  themselves  are  still  those of Perl, subject to the setting of
       various PCRE options, as described below. "POSIX-like in  style"  means
       that  the  API  approximates  to  the POSIX definition; it is not fully
       POSIX-compatible, and in multi-byte encoding  domains  it  is  probably
       even less compatible.

This would probably surprise some "git grep" users quite a lot, I think.

I like your other two suggestions though. The stuff already in compat/
seems to work well enough, so with Paolo's improved pattern it should
be fine.

-- 
Andreas Ericsson                   andreas.ericsson@op5.se
OP5 AB                             www.op5.se
Tel: +46 8-230225                  Fax: +46 8-230231

Considering the successes of the wars on alcohol, poverty, drugs and
terror, I think we should give some serious thought to declaring war
on peace.

The glibc implementation is quite large. Cutting the library-specific
cruft it still sits at about 10k LOC.

Using PCRE is a no-go, as it uses perl-compatible regexes even for the
posix-compatible API, as per pcreposix(3):

I have a PCRE fork that has POSIX semantics (except the braindead 
leftmost-longest *sub*expressions).  It weighs 8kLOC, you can find it in 
branch ssed of GNU sed's git repository.

Paolo

Paolo Bonzini wrote:

quoted

The glibc implementation is quite large. Cutting the library-specific
cruft it still sits at about 10k LOC.

Using PCRE is a no-go, as it uses perl-compatible regexes even for the
posix-compatible API, as per pcreposix(3):

I have a PCRE fork that has POSIX semantics (except the braindead 
leftmost-longest *sub*expressions).  It weighs 8kLOC, you can find it in 
branch ssed of GNU sed's git repository.

Sounds neat. Do you by any chance have some performance measurements
for it? If the work's already done and it provides a significant
improvement I'm all for it ;-)

-- 
Andreas Ericsson                   andreas.ericsson@op5.se
OP5 AB                             www.op5.se
Tel: +46 8-230225                  Fax: +46 8-230231

Considering the successes of the wars on alcohol, poverty, drugs and
terror, I think we should give some serious thought to declaring war
on peace.

Sounds neat. Do you by any chance have some performance measurements
for it? If the work's already done and it provides a significant
improvement I'm all for it ;-)

It's very very fast, but only as fast as a backtracking matcher can be. 
  I think it would trounce glibc on my regex but probably not on the 
buggy one.

Paolo

In the old regex

^[ \t]*(([ \t]*[A-Za-z_][A-Za-z_0-9]*){2,}[ \t]*\([^;]*)$
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

you can backtrack arbitrarily from [A-Za-z_0-9]* into [A-Za-z_], thus
causing an exponential number of backtracks.  Ironically it also causes
the regex not to work as intended; for example "catch" can match the
underlined part of the regex, the first repetition matching "c" and
the second matching "atch".

The replacement regex avoids this problem, because it makes sure that
at least a space/tab is eaten on each repetition.  In other words,
a suffix of a repetition can never be a prefix of the next repetition.

Signed-off-by: Paolo Bonzini <redacted>
---
 userdiff.c |    5 +++--
 1 files changed, 3 insertions(+), 2 deletions(-)

diff --git a/userdiff.c b/userdiff.c
index d556da9..57529ae 100644
--- a/userdiff.c
+++ b/userdiff.c

@@ -13,7 +13,8 @@ PATTERNS("html", "^[ \t]*(<[Hh][1-6][ \t].*>.*)$",
 	 "[^<>= \t]+|[^[:space:]]|[\x80-\xff]+"),
 PATTERNS("java",
 	 "!^[ \t]*(catch|do|for|if|instanceof|new|return|switch|throw|while)\n"
-	 "^[ \t]*(([ \t]*[A-Za-z_][A-Za-z_0-9]*){2,}[ \t]*\\([^;]*)$",
+	 "^[ \t]*(([A-Za-z_][A-Za-z_0-9]*[ \t]+)+[A-Za-z_][A-Za-z_0-9]*[ \t]*\\([^;]*)$",
+	 /* -- */
 	 "[a-zA-Z_][a-zA-Z0-9_]*"
 	 "|[-+0-9.e]+[fFlL]?|0[xXbB]?[0-9a-fA-F]+[lL]?"
 	 "|[-+*/<>%&^|=!]="

@@ -25,7 +26,7 @@ PATTERNS("objc",
 	 /* Objective-C methods */
 	 "^[ \t]*([-+][ \t]*\\([ \t]*[A-Za-z_][A-Za-z_0-9* \t]*\\)[ \t]*[A-Za-z_].*)$\n"
 	 /* C functions */
-	 "^[ \t]*(([ \t]*[A-Za-z_][A-Za-z_0-9]*){2,}[ \t]*\\([^;]*)$\n"
+	 "^[ \t]*(([A-Za-z_][A-Za-z_0-9]*[ \t]+)+[A-Za-z_][A-Za-z_0-9]*[ \t]*\\([^;]*)$\n"
 	 /* Objective-C class/protocol definitions */
 	 "^(@(implementation|interface|protocol)[ \t].*)$",
 	 /* -- */

-- 
1.6.0.3

Just  a note, but If the  Java regex library you are using supports
the PCRE compatible (?>...) atomic matching construct (or their
equivalent *+ and ++) then these patterns can be significantly
improved beyond their current state.


2009/6/17 Paolo Bonzini [off-list ref]:

-- 
perl -Mre=debug -e "/just|another|perl|hacker/"

On Wed, Jun 17, 2009 at 05:46:54PM +0200, demerphq wrote:

Just  a note, but If the  Java regex library you are using supports
the PCRE compatible (?>...) atomic matching construct (or their
equivalent *+ and ++) then these patterns can be significantly
improved beyond their current state.

To clarify, this isn't a java regex library, but rather regexps used to
match function names inside java language files when generating diffs.
The regex library itself is the POSIX regex routines provided by libc.

PCRE syntax is nice, but we don't want to require it for every build,
and it's important to have the same syntax everywhere (so that, e.g.,
your config from one build works on a different build).

-Peff

2009/6/17 Jeff King [off-list ref]:

On Wed, Jun 17, 2009 at 05:46:54PM +0200, demerphq wrote:

quoted

Just  a note, but If the  Java regex library you are using supports
the PCRE compatible (?>...) atomic matching construct (or their
equivalent *+ and ++) then these patterns can be significantly
improved beyond their current state.

To clarify, this isn't a java regex library, but rather regexps used to
match function names inside java language files when generating diffs.
The regex library itself is the POSIX regex routines provided by libc.

PCRE syntax is nice, but we don't want to require it for every build,
and it's important to have the same syntax everywhere (so that, e.g.,
your config from one build works on a different build).

Ah ok. Im not familiar with the finer points of the POSIX engine, but
PCRE and Perl's engine, and most similar engines are not true regular
expression engines and thus benefit *greatly* from atomic matching if
it is available.

Like the difference between heat-death performance (or stack
overflow), and running instantly.

Yves



-- 
perl -Mre=debug -e "/just|another|perl|hacker/"

Ah ok. Im not familiar with the finer points of the POSIX engine, but
PCRE and Perl's engine, and most similar engines are not true regular
expression engines and thus benefit *greatly* from atomic matching if
it is available.

Like the difference between heat-death performance (or stack
overflow), and running instantly.

You can almost always fix the regex to avoid this, by ensuring that 
whenever you have (...)+ (or *) a suffix of the subexpression cannot be 
a prefix of the subexpression too.  This is what my patch did -- 
changing a bad regex to a nicely behaving one.

Paolo