{"thread":{"id":"20202","subject":"[PATCH 1/2] combine-diff.c: fix performance problem when folding common deleted lines","startedAt":"2009-07-22T21:48:27Z","lastAt":"2009-07-22T21:48:29Z","messageCount":3,"participants":["Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"118499","messageId":"1248299309-10579-1-git-send-email-gitster@pobox.com","threadId":"20202","inReplyTo":null,"subject":"[PATCH 0/2 for maint] \"show --cc\" fixes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-07-22T21:48:27Z","receivedAt":"2009-07-22T21:48:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The first one is the same \"performance\" patch from yesterday, only with\nbetter commit log message.\n\nThe second is a bugfix.  \"git show --cc\" displays merge result incorrectly\nwhen they touch the first line of the affected file (the bug is not about\nthe commit being wrong; it is about showing the commit incorrectly).  This\nwas found while writing a new test\n\nAmong the 3040 merges up to v1.6.4-rc1 in git.git history, only 643 of\nthem are interesting merges in \"show --cc\" sense, and there is only one\ncommit for which \"git show\" gives a wrong output due to this bug.\n\n  3ed02de Merge branch 'maint' of git://repo.or.cz/git-gui into maint\n\nThe reason git.git history has more \"cc-interesting\" merges (compared to a\nlot larger and more complex kernel history---see below) is an atrifact of\nthe use of subtree merges.  Most of these are actually not interesting at\nall, and the above commit that is shown incorrectly is not interesting\neither.  We probably should discourage the use of subtree merges and\nswitch to use submodules for gitk and git-gui ourselves, but we need to\nwait until we can be sure that everybody's installed git is submodule\ncapable.\n\nSimilarly, among the 9487 merges in the Linux kernel history (today's tip\nfrom Linus), only 920 of them are interesting.  There are a handful of\ncommits for which \"git show\" gives a wrong output due to this bug.\n\n  f541ae3 Merge branch 'linus' into perfcounters/core-v2\n  0ca0f16 Merge branches 'x86/apic', 'x86/asm', 'x86/cleanups', 'x86/debug',...\n  9b6a517 Merge branch 'juju' of git://git.kernel.org/pub/scm/linux/kernel/...\n  22a3e23 Merge git://git.kernel.org/pub/scm/linux/kernel/git/bunk/trivial\n\nTake Ingo's 0ca0f16 as an example.  The diff between its first parent and\nthe commit begins arch/x86/kernel/cpu/common.c like this:\n\n    --- a/arch/x86/kernel/cpu/common.c\n    +++ b/arch/x86/kernel/cpu/common.c\n    @@ -1,52 +1,52 @@\n    -#include <linux/init.h>\n    -#include <linux/kernel.h>\n    -#include <linux/sched.h>\n    -#include <linux/string.h>\n     #include <linux/bootmem.h>\n    +#include <linux/linkage.h>\n\nWhen shown in \"git show\", however, it begins like this (this is an 11-way\noctopus):\n\n    --- a/arch/x86/kernel/cpu/common.c\n    +++ b/arch/x86/kernel/cpu/common.c\n    @@@@@@@@@@@ -1,44 -1,44 -1,44 -1,44 -1,44 -1,44 -1,44 -1,4...\n\t      #include <linux/bootmem.h>\n    --- ------#include <linux/init.h>\n    --- ------#include <linux/kernel.h>\n    --- ------#include <linux/sched.h>\n\nwhich is clearly wrong.\n\nIn other words, the bug may be rare, but it is real.\n\nAn interesting tangent is this graph:\n\n    838 x x\n     26 x x x\n     18 x x x x\n      3 x x x x x\n      7 x x x x x x\n      5 x x x x x x x\n      6 x x x x x x x x\n      2 x x x x x x x x x\n      1 x x x x x x x x x x\n      3 x x x x x x x x x x x\n      3 x x x x x x x x x x x x\n      1 x x x x x x x x x x x x x\n      2 x x x x x x x x x x x x x x\n      1 x x x x x x x x x x x x x x x x x x\n      1 x x x x x x x x x x x x x x x x x x x x\n      1 x x x x x x x x x x x x x x x x x x x x x\n      1 x x x x x x x x x x x x x x x x x x x x x x x x\n      1 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x\n\nwhich is an output from this command in the kernel repository:\n\n    git log --pretty=short |\n    sed -ne '/^Merge: /{\n\t    s/^Merge: //\n\t    s/[0-9a-f][0-9a-f]*/x/g\n\t    p\n    }' |\n    sort |\n    uniq -c\n\nIngo stole the octopus gold star from Len Brown with that 30-way octopus.\n\nJunio C Hamano (2):\n  combine-diff.c: fix performance problem when folding common deleted\n    lines\n  diff --cc: a lost line at the beginning of the file is shown\n    incorrectly\n\n combine-diff.c           |   29 ++++++++--------\n t/t4038-diff-combined.sh |   84 ++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 98 insertions(+), 15 deletions(-)\n create mode 100755 t/t4038-diff-combined.sh\n"},{"id":"118497","messageId":"1248299309-10579-2-git-send-email-gitster@pobox.com","threadId":"20202","inReplyTo":"1248299309-10579-1-git-send-email-gitster@pobox.com","subject":"[PATCH 1/2] combine-diff.c: fix performance problem when folding common deleted lines","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-07-22T21:48:28Z","receivedAt":"2009-07-22T21:48:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"For a deleted line in a patch with the parent we are looking at, the\nappend_lost() function finds the same line among a run of lines that were\ndeleted from the same location by patches from parents we previously\nchecked.  This is so that patches with two parents\n\n    @@ -1,4 +1,3 @@    @@ -1,4 +1,3 @@\n     one                   one\n    -two                  -two\n     three                 three\n    -quatro               -fyra\n    +four                 +four\n\ncan be coalesced into this sequence, reusing one line that describes the\nremoval of \"two\" for both parents.\n\n   @@@ -1,4 -1,4 +1,3 @@@\n     one\n   --two\n     three\n   - quatro\n    -frya\n   ++four\n\nWhile reading the second patch (that removes \"two\" and then \"fyra\"), after\nfinding where removal of the \"two\" matches, we need to find existing\nremoval of \"fyra\" (if exists) in the removal list, but the match has to\nhappen after all the existing matches (in this case \"two\").  The code used\na naïve O(n^2) algorithm to compute this by scanning the whole removal\nlist over and over again.\n\nThis patch remembers where the next scan should be started in the existing\nremoval list to avoid this.\n\nNoticed by Linus Torvalds.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\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 60d0367..b82f46c 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-- \n1.6.4.rc1.10.g2a679\n"},{"id":"118498","messageId":"1248299309-10579-3-git-send-email-gitster@pobox.com","threadId":"20202","inReplyTo":"1248299309-10579-2-git-send-email-gitster@pobox.com","subject":"[PATCH 2/2] diff --cc: a lost line at the beginning of the file is shown incorrectly","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-07-22T21:48:29Z","receivedAt":"2009-07-22T21:48:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"When combine-diff inspected the diff from one parent to the merge result,\nit misinterpreted a header in the form @@ -l,k +0,0 @@.\n\nThis hunk header means that K lines were removed from the beginning of the\nfile, so the lost lines must be queued to the sline that represents the\nfirst line of the merge result, but we incremented our pointer incorrectly\nand ended up queuing it to the second line, which in turn made the lossage\nappear _after_ the first line.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n combine-diff.c           |   16 +++++----\n t/t4038-diff-combined.sh |   84 ++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 93 insertions(+), 7 deletions(-)\n create mode 100755 t/t4038-diff-combined.sh\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex b82f46c..38f4e2c 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -164,20 +164,22 @@ static void consume_line(void *state_, char *line, unsigned long len)\n \t\t\t\t      &state->nb, &state->nn))\n \t\t\treturn;\n \t\tstate->lno = state->nb;\n-\t\tif (!state->nb)\n-\t\t\t/* @@ -1,2 +0,0 @@ to remove the\n-\t\t\t * first two lines...\n-\t\t\t */\n-\t\t\tstate->nb = 1;\n-\t\tif (state->nn == 0)\n+\t\tif (state->nn == 0) {\n \t\t\t/* @@ -X,Y +N,0 @@ removed Y lines\n \t\t\t * that would have come *after* line N\n \t\t\t * in the result.  Our lost buckets hang\n \t\t\t * to the line after the removed lines,\n+\t\t\t *\n+\t\t\t * Note that this is correct even when N == 0,\n+\t\t\t * in which case the hunk removes the first\n+\t\t\t * line in the file.\n \t\t\t */\n \t\t\tstate->lost_bucket = &state->sline[state->nb];\n-\t\telse\n+\t\t\tif (!state->nb)\n+\t\t\t\tstate->nb = 1;\n+\t\t} else {\n \t\t\tstate->lost_bucket = &state->sline[state->nb-1];\n+\t\t}\n \t\tif (!state->sline[state->nb-1].p_lno)\n \t\t\tstate->sline[state->nb-1].p_lno =\n \t\t\t\txcalloc(state->num_parent,\ndiff --git a/t/t4038-diff-combined.sh b/t/t4038-diff-combined.sh\nnew file mode 100755\nindex 0000000..2cf7e01\n--- /dev/null\n+++ b/t/t4038-diff-combined.sh\n@@ -0,0 +1,84 @@\n+#!/bin/sh\n+\n+test_description='combined diff'\n+\n+. ./test-lib.sh\n+\n+setup_helper () {\n+\tone=$1 branch=$2 side=$3 &&\n+\n+\tgit branch $side $branch &&\n+\tfor l in $one two three fyra\n+\tdo\n+\t\techo $l\n+\tdone >file &&\n+\tgit add file &&\n+\ttest_tick &&\n+\tgit commit -m $branch &&\n+\tgit checkout $side &&\n+\tfor l in $one two three quatro\n+\tdo\n+\t\techo $l\n+\tdone >file &&\n+\tgit add file &&\n+\ttest_tick &&\n+\tgit commit -m $side &&\n+\ttest_must_fail git merge $branch &&\n+\tfor l in $one three four\n+\tdo\n+\t\techo $l\n+\tdone >file &&\n+\tgit add file &&\n+\ttest_tick &&\n+\tgit commit -m \"merge $branch into $side\"\n+}\n+\n+verify_helper () {\n+\tit=$1 &&\n+\n+\t# Ignore lines that were removed only from the other parent\n+\tsed -e '\n+\t\t1,/^@@@/d\n+\t\t/^ -/d\n+\t\ts/^\\(.\\)./\\1/\n+\t' \"$it\" >\"$it.actual.1\" &&\n+\tsed -e '\n+\t\t1,/^@@@/d\n+\t\t/^- /d\n+\t\ts/^.\\(.\\)/\\1/\n+\t' \"$it\" >\"$it.actual.2\" &&\n+\n+\tgit diff \"$it^\" \"$it\" -- | sed -e '1,/^@@/d' >\"$it.expect.1\" &&\n+\ttest_cmp \"$it.expect.1\" \"$it.actual.1\" &&\n+\n+\tgit diff \"$it^2\" \"$it\" -- | sed -e '1,/^@@/d' >\"$it.expect.2\" &&\n+\ttest_cmp \"$it.expect.2\" \"$it.actual.2\"\n+}\n+\n+test_expect_success setup '\n+\t>file &&\n+\tgit add file &&\n+\ttest_tick &&\n+\tgit commit -m initial &&\n+\n+\tgit branch withone &&\n+\tgit branch sansone &&\n+\n+\tgit checkout withone &&\n+\tsetup_helper one withone sidewithone &&\n+\n+\tgit checkout sansone &&\n+\tsetup_helper \"\" sansone sidesansone\n+'\n+\n+test_expect_success 'check combined output (1)' '\n+\tgit show sidewithone -- >sidewithone &&\n+\tverify_helper sidewithone\n+'\n+\n+test_expect_failure 'check combined output (2)' '\n+\tgit show sidesansone -- >sidesansone &&\n+\tverify_helper sidesansone\n+'\n+\n+test_done\n-- \n1.6.4.rc1.10.g2a679\n"}]}