{"thread":{"id":"19823","subject":"git diff looping?","startedAt":"2009-06-16T01:37:21Z","lastAt":"2009-06-18T06:45:37Z","messageCount":37,"participants":["John Bito","Jeff Epler","Jeff King","Junio C Hamano","Brandon Casey","Johannes Sixt","Paolo Bonzini","Andreas Ericsson","Mike Ralphson","demerphq"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"116375","messageId":"3ae83b000906151837r186221f2q1f8a670f13841877@mail.gmail.com","threadId":"19823","inReplyTo":null,"subject":"git diff looping?","fromName":"John Bito","fromEmail":"jwbito@gmail.com","sentAt":"2009-06-16T01:37:21Z","receivedAt":"2009-06-16T01:37:21Z","isPatch":false,"sender":{"key":"jwbito@gmail.com","avatar":"https://gravatar.com/avatar/e94274c6b71a11e3fa03d91e75937609e66315f23267efd591ef1f98bb860bf9?d=mp&s=160"},"body":"Running Git 1.6.1 on Solaris 10, git diff seems to go into a loop -\nconsuming CPU and producing no output after a little bit. While the\nrepository isn't small, it's not huge (it's\nhttp://repo.or.cz/w/egit.git). I've tried the following:\n\n$ git diff v0.4.0 > ~/t.diff\n$ git diff v0.4.0 HEAD > ~/t.diff\nBoth sit indefinitely eating most of 1 CPU\n$ git fsck\nExits quickly with no output.\n\nI don't mind going to a newer version of Git, but I'd like to have\nsome idea of the source of the problem before I start trying things.\n\nThanks!\nJohn\n"},{"id":"116381","messageId":"20090616024457.GA9513@unpythonic.net","threadId":"19823","inReplyTo":"3ae83b000906151837r186221f2q1f8a670f13841877@mail.gmail.com","subject":"Re: git diff looping?","fromName":"Jeff Epler","fromEmail":"jepler@unpythonic.net","sentAt":"2009-06-16T02:44:57Z","receivedAt":"2009-06-16T02:44:57Z","isPatch":false,"sender":{"key":"jepler@unpythonic.net","avatar":"https://avatars.githubusercontent.com/u/1517291?v=4"},"body":"It's apples and oranges, but I had no problem on\n $ git --version\n git version 1.5.4.3\n $ uname -a\n Linux platte 2.6.24-24-generic #1 SMP Wed Apr 15 15:11:35 UTC 2009 x86_64 GNU/Linux\nor \n $ /usr/src/git/git --version\n git version 1.6.3.2.31.g7af0\n\n $ git clone git://repo.or.cz/egit.git\n $ cd egit\n $ git diff v0.4.0 | wc -l\n 47943\n\n $ /usr/src/git/git diff v0.4.0 | wc -l\n 47943\n\nJeff\n"},{"id":"116382","messageId":"3ae83b000906151953h570df143kd4d2c51b8dc2ac66@mail.gmail.com","threadId":"19823","inReplyTo":"20090616024457.GA9513@unpythonic.net","subject":"Re: git diff looping?","fromName":"John Bito","fromEmail":"jwbito@gmail.com","sentAt":"2009-06-16T02:53:22Z","receivedAt":"2009-06-16T02:53:22Z","isPatch":false,"sender":{"key":"jwbito@gmail.com","avatar":"https://gravatar.com/avatar/e94274c6b71a11e3fa03d91e75937609e66315f23267efd591ef1f98bb860bf9?d=mp&s=160"},"body":"Thanks, Jeff!\n\nI didn't mean to suggest there was a problem in the (origin)\nrepository. I was wondering if anyone could recommend an approach to\nfinding out what went wrong. I can certainly clone a fresh repo and\napply my changes there. I'd just like to have some idea of what went\nwrong.\n\n~John\n\nOn Mon, Jun 15, 2009 at 7:44 PM, Jeff Epler wrote:\n> It's apples and oranges, but I had no problem on\n>    $ git --version\n>    git version 1.5.4.3\n>    $ uname -a\n>    Linux platte 2.6.24-24-generic #1 SMP Wed Apr 15 15:11:35 UTC 2009 x86_64 GNU/Linux\n> or\n>    $ /usr/src/git/git --version\n>    git version 1.6.3.2.31.g7af0\n>\n>    $ git clone git://repo.or.cz/egit.git\n>    $ cd egit\n>    $ git diff v0.4.0 | wc -l\n>    47943\n>\n>    $ /usr/src/git/git diff v0.4.0 | wc -l\n>    47943\n>\n> Jeff\n>\n"},{"id":"116404","messageId":"20090616114726.GA4343@coredump.intra.peff.net","threadId":"19823","inReplyTo":"3ae83b000906151837r186221f2q1f8a670f13841877@mail.gmail.com","subject":"Re: git diff looping?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-06-16T11:47:26Z","receivedAt":"2009-06-16T11:47:26Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jun 15, 2009 at 06:37:21PM -0700, John Bito wrote:\n\n> Running Git 1.6.1 on Solaris 10, git diff seems to go into a loop -\n> consuming CPU and producing no output after a little bit. While the\n> repository isn't small, it's not huge (it's\n> http://repo.or.cz/w/egit.git). I've tried the following:\n\nI can reproduce the problem on Solaris 8 using git v1.6.3. It seems to\nbe caused by a horribly slow system regex implementation; it really\nchokes on the regex we use to find the \"funcname\" line for java files. I\ntried running \"git diff v0.4.0\" and it still hadn't finished after 90\nseconds. Then I did:\n\n git config diff.java.xfuncname foo ;# some garbage regex\n git diff v0.4.0\n\nand it completed in about 2.5 seconds.\n\nCan you try that and see if it works around the problem for you?\n\nIf anybody wants to look further into the problem, I think it is\nspecifically triggered by this file (and the built-in xfuncname for java\nfiles):\n\n $ git clone git://repo.or.cz/egit.git\n $ git diff v0.4.0 -- \\\n org.spearce.egit.core.test/src/org/spearce/egit/core/op/T0001_ConnectProviderOperationTest.java\n\nwhich isn't even all that big a file, but it is either causing some\nhorrible algorithmic behavior in the regex library, or is outright\nsending it into an infinite loop.\n\nI tried building against the code in compat/regex; it completes in a\nreasonable amount of time, though it is still noticeably slow. With\nsystem regex, the diff given above doesn't complete in less than 90\nseconds (at which I get bored and kill it). With compat/regex, it\ncompletes in about 2.2 seconds. Disabling the xfuncname, it completes in\n0.14 seconds.\n\nSo I think it is a viable solution to recommend building against\ncompat/regex on Solaris, but I think there is still room for improvement\nin what we ship in compat/.\n\n-Peff\n"},{"id":"116405","messageId":"20090616120737.GA5227@coredump.intra.peff.net","threadId":"19823","inReplyTo":"20090616114726.GA4343@coredump.intra.peff.net","subject":"Re: git diff looping?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-06-16T12:07:37Z","receivedAt":"2009-06-16T12:07:37Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jun 16, 2009 at 07:47:26AM -0400, Jeff King wrote:\n\n> $ git clone git://repo.or.cz/egit.git\n> $ git diff v0.4.0 -- \\\n> org.spearce.egit.core.test/src/org/spearce/egit/core/op/T0001_ConnectProviderOperationTest.java\n> \n> which isn't even all that big a file, but it is either causing some\n> horrible algorithmic behavior in the regex library, or is outright\n> sending it into an infinite loop.\n> \n> I tried building against the code in compat/regex; it completes in a\n> reasonable amount of time, though it is still noticeably slow. With\n> system regex, the diff given above doesn't complete in less than 90\n> seconds (at which I get bored and kill it). With compat/regex, it\n> completes in about 2.2 seconds. Disabling the xfuncname, it completes in\n> 0.14 seconds.\n\nAnd here is a patch series to use compat/regex on Solaris. I think the\nfirst one should be non-controversial, as it just makes the knob more\nconvenient to turn. The second one is up for debate.\n\n 1/2: Makefile: refactor regex compat support\n 2/2: Makefile: use compat regex on Solaris\n\n-Peff\n"},{"id":"116407","messageId":"20090616121126.GA11918@coredump.intra.peff.net","threadId":"19823","inReplyTo":"20090616120737.GA5227@coredump.intra.peff.net","subject":"[PATCH 1/2] Makefile: refactor regex compat support","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-06-16T12:11:26Z","receivedAt":"2009-06-16T12:11:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"There was no tweakable knob to use the regex compat code; it\nwas embedded in the mingw build. Since other platforms may\nwant to use it, let's factor it out in the usual way for\nbuild configuration knobs.\n\nSigned-off-by: Jeff King \n---\nThis should behave the same as before on all platforms. The only one I\nmight have screwed up by doing it wrong is mingw, but I have no machine\nto test on. Johannes, can you confirm that it is right?\n\n Makefile | 11 +++++++++--\n 1 files changed, 9 insertions(+), 2 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex 04bf8b1..a1e4e45 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -182,6 +182,8 @@ all::\n #\n # Define NO_CROSS_DIRECTORY_HARDLINKS if you plan to distribute the installed\n # programs as a tar, where bin/ and libexec/ might be on different file systems.\n+#\n+# Define NO_REGEX if you have no or inferior regex support in your C library.\n \n GIT-VERSION-FILE: .FORCE-GIT-VERSION-FILE\n \t@$(SHELL_PATH) ./GIT-VERSION-GEN\n@@ -863,10 +865,11 @@ ifneq (,$(findstring MINGW,$(uname_S)))\n \tUSE_WIN32_MMAP = YesPlease\n \tUNRELIABLE_FSTAT = UnfortunatelyYes\n \tOBJECT_CREATION_USES_RENAMES = UnfortunatelyNeedsTo\n-\tCOMPAT_CFLAGS += -D__USE_MINGW_ACCESS -DNOGDI -Icompat -Icompat/regex -Icompat/fnmatch\n+\tNO_REGEX = YesPlease\n+\tCOMPAT_CFLAGS += -D__USE_MINGW_ACCESS -DNOGDI -Icompat -Icompat/fnmatch\n \tCOMPAT_CFLAGS += -DSNPRINTF_SIZE_CORR=1\n \tCOMPAT_CFLAGS += -DSTRIP_EXTENSION=\\\".exe\\\"\n-\tCOMPAT_OBJS += compat/mingw.o compat/fnmatch/fnmatch.o compat/regex/regex.o compat/winansi.o\n+\tCOMPAT_OBJS += compat/mingw.o compat/fnmatch/fnmatch.o compat/winansi.o\n \tEXTLIBS += -lws2_32\n \tX = .exe\n endif\n@@ -1157,6 +1160,10 @@ endif\n ifdef UNRELIABLE_FSTAT\n \tBASIC_CFLAGS += -DUNRELIABLE_FSTAT\n endif\n+ifdef NO_REGEX\n+\tCOMPAT_CFLAGS += -Icompat/regex\n+\tCOMPAT_OBJS += compat/regex/regex.o\n+endif\n \n ifeq ($(TCLTK_PATH),)\n NO_TCLTK=NoThanks\n-- \n1.6.3.2.225.gb8364.dirty\n"},{"id":"116408","messageId":"20090616121440.GB11918@coredump.intra.peff.net","threadId":"19823","inReplyTo":"20090616120737.GA5227@coredump.intra.peff.net","subject":"[PATCH 2/2] Makefile: use compat regex on Solaris","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-06-16T12:14:40Z","receivedAt":"2009-06-16T12:14:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The system regex is either slow or buggy for complex\npatterns, like the built-in xfuncname pattern for java\nfiles.\n\nSigned-off-by: Jeff King \n---\nIf people want to see the speed difference, try:\n\n $ git clone git://repo.or.cz/egit.git\n $ cd egit\n $ time git diff v0.4.0 >/dev/null\n\nbefore and after.\n\n Makefile | 1 +\n 1 files changed, 1 insertions(+), 0 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex a1e4e45..0e09ec8 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -713,6 +713,7 @@ ifeq ($(uname_S),SunOS)\n \tNO_HSTRERROR = YesPlease\n \tNO_MKDTEMP = YesPlease\n \tNO_MKSTEMPS = YesPlease\n+\tNO_REGEX = YesPlease\n \tifneq ($(uname_R),5.11)\n \t\tOLD_ICONV = UnfortunatelyYes\n \tendif\n-- \n1.6.3.2.225.gb8364.dirty\n"},{"id":"116416","messageId":"3ae83b000906160848x12ff8a27m57520c687306e1fa@mail.gmail.com","threadId":"19823","inReplyTo":"20090616114726.GA4343@coredump.intra.peff.net","subject":"Re: git diff looping?","fromName":"John Bito","fromEmail":"jwbito@gmail.com","sentAt":"2009-06-16T15:48:41Z","receivedAt":"2009-06-16T15:48:41Z","isPatch":false,"sender":{"key":"jwbito@gmail.com","avatar":"https://gravatar.com/avatar/e94274c6b71a11e3fa03d91e75937609e66315f23267efd591ef1f98bb860bf9?d=mp&s=160"},"body":"Thank you, Jeff!\n\nConfiguring the dummy regex allows the diff process to complete on\nSolaris 10, as well.\n\n~John\n\nOn Tue, Jun 16, 2009 at 4:47 AM, Jeff King wrote:\n> On Mon, Jun 15, 2009 at 06:37:21PM -0700, John Bito wrote:\n>\n>> Running Git 1.6.1 on Solaris 10, git diff seems to go into a loop -\n>> consuming CPU and producing no output after a little bit.  While the\n>> repository isn't small, it's not huge (it's\n>> http://repo.or.cz/w/egit.git). I've tried the following:\n>\n> I can reproduce the problem on Solaris 8 using git v1.6.3. It seems to\n> be caused by a horribly slow system regex implementation; it really\n> chokes on the regex we use to find the \"funcname\" line for java files. I\n> tried running \"git diff v0.4.0\" and it still hadn't finished after 90\n> seconds. Then I did:\n>\n>  git config diff.java.xfuncname foo ;# some garbage regex\n>  git diff v0.4.0\n>\n> and it completed in about 2.5 seconds.\n>\n> Can you try that and see if it works around the problem for you?\n>\n> If anybody wants to look further into the problem, I think it is\n> specifically triggered by this file (and the built-in xfuncname for java\n> files):\n>\n>  $ git clone git://repo.or.cz/egit.git\n>  $ git diff v0.4.0 -- \\\n>    org.spearce.egit.core.test/src/org/spearce/egit/core/op/T0001_ConnectProviderOperationTest.java\n>\n> which isn't even all that big a file, but it is either causing some\n> horrible algorithmic behavior in the regex library, or is outright\n> sending it into an infinite loop.\n>\n> I tried building against the code in compat/regex; it completes in a\n> reasonable amount of time, though it is still noticeably slow. With\n> system regex, the diff given above doesn't complete in less than 90\n> seconds (at which I get bored and kill it). With compat/regex, it\n> completes in about 2.2 seconds. Disabling the xfuncname, it completes in\n> 0.14 seconds.\n>\n> So I think it is a viable solution to recommend building against\n> compat/regex on Solaris, but I think there is still room for improvement\n> in what we ship in compat/.\n>\n> -Peff\n>\n"},{"id":"116418","messageId":"7v3aa0dsvn.fsf@alter.siamese.dyndns.org","threadId":"19823","inReplyTo":"20090616114726.GA4343@coredump.intra.peff.net","subject":"Re: git diff looping?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-06-16T16:51:24Z","receivedAt":"2009-06-16T16:51:24Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> I can reproduce the problem on Solaris 8 using git v1.6.3. It seems to\n> be caused by a horribly slow system regex implementation; it really\n> chokes on the regex we use to find the \"funcname\" line for java files.\n\nHmm. Is running under LC_ALL=C LANG=C _with_ the slow system regex help?\n\n> I tried building against the code in compat/regex; it completes in a\n> reasonable amount of time, though it is still noticeably slow. With\n> system regex, the diff given above doesn't complete in less than 90\n> seconds (at which I get bored and kill it). With compat/regex, it\n> completes in about 2.2 seconds. Disabling the xfuncname, it completes in\n> 0.14 seconds.\n\nIn this particular case it is clear that a good way to fix the problem is\nto replace Solaris's dumb regex implemention with what comes in compat/,\nbut I at the same time have to wonder if that funcname pattern for java\ncan somehow be simplified, so that it does not to require so sophisticated\nimplementation of regexp?\n"},{"id":"116419","messageId":"20090616171531.GA17538@coredump.intra.peff.net","threadId":"19823","inReplyTo":"7v3aa0dsvn.fsf@alter.siamese.dyndns.org","subject":"Re: git diff looping?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-06-16T17:15:31Z","receivedAt":"2009-06-16T17:15:31Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jun 16, 2009 at 09:51:24AM -0700, Junio C Hamano wrote:\n\n> > I can reproduce the problem on Solaris 8 using git v1.6.3. It seems to\n> > be caused by a horribly slow system regex implementation; it really\n> > chokes on the regex we use to find the \"funcname\" line for java files.\n> \n> Hmm. Is running under LC_ALL=C LANG=C _with_ the slow system regex help?\n\nNo, it remains extremely slow (it is possible that it _is_ faster,\nthough, but I never managed to run either case to completion; they are\nboth clearly orders of magnitude off of acceptable).\n\n> In this particular case it is clear that a good way to fix the problem is\n> to replace Solaris's dumb regex implemention with what comes in compat/,\n> but I at the same time have to wonder if that funcname pattern for java\n> can somehow be simplified, so that it does not to require so sophisticated\n> implementation of regexp?\n\nThat may be a possibility. The default pattern is actually two regexes\n(one is a \"do not match this\" and the other is \"match this\"). The\nproblematic one seems to be (and that is a space and a tab between the\nbrackets):\n\n ^[ ]*(([ ]*[A-Za-z_][A-Za-z_0-9]*){2,}[ ]*\\([^;]*)$\n\nwhich I determined by setting diff.java.xfuncname just to that (and it\nremains slow). Whereas setting it to:\n\n ^[ ]*(catch|do|for|if|instanceof|new|return|switch|throw|while)\n\ncompletes in about 5 seconds of CPU time (in the actual pattern it is\nnegated, but that shouldn't matter as we do the negation ourselves).\n\nNow that being said, 5 seconds is still embarrassingly bad. Watch this\n(with the solaris system regex):\n\n $ git config diff.java.xfuncname '^[ \t]*(catch|do|for|if|instanceof|new|return|switch|throw|while)'\n $ time git diff v0.4.0 >/dev/null\n real 0m5.869s\n user 0m4.720s\n sys 0m0.200s\n\n $ git config diff.java.xfuncname foo\n $ time git diff v0.4.0 >/dev/null\n real 0m1.895s\n user 0m0.980s\n sys 0m0.210s\n\nSo besides learning that this machine is horribly slow, we can see that\nrunning that relatively simple regex takes almost 4 seconds, compared to\na little over 1 second to do the entire rest of the diff. I am inclined\nto say that regex performance like that is so bad that we shouldn't care\nabout optimizing for it, and just use something else.\n\nBear in mind that the same engine will be used for \"grep\", too. So you\naren't really doing \"git grep\" users any favors by linking against such\nan awful library.\n\nReally, that performance is so bad that I'm beginning to wonder if I am\nsomehow measuring something wrong. How could they ship something so\ncrappy through so many versions?\n\n-Peff\n"},{"id":"116420","messageId":"3ae83b000906161016k4927a91cke86d6c4aa087a590@mail.gmail.com","threadId":"19823","inReplyTo":"7v3aa0dsvn.fsf@alter.siamese.dyndns.org","subject":"Re: git diff looping?","fromName":"John Bito","fromEmail":"jwbito@gmail.com","sentAt":"2009-06-16T17:16:39Z","receivedAt":"2009-06-16T17:16:39Z","isPatch":false,"sender":{"key":"jwbito@gmail.com","avatar":"https://gravatar.com/avatar/e94274c6b71a11e3fa03d91e75937609e66315f23267efd591ef1f98bb860bf9?d=mp&s=160"},"body":"The Solaris 10 server here isn't set up to build git. git/Makefile\nisn't compatible with /usr/ccs/bin/make. Is it desired to have a\nMakefile that's portable to the Sun tools?\n\nI was going to test Jeff's patch, but I probably won't install GNU\nmake on this machine unless I find I more compelling need to build git\non Solaris.\n\nIf it would help folks out, I'd be willing to try to create a Makefile\npatch that works with the Sun tools, but I don't currently have a\nLinux machine that I can easily use to verify compatibility.\n\n\nOn Tue, Jun 16, 2009 at 9:51 AM, Junio C Hamano wrote:\n> Jeff King writes:\n>\n>> I can reproduce the problem on Solaris 8 using git v1.6.3. It seems to\n>> be caused by a horribly slow system regex implementation; it really\n>> chokes on the regex we use to find the \"funcname\" line for java files.\n>\n> Hmm.  Is running under LC_ALL=C LANG=C _with_ the slow system regex help?\n>\n>> I tried building against the code in compat/regex; it completes in a\n>> reasonable amount of time, though it is still noticeably slow. With\n>> system regex, the diff given above doesn't complete in less than 90\n>> seconds (at which I get bored and kill it). With compat/regex, it\n>> completes in about 2.2 seconds. Disabling the xfuncname, it completes in\n>> 0.14 seconds.\n>\n> In this particular case it is clear that a good way to fix the problem is\n> to replace Solaris's dumb regex implemention with what comes in compat/,\n> but I at the same time have to wonder if that funcname pattern for java\n> can somehow be simplified, so that it does not to require so sophisticated\n> implementation of regexp?\n>\n"},{"id":"116421","messageId":"20090616172428.GA18118@coredump.intra.peff.net","threadId":"19823","inReplyTo":"3ae83b000906161016k4927a91cke86d6c4aa087a590@mail.gmail.com","subject":"Re: git diff looping?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-06-16T17:24:28Z","receivedAt":"2009-06-16T17:24:28Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jun 16, 2009 at 10:16:39AM -0700, John Bito wrote:\n\n> The Solaris 10 server here isn't set up to build git. git/Makefile\n> isn't compatible with /usr/ccs/bin/make. Is it desired to have a\n> Makefile that's portable to the Sun tools?\n\nNo, the Makefile is hopelessly GNU, and that is intentional: the subset\nof make that is portable means there are a lot of things you just can't\ndo. I think it was decided long ago that it wasn't worth trying to\nsupport non-gmake.\n\n-Peff\n"},{"id":"116423","messageId":"RFQLUdKWnVWgwwX0qsqUhC-pl9v39aFOKMpTbbABiCEXczTo26fVow@cipher.nrlssc.navy.mil","threadId":"19823","inReplyTo":"20090616171531.GA17538@coredump.intra.peff.net","subject":"Re: git diff looping?","fromName":"Brandon Casey","fromEmail":"casey@nrlssc.navy.mil","sentAt":"2009-06-16T17:35:25Z","receivedAt":"2009-06-16T17:35:25Z","isPatch":false,"sender":{"key":"drafnel@gmail.com","avatar":"https://avatars.githubusercontent.com/u/921167?v=4"},"body":"Jeff King wrote:\n> On Tue, Jun 16, 2009 at 09:51:24AM -0700, Junio C Hamano wrote:\n> \n>>> I can reproduce the problem on Solaris 8 using git v1.6.3. It seems to\n>>> be caused by a horribly slow system regex implementation; it really\n>>> chokes on the regex we use to find the \"funcname\" line for java files.\n>> Hmm. Is running under LC_ALL=C LANG=C _with_ the slow system regex help?\n> \n> No, it remains extremely slow (it is possible that it _is_ faster,\n> though, but I never managed to run either case to completion; they are\n> both clearly orders of magnitude off of acceptable).\n\nI haven't tried setting LC_ALL, LANG, but this Solaris regex is MANY orders\nof magnitude slower. I've been running your example diff on the egit\nrepository for 2 hours and it still hasn't finished. The compat/regex\nversion finished in 3 seconds. Solaris 10 x86.\n\n-brandon\n"},{"id":"116424","messageId":"3ae83b000906161039s1cd540a9k3506a09a5e616c67@mail.gmail.com","threadId":"19823","inReplyTo":"RFQLUdKWnVWgwwX0qsqUhC-pl9v39aFOKMpTbbABiCEXczTo26fVow@cipher.nrlssc.navy.mil","subject":"Re: git diff looping?","fromName":"John Bito","fromEmail":"jwbito@gmail.com","sentAt":"2009-06-16T17:39:39Z","receivedAt":"2009-06-16T17:39:39Z","isPatch":false,"sender":{"key":"jwbito@gmail.com","avatar":"https://gravatar.com/avatar/e94274c6b71a11e3fa03d91e75937609e66315f23267efd591ef1f98bb860bf9?d=mp&s=160"},"body":"I believe the issue is that Solaris implements 'extended' regular\nexpressions only in regcomp/regexec. The implementation of\nregcmp/regex seems to be from SysV and supports only 'basic' regular\nexpressions.\n\nOn Tue, Jun 16, 2009 at 10:35 AM, Brandon Casey wrote:\n> Jeff King wrote:\n>> On Tue, Jun 16, 2009 at 09:51:24AM -0700, Junio C Hamano wrote:\n>>\n>>>> I can reproduce the problem on Solaris 8 using git v1.6.3. It seems to\n>>>> be caused by a horribly slow system regex implementation; it really\n>>>> chokes on the regex we use to find the \"funcname\" line for java files.\n>>> Hmm.  Is running under LC_ALL=C LANG=C _with_ the slow system regex help?\n>>\n>> No, it remains extremely slow (it is possible that it _is_ faster,\n>> though, but I never managed to run either case to completion; they are\n>> both clearly orders of magnitude off of acceptable).\n>\n> I haven't tried setting LC_ALL, LANG, but this Solaris regex is MANY orders\n> of magnitude slower.  I've been running your example diff on the egit\n> repository for 2 hours and it still hasn't finished.  The compat/regex\n> version finished in 3 seconds.  Solaris 10 x86.\n>\n> -brandon\n>\n"},{"id":"116425","messageId":"20090616174159.GA18479@coredump.intra.peff.net","threadId":"19823","inReplyTo":"3ae83b000906161039s1cd540a9k3506a09a5e616c67@mail.gmail.com","subject":"Re: git diff looping?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-06-16T17:41:59Z","receivedAt":"2009-06-16T17:41:59Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jun 16, 2009 at 10:39:39AM -0700, John Bito wrote:\n\n> I believe the issue is that Solaris implements 'extended' regular\n> expressions only in regcomp/regexec. The implementation of\n> regcmp/regex seems to be from SysV and supports only 'basic' regular\n> expressions.\n\nThe regexps in question end up being compiled by regcomp (see\nxdiff-interface.c:xdiff_set_find_func), so I don't think that is the\nissue.\n\n-Peff\n"},{"id":"116430","messageId":"200906162047.28368.j6t@kdbg.org","threadId":"19823","inReplyTo":"20090616121126.GA11918@coredump.intra.peff.net","subject":"Re: [PATCH 1/2] Makefile: refactor regex compat support","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2009-06-16T18:47:28Z","receivedAt":"2009-06-16T18:47:28Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"On Dienstag, 16. Juni 2009, Jeff King wrote:\n> There was no tweakable knob to use the regex compat code; it\n> was embedded in the mingw build. Since other platforms may\n> want to use it, let's factor it out in the usual way for\n> build configuration knobs.\n>\n> Signed-off-by: Jeff King \n> ---\n> This should behave the same as before on all platforms. The only one I\n> might have screwed up by doing it wrong is mingw, but I have no machine\n> to test on. Johannes, can you confirm that it is right?\n\nIt compiles and passes t/t40* (diff stuff) on Windows. But the patch conflicts \nwith recent master, though nothing worrisome.\n\n-- Hannes\n"},{"id":"116434","messageId":"20090616190550.GA22905@coredump.intra.peff.net","threadId":"19823","inReplyTo":"200906162047.28368.j6t@kdbg.org","subject":"Re: [PATCH 1/2] Makefile: refactor regex compat support","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-06-16T19:05:50Z","receivedAt":"2009-06-16T19:05:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jun 16, 2009 at 08:47:28PM +0200, Johannes Sixt wrote:\n\n> It compiles and passes t/t40* (diff stuff) on Windows. But the patch\n> conflicts with recent master, though nothing worrisome.\n\nThanks for checking.\n\nYeah, it looks like several changes got merged to master right after\nmy branch point. All the conflicts are purely textual. For convenience,\nI'll repost a rebased version.\n\n-Peff\n"},{"id":"116435","messageId":"20090616190740.GA23197@coredump.intra.peff.net","threadId":"19823","inReplyTo":"20090616190550.GA22905@coredump.intra.peff.net","subject":"[PATCH v2 1/2] Makefile: refactor regex compat support","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-06-16T19:07:40Z","receivedAt":"2009-06-16T19:07:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"There was no tweakable knob to use the regex compat code; it\nwas embedded in the mingw build. Since other platforms may\nwant to use it, let's factor it out in the usual way for\nbuild configuration knobs.\n\nSigned-off-by: Jeff King \n---\nRebased on today's master to resolve textual conflicts.\n\n Makefile | 11 +++++++++--\n 1 files changed, 9 insertions(+), 2 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex 41ab8e9..0cb21da 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -194,6 +194,8 @@ all::\n #\n # Define USE_NED_ALLOCATOR if you want to replace the platforms default\n # memory allocators with the nedmalloc allocator written by Niall Douglas.\n+#\n+# Define NO_REGEX if you have no or inferior regex support in your C library.\n \n GIT-VERSION-FILE: .FORCE-GIT-VERSION-FILE\n \t@$(SHELL_PATH) ./GIT-VERSION-GEN\n@@ -884,9 +886,10 @@ ifneq (,$(findstring MINGW,$(uname_S)))\n \tUSE_NED_ALLOCATOR = YesPlease\n \tUNRELIABLE_FSTAT = UnfortunatelyYes\n \tOBJECT_CREATION_USES_RENAMES = UnfortunatelyNeedsTo\n-\tCOMPAT_CFLAGS += -D__USE_MINGW_ACCESS -DNOGDI -Icompat -Icompat/regex -Icompat/fnmatch\n+\tNO_REGEX = YesPlease\n+\tCOMPAT_CFLAGS += -D__USE_MINGW_ACCESS -DNOGDI -Icompat -Icompat/fnmatch\n \tCOMPAT_CFLAGS += -DSTRIP_EXTENSION=\\\".exe\\\"\n-\tCOMPAT_OBJS += compat/mingw.o compat/fnmatch/fnmatch.o compat/regex/regex.o compat/winansi.o\n+\tCOMPAT_OBJS += compat/mingw.o compat/fnmatch/fnmatch.o compat/winansi.o\n \tEXTLIBS += -lws2_32\n \tX = .exe\n ifneq (,$(wildcard ../THIS_IS_MSYSGIT))\n@@ -1200,6 +1203,10 @@ endif\n ifdef UNRELIABLE_FSTAT\n \tBASIC_CFLAGS += -DUNRELIABLE_FSTAT\n endif\n+ifdef NO_REGEX\n+\tCOMPAT_CFLAGS += -Icompat/regex\n+\tCOMPAT_OBJS += compat/regex/regex.o\n+endif\n \n ifdef USE_NED_ALLOCATOR\n COMPAT_CFLAGS += -DUSE_NED_ALLOCATOR -DOVERRIDE_STRDUP -DNDEBUG -DREPLACE_SYSTEM_ALLOCATOR -Icompat/nedmalloc\n-- \n1.6.3.2.411.gffb5\n"},{"id":"116436","messageId":"20090616190821.GB23197@coredump.intra.peff.net","threadId":"19823","inReplyTo":"20090616190550.GA22905@coredump.intra.peff.net","subject":"[PATCH v2 2/2] Makefile: use compat regex on Solaris","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-06-16T19:08:21Z","receivedAt":"2009-06-16T19:08:21Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The system regex is either slow or buggy for complex\npatterns, like the built-in xfuncname pattern for java\nfiles.\n\nSigned-off-by: Jeff King \n---\nRebased to today's master to resolve textual conflicts.\n\n Makefile | 1 +\n 1 files changed, 1 insertions(+), 0 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex 0cb21da..3bd0c08 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -725,6 +725,7 @@ ifeq ($(uname_S),SunOS)\n \tNO_MEMMEM = YesPlease\n \tNO_MKDTEMP = YesPlease\n \tNO_MKSTEMPS = YesPlease\n+\tNO_REGEX = YesPlease\n \tifeq ($(uname_R),5.7)\n \t\tNEEDS_RESOLV = YesPlease\n \t\tNO_IPV6 = YesPlease\n-- \n1.6.3.2.411.gffb5\n"},{"id":"116439","messageId":"v5GZyk1pvyw2mnFGX-8GiCIBKzquUZb5YYcjHNvgkczpXD2vQ4qdjg@cipher.nrlssc.navy.mil","threadId":"19823","inReplyTo":"20090616190821.GB23197@coredump.intra.peff.net","subject":"Re: [PATCH v2 2/2] Makefile: use compat regex on Solaris","fromName":"Brandon Casey","fromEmail":"casey@nrlssc.navy.mil","sentAt":"2009-06-16T20:07:40Z","receivedAt":"2009-06-16T20:07:40Z","isPatch":true,"sender":{"key":"drafnel@gmail.com","avatar":"https://avatars.githubusercontent.com/u/921167?v=4"},"body":"Jeff King wrote:\n> The system regex is either slow or buggy for complex\n> patterns, like the built-in xfuncname pattern for java\n> files.\n> \n> Signed-off-by: Jeff King \n> ---\n> Rebased to today's master to resolve textual conflicts.\n> \n> Makefile | 1 +\n> 1 files changed, 1 insertions(+), 0 deletions(-)\n> \n> diff --git a/Makefile b/Makefile\n> index 0cb21da..3bd0c08 100644\n> --- a/Makefile\n> +++ b/Makefile\n> @@ -725,6 +725,7 @@ ifeq ($(uname_S),SunOS)\n> \tNO_MEMMEM = YesPlease\n> \tNO_MKDTEMP = YesPlease\n> \tNO_MKSTEMPS = YesPlease\n> +\tNO_REGEX = YesPlease\n> \tifeq ($(uname_R),5.7)\n> \t\tNEEDS_RESOLV = YesPlease\n> \t\tNO_IPV6 = YesPlease\n\n\nYou need to add -DHAVE_ALLOCA_H to the BASIC_CFLAGS statement in\nthe SunOS section of the Makefile so that alloca.h will be included\nin compat/regex/regex.c. This is necessary for the SUNWspro compiler.\nIt takes me a long time to compile, so I haven't checked yet whether\nthis causes any problems for the GNU compiler.\n\n-brandon\n"},{"id":"116441","messageId":"ewZ5ok_uS4Wg9yUHVY7a_6-lG5HI1Uq4csZRDyqCMDgtwGkWzQVNCw@cipher.nrlssc.navy.mil","threadId":"19823","inReplyTo":"RFQLUdKWnVWgwwX0qsqUhC-pl9v39aFOKMpTbbABiCEXczTo26fVow@cipher.nrlssc.navy.mil","subject":"Re: git diff looping?","fromName":"Brandon Casey","fromEmail":"casey@nrlssc.navy.mil","sentAt":"2009-06-16T20:22:53Z","receivedAt":"2009-06-16T20:22:53Z","isPatch":false,"sender":{"key":"drafnel@gmail.com","avatar":"https://avatars.githubusercontent.com/u/921167?v=4"},"body":"Brandon Casey wrote:\n> Jeff King wrote:\n>> On Tue, Jun 16, 2009 at 09:51:24AM -0700, Junio C Hamano wrote:\n>>\n>>>> I can reproduce the problem on Solaris 8 using git v1.6.3. It seems to\n>>>> be caused by a horribly slow system regex implementation; it really\n>>>> chokes on the regex we use to find the \"funcname\" line for java files.\n>>> Hmm. Is running under LC_ALL=C LANG=C _with_ the slow system regex help?\n>> No, it remains extremely slow (it is possible that it _is_ faster,\n>> though, but I never managed to run either case to completion; they are\n>> both clearly orders of magnitude off of acceptable).\n> \n> I haven't tried setting LC_ALL, LANG, but this Solaris regex is MANY orders\n> of magnitude slower. I've been running your example diff on the egit\n> repository for 2 hours and it still hasn't finished. The compat/regex\n> version finished in 3 seconds. Solaris 10 x86.\n\nOk, I don't think this call is going to finish. 'git diff v0.4.0' on\nSolaris 10 x86 using the native regex library. It has been running now\nfor over 4.5 hours.\n\nIf you're interested in a data point from another non-gnu regex library,\nI ran the same test on a mips IRIX6.5. It took 19.5 secs, and this is\nnot a young machine. It takes 4 secs when diff.java.xfuncname is set\nto 'foo'.\n\n-brandon\n"},{"id":"116459","messageId":"4A38AD5D.6010404@gmail.com","threadId":"19823","inReplyTo":"20090616171531.GA17538@coredump.intra.peff.net","subject":"Re: git diff looping?","fromName":"Paolo Bonzini","fromEmail":"paolo.bonzini@gmail.com","sentAt":"2009-06-17T08:46:21Z","receivedAt":"2009-06-17T08:46:21Z","isPatch":false,"sender":{"key":"paolo.bonzini@gmail.com","avatar":"https://gravatar.com/avatar/7817ef2e168b4ef0570c5bb5bdc1d4b44f34d3075fe32b871710dd942d0a89f5?d=mp&s=160"},"body":"\n> Really, that performance is so bad that I'm beginning to wonder if I am\n> somehow measuring something wrong. How could they ship something so\n> crappy through so many versions?\n\nBecause without some care in the matcher, the regex can be exponential. \nThis happens because you can backtrack arbitrarily from [A-Za-z_0-9]* \ninto [A-Za-z_] and ironically it also causes the regex not to work as \nintended; for example \"catch(\" can match the complex part of the regex \n(e.g. the first repetition can be \"c\" and the second can be \"atch\".\n\nWe can make it faster and more correct at the expense of additional \ncomplication.\n\nStarting from:\n\n^[ \\t]*(([ \\t]*[A-Za-z_][A-Za-z_0-9]*){2,}[ \\t]*\\([^;]*)$\n\nwe have to:\n\n1) move [ \\t] at the end of the repeated subexpression so that it \nremoves the need for the [ \\t] after\n\n^[ \\t]*(([A-Za-z_][A-Za-z_0-9]*[ \\t]*){2,}\\([^;]*)$\n\n2) make sure that at least one space/tab is eaten on all but the last \noccurrence of the repeated subexpression. To this end the LHS of {2,} \nis duplicated, once with [ \\t]+ and once with [ \\t]*. The repetition \nitself becomes a + since the last occurrence is now separately handled:\n\n^[ \\t]*(([A-Za-z_][A-Za-z_0-9]*[ \\t]+)+[A-Za-z_][A-Za-z_0-9]*\n[ \\t]*\\([^;]*)$\n\nPaolo\n"},{"id":"116462","messageId":"20090617102332.GA32353@coredump.intra.peff.net","threadId":"19823","inReplyTo":"4A38AD5D.6010404@gmail.com","subject":"Re: git diff looping?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-06-17T10:23:33Z","receivedAt":"2009-06-17T10:23:33Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jun 17, 2009 at 10:46:21AM +0200, Paolo Bonzini wrote:\n\n> 2) make sure that at least one space/tab is eaten on all but the last \n> occurrence of the repeated subexpression. To this end the LHS of {2,} is \n> duplicated, once with [ \\t]+ and once with [ \\t]*. The repetition itself \n> becomes a + since the last occurrence is now separately handled:\n>\n> ^[ \\t]*(([A-Za-z_][A-Za-z_0-9]*[ \\t]+)+[A-Za-z_][A-Za-z_0-9]*\n> [ \\t]*\\([^;]*)$\n\nThanks, I can confirm that this is _much_ faster. Here are some timings\nfrom my Solaris 8 box for the \"git diff v0.4.0\" case using the system\nand compat engines, and using three regexes: the original that git is\nusing now, an updated one with your regex above[1] replacing the second\nline of the stock pattern, and a baseline regex of \".\" which should take\nvirtually no time at all.\n\n system, orig: infinite\n system, paolo: 2.5s\n system, \".\": 0.6s\n compat, orig: 288.0s\n compat, paolo: 1.5s\n compat, \".\": 0.6s\n\nSo it goes from infinite to 2.5s. Which still spends 3 times as long\nmatching funcname regexes as it does actually calculating the diff. The\ncompat library is a little better, but still chokes pretty badly on the\noriginal regex.\n\nLet's compare compat to the glibc implementation on my Debian box:\n\n system, orig: 0.22s\n system, paolo: 0.22s\n system, \".\": 0.15s\n compat, orig: 150.88s\n compat, paolo: 0.43s\n compat, \".\": 0.15s\n\nBesides the exponential behavior on the original regex, it is still\nabout twice as slow as the system one.\n\nSo I think there are three possible optimizations worth considering:\n\n 1. Replace the builtin diff.java.xfuncname pattern with what Paolo\n suggested (though I haven't verified its correctness beyond a\n cursory look at the results). This is easy to do, and will help\n people with crappy system regex libraries and people on\n compat/regex/ (right now just mingw) a _lot_. The downside is that\n it's a little harder to read the regex, but not terribly so.\n\n 2. Recommend NO_REGEX for people with slow system regex libraries.\n This is also easy to do, and will help people even if we do (1) for\n two reasons:\n\n a. we process user-defined regexes through diff.*.xfuncname\n patterns, as well as through \"git grep\"; so we are protecting\n against poor performance when they give us a complex regex\n\n b. even on more reasonable regexps like Paolo's, we seem to get a\n 2:1 speedup over the Solaris system library\n\n 3. Replace compat/regex with something faster. It still produces\n exponential behavior in complex cases where glibc does not, and it\n seems to be about 1/3 as fast on Paolo's regex.\n\n I haven't looked at how large or how portable the glibc\n implementation is. Another alternative is that we could provide a\n simple compat/ as now, and have better support for linking against\n an external library like pcre, if it is available.\n\n-Peff\n\n[1] Note if you are cutting and pasting Paolo's regex into the C code,\n the \"\\(\" needs to be \"\\\\(\", which I screwed up in my initial\n timings. :)\n"},{"id":"116463","messageId":"4A38CD33.9020402@gmail.com","threadId":"19823","inReplyTo":"20090617102332.GA32353@coredump.intra.peff.net","subject":"Re: git diff looping?","fromName":"Paolo Bonzini","fromEmail":"paolo.bonzini@gmail.com","sentAt":"2009-06-17T11:02:11Z","receivedAt":"2009-06-17T11:02:11Z","isPatch":false,"sender":{"key":"paolo.bonzini@gmail.com","avatar":"https://gravatar.com/avatar/7817ef2e168b4ef0570c5bb5bdc1d4b44f34d3075fe32b871710dd942d0a89f5?d=mp&s=160"},"body":"> system, orig: 0.22s\n> system, paolo: 0.22s\n> system, \".\": 0.15s\n> compat, orig: 150.88s\n> compat, paolo: 0.43s\n> compat, \".\": 0.15s\n> \n> Besides the exponential behavior on the original regex, it is still\n> about twice as slow as the system one.\n\nThe reason is that the glibc regex is a DFA-based matcher. It is much \nslower on regexes with backreferences, but otherwise it is faster.\n\n> 1. Replace the builtin diff.java.xfuncname pattern with what Paolo\n> suggested (though I haven't verified its correctness beyond a\n> cursory look at the results).\n\nI checked it a bit harder, but still it is not easy to check because of \nthe false positives in the original regex. I'm pretty sure it's correct \n though; I find it even easier to read (though longer) than the \noriginal one.\n\n> I haven't looked at how large or how portable the glibc\n> implementation is.\n\nDecently portable, but I don't think it's worth it. Users that write \nregexes so complex should know of the exponential behavior, I think.\n\nPaolo\n"},{"id":"116464","messageId":"4A38D408.7000302@op5.se","threadId":"19823","inReplyTo":"20090617102332.GA32353@coredump.intra.peff.net","subject":"Re: git diff looping?","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2009-06-17T11:31:20Z","receivedAt":"2009-06-17T11:31:20Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Jeff King wrote:\n> \n> 3. Replace compat/regex with something faster. It still produces\n> exponential behavior in complex cases where glibc does not, and it\n> seems to be about 1/3 as fast on Paolo's regex.\n> \n> I haven't looked at how large or how portable the glibc\n> implementation is. Another alternative is that we could provide a\n> simple compat/ as now, and have better support for linking against\n> an external library like pcre, if it is available.\n> \n\nThe glibc implementation is quite large. Cutting the library-specific\ncruft it still sits at about 10k LOC.\n\nUsing PCRE is a no-go, as it uses perl-compatible regexes even for the\nposix-compatible API, as per pcreposix(3):\n\n When PCRE is called via these functions, it is only the API that is\n POSIX-like in style. The syntax and semantics of the regular expres-\n sions themselves are still those of Perl, subject to the setting of\n various PCRE options, as described below. \"POSIX-like in style\" means\n that the API approximates to the POSIX definition; it is not fully\n POSIX-compatible, and in multi-byte encoding domains it is probably\n even less compatible.\n\nThis would probably surprise some \"git grep\" users quite a lot, I think.\n\nI like your other two suggestions though. The stuff already in compat/\nseems to work well enough, so with Paolo's improved pattern it should\nbe fine.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n\nConsidering the successes of the wars on alcohol, poverty, drugs and\nterror, I think we should give some serious thought to declaring war\non peace.\n"},{"id":"116469","messageId":"4A38EACD.3050602@gmail.com","threadId":"19823","inReplyTo":"4A38D408.7000302@op5.se","subject":"Re: git diff looping?","fromName":"Paolo Bonzini","fromEmail":"paolo.bonzini@gmail.com","sentAt":"2009-06-17T13:08:29Z","receivedAt":"2009-06-17T13:08:29Z","isPatch":false,"sender":{"key":"paolo.bonzini@gmail.com","avatar":"https://gravatar.com/avatar/7817ef2e168b4ef0570c5bb5bdc1d4b44f34d3075fe32b871710dd942d0a89f5?d=mp&s=160"},"body":"\n> The glibc implementation is quite large. Cutting the library-specific\n> cruft it still sits at about 10k LOC.\n> \n> Using PCRE is a no-go, as it uses perl-compatible regexes even for the\n> posix-compatible API, as per pcreposix(3):\n\nI have a PCRE fork that has POSIX semantics (except the braindead \nleftmost-longest *sub*expressions). It weighs 8kLOC, you can find it in \nbranch ssed of GNU sed's git repository.\n\nPaolo\n"},{"id":"116470","messageId":"e2b179460906170615u46a71241wf012d98020ef91e0@mail.gmail.com","threadId":"19823","inReplyTo":"20090616190821.GB23197@coredump.intra.peff.net","subject":"Re: [PATCH v2 2/2] Makefile: use compat regex on Solaris","fromName":"Mike Ralphson","fromEmail":"mike.ralphson@gmail.com","sentAt":"2009-06-17T13:15:54Z","receivedAt":"2009-06-17T13:15:54Z","isPatch":true,"sender":{"key":"mike.ralphson@gmail.com","avatar":"https://avatars.githubusercontent.com/u/21603?v=4"},"body":"2009/6/16 Jeff King \n>\n> The system regex is either slow or buggy for complex\n> patterns, like the built-in xfuncname pattern for java\n> files.\n\nAlso required on AIX (5.3). I thought this was a major performance\nregression somewhere else, but my 'old stable' version dates from a\ntime when we were briefly using compat/regex on this platform before\nwe reverted that change and switched over to extended regexes.\n\nWith the above:\n3m33.399s\n\nWithout:\n... manually aborted after 58m !\n\ngit 1.6.0.2.229.g1293c\n3m21.645s\n\nCould you squash\n\n+ NO_REGEX = YesPlease\n\nin ifeq ($(uname_S),AIX) please? Shout if follow-up patch preferred.\n\nSigned-off-by: Mike Ralphson \n\nMike\n\nPS Pound to a penny INTERNAL_QSORT would be a win on Solaris too...\n"},{"id":"116471","messageId":"4A38ECB2.6010100@op5.se","threadId":"19823","inReplyTo":"4A38EACD.3050602@gmail.com","subject":"Re: git diff looping?","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2009-06-17T13:16:34Z","receivedAt":"2009-06-17T13:16:34Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Paolo Bonzini wrote:\n> \n>> The glibc implementation is quite large. Cutting the library-specific\n>> cruft it still sits at about 10k LOC.\n>>\n>> Using PCRE is a no-go, as it uses perl-compatible regexes even for the\n>> posix-compatible API, as per pcreposix(3):\n> \n> I have a PCRE fork that has POSIX semantics (except the braindead \n> leftmost-longest *sub*expressions). It weighs 8kLOC, you can find it in \n> branch ssed of GNU sed's git repository.\n> \n\nSounds neat. Do you by any chance have some performance measurements\nfor it? If the work's already done and it provides a significant\nimprovement I'm all for it ;-)\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n\nConsidering the successes of the wars on alcohol, poverty, drugs and\nterror, I think we should give some serious thought to declaring war\non peace.\n"},{"id":"116474","messageId":"e2b179460906170655t6ae0f188t88a01cc14bc79135@mail.gmail.com","threadId":"19823","inReplyTo":"e2b179460906170615u46a71241wf012d98020ef91e0@mail.gmail.com","subject":"Re: [PATCH v2 2/2] Makefile: use compat regex on Solaris","fromName":"Mike Ralphson","fromEmail":"mike.ralphson@gmail.com","sentAt":"2009-06-17T13:55:40Z","receivedAt":"2009-06-17T13:55:40Z","isPatch":true,"sender":{"key":"mike.ralphson@gmail.com","avatar":"https://avatars.githubusercontent.com/u/21603?v=4"},"body":"2009/6/17 Mike Ralphson :\n> Also required on AIX (5.3).\n\nScratch that, sorry - I hadn't seen the related thread (git diff looping?)\n\nPaolo's fix is the only one required for AIX.\n\nSorry for the noise.\n\nMike\n"},{"id":"116475","messageId":"4A38F66B.4050604@gmail.com","threadId":"19823","inReplyTo":"4A38ECB2.6010100@op5.se","subject":"Re: git diff looping?","fromName":"Paolo Bonzini","fromEmail":"paolo.bonzini@gmail.com","sentAt":"2009-06-17T13:58:03Z","receivedAt":"2009-06-17T13:58:03Z","isPatch":false,"sender":{"key":"paolo.bonzini@gmail.com","avatar":"https://gravatar.com/avatar/7817ef2e168b4ef0570c5bb5bdc1d4b44f34d3075fe32b871710dd942d0a89f5?d=mp&s=160"},"body":"\n> Sounds neat. Do you by any chance have some performance measurements\n> for it? If the work's already done and it provides a significant\n> improvement I'm all for it ;-)\n\nIt's very very fast, but only as fast as a backtracking matcher can be. \n I think it would trounce glibc on my regex but probably not on the \nbuggy one.\n\nPaolo\n"},{"id":"116478","messageId":"1245248766-14867-1-git-send-email-bonzini@gnu.org","threadId":"19823","inReplyTo":"20090617102332.GA32353@coredump.intra.peff.net","subject":"[PATCH] avoid exponential regex match for java and objc function names","fromName":"Paolo Bonzini","fromEmail":"bonzini@gnu.org","sentAt":"2009-06-17T14:26:06Z","receivedAt":"2009-06-17T14:26:06Z","isPatch":true,"sender":{"key":"bonzini@gnu.org","avatar":"https://avatars.githubusercontent.com/u/42082?v=4"},"body":"In the old regex\n\n^[ \\t]*(([ \\t]*[A-Za-z_][A-Za-z_0-9]*){2,}[ \\t]*\\([^;]*)$\n ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nyou can backtrack arbitrarily from [A-Za-z_0-9]* into [A-Za-z_], thus\ncausing an exponential number of backtracks. Ironically it also causes\nthe regex not to work as intended; for example \"catch\" can match the\nunderlined part of the regex, the first repetition matching \"c\" and\nthe second matching \"atch\".\n\nThe replacement regex avoids this problem, because it makes sure that\nat least a space/tab is eaten on each repetition. In other words,\na suffix of a repetition can never be a prefix of the next repetition.\n\nSigned-off-by: Paolo Bonzini \n---\n userdiff.c | 5 +++--\n 1 files changed, 3 insertions(+), 2 deletions(-)\n\ndiff --git a/userdiff.c b/userdiff.c\nindex d556da9..57529ae 100644\n--- a/userdiff.c\n+++ b/userdiff.c\n@@ -13,7 +13,8 @@ PATTERNS(\"html\", \"^[ \\t]*(<[Hh][1-6][ \\t].*>.*)$\",\n \t \"[^<>= \\t]+|[^[:space:]]|[\\x80-\\xff]+\"),\n PATTERNS(\"java\",\n \t \"!^[ \\t]*(catch|do|for|if|instanceof|new|return|switch|throw|while)\\n\"\n-\t \"^[ \\t]*(([ \\t]*[A-Za-z_][A-Za-z_0-9]*){2,}[ \\t]*\\\\([^;]*)$\",\n+\t \"^[ \\t]*(([A-Za-z_][A-Za-z_0-9]*[ \\t]+)+[A-Za-z_][A-Za-z_0-9]*[ \\t]*\\\\([^;]*)$\",\n+\t /* -- */\n \t \"[a-zA-Z_][a-zA-Z0-9_]*\"\n \t \"|[-+0-9.e]+[fFlL]?|0[xXbB]?[0-9a-fA-F]+[lL]?\"\n \t \"|[-+*/<>%&^|=!]=\"\n@@ -25,7 +26,7 @@ PATTERNS(\"objc\",\n \t /* Objective-C methods */\n \t \"^[ \\t]*([-+][ \\t]*\\\\([ \\t]*[A-Za-z_][A-Za-z_0-9* \\t]*\\\\)[ \\t]*[A-Za-z_].*)$\\n\"\n \t /* C functions */\n-\t \"^[ \\t]*(([ \\t]*[A-Za-z_][A-Za-z_0-9]*){2,}[ \\t]*\\\\([^;]*)$\\n\"\n+\t \"^[ \\t]*(([A-Za-z_][A-Za-z_0-9]*[ \\t]+)+[A-Za-z_][A-Za-z_0-9]*[ \\t]*\\\\([^;]*)$\\n\"\n \t /* Objective-C class/protocol definitions */\n \t \"^(@(implementation|interface|protocol)[ \\t].*)$\",\n \t /* -- */\n-- \n1.6.0.3\n"},{"id":"116481","messageId":"9b18b3110906170846o5b3c3000r72506bf62765a044@mail.gmail.com","threadId":"19823","inReplyTo":"1245248766-14867-1-git-send-email-bonzini@gnu.org","subject":"Re: [PATCH] avoid exponential regex match for java and objc function names","fromName":"demerphq","fromEmail":"demerphq@gmail.com","sentAt":"2009-06-17T15:46:54Z","receivedAt":"2009-06-17T15:46:54Z","isPatch":true,"sender":{"key":"demerphq@gmail.com","avatar":null},"body":"Just a note, but If the Java regex library you are using supports\nthe PCRE compatible (?>...) atomic matching construct (or their\nequivalent *+ and ++) then these patterns can be significantly\nimproved beyond their current state.\n\n\n2009/6/17 Paolo Bonzini :\n> In the old regex\n>\n> ^[ \\t]*(([ \\t]*[A-Za-z_][A-Za-z_0-9]*){2,}[ \\t]*\\([^;]*)$\n>        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n>\n> you can backtrack arbitrarily from [A-Za-z_0-9]* into [A-Za-z_], thus\n> causing an exponential number of backtracks.  Ironically it also causes\n> the regex not to work as intended; for example \"catch\" can match the\n> underlined part of the regex, the first repetition matching \"c\" and\n> the second matching \"atch\".\n>\n> The replacement regex avoids this problem, because it makes sure that\n> at least a space/tab is eaten on each repetition.  In other words,\n> a suffix of a repetition can never be a prefix of the next repetition.\n>\n> Signed-off-by: Paolo Bonzini \n> ---\n>  userdiff.c |    5 +++--\n>  1 files changed, 3 insertions(+), 2 deletions(-)\n>\n> diff --git a/userdiff.c b/userdiff.c\n> index d556da9..57529ae 100644\n> --- a/userdiff.c\n> +++ b/userdiff.c\n> @@ -13,7 +13,8 @@ PATTERNS(\"html\", \"^[ \\t]*(<[Hh][1-6][ \\t].*>.*)$\",\n>         \"[^<>= \\t]+|[^[:space:]]|[\\x80-\\xff]+\"),\n>  PATTERNS(\"java\",\n>         \"!^[ \\t]*(catch|do|for|if|instanceof|new|return|switch|throw|while)\\n\"\n> -        \"^[ \\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> +        /* -- */\n>         \"[a-zA-Z_][a-zA-Z0-9_]*\"\n>         \"|[-+0-9.e]+[fFlL]?|0[xXbB]?[0-9a-fA-F]+[lL]?\"\n>         \"|[-+*/<>%&^|=!]=\"\n> @@ -25,7 +26,7 @@ PATTERNS(\"objc\",\n>         /* Objective-C methods */\n>         \"^[ \\t]*([-+][ \\t]*\\\\([ \\t]*[A-Za-z_][A-Za-z_0-9* \\t]*\\\\)[ \\t]*[A-Za-z_].*)$\\n\"\n>         /* C functions */\n> -        \"^[ \\t]*(([ \\t]*[A-Za-z_][A-Za-z_0-9]*){2,}[ \\t]*\\\\([^;]*)$\\n\"\n> +        \"^[ \\t]*(([A-Za-z_][A-Za-z_0-9]*[ \\t]+)+[A-Za-z_][A-Za-z_0-9]*[ \\t]*\\\\([^;]*)$\\n\"\n>         /* Objective-C class/protocol definitions */\n>         \"^(@(implementation|interface|protocol)[ \\t].*)$\",\n>         /* -- */\n> --\n> 1.6.0.3\n>\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at  http://vger.kernel.org/majordomo-info.html\n>\n\n\n\n-- \nperl -Mre=debug -e \"/just|another|perl|hacker/\"\n"},{"id":"116482","messageId":"20090617155603.GA14545@sigill.intra.peff.net","threadId":"19823","inReplyTo":"9b18b3110906170846o5b3c3000r72506bf62765a044@mail.gmail.com","subject":"Re: [PATCH] avoid exponential regex match for java and objc function names","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-06-17T15:56:04Z","receivedAt":"2009-06-17T15:56:04Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jun 17, 2009 at 05:46:54PM +0200, demerphq wrote:\n\n> Just a note, but If the Java regex library you are using supports\n> the PCRE compatible (?>...) atomic matching construct (or their\n> equivalent *+ and ++) then these patterns can be significantly\n> improved beyond their current state.\n\nTo clarify, this isn't a java regex library, but rather regexps used to\nmatch function names inside java language files when generating diffs.\nThe regex library itself is the POSIX regex routines provided by libc.\n\nPCRE syntax is nice, but we don't want to require it for every build,\nand it's important to have the same syntax everywhere (so that, e.g.,\nyour config from one build works on a different build).\n\n-Peff\n"},{"id":"116483","messageId":"9b18b3110906170900g778b3c8aie627fb45a4967eb2@mail.gmail.com","threadId":"19823","inReplyTo":"20090617155603.GA14545@sigill.intra.peff.net","subject":"Re: [PATCH] avoid exponential regex match for java and objc function names","fromName":"demerphq","fromEmail":"demerphq@gmail.com","sentAt":"2009-06-17T16:00:37Z","receivedAt":"2009-06-17T16:00:37Z","isPatch":true,"sender":{"key":"demerphq@gmail.com","avatar":null},"body":"2009/6/17 Jeff King :\n> On Wed, Jun 17, 2009 at 05:46:54PM +0200, demerphq wrote:\n>\n>> Just  a note, but If the  Java regex library you are using supports\n>> the PCRE compatible (?>...) atomic matching construct (or their\n>> equivalent *+ and ++) then these patterns can be significantly\n>> improved beyond their current state.\n>\n> To clarify, this isn't a java regex library, but rather regexps used to\n> match function names inside java language files when generating diffs.\n> The regex library itself is the POSIX regex routines provided by libc.\n>\n> PCRE syntax is nice, but we don't want to require it for every build,\n> and it's important to have the same syntax everywhere (so that, e.g.,\n> your config from one build works on a different build).\n\nAh ok. Im not familiar with the finer points of the POSIX engine, but\nPCRE and Perl's engine, and most similar engines are not true regular\nexpression engines and thus benefit *greatly* from atomic matching if\nit is available.\n\nLike the difference between heat-death performance (or stack\noverflow), and running instantly.\n\nYves\n\n\n\n-- \nperl -Mre=debug -e \"/just|another|perl|hacker/\"\n"},{"id":"116484","messageId":"4A391429.4010706@gmail.com","threadId":"19823","inReplyTo":"9b18b3110906170900g778b3c8aie627fb45a4967eb2@mail.gmail.com","subject":"Re: [PATCH] avoid exponential regex match for java and objc function names","fromName":"Paolo Bonzini","fromEmail":"paolo.bonzini@gmail.com","sentAt":"2009-06-17T16:04:57Z","receivedAt":"2009-06-17T16:04:57Z","isPatch":true,"sender":{"key":"paolo.bonzini@gmail.com","avatar":"https://gravatar.com/avatar/7817ef2e168b4ef0570c5bb5bdc1d4b44f34d3075fe32b871710dd942d0a89f5?d=mp&s=160"},"body":"\n> Ah ok. Im not familiar with the finer points of the POSIX engine, but\n> PCRE and Perl's engine, and most similar engines are not true regular\n> expression engines and thus benefit *greatly* from atomic matching if\n> it is available.\n> \n> Like the difference between heat-death performance (or stack\n> overflow), and running instantly.\n\nYou can almost always fix the regex to avoid this, by ensuring that \nwhenever you have (...)+ (or *) a suffix of the subexpression cannot be \na prefix of the subexpression too. This is what my patch did -- \nchanging a bad regex to a nicely behaving one.\n\nPaolo\n"},{"id":"116487","messageId":"7vab46rev0.fsf@alter.siamese.dyndns.org","threadId":"19823","inReplyTo":"1245248766-14867-1-git-send-email-bonzini@gnu.org","subject":"Re: [PATCH] avoid exponential regex match for java and objc function names","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-06-17T16:42:43Z","receivedAt":"2009-06-17T16:42:43Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Paolo Bonzini writes:\n\n> In the old regex\n>\n> ^[ \\t]*(([ \\t]*[A-Za-z_][A-Za-z_0-9]*){2,}[ \\t]*\\([^;]*)$\n> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n>\n> you can backtrack arbitrarily from [A-Za-z_0-9]* into [A-Za-z_], thus\n> causing an exponential number of backtracks. Ironically it also causes\n> the regex not to work as intended; for example \"catch\" can match the\n> underlined part of the regex, the first repetition matching \"c\" and\n> the second matching \"atch\".\n>\n> The replacement regex avoids this problem, because it makes sure that\n> at least a space/tab is eaten on each repetition. In other words,\n> a suffix of a repetition can never be a prefix of the next repetition.\n\nThanks; nicely done.\n\nShould I remove the \"/* -- */\" or is it for better readability I should\nkeep?\n\n> Signed-off-by: Paolo Bonzini \n> ---\n> userdiff.c | 5 +++--\n> 1 files changed, 3 insertions(+), 2 deletions(-)\n>\n> diff --git a/userdiff.c b/userdiff.c\n> index d556da9..57529ae 100644\n> --- a/userdiff.c\n> +++ b/userdiff.c\n> @@ -13,7 +13,8 @@ PATTERNS(\"html\", \"^[ \\t]*(<[Hh][1-6][ \\t].*>.*)$\",\n> \t \"[^<>= \\t]+|[^[:space:]]|[\\x80-\\xff]+\"),\n> PATTERNS(\"java\",\n> \t \"!^[ \\t]*(catch|do|for|if|instanceof|new|return|switch|throw|while)\\n\"\n> -\t \"^[ \\t]*(([ \\t]*[A-Za-z_][A-Za-z_0-9]*){2,}[ \\t]*\\\\([^;]*)$\",\n> +\t \"^[ \\t]*(([A-Za-z_][A-Za-z_0-9]*[ \\t]+)+[A-Za-z_][A-Za-z_0-9]*[ \\t]*\\\\([^;]*)$\",\n> +\t /* -- */\n> \t \"[a-zA-Z_][a-zA-Z0-9_]*\"\n> \t \"|[-+0-9.e]+[fFlL]?|0[xXbB]?[0-9a-fA-F]+[lL]?\"\n> \t \"|[-+*/<>%&^|=!]=\"\n> @@ -25,7 +26,7 @@ PATTERNS(\"objc\",\n> \t /* Objective-C methods */\n> \t \"^[ \\t]*([-+][ \\t]*\\\\([ \\t]*[A-Za-z_][A-Za-z_0-9* \\t]*\\\\)[ \\t]*[A-Za-z_].*)$\\n\"\n> \t /* C functions */\n> -\t \"^[ \\t]*(([ \\t]*[A-Za-z_][A-Za-z_0-9]*){2,}[ \\t]*\\\\([^;]*)$\\n\"\n> +\t \"^[ \\t]*(([A-Za-z_][A-Za-z_0-9]*[ \\t]+)+[A-Za-z_][A-Za-z_0-9]*[ \\t]*\\\\([^;]*)$\\n\"\n> \t /* Objective-C class/protocol definitions */\n> \t \"^(@(implementation|interface|protocol)[ \\t].*)$\",\n> \t /* -- */\n> -- \n> 1.6.0.3\n"},{"id":"116525","messageId":"4A39E291.8030207@gmail.com","threadId":"19823","inReplyTo":"7vab46rev0.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] avoid exponential regex match for java and objc function names","fromName":"Paolo Bonzini","fromEmail":"paolo.bonzini@gmail.com","sentAt":"2009-06-18T06:45:37Z","receivedAt":"2009-06-18T06:45:37Z","isPatch":true,"sender":{"key":"paolo.bonzini@gmail.com","avatar":"https://gravatar.com/avatar/7817ef2e168b4ef0570c5bb5bdc1d4b44f34d3075fe32b871710dd942d0a89f5?d=mp&s=160"},"body":"\n> Should I remove the \"/* -- */\" or is it for better readability I should\n> keep?\n\nIt helps detecting the separation between the function regex and the \nword regex:\n\n>> -\t \"^[ \\t]*(([ \\t]*[A-Za-z_][A-Za-z_0-9]*){2,}[ \\t]*\\\\([^;]*)$\",\n>> +\t \"^[ \\t]*(([A-Za-z_][A-Za-z_0-9]*[ \\t]+)+[A-Za-z_][A-Za-z_0-9]*[ \\t]*\\\\([^;]*)$\",\n>> +\t /* -- */\n\nI stole the idea from the Objective-C part:\n\n>> \t /* C functions */\n>> -\t \"^[ \\t]*(([ \\t]*[A-Za-z_][A-Za-z_0-9]*){2,}[ \\t]*\\\\([^;]*)$\\n\"\n>> +\t \"^[ \\t]*(([A-Za-z_][A-Za-z_0-9]*[ \\t]+)+[A-Za-z_][A-Za-z_0-9]*[ \\t]*\\\\([^;]*)$\\n\"\n>> \t /* Objective-C class/protocol definitions */\n>> \t \"^(@(implementation|interface|protocol)[ \\t].*)$\",\n>> \t /* -- */\n\nPaolo\n"}]}