{"thread":{"id":"22730","subject":"Git has bad performance when traversing change-sets with large PPM files","startedAt":"2010-02-19T21:24:05Z","lastAt":"2010-02-21T07:46:06Z","messageCount":8,"participants":["Laine Walker-Avina","Thomas Rast","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"135111","messageId":"dfb660301002191324i7aeca7f5x990501bbca1475a9@mail.gmail.com","threadId":"22730","inReplyTo":null,"subject":"Git has bad performance when traversing change-sets with large PPM files","fromName":"Laine Walker-Avina","fromEmail":"lwalkera@pasco.com","sentAt":"2010-02-19T21:24:05Z","receivedAt":"2010-02-19T21:24:05Z","isPatch":false,"sender":{"key":"lwalkera@pasco.com","avatar":null},"body":"Steps to reproduce:\n\n1. Create a new git repo and add a 640x480 PPM image in ASCII format\n2. Add a .gitattributes file with the line \"*.ppm binary\"\n3. Commit the PPM file\n4. Change the PPM image's contents\n5. Add and commit\n6. Try to do a git rebase -i to the initial commit\n7. Watch the CPU peg at 100%\n\nI'm using git version 1.6.3.3\n\nPlease CC me, I'm not on the list.\n\nThanks,\n-- \nLaine Walker-Avina\nFirmware Engineer\nPASCO scientific\n"},{"id":"135130","messageId":"d1a75633daa062b25527dfb0675673480974c940.1266620423.git.trast@student.ethz.ch","threadId":"22730","inReplyTo":"dfb660301002191324i7aeca7f5x990501bbca1475a9@mail.gmail.com","subject":"[PATCH] rebase -i: avoid --cherry-pick when rebasing to a direct ancestor","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2010-02-19T23:30:52Z","receivedAt":"2010-02-19T23:30:52Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Ordinary 'rebase -i' reads the commits to rebase with (roughly)\n\n  git rev-list --left-right --cherry-pick $upstream...\n\nwhich gives it the feature of skipping commits that are already\npresent in $upstream.  However, in the common use-case of rewriting a\nfew commits up to an ancestor, as in 'git rebase -i HEAD~3', the\n--cherry-pick is useless since there are no commits to compare to.\n\nAdd a check if $upstream is a direct ancestor of HEAD, and leave away\nthe --cherry-pick if so.  Since the --cherry-pick is already in\n$MERGES_OPTION, we need to decide this before setting the latter.\n\nFor simplicity we skip --root mode.  In theory we could do the same\noptimization, but using --root --onto <ancestor> is probably even more\nrare than having performance issues with --cherry-pick.\n\nSigned-off-by: Thomas Rast <trast@student.ethz.ch>\n---\n\nThe --cherry-pick mechanism itself could get a similar optimization,\nbut I don't know that code.\n\n\n git-rebase--interactive.sh |    7 ++++++-\n 1 files changed, 6 insertions(+), 1 deletions(-)\n\ndiff --git a/git-rebase--interactive.sh b/git-rebase--interactive.sh\nindex 1fda620..10b0ed8 100755\n--- a/git-rebase--interactive.sh\n+++ b/git-rebase--interactive.sh\n@@ -870,7 +870,12 @@ first and then run 'git rebase --continue' again.\"\n \t\t\tMERGES_OPTION=\n \t\t\tfirst_after_upstream=\"$(git rev-list --reverse --first-parent $UPSTREAM..$HEAD | head -n 1)\"\n \t\telse\n-\t\t\tMERGES_OPTION=\"--no-merges --cherry-pick\"\n+\t\t\tif test -z \"$REBASE_ROOT\" &&\n+\t\t\t\ttest $(git merge-base $UPSTREAM $HEAD) = $UPSTREAM; then\n+\t\t\t\tMERGES_OPTION=\"--no-merges\"\n+\t\t\telse\n+\t\t\t\tMERGES_OPTION=\"--no-merges --cherry-pick\"\n+\t\t\tfi\n \t\tfi\n \n \t\tSHORTHEAD=$(git rev-parse --short $HEAD)\n-- \n1.7.0.139.gd1a75\n"},{"id":"135134","messageId":"201002200102.15777.trast@student.ethz.ch","threadId":"22730","inReplyTo":"d1a75633daa062b25527dfb0675673480974c940.1266620423.git.trast@student.ethz.ch","subject":"Re: [PATCH] rebase -i: avoid --cherry-pick when rebasing to a direct ancestor","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2010-02-20T00:02:15Z","receivedAt":"2010-02-20T00:02:15Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"On Saturday 20 February 2010 00:30:52 Thomas Rast wrote:\n> Ordinary 'rebase -i' reads the commits to rebase with (roughly)\n> \n>   git rev-list --left-right --cherry-pick $upstream...\n> \n> which gives it the feature of skipping commits that are already\n> present in $upstream.  However, in the common use-case of rewriting a\n> few commits up to an ancestor, as in 'git rebase -i HEAD~3', the\n> --cherry-pick is useless since there are no commits to compare to.\n[...]\n> The --cherry-pick mechanism itself could get a similar optimization,\n> but I don't know that code.\n\nOr maybe it's as simple as this?\n\ndiff --git i/revision.c w/revision.c\nindex 438cc87..29721ec 100644\n--- i/revision.c\n+++ w/revision.c\n@@ -547,6 +547,9 @@ static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)\n \t\t\tright_count++;\n \t}\n \n+\tif (!left_count || !right_count)\n+\t\treturn;\n+\n \tleft_first = left_count < right_count;\n \tinit_patch_ids(&ids);\n \tif (revs->diffopt.nr_paths) {\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"135146","messageId":"20100220072728.GA12168@coredump.intra.peff.net","threadId":"22730","inReplyTo":"201002200102.15777.trast@student.ethz.ch","subject":"Re: [PATCH] rebase -i: avoid --cherry-pick when rebasing to a direct ancestor","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-02-20T07:27:28Z","receivedAt":"2010-02-20T07:27:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Feb 20, 2010 at 01:02:15AM +0100, Thomas Rast wrote:\n\n> > the --cherry-pick is useless since there are no commits to compare to.\n> [...]\n> Or maybe it's as simple as this?\n> \n> diff --git i/revision.c w/revision.c\n> index 438cc87..29721ec 100644\n> --- i/revision.c\n> +++ w/revision.c\n> @@ -547,6 +547,9 @@ static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)\n>  \t\t\tright_count++;\n>  \t}\n>  \n> +\tif (!left_count || !right_count)\n> +\t\treturn;\n> +\n>  \tleft_first = left_count < right_count;\n>  \tinit_patch_ids(&ids);\n>  \tif (revs->diffopt.nr_paths) {\n\n>From my reading of the code, that is right, but this is the first time I\never looked at it, so who knows? :)\n\nAlso, I was curious whether we correctly respected gitattributes when\ncalculating patch ids (specifically, do we actually treat this thing as\nbinary). But it looks like patch-id's don't make any exceptions for\nbinary files, and they get fed to xdiff. I think this is not buggy (the\nxdiff consumer seems to get the diff content with a length, so we are\nnot treating the potentially binary data as a C-string anywhere that I\nsee). But it is probably the source of the slowness to xdiff that\ngigantic files.\n\nDoes it really make sense to treat binary files as anything other than a\nblob for generating patch id? That is, should we simply turn it into:\n\n  binary diff\n  $from_sha1\n  $to_sha1\n\nand hash that for the patch id?\n\n-Peff\n"},{"id":"135154","messageId":"a39e9a6e6f043121568de106f41f5b01eb38a200.1266665083.git.trast@student.ethz.ch","threadId":"22730","inReplyTo":"20100220072728.GA12168@coredump.intra.peff.net","subject":"[PATCH] cherry_pick_list: quit early if one side is empty","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2010-02-20T11:42:04Z","receivedAt":"2010-02-20T11:42:04Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"The --cherry-pick logic starts by counting the commits on each side,\nso that it can filter away commits on the bigger one.  However, so\nfar it missed an opportunity for optimization: it doesn't need to do\nany work if either side is empty.\n\nThis in particular helps the common use-case 'git rebase -i HEAD~$n':\nit internally uses --cherry-pick, but since HEAD~$n is a direct\nancestor the left side is always empty.\n\nSigned-off-by: Thomas Rast <trast@student.ethz.ch>\n---\n\nOn Saturday 20 February 2010 08:27:28 Jeff King wrote:\n> \n> From my reading of the code, that is right, but this is the first time I\n> ever looked at it, so who knows? :)\n\nJunio agreed too, so here's a real patch.  To keep the complexity of\ngit-rebase--interactive from exploding even further, you can drop the\nearlier one.\n\n> Does it really make sense to treat binary files as anything other than a\n> blob for generating patch id? That is, should we simply turn it into:\n> \n>   binary diff\n>   $from_sha1\n>   $to_sha1\n> \n> and hash that for the patch id?\n\nI tend to agree, but I can't seem to find out what flags to flip :-(\n\n\n revision.c |    3 +++\n 1 files changed, 3 insertions(+), 0 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 438cc87..29721ec 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -547,6 +547,9 @@ static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)\n \t\t\tright_count++;\n \t}\n \n+\tif (!left_count || !right_count)\n+\t\treturn;\n+\n \tleft_first = left_count < right_count;\n \tinit_patch_ids(&ids);\n \tif (revs->diffopt.nr_paths) {\n-- \n1.7.0.139.gd1a75.dirty\n"},{"id":"135156","messageId":"201002201438.29635.trast@student.ethz.ch","threadId":"22730","inReplyTo":"20100220072728.GA12168@coredump.intra.peff.net","subject":"Re: [PATCH] rebase -i: avoid --cherry-pick when rebasing to a direct ancestor","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2010-02-20T13:38:29Z","receivedAt":"2010-02-20T13:38:29Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"On Saturday 20 February 2010 08:27:28 Jeff King wrote:\n> But it is probably the source of the slowness to xdiff that\n> gigantic files.\n\nBTW, here's a weird data point:\n\n$ ls -l a b\n-rw-r--r-- 1 thomas users 3300765 2010-02-20 12:48 a\n-rw-r--r-- 1 thomas users 3253762 2010-02-20 12:48 b\n$ time diff -u a b | wc -l\n54530\n\nreal    0m0.644s\nuser    0m0.562s\nsys     0m0.044s\n$ time git diff --no-index a b >/dev/null\n\nreal    0m22.848s\nuser    0m21.956s\nsys     0m0.137s\n$ time git diff --no-index --patience a b >/dev/null\n\nreal    0m19.508s\nuser    0m18.673s\nsys     0m0.273s\n\n'a' and 'b' are two pnm's as per the OPs specification, I made 'a' a\ngradient and 'b' the same with two crosses drawn over it.  You can\nfind them at\n\n  http://thomasrast.ch/download/slow-diff-pnms.zip\n\nif you want to reproduce.\n\nSo what on earth does 'diff' do that makes it 35 times as fast?\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"135225","messageId":"20100221065009.GB2840@coredump.intra.peff.net","threadId":"22730","inReplyTo":"a39e9a6e6f043121568de106f41f5b01eb38a200.1266665083.git.trast@student.ethz.ch","subject":"Re: [PATCH] cherry_pick_list: quit early if one side is empty","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-02-21T06:50:10Z","receivedAt":"2010-02-21T06:50:10Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Feb 20, 2010 at 12:42:04PM +0100, Thomas Rast wrote:\n\n> > Does it really make sense to treat binary files as anything other than a\n> > blob for generating patch id? That is, should we simply turn it into:\n> > \n> >   binary diff\n> >   $from_sha1\n> >   $to_sha1\n> > \n> > and hash that for the patch id?\n> \n> I tend to agree, but I can't seem to find out what flags to flip :-(\n\nYou would need to call diff_filespec_is_binary when flushing the diff\nqueue, which handles both attributes and autodetection. Something like:\n\ndiff --git a/diff.c b/diff.c\nindex 989dbc5..97ce40a 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -3381,6 +3381,14 @@ static int diff_get_patch_id(struct diff_options *options, unsigned char *sha1)\n \n \t\tdiff_fill_sha1_info(p->one);\n \t\tdiff_fill_sha1_info(p->two);\n+\n+\t\tif (diff_filespec_is_binary(p->one) ||\n+\t\t    diff_filespec_is_binary(p->two)) {\n+\t\t\t/* TODO: write binary patch into buffer */\n+\t\t\tgit_SHA1_Update(&ctx, buffer, len);\n+\t\t\tcontinue;\n+\t\t}\n+\n \t\tif (fill_mmfile(&mf1, p->one) < 0 ||\n \t\t\t\tfill_mmfile(&mf2, p->two) < 0)\n \t\t\treturn error(\"unable to read files to diff\");\n\nHowever, thinking on it more, it is a bit more complicated than that.\nThe patch-id we generate for --cherry-pick is not purely internal. You\ncan also generate patch-id's by handing the patch text to git-patch-id,\nwhich strips out whitespace and line numbers.  Which means that whatever\nwe generate should probably match the binary patch format output by the\nregular diff.\n\nOn the other hand, what we do now for cherry-pick totally does not match\nwhat \"git log\" would output, and nobody has complained, so perhaps it is\nnot a big deal.\n\nAnd I guess they don't technically need to match. The --cherry-pick\nthing is internal (i.e., as long as you use the same format for both\nsides, you are fine). But I suspect there are other code paths that use\nthat patch-id code.\n\n-Peff\n"},{"id":"135229","messageId":"20100221074605.GD2840@coredump.intra.peff.net","threadId":"22730","inReplyTo":"201002201438.29635.trast@student.ethz.ch","subject":"Re: [PATCH] rebase -i: avoid --cherry-pick when rebasing to a direct ancestor","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-02-21T07:46:06Z","receivedAt":"2010-02-21T07:46:06Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Feb 20, 2010 at 02:38:29PM +0100, Thomas Rast wrote:\n\n> BTW, here's a weird data point:\n> \n> $ ls -l a b\n> -rw-r--r-- 1 thomas users 3300765 2010-02-20 12:48 a\n> -rw-r--r-- 1 thomas users 3253762 2010-02-20 12:48 b\n> $ time diff -u a b | wc -l\n> 54530\n> \n> real    0m0.644s\n> user    0m0.562s\n> sys     0m0.044s\n> $ time git diff --no-index a b >/dev/null\n> \n> real    0m22.848s\n> user    0m21.956s\n> sys     0m0.137s\n> $ time git diff --no-index --patience a b >/dev/null\n> \n> real    0m19.508s\n> user    0m18.673s\n> sys     0m0.273s\n\nI was able to reproduce here. According to 'perf', git spends 70% of its\ntime in xdl_split, which says:\n\n/*\n * See \"An O(ND) Difference Algorithm and its Variations\", by Eugene Myers.\n * Basically considers a \"box\" (off1, off2, lim1, lim2) and scan from both\n * the forward diagonal starting from (off1, off2) and the backward diagonal\n * starting from (lim1, lim2). If the K values on the same diagonal crosses\n * returns the furthest point of reach. We might end up having to expensive\n * cases using this algorithm is full, so a little bit of heuristic is needed\n * to cut the search and to return a suboptimal point.\n */\n\nGNU diff also seems to use the same basic Myers algorithm, but says:\n\n   The basic algorithm is described in:\n   \"An O(ND) Difference Algorithm and its Variations\", Eugene Myers,\n   Algorithmica Vol. 1 No. 2, 1986, pp. 251-266;\n   see especially section 4.2, which describes the variation used below.\n\n   The basic algorithm was independently discovered as described in:\n   \"Algorithms for Approximate String Matching\", E. Ukkonen,\n   Information and Control Vol. 64, 1985, pp. 100-118.\n\n   Unless the 'find_minimal' flag is set, this code uses the TOO_EXPENSIVE\n   heuristic, by Paul Eggert, to limit the cost to O(N**1.5 log N)\n   at the price of producing suboptimal output for large inputs with\n   many differences.\n\nSo it may be that TOO_EXPENSIVE heuristic. I don't know enough about the\ndiff code (git's or otherwise) to say how difficult it would be to adapt\nGNU diff's tricks.\n\n-Peff\n"}]}