{"thread":{"id":"20183","subject":"three-way diff performance problem","startedAt":"2009-07-21T18:10:01Z","lastAt":"2009-07-21T21:01:03Z","messageCount":8,"participants":["Linus Torvalds","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"118391","messageId":"alpine.LFD.2.01.0907211038120.19335@localhost.localdomain","threadId":"20183","inReplyTo":null,"subject":"three-way diff performance problem","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-07-21T18:10:01Z","receivedAt":"2009-07-21T18:10:01Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nOk, so I decided to abuse git today, because I actually had a problem \nwhere git could potentially solve it. Sadly, it's now 55 minutes later, \nand my single git command hasn't completed yet :(\n\nWhat did I do?\n\nWe have a really odd bug-report for the kernel where switching the \ncompiler from using '-fwrapv' to using '-fno-strict-overflow' causes a \nnon-working kernel.\n\nSo the exact same kernel sources work fine with either 'fwrapv' or, \nindeed, with neither option, but with '-fno-strict-overflow' it just hangs \nat boot. \n\nNow, the problem is that I can't actually see the issue, so I just have \nthree kernel binaries, two of which work, and one which does not. I can \ndisassemble them, and I did, and the end result are three files with \nroughly 1.14 million lines.\n\nThe diffs between them are in the 40- to 90-thousand line area, and it's \nreally hard to read diffs of assembly code and try to figure out what the \nproblem with the generated code is. Yeah, I'm pretty good at reading \nassembler, but I'm not _that_ good. Just scanning 40 thousand lines takes \na while, looking at it _closely_ is just incredibly hard and isn't going \nto ever really work out.\n\nBut there's a saving grace: I have two working kernels. And the \ndifferences are often silly things like different register allocation, and \nthey are _different_. Many functions end up being the same between one \nworking kernel and the failing one, while being different in another \nworking kernel.\n\nSo what I want is the differences that are different from _both_ working \nkernels, since being the same as _one_ of them means that it's not a bug.\n\nNow, being a git person, what does that say? Right: just check in the \nworking kernels as two branches under the same filename, then merge the \nbranches, and force the merge result to be the non-working kernel, and do \na three-way combined context diff! So I did exactly that.\n\nAn hour later, it's still thinking.\n\nSo I used our nice new 'perf' tool from the kernel on a run that I killed \nafter five minuets, and lookie here:\n\n\t#\n\t# (17566764 samples)\n\t#\n\t# Overhead Command Shared Object Symbol\n\t# ........ ................ ......................... ......\n\t#\n\t 96.26% git /home/torvalds/bin/git [.] consume_line\n\t...\n\nit says we're spending pretty much all our time in a single function.\n\nIn fact, on the instruction-level profile, it looks like it's all spent on \nfour instructions:\n\n 3.51 : 45aec0: 4c 85 72 10 test %r14,0x10(%rdx)\n 86.27 : 45aec4: 48 0f 45 ca cmovne %rdx,%rcx\n : if (sline->lost_head) {\n : struct lline *last_one = NULL;\n : /* We cannot squash it with earlier one */\n : for (lline = sline->lost_head;\n : lline;\n : lline = lline->next)\n 6.69 : 45aec8: 48 8b 12 mov (%rdx),%rdx\n :\n : /* Check to see if we can squash things */\n : if (sline->lost_head) {\n : struct lline *last_one = NULL;\n : /* We cannot squash it with earlier one */\n : for (lline = sline->lost_head;\n 3.51 : 45aecb: 48 85 d2 test %rdx,%rdx\n 0.01 : 45aece: 75 f0 jne 45aec0 \n\n(ok, five, I included the 0.01% of the branch instruction that finishes \nthe loop - the way Nehalem works, it will merge those test+jne \ninstructions into one macro-instruction internally, which is why the \nbranch that is obviously part of the loop doesn't get a lot of hits)\n\nJust FYI, those four instructions come from inlining 'append_lost()'. It's \ncompiled that first for-loop into some very good assembly language, but \nthe problem is that this all looks very much quadratic in number of \nlost_lines. The quality of the compiler thus sadly in no way helps make up \nfor a really really expensive algorithm.\n\nAny ideas?\n\nFor any git people who want to look at the horror that caused this, feel \nfree to download the (fairly small) git repository from\n\n\tgit://git.kernel.org/pub/scm/linux/kernel/git/torvalds/git-merge-test.git\n\nand try to do a\n\n\tgit show --color fno-strict-overflow\n\njust for fun. Do \"gitk --all\" to see the simple nature of the repository, \nbut if you do, you'll need to kill the \"git diff-tree -r -p --textconv ..\" \nprocess that gitk will start (and which will take forever).\n\nThe code in question is all Junio's, and is over three years old. So it's \nobviously been working fine. And the load is obviously not really \nappropriate, but at the same time I think it's an interesting thing to \ntry. An it doesn't seem to be about memory use - It's now been running for \n85 minutes (ok, this email took long to write, and I uploaded the thing \netc in the meantime etc), and it's holding steady at roughly 175MB RSS.\n\n\t\t\tLinus\n"},{"id":"118392","messageId":"alpine.LFD.2.01.0907211113260.19335@localhost.localdomain","threadId":"20183","inReplyTo":"alpine.LFD.2.01.0907211038120.19335@localhost.localdomain","subject":"Re: three-way diff performance problem","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-07-21T18:16:32Z","receivedAt":"2009-07-21T18:16:32Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 21 Jul 2009, Linus Torvalds wrote:\n> \n> Now, being a git person, what does that say? Right: just check in the \n> working kernels as two branches under the same filename, then merge the \n> branches, and force the merge result to be the non-working kernel, and do \n> a three-way combined context diff! So I did exactly that.\n\nBtw, I did it wrong, which is why it takes too long. Instead of making the \nresult be the right dump-file, I made it be a bad one, so the diffs are \nmuch bigger than they should be. Which then makes the combined-merge diff \ntake longer than necessary (with the O(n^2) thing).\n\nDoing it _correctly_ actually made the three-way diff only take 45 \nseconds, but sadly still left me with 22 thousand lines.\n\n\t\t\tLinus\n"},{"id":"118394","messageId":"7v7hy1g7vg.fsf@alter.siamese.dyndns.org","threadId":"20183","inReplyTo":"alpine.LFD.2.01.0907211038120.19335@localhost.localdomain","subject":"Re: three-way diff performance problem","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-07-21T19:21:07Z","receivedAt":"2009-07-21T19:21:07Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> In fact, on the instruction-level profile, it looks like it's all spent on \n> four instructions:\n>\n> 3.51 : 45aec0: 4c 85 72 10 test %r14,0x10(%rdx)\n> 86.27 : 45aec4: 48 0f 45 ca cmovne %rdx,%rcx\n> : if (sline->lost_head) {\n> : struct lline *last_one = NULL;\n> : /* We cannot squash it with earlier one */\n> : for (lline = sline->lost_head;\n> : lline;\n> : lline = lline->next)\n> 6.69 : 45aec8: 48 8b 12 mov (%rdx),%rdx\n> :\n> : /* Check to see if we can squash things */\n> : if (sline->lost_head) {\n> : struct lline *last_one = NULL;\n> : /* We cannot squash it with earlier one */\n> : for (lline = sline->lost_head;\n> 3.51 : 45aecb: 48 85 d2 test %rdx,%rdx\n> 0.01 : 45aece: 75 f0 jne 45aec0 \n>\n> (ok, five, I included the 0.01% of the branch instruction that finishes \n> the loop - the way Nehalem works, it will merge those test+jne \n> instructions into one macro-instruction internally, which is why the \n> branch that is obviously part of the loop doesn't get a lot of hits)\n>\n> Just FYI, those four instructions come from inlining 'append_lost()'. It's \n> compiled that first for-loop into some very good assembly language, but \n> the problem is that this all looks very much quadratic in number of \n> lost_lines. The quality of the compiler thus sadly in no way helps make up \n> for a really really expensive algorithm.\n>\n> Any ideas?\n\nWhat's that cmovne?\n\nThe function append_lost() is the meat of combining. When you have seen\na hunk like this:\n\n @@ -l,k +m,n @@\n -lost line\n -another lost line\n common line\n +added line\n\nWe queue the lost lines in front of a surviving line (that is sline that\npoints at \"common line\"). \"lost line\" and \"another lost line\" are stored\nin lline (lost line) and they are queued to sline->lost_head.\n\nWhen another diff that corresponds to this section looks like this:\n\n @@ -l,k +m1,n1 @@\n -lost line\n common line\n +added line\n\nthe function looks at \"lost line\", tries to find the identical one in the\nlist of llines. We find one, and mark the fact that the lline element is\nshared among the two parents.\n\nThat allows the output routine to say\n\n @@@ -l,k +m,n +m1,n1 @@@\n --lost line\n - another lost line\n common line\n ++added line\n\nIf that cmovne that eats 86.27% of the run time has something to do with\nthe memcmp() that is repeatedly done, and if the length of lost_head list\nis very large, I think a possible optimization is to add a line hash value\nin struct lline.\n\nAfter feeding the first diff (forget the one with +m1,n1 example above),\nif the second diff looks like this:\n\n @@ -l,k +m2,n2 @@\n -another lost line\n -lost line\n common line\n +added line\n\nwe match \"-another lost line\" with the second element in lost_head list,\nand when processing the next line \"-lost line\", we try to avoid matching\nit with the first one in the list, by stupidly scanning from the front of\nthe list. I think we should add a member to struct sline to remember the\nlast element in lost_head list for the current parent to skip that scan.\nPerhaps that scan is the one that is costing, not memcmp()?\n"},{"id":"118395","messageId":"alpine.LFD.2.01.0907211225220.19335@localhost.localdomain","threadId":"20183","inReplyTo":"7v7hy1g7vg.fsf@alter.siamese.dyndns.org","subject":"Re: three-way diff performance problem","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-07-21T19:31:50Z","receivedAt":"2009-07-21T19:31:50Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 21 Jul 2009, Junio C Hamano wrote:\n> \n> What's that cmovne?\n\nIt's \"conditional move if not equal\".\n\nSo the source code is\n\n /* We cannot squash it with earlier one */\n for (lline = sline->lost_head;\n lline;\n lline = lline->next)\n if (lline->parent_map & this_mask)\n last_one = lline;\n\nadn the compiler has generated this:\n\n\tloop:\n\t\ttest %r14,0x10(%rdx)\n\t\tcmovne %rdx,%rcx\n\t\tmov (%rdx),%rdx\n\t\ttest %rdx,%rdx\n\t\tjne loop\n\nfrom it. In the above, '%r14' contains this_mask, and '%rcx' contains \n'last_line' and '%rdx' contains 'lline'.\n\nSo:\n\n - test %r14,0x10(%rdx)\n\n test \"this_mask & lline->parent_map\"\n\n - cmovne %rdx,%rcx\n\n \"if the test above was non-zero, then last_one = lline\"\n\n - mov (%rdx),%rdx\n\n \"lline = lline->next\"\n\n - test %rdx,%rdx\n\n \"is lline NULL\"\n\n - jne loop\n\n no, continue.\n\n> The function append_lost() is the meat of combining. When you have seen\n> a hunk like this:\n> \n> @@ -l,k +m,n @@\n> -lost line\n> -another lost line\n> common line\n> +added line\n> \n> We queue the lost lines in front of a surviving line (that is sline that\n> points at \"common line\"). \"lost line\" and \"another lost line\" are stored\n> in lline (lost line) and they are queued to sline->lost_head.\n\nRight. And \"sline->lost_head\" is going to have over a _million_ entries.\n\nSo each time you add one, we'll traverse that loop a million times. For \neach new entry. End result: that loop gets executed on the order of a \nmillion million times. It doesn't help that the compiler made it be very \nefficient code ;(\n\n\t\t\tLinus\n"},{"id":"118398","messageId":"7vd47tes2y.fsf@alter.siamese.dyndns.org","threadId":"20183","inReplyTo":"7v7hy1g7vg.fsf@alter.siamese.dyndns.org","subject":"Re: three-way diff performance problem","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-07-21T19:47:33Z","receivedAt":"2009-07-21T19:47:33Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Linus Torvalds writes:\n>\n>> In fact, on the instruction-level profile, it looks like it's all spent on \n>> four instructions:\n>>\n>> 3.51 : 45aec0: 4c 85 72 10 test %r14,0x10(%rdx)\n>> 86.27 : 45aec4: 48 0f 45 ca cmovne %rdx,%rcx\n>> : if (sline->lost_head) {\n>> : struct lline *last_one = NULL;\n>> : /* We cannot squash it with earlier one */\n>> : for (lline = sline->lost_head;\n>> : lline;\n>> : lline = lline->next)\n>> 6.69 : 45aec8: 48 8b 12 mov (%rdx),%rdx\n>> :\n>> : /* Check to see if we can squash things */\n>> : if (sline->lost_head) {\n>> : struct lline *last_one = NULL;\n>> : /* We cannot squash it with earlier one */\n>> : for (lline = sline->lost_head;\n>> 3.51 : 45aecb: 48 85 d2 test %rdx,%rdx\n>> 0.01 : 45aece: 75 f0 jne 45aec0 \n>> ...\n> After feeding the first diff (forget the one with +m1,n1 example above),\n> if the second diff looks like this:\n>\n> @@ -l,k +m2,n2 @@\n> -another lost line\n> -lost line\n> common line\n> +added line\n>\n> we match \"-another lost line\" with the second element in lost_head list,\n> and when processing the next line \"-lost line\", we try to avoid matching\n> it with the first one in the list, by stupidly scanning from the front of\n> the list. I think we should add a member to struct sline to remember the\n> last element in lost_head list for the current parent to skip that scan.\n> Perhaps that scan is the one that is costing, not memcmp()?\n\nHere is a patch to do that. I haven't tested it yet though.\n\n combine-diff.c | 16 ++++++++--------\n 1 files changed, 8 insertions(+), 8 deletions(-)\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex bbf74fc..8194104 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -80,6 +80,7 @@ struct lline {\n /* Lines surviving in the merge result */\n struct sline {\n \tstruct lline *lost_head, **lost_tail;\n+\tstruct lline *lost_last_for_current_parent;\n \tchar *bol;\n \tint len;\n \t/* bit 0 up to (N-1) are on if the parent has this line (i.e.\n@@ -121,18 +122,15 @@ static void append_lost(struct sline *sline, int n, const char *line, int len)\n \n \t/* Check to see if we can squash things */\n \tif (sline->lost_head) {\n-\t\tstruct lline *last_one = NULL;\n-\t\t/* We cannot squash it with earlier one */\n-\t\tfor (lline = sline->lost_head;\n-\t\t lline;\n-\t\t lline = lline->next)\n-\t\t\tif (lline->parent_map & this_mask)\n-\t\t\t\tlast_one = lline;\n-\t\tlline = last_one ? last_one->next : sline->lost_head;\n+\t\tif (sline->lost_last_for_current_parent)\n+\t\t\tlline = sline->lost_last_for_current_parent;\n+\t\telse\n+\t\t\tlline = sline->lost_head;\n \t\twhile (lline) {\n \t\t\tif (lline->len == len &&\n \t\t\t !memcmp(lline->line, line, len)) {\n \t\t\t\tlline->parent_map |= this_mask;\n+\t\t\t\tsline->lost_last_for_current_parent = lline;\n \t\t\t\treturn;\n \t\t\t}\n \t\t\tlline = lline->next;\n@@ -147,6 +145,7 @@ static void append_lost(struct sline *sline, int n, const char *line, int len)\n \tlline->line[len] = 0;\n \t*sline->lost_tail = lline;\n \tsline->lost_tail = &lline->next;\n+\tsline->lost_last_for_current_parent = lline;\n }\n \n struct combine_diff_state {\n@@ -187,6 +186,7 @@ static void consume_line(void *state_, char *line, unsigned long len)\n \t\t\t\txcalloc(state->num_parent,\n \t\t\t\t\tsizeof(unsigned long));\n \t\tstate->sline[state->nb-1].p_lno[state->n] = state->ob;\n+\t\tstate->lost_bucket->lost_last_for_current_parent = NULL;\n \t\treturn;\n \t}\n \tif (!state->lost_bucket)\n"},{"id":"118420","messageId":"alpine.LFD.2.01.0907211324220.19335@localhost.localdomain","threadId":"20183","inReplyTo":"7vd47tes2y.fsf@alter.siamese.dyndns.org","subject":"Re: three-way diff performance problem","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-07-21T20:34:07Z","receivedAt":"2009-07-21T20:34:07Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 21 Jul 2009, Junio C Hamano wrote:\n> \n> Here is a patch to do that. I haven't tested it yet though.\n\nWell, it seems to work.\n\nIt turned the 85+ minute thing (which I eventually just killed) into \nsomething that took 1.4 _seconds_. Of course, I didn't check that the end \nresult was identical, since I never had the patience to wait for the \noriginal case.\n\nNow sadly, my fixed test (which took 45 seconds before) didn't much \nimprove (it doesn't have nearly as many removed lines, since I checked in \nthe _right_ file that is a much closer version to the parent files).\n\nBut what is intriguing is that it it gets different results. So I suspect \nthis one actually changed behavior some way:\n\n\t[torvalds@nehalem git-merge]$ time git show --color HEAD | wc\n\t 22671 63302 672234\n\t\n\treal\t0m44.024s\n\tuser\t0m43.879s\n\tsys\t0m0.148s\n\n\t[torvalds@nehalem git-merge]$ time ~/git/git show --color HEAD | wc\n\t 22596 63122 671076\n\t\n\treal\t0m43.553s\n\tuser\t0m43.435s\n\tsys\t0m0.128s\n\nand notice how the git version with your change gives different line \nnumbers.\n\nNow, this is a diff, and different answers are possibly _both_ valid, so \nwho knows. But I suspect that you _intended_ for the patch to be a \nsemantic no-op, and it doesn't seem to be.\n\n\t\t\tLinus\n"},{"id":"118424","messageId":"7vd47tbw7q.fsf@alter.siamese.dyndns.org","threadId":"20183","inReplyTo":"alpine.LFD.2.01.0907211324220.19335@localhost.localdomain","subject":"Re: three-way diff performance problem","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-07-21T20:46:33Z","receivedAt":"2009-07-21T20:46:33Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Tue, 21 Jul 2009, Junio C Hamano wrote:\n>> \n>> Here is a patch to do that. I haven't tested it yet though.\n>\n> Well, it seems to work.\n>\n> It turned the 85+ minute thing (which I eventually just killed) into \n> something that took 1.4 _seconds_. Of course, I didn't check that the end \n> result was identical, since I never had the patience to wait for the \n> original case.\n>\n> Now sadly, my fixed test (which took 45 seconds before) didn't much \n> improve (it doesn't have nearly as many removed lines, since I checked in \n> the _right_ file that is a much closer version to the parent files).\n>\n> But what is intriguing is that it it gets different results. So I suspect \n> this one actually changed behavior some way:\n>\n> \t[torvalds@nehalem git-merge]$ time git show --color HEAD | wc\n> \t 22671 63302 672234\n> \t\n> \treal\t0m44.024s\n> \tuser\t0m43.879s\n> \tsys\t0m0.148s\n>\n> \t[torvalds@nehalem git-merge]$ time ~/git/git show --color HEAD | wc\n> \t 22596 63122 671076\n> \t\n> \treal\t0m43.553s\n> \tuser\t0m43.435s\n> \tsys\t0m0.128s\n>\n> and notice how the git version with your change gives different line \n> numbers.\n>\n> Now, this is a diff, and different answers are possibly _both_ valid, so \n> who knows. But I suspect that you _intended_ for the patch to be a \n> semantic no-op, and it doesn't seem to be.\n\nI know why. The conversion was wrong. The original found the last_one\nthat was from the parent we are looking at, and when there is such, it\nstarted the scan from the one _after that_. Otherwise, if lost_head list\nhad an entry\n\n\t@@ -l,k +m,n @@\n -one\n two\n three\n\nand the diff with the parent we are currently looking at duplicates\nremoval:\n\n\t@@ -l,k +m1,n1 @@\n\t-one\n -one\n two\n three\n\nwe will end up losing the second removal, which would be what is happening\nwith the patch you tried.\n\nI actually was scratching my head wondering why it wasn't happening in the\noriginal code after I sent that faulty patch.\n\nHere is another attempt.\n\n combine-diff.c | 13 +++++--------\n 1 files changed, 5 insertions(+), 8 deletions(-)\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex bbf74fc..2438490 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -80,6 +80,7 @@ struct lline {\n /* Lines surviving in the merge result */\n struct sline {\n \tstruct lline *lost_head, **lost_tail;\n+\tstruct lline *next_lost;\n \tchar *bol;\n \tint len;\n \t/* bit 0 up to (N-1) are on if the parent has this line (i.e.\n@@ -121,18 +122,12 @@ static void append_lost(struct sline *sline, int n, const char *line, int len)\n \n \t/* Check to see if we can squash things */\n \tif (sline->lost_head) {\n-\t\tstruct lline *last_one = NULL;\n-\t\t/* We cannot squash it with earlier one */\n-\t\tfor (lline = sline->lost_head;\n-\t\t lline;\n-\t\t lline = lline->next)\n-\t\t\tif (lline->parent_map & this_mask)\n-\t\t\t\tlast_one = lline;\n-\t\tlline = last_one ? last_one->next : sline->lost_head;\n+\t\tlline = sline->next_lost;\n \t\twhile (lline) {\n \t\t\tif (lline->len == len &&\n \t\t\t !memcmp(lline->line, line, len)) {\n \t\t\t\tlline->parent_map |= this_mask;\n+\t\t\t\tsline->next_lost = lline->next;\n \t\t\t\treturn;\n \t\t\t}\n \t\t\tlline = lline->next;\n@@ -147,6 +142,7 @@ static void append_lost(struct sline *sline, int n, const char *line, int len)\n \tlline->line[len] = 0;\n \t*sline->lost_tail = lline;\n \tsline->lost_tail = &lline->next;\n+\tsline->next_lost = NULL;\n }\n \n struct combine_diff_state {\n@@ -187,6 +183,7 @@ static void consume_line(void *state_, char *line, unsigned long len)\n \t\t\t\txcalloc(state->num_parent,\n \t\t\t\t\tsizeof(unsigned long));\n \t\tstate->sline[state->nb-1].p_lno[state->n] = state->ob;\n+\t\tstate->lost_bucket->next_lost = state->lost_bucket->lost_head;\n \t\treturn;\n \t}\n \tif (!state->lost_bucket)\n"},{"id":"118429","messageId":"alpine.LFD.2.01.0907211349570.19335@localhost.localdomain","threadId":"20183","inReplyTo":"7vd47tbw7q.fsf@alter.siamese.dyndns.org","subject":"Re: three-way diff performance problem","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-07-21T21:01:03Z","receivedAt":"2009-07-21T21:01:03Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 21 Jul 2009, Junio C Hamano wrote:\n> \n> I know why. The conversion was wrong. The original found the last_one\n> that was from the parent we are looking at, and when there is such, it\n> started the scan from the one _after that_. Otherwise, if lost_head list\n> had an entry\n> \n> \t@@ -l,k +m,n @@\n> -one\n> two\n> three\n> \n> and the diff with the parent we are currently looking at duplicates\n> removal:\n> \n> \t@@ -l,k +m1,n1 @@\n> \t-one\n> -one\n> two\n> three\n> \n> we will end up losing the second removal, which would be what is happening\n> with the patch you tried.\n\nOk, that matches what I saw. Doing a 'diff' between the outputs showed \nmissing lines from the result with your first patch.\n\n> I actually was scratching my head wondering why it wasn't happening in the\n> original code after I sent that faulty patch.\n> \n> Here is another attempt.\n\nYup. This attempt now generates output that matches the original one (in \n44s), while at the same time still handling the previously very expensive \ncase quickly (1.4s).\n\nSo it looks good now from my testing - I'm not going to say anything else \nabout the patch, since I'm not all that familiar with the code itself.\n\nBtw, the 'perf report' on the fixed build now says\n\n 89.67% git /home/torvalds/git/git [.] xdl_prepare_env\n 6.42% git /home/torvalds/git/git [.] xdl_recs_cmp\n 0.92% git [kernel] [k] hpet_next_event\n 0.52% git /home/torvalds/git/git [.] xdl_prepare_ctx\n 0.44% git /lib64/libz.so.1.2.3 [.] inflate_fast\n 0.29% git /home/torvalds/git/git [.] xdl_hash_record\n 0.27% git /lib64/libc-2.10.1.so [.] __GI_memcmp\n 0.26% git /home/torvalds/git/git [.] show_patch_diff\n 0.14% git [kernel] [k] _spin_lock\n 0.09% git [kernel] [k] clear_page_c\n 0.09% git /lib64/libz.so.1.2.3 [.] adler32\n\nso now the expensive part is xdl_prepare_env. And that does actually make \nsense: it's the code that generates all the hash records for the lines to \nbe compared, so there doesn't seem to be anything hugely wrong with it. If \nthere are a lot of identical lines, I'd expect that to be fairly \nexpensive.\n\n\t\t\tLinus\n"}]}