{"thread":{"id":"16213","subject":"absurdly slow git-diff","startedAt":"2008-11-07T20:01:27Z","lastAt":"2008-11-08T21:02:52Z","messageCount":13,"participants":["Abhijit Menon-Sen","Mike Hommey","Linus Torvalds","Davide Libenzi","Pierre Habouzit","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"95142","messageId":"20081107200126.GA20284@toroid.org","threadId":"16213","inReplyTo":null,"subject":"absurdly slow git-diff","fromName":"Abhijit Menon-Sen","fromEmail":"ams@toroid.org","sentAt":"2008-11-07T20:01:27Z","receivedAt":"2008-11-07T20:01:27Z","isPatch":false,"sender":{"key":"ams@toroid.org","avatar":null},"body":"I have a 240k-line file, and I change one character on every sixth line.\nThe resulting diff gives git serious indigestion:\n\n$ git --version\ngit version 1.6.0.3.640.g6331a\n$ mkdir a; cd a; git init\nInitialized empty Git repository in /home/ams/a/.git/\n$ cp ../1 .; git add 1; git commit -q -m 1\n$ cp ../2 1; git add 1; git commit -q -m 2 \n$ time git show HEAD > x\ngit show HEAD > x 309.88s user 0.46s system 97% cpu 5:17.06 total\n\n(I use commit -q above not only for brevity; for the second commit,\ncalculating the diffstat takes the same five minutes that git show,\ngit log -p, git log --stat etc. all take.)\n\nNote that diff(1) can handle the patch fine:\n\n$ time diff -u ../1 ../2 >/dev/null\ndiff -u ../1 ../2 > /dev/null 0.30s user 0.06s system 69% cpu 0.519 total\n\nIf anyone's interested, the files are http://toroid.org/misc/1 and\nhttp://toroid.org/misc/2\n\nDoes anyone understand why this slowdown might happen or have\nsuggestions about where I should look for it?\n\nThanks.\n\n-- ams\n"},{"id":"95147","messageId":"20081107212836.GA22717@glandium.org","threadId":"16213","inReplyTo":"20081107200126.GA20284@toroid.org","subject":"Re: absurdly slow git-diff","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2008-11-07T21:28:36Z","receivedAt":"2008-11-07T21:28:36Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Sat, Nov 08, 2008 at 01:31:27AM +0530, Abhijit Menon-Sen wrote:\n> I have a 240k-line file, and I change one character on every sixth line.\n> The resulting diff gives git serious indigestion:\n> \n> $ git --version\n> git version 1.6.0.3.640.g6331a\n> $ mkdir a; cd a; git init\n> Initialized empty Git repository in /home/ams/a/.git/\n> $ cp ../1 .; git add 1; git commit -q -m 1\n> $ cp ../2 1; git add 1; git commit -q -m 2 \n\nYou don't need to go that far. You can stop at cp ../2 1 and run git\ndiff from there.\n\nAll the time is spent in the two loops in\nxdiff/xprepare.c:xdl_cleanup_records, on line 400 and 412.\n\nI'll leave the rest of the investigation to people actually knowing this\ncode ;)\n\nMike\n"},{"id":"95148","messageId":"alpine.LFD.2.00.0811071335010.3468@nehalem.linux-foundation.org","threadId":"16213","inReplyTo":"20081107200126.GA20284@toroid.org","subject":"Re: absurdly slow git-diff","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-11-07T21:37:29Z","receivedAt":"2008-11-07T21:37:29Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nOn Sat, 8 Nov 2008, Abhijit Menon-Sen wrote:\n>\n> If anyone's interested, the files are http://toroid.org/misc/1 and\n> http://toroid.org/misc/2\n\nBtw, you can see this by just doing\n\n\tgit diff 1 2\n\nwithout even doing \"git init\" or doing any actual git repository.\n\n> Does anyone understand why this slowdown might happen or have\n> suggestions about where I should look for it?\n\nSure. It's actually fairly simple. You're hitting a O(n^2) thing (possibly \nhigher), and it's triggered by the fact that almost all your lines are \nidentical, ie you have a file that basically has 40,000 lines of each of\n\n\txxxx: xxx, xx xxx xxxx xx:xx:xx +xxxx\n\txx: xxxx xxxxxxxxxxx \n\txxxx: xxxx xxxxxxxxxxx \n\nand 30,000 of \n\n\t* xxxxx xxxxx (xxxxxx.xxxx xxx xxxxx (\\Xxxxxx) xxxxxx.xxxxxx {xxx}\n\nwith a smattering of others. And this is a case where the internal git \nimplementation does really badly. And nobody has really cared before, \nbecause nobody has ever had a case that mattered.\n\nThere's a number of different 'diff' algorithms, and it looks like GNU \ndiff has one that avoids the O(n^2) case for this case.\n\nI'm adding Davide as the original author of the diff library to the cc. \nI'm also adding Pierre, since he was talking about trying to implement\nanother diff algorithm (although I'm not at all sure that the patience \ndiff really would help this case at all).\n\n\t\tLinus\n"},{"id":"95171","messageId":"alpine.DEB.1.10.0811071503120.8736@alien.or.mcafeemobile.com","threadId":"16213","inReplyTo":"alpine.LFD.2.00.0811071335010.3468@nehalem.linux-foundation.org","subject":"Re: absurdly slow git-diff","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2008-11-07T23:04:22Z","receivedAt":"2008-11-07T23:04:22Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Fri, 7 Nov 2008, Linus Torvalds wrote:\n\n> On Sat, 8 Nov 2008, Abhijit Menon-Sen wrote:\n> >\n> > If anyone's interested, the files are http://toroid.org/misc/1 and\n> > http://toroid.org/misc/2\n> \n> Btw, you can see this by just doing\n> \n> \tgit diff 1 2\n> \n> without even doing \"git init\" or doing any actual git repository.\n> \n> > Does anyone understand why this slowdown might happen or have\n> > suggestions about where I should look for it?\n> \n> Sure. It's actually fairly simple. You're hitting a O(n^2) thing (possibly \n> higher), and it's triggered by the fact that almost all your lines are \n> identical, ie you have a file that basically has 40,000 lines of each of\n> \n> \txxxx: xxx, xx xxx xxxx xx:xx:xx +xxxx\n> \txx: xxxx xxxxxxxxxxx \n> \txxxx: xxxx xxxxxxxxxxx \n> \n> and 30,000 of \n> \n> \t* xxxxx xxxxx (xxxxxx.xxxx xxx xxxxx (\\Xxxxxx) xxxxxx.xxxxxx {xxx}\n> \n> with a smattering of others. And this is a case where the internal git \n> implementation does really badly. And nobody has really cared before, \n> because nobody has ever had a case that mattered.\n> \n> There's a number of different 'diff' algorithms, and it looks like GNU \n> diff has one that avoids the O(n^2) case for this case.\n> \n> I'm adding Davide as the original author of the diff library to the cc. \n> I'm also adding Pierre, since he was talking about trying to implement\n> another diff algorithm (although I'm not at all sure that the patience \n> diff really would help this case at all).\n\nThat should be an easy fix. Just need to limit the window by which \nxdl_clean_mmatch() scans the current position.\n\n\n\n- Davide\n"},{"id":"95175","messageId":"alpine.DEB.1.10.0811071517280.8736@alien.or.mcafeemobile.com","threadId":"16213","inReplyTo":"alpine.DEB.1.10.0811071503120.8736@alien.or.mcafeemobile.com","subject":"Re: absurdly slow git-diff","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2008-11-07T23:18:51Z","receivedAt":"2008-11-07T23:18:51Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Fri, 7 Nov 2008, Davide Libenzi wrote:\n\n> On Fri, 7 Nov 2008, Linus Torvalds wrote:\n> \n> > On Sat, 8 Nov 2008, Abhijit Menon-Sen wrote:\n> > >\n> > > If anyone's interested, the files are http://toroid.org/misc/1 and\n> > > http://toroid.org/misc/2\n> > \n> > Btw, you can see this by just doing\n> > \n> > \tgit diff 1 2\n> > \n> > without even doing \"git init\" or doing any actual git repository.\n> > \n> > > Does anyone understand why this slowdown might happen or have\n> > > suggestions about where I should look for it?\n> > \n> > Sure. It's actually fairly simple. You're hitting a O(n^2) thing (possibly \n> > higher), and it's triggered by the fact that almost all your lines are \n> > identical, ie you have a file that basically has 40,000 lines of each of\n> > \n> > \txxxx: xxx, xx xxx xxxx xx:xx:xx +xxxx\n> > \txx: xxxx xxxxxxxxxxx \n> > \txxxx: xxxx xxxxxxxxxxx \n> > \n> > and 30,000 of \n> > \n> > \t* xxxxx xxxxx (xxxxxx.xxxx xxx xxxxx (\\Xxxxxx) xxxxxx.xxxxxx {xxx}\n> > \n> > with a smattering of others. And this is a case where the internal git \n> > implementation does really badly. And nobody has really cared before, \n> > because nobody has ever had a case that mattered.\n> > \n> > There's a number of different 'diff' algorithms, and it looks like GNU \n> > diff has one that avoids the O(n^2) case for this case.\n> > \n> > I'm adding Davide as the original author of the diff library to the cc. \n> > I'm also adding Pierre, since he was talking about trying to implement\n> > another diff algorithm (although I'm not at all sure that the patience \n> > diff really would help this case at all).\n> \n> That should be an easy fix. Just need to limit the window by which \n> xdl_clean_mmatch() scans the current position.\n\nWith +/- 100 lines (200 lines window):\n\ndavide@alien:~$ time ./xdiff_test --diff 1 2 > /dev/null \n\nreal 0m1.534s\nuser 0m1.466s\nsys 0m0.040s\n\n\n\n- Davide\n"},{"id":"95176","messageId":"alpine.LFD.2.00.0811071540340.3468@nehalem.linux-foundation.org","threadId":"16213","inReplyTo":"alpine.DEB.1.10.0811071517280.8736@alien.or.mcafeemobile.com","subject":"Re: absurdly slow git-diff","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-11-07T23:42:24Z","receivedAt":"2008-11-07T23:42:24Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 7 Nov 2008, Davide Libenzi wrote:\n> \n> With +/- 100 lines (200 lines window):\n> \n> davide@alien:~$ time ./xdiff_test --diff 1 2 > /dev/null \n> \n> real 0m1.534s\n> user 0m1.466s\n> sys 0m0.040s\n\nI assume the patch is something like the appended?\n\n\t\tLinus\n\n---\n xdiff/xprepare.c | 4 ++--\n 1 files changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex e87ab57..4bebd76 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -318,7 +318,7 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {\n \t * Note that we always call this function with dis[i] > 1, so the\n \t * current line (i) is already a multimatch line.\n \t */\n-\tfor (r = 1, rdis0 = 0, rpdis0 = 1; (i - r) >= s; r++) {\n+\tfor (r = 1, rdis0 = 0, rpdis0 = 1; r < 100 && (i - r) >= s; r++) {\n \t\tif (!dis[i - r])\n \t\t\trdis0++;\n \t\telse if (dis[i - r] == 2)\n@@ -334,7 +334,7 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {\n \t */\n \tif (rdis0 == 0)\n \t\treturn 0;\n-\tfor (r = 1, rdis1 = 0, rpdis1 = 1; (i + r) <= e; r++) {\n+\tfor (r = 1, rdis1 = 0, rpdis1 = 1; r < 100 && (i + r) <= e; r++) {\n \t\tif (!dis[i + r])\n \t\t\trdis1++;\n \t\telse if (dis[i + r] == 2)\n"},{"id":"95178","messageId":"alpine.DEB.1.10.0811071547080.8736@alien.or.mcafeemobile.com","threadId":"16213","inReplyTo":"alpine.LFD.2.00.0811071540340.3468@nehalem.linux-foundation.org","subject":"Re: absurdly slow git-diff","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2008-11-07T23:48:34Z","receivedAt":"2008-11-07T23:48:34Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Fri, 7 Nov 2008, Linus Torvalds wrote:\n\n> \n> \n> On Fri, 7 Nov 2008, Davide Libenzi wrote:\n> > \n> > With +/- 100 lines (200 lines window):\n> > \n> > davide@alien:~$ time ./xdiff_test --diff 1 2 > /dev/null \n> > \n> > real 0m1.534s\n> > user 0m1.466s\n> > sys 0m0.040s\n> \n> I assume the patch is something like the appended?\n> \n> \t\tLinus\n> \n> ---\n> xdiff/xprepare.c | 4 ++--\n> 1 files changed, 2 insertions(+), 2 deletions(-)\n> \n> diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\n> index e87ab57..4bebd76 100644\n> --- a/xdiff/xprepare.c\n> +++ b/xdiff/xprepare.c\n> @@ -318,7 +318,7 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {\n> \t * Note that we always call this function with dis[i] > 1, so the\n> \t * current line (i) is already a multimatch line.\n> \t */\n> -\tfor (r = 1, rdis0 = 0, rpdis0 = 1; (i - r) >= s; r++) {\n> +\tfor (r = 1, rdis0 = 0, rpdis0 = 1; r < 100 && (i - r) >= s; r++) {\n> \t\tif (!dis[i - r])\n> \t\t\trdis0++;\n> \t\telse if (dis[i - r] == 2)\n> @@ -334,7 +334,7 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {\n> \t */\n> \tif (rdis0 == 0)\n> \t\treturn 0;\n> -\tfor (r = 1, rdis1 = 0, rpdis1 = 1; (i + r) <= e; r++) {\n> +\tfor (r = 1, rdis1 = 0, rpdis1 = 1; r < 100 && (i + r) <= e; r++) {\n> \t\tif (!dis[i + r])\n> \t\t\trdis1++;\n> \t\telse if (dis[i + r] == 2)\n> \n\nYeah, similar. Mine is below. There's one less branch in the for loops.\n\n\n\n- Davide\n\n\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex deba25a..3ebd87c 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -23,10 +23,9 @@\n #include \"xinclude.h\"\n \n \n-\n #define XDL_KPDIS_RUN 4\n #define XDL_MAX_EQLIMIT 1024\n-\n+#define XDL_SIMSCAN_WINDOWN 100\n \n \n typedef struct s_xdlclass {\n@@ -246,6 +245,18 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {\n \tlong r, rdis0, rpdis0, rdis1, rpdis1;\n \n \t/*\n+\t * Limits the window the is examined during the similar-lines\n+\t * scan. The loops below stops when dis[i - r] == 1 (line that\n+\t * has no match), but there are corner cases where the loop\n+\t * proceed all the way to the extremities by causing huge\n+\t * performance penalties in case of big files.\n+\t */\n+\tif (i - s > XDL_SIMSCAN_WINDOWN)\n+\t\ts = i - XDL_SIMSCAN_WINDOWN;\n+\tif (e - i > XDL_SIMSCAN_WINDOWN)\n+\t\te = i + XDL_SIMSCAN_WINDOWN;\n+\n+\t/*\n \t * Scans the lines before 'i' to find a run of lines that either\n \t * have no match (dis[j] == 0) or have multiple matches (dis[j] > 1).\n \t * Note that we always call this function with dis[i] > 1, so the\n"},{"id":"95179","messageId":"alpine.LFD.2.00.0811071554590.3468@nehalem.linux-foundation.org","threadId":"16213","inReplyTo":"alpine.DEB.1.10.0811071547080.8736@alien.or.mcafeemobile.com","subject":"Re: absurdly slow git-diff","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-11-07T23:57:23Z","receivedAt":"2008-11-07T23:57:23Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 7 Nov 2008, Davide Libenzi wrote:\n> \n> Yeah, similar. Mine is below. There's one less branch in the for loops.\n\n..and has a comment and made the magic constant be named.\n\nJunio, the time difference is quite big for Abhijit's admittedly odd \ntest-case:\n\n - Before:\n\n\t[torvalds@nehalem slow-diff]$ time git diff 1 2 > out.old\n\t\n\treal\t2m19.912s\n\tuser\t2m19.885s\n\tsys\t0m0.024s\n\n - After:\n\n\t[torvalds@nehalem slow-diff]$ time ~/git/git diff 1 2 > out\n\n\treal\t0m0.841s\n\tuser\t0m0.816s\n\tsys\t0m0.024s\n\nwith no difference in output.\n\n\t\t\tLinus\n"},{"id":"95180","messageId":"20081108001426.GA19357@artemis.corp","threadId":"16213","inReplyTo":"alpine.LFD.2.00.0811071335010.3468@nehalem.linux-foundation.org","subject":"Re: absurdly slow git-diff","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2008-11-08T00:14:26Z","receivedAt":"2008-11-08T00:14:26Z","isPatch":false,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":"On Fri, Nov 07, 2008 at 09:37:29PM +0000, Linus Torvalds wrote:\n> \n> On Sat, 8 Nov 2008, Abhijit Menon-Sen wrote:\n> >\n> > If anyone's interested, the files are http://toroid.org/misc/1 and\n> > http://toroid.org/misc/2\n\n> I'm also adding Pierre, since he was talking about trying to implement\n> another diff algorithm (although I'm not at all sure that the patience \n> diff really would help this case at all).\n\nFWIW Patience diff wouldn't help at all here. Patience diff is just a\nmatter of preseeding your preferred diff algorithm with better (wrt\nhuman readability) candidate for the invariant lines. IOW it helps\ndividing the problem into smaller bits, but requires *unique lines* to\nstart with. If you haven't any, then basically, Patience diff does\nnothing and calls your usual diff algorithm on the whole files.\n\nIt does so in a pseudo linear complexity, hence should not make overall\ntime really worse, but will not help for the ending time usually either.\n\n-- \n·O· Pierre Habouzit\n··O madcoder@debian.org\nOOO http://www.madism.org\n"},{"id":"95189","messageId":"20081108045742.GA26716@toroid.org","threadId":"16213","inReplyTo":"alpine.LFD.2.00.0811071554590.3468@nehalem.linux-foundation.org","subject":"Re: absurdly slow git-diff","fromName":"Abhijit Menon-Sen","fromEmail":"ams@toroid.org","sentAt":"2008-11-08T04:57:42Z","receivedAt":"2008-11-08T04:57:42Z","isPatch":false,"sender":{"key":"ams@toroid.org","avatar":null},"body":"At 2008-11-07 15:57:23 -0800, torvalds@linux-foundation.org wrote:\n>\n> > Yeah, similar. Mine is below. There's one less branch in the for\n> > loops.\n> \n> ..and has a comment and made the magic constant be named.\n\nIt works fine for me (the time went from 5m17s to 1.8s).\n\n(By the way, my test case is certainly very odd, but it is a real file\nfrom my test suite, albeit with the content x'ed away; and the change\nwas to adjust the expected output for all the items. I wasn't looking\nfor bugs. :-)\n\nThanks for the explanation and the patch.\n\n-- ams\n"},{"id":"95194","messageId":"7v7i7eeqcz.fsf@gitster.siamese.dyndns.org","threadId":"16213","inReplyTo":"alpine.DEB.1.10.0811071547080.8736@alien.or.mcafeemobile.com","subject":"Re: absurdly slow git-diff","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-11-08T05:30:52Z","receivedAt":"2008-11-08T05:30:52Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Davide Libenzi writes:\n\n> Yeah, similar. Mine is below. There's one less branch in the for loops.\n\nThanks, will apply like this, but I am not sure if you meant windowN or\njust window...\n\n-- >8 --\nFrom: Davide Libenzi \nDate: Fri, 7 Nov 2008 21:24:33 -0800\nSubject: [PATCH] xdiff: give up scanning similar lines early\n\nIn a corner case of large files whose lines do not match uniquely, the\nloop to eliminate a line that matches multiple locations adjacent to a run\nof lines that do not uniquely match wasted too much cycles. Fix this by\ngiving up early after scanning 100 lines in both direction.\n---\n xdiff/xprepare.c | 15 +++++++++++++--\n 1 files changed, 13 insertions(+), 2 deletions(-)\n\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex e87ab57..6a70cdf 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -23,10 +23,9 @@\n #include \"xinclude.h\"\n \n \n-\n #define XDL_KPDIS_RUN 4\n #define XDL_MAX_EQLIMIT 1024\n-\n+#define XDL_SIMSCAN_WINDOWN 100\n \n \n typedef struct s_xdlclass {\n@@ -313,6 +312,18 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {\n \tlong r, rdis0, rpdis0, rdis1, rpdis1;\n \n \t/*\n+\t * Limits the window the is examined during the similar-lines\n+\t * scan. The loops below stops when dis[i - r] == 1 (line that\n+\t * has no match), but there are corner cases where the loop\n+\t * proceed all the way to the extremities by causing huge\n+\t * performance penalties in case of big files.\n+\t */\n+\tif (i - s > XDL_SIMSCAN_WINDOWN)\n+\t\ts = i - XDL_SIMSCAN_WINDOWN;\n+\tif (e - i > XDL_SIMSCAN_WINDOWN)\n+\t\te = i + XDL_SIMSCAN_WINDOWN;\n+\n+\t/*\n \t * Scans the lines before 'i' to find a run of lines that either\n \t * have no match (dis[j] == 0) or have multiple matches (dis[j] > 1).\n \t * Note that we always call this function with dis[i] > 1, so the\n-- \n1.6.0.3.674.gdf99f\n"},{"id":"95223","messageId":"Pine.LNX.4.64.0811080825080.10880@alien.or.mcafeemobile.com","threadId":"16213","inReplyTo":"7v7i7eeqcz.fsf@gitster.siamese.dyndns.org","subject":"Re: absurdly slow git-diff","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2008-11-08T16:27:34Z","receivedAt":"2008-11-08T16:27:34Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Fri, 7 Nov 2008, Junio C Hamano wrote:\n\n> Davide Libenzi writes:\n> \n> > Yeah, similar. Mine is below. There's one less branch in the for loops.\n> \n> Thanks, will apply like this, but I am not sure if you meant windowN or\n> just window...\n\nWhoops, just WINDOW.\n\n\n- Davide\n"},{"id":"95240","messageId":"7vr65maq2r.fsf@gitster.siamese.dyndns.org","threadId":"16213","inReplyTo":"alpine.LFD.2.00.0811071554590.3468@nehalem.linux-foundation.org","subject":"Re: absurdly slow git-diff","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-11-08T21:02:52Z","receivedAt":"2008-11-08T21:02:52Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> Junio, the time difference is quite big for Abhijit's admittedly odd \n> test-case:\n> ...\n> with no difference in output.\n\nIn git.git history, \"git-whatchanged -m -p -1\" gives different output for\nthe following commits, with and without the patch:\n\n c0e9892637e8144f10f2c408e276a470520f3601\n d6b3e3a33f71910526ccf80af6c13a230363cd89\n cecb98a9c3ed9271b0974bb6d7edbcf16e8a68f3\n ce18135d862b5dbc731d203b27c279529e58b54b\n 36b5b3c65948694d9a92de5a17f2b97c3cd84879\n 767e130915015f897fb87b939843b4882212574b\n 927a503cd07718ea0f700052043f383253904a56\n\nI've sampled a few (but not all) of them and they are different only\nbecause just how common lines are matched up, which is expected.\n"}]}