git diff looping?

Running Git 1.6.1 on Solaris 10, git diff seems to go into a loop - consuming CPU and producing no output after a little bit. While the repository isn't small, it's not huge (it's http://repo.or.cz/w/egit.git). I've tried the following:

$ git diff v0.4.0 > ~/t.diff $ git diff v0.4.0 HEAD > ~/t.diff Both sit indefinitely eating most of 1 CPU $ git fsck Exits quickly with no output.

I don't mind going to a newer version of Git, but I'd like to have some idea of the source of the problem before I start trying things.

Thanks! John

It's apples and oranges, but I had no problem on
    $ git --version
    git version 1.5.4.3
    $ uname -a
    Linux platte 2.6.24-24-generic #1 SMP Wed Apr 15 15:11:35 UTC 2009 x86_64 GNU/Linux
or 
    $ /usr/src/git/git --version
    git version 1.6.3.2.31.g7af0

    $ git clone git://repo.or.cz/egit.git
    $ cd egit
    $ git diff v0.4.0 | wc -l
    47943

    $ /usr/src/git/git diff v0.4.0 | wc -l
    47943

Jeff

Thanks, Jeff!

I didn't mean to suggest there was a problem in the (origin) repository. I was wondering if anyone could recommend an approach to finding out what went wrong. I can certainly clone a fresh repo and apply my changes there. I'd just like to have some idea of what went wrong.

~John

On Mon, Jun 15, 2009 at 7:44 PM, Jeff Epler<jepler@unpythonic.net> wrote:

On Mon, Jun 15, 2009 at 06:37:21PM -0700, John Bito wrote:

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. I tried running "git diff v0.4.0" and it still hadn't finished after 90 seconds. Then I did:

  git config diff.java.xfuncname foo ;# some garbage regex
  git diff v0.4.0

and it completed in about 2.5 seconds.

Can you try that and see if it works around the problem for you?

If anybody wants to look further into the problem, I think it is specifically triggered by this file (and the built-in xfuncname for java files):

  $ git clone git://repo.or.cz/egit.git
  $ git diff v0.4.0 -- \
    org.spearce.egit.core.test/src/org/spearce/egit/core/op/T0001_ConnectProviderOperationTest.java

which isn't even all that big a file, but it is either causing some horrible algorithmic behavior in the regex library, or is outright sending it into an infinite loop.

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.

So I think it is a viable solution to recommend building against compat/regex on Solaris, but I think there is still room for improvement in what we ship in compat/.

-Peff

On Tue, Jun 16, 2009 at 07:47:26AM -0400, Jeff King wrote:

And here is a patch series to use compat/regex on Solaris. I think the first one should be non-controversial, as it just makes the knob more convenient to turn. The second one is up for debate.

  1/2: Makefile: refactor regex compat support
  2/2: Makefile: use compat regex on Solaris

-Peff

There was no tweakable knob to use the regex compat code; it was embedded in the mingw build. Since other platforms may want to use it, let's factor it out in the usual way for build configuration knobs.

Signed-off-by: Jeff King <peff@peff.net>
---
This should behave the same as before on all platforms. The only one I
might have screwed up by doing it wrong is mingw, but I have no machine
to test on. Johannes, can you confirm that it is right?

 Makefile |   11 +++++++++--
 1 files changed, 9 insertions(+), 2 deletions(-)

On Dienstag, 16. Juni 2009, Jeff King wrote:

It compiles and passes t/t40* (diff stuff) on Windows. But the patch conflicts with recent master, though nothing worrisome.

-- Hannes

On Tue, Jun 16, 2009 at 08:47:28PM +0200, Johannes Sixt wrote:

Thanks for checking.

Yeah, it looks like several changes got merged to master right after my branch point. All the conflicts are purely textual. For convenience, I'll repost a rebased version.

-Peff

There was no tweakable knob to use the regex compat code; it was embedded in the mingw build. Since other platforms may want to use it, let's factor it out in the usual way for build configuration knobs.

Signed-off-by: Jeff King <peff@peff.net>
---
Rebased on today's master to resolve textual conflicts.

 Makefile |   11 +++++++++--
 1 files changed, 9 insertions(+), 2 deletions(-)

The system regex is either slow or buggy for complex patterns, like the built-in xfuncname pattern for java files.

Signed-off-by: Jeff King <peff@peff.net>
---
Rebased to today's master to resolve textual conflicts.

 Makefile |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

Jeff King wrote:

You need to add -DHAVE_ALLOCA_H to the BASIC_CFLAGS statement in the SunOS section of the Makefile so that alloca.h will be included in compat/regex/regex.c. This is necessary for the SUNWspro compiler. It takes me a long time to compile, so I haven't checked yet whether this causes any problems for the GNU compiler.

-brandon

2009/6/16 Jeff King <peff@peff.net>

Also required on AIX (5.3). I thought this was a major performance regression somewhere else, but my 'old stable' version dates from a time when we were briefly using compat/regex on this platform before we reverted that change and switched over to extended regexes.

With the above: 3m33.399s

Without: ... manually aborted after 58m !

git 1.6.0.2.229.g1293c 3m21.645s

Could you squash

+       NO_REGEX = YesPlease

in ifeq ($(uname_S),AIX) please? Shout if follow-up patch preferred.

Signed-off-by: Mike Ralphson <mike@abacus.co.uk>

Mike

PS Pound to a penny INTERNAL_QSORT would be a win on Solaris too...

2009/6/17 Mike Ralphson <mike.ralphson@gmail.com>:

Scratch that, sorry - I hadn't seen the related thread (git diff looping?)

Paolo's fix is the only one required for AIX.

Sorry for the noise.

Mike

The system regex is either slow or buggy for complex patterns, like the built-in xfuncname pattern for java files.

Signed-off-by: Jeff King <peff@peff.net>
---
If people want to see the speed difference, try:

  $ git clone git://repo.or.cz/egit.git
  $ cd egit
  $ time git diff v0.4.0 >/dev/null

before and after.

 Makefile |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

Thank you, Jeff!

Configuring the dummy regex allows the diff process to complete on Solaris 10, as well.

~John

On Tue, Jun 16, 2009 at 4:47 AM, Jeff King<peff@peff.net> wrote:

Jeff King <peff@peff.net> writes:

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

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:

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).

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

Jeff King wrote:

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<casey@nrlssc.navy.mil> wrote:

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

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:

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

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:

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. :)

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.

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.

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:

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.

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:

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 <bonzini@gnu.org>
---
 userdiff.c |    5 +++--
 1 files changed, 3 insertions(+), 2 deletions(-)

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 <bonzini@gnu.org>:

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

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 <peff@peff.net>:

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

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

Paolo Bonzini <bonzini@gnu.org> writes:

Thanks; nicely done.

Should I remove the "/* -- */" or is it for better readability I should keep?

It helps detecting the separation between the function regex and the word regex:

I stole the idea from the Objective-C part:

Paolo

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<gitster@pobox.com> wrote:

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

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