{"thread":{"id":"24727","subject":"[PATCH] hash binary sha1 into patch id","startedAt":"2010-08-13T09:40:27Z","lastAt":"2010-10-14T07:19:21Z","messageCount":13,"participants":["Clemens Buchacher","Jonathan Nieder","Marat Radchenko"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"147996","messageId":"20100813094027.GA20906@localhost","threadId":"24727","inReplyTo":null,"subject":"[PATCH] hash binary sha1 into patch id","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2010-08-13T09:40:27Z","receivedAt":"2010-08-13T09:40:27Z","isPatch":true,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"Since commit 2f82f760 (Take binary diffs into account for \"git rebase\"), binary\nfiles are included in patch ID computation. Binary files are diffed using the\ntext diff algorithm, however, which has a huge impact on performance. The\nfollowing tests performance for a 50000 line file marked as binary in\n.gitattributes.\n\n$ git format-patch --stdout --full-index --ignore-if-in-upstream master\n\nreal\t0m0.367s\nuser\t0m0.354s\nsys\t0m0.010s\n\nInstead of hashing the diff of binary files, use the post-image sha1, which is\njust as unique. As a result, performance is much improved.\n\n$ git format-patch --stdout --full-index --ignore-if-in-upstream master\n\nreal\t0m0.016s\nuser\t0m0.015s\nsys\t0m0.001s\n\nSigned-off-by: Clemens Buchacher <drizzd@aon.at>\n---\n\nThis may be related to the rebase performance issue discussed in\nthe following thread.\n \n http://mid.gmane.org/loom.20100713T082913-327@post.gmane.org\n\nI am attaching the script which I used to test performance.\n\n diff.c |    6 ++++++\n 1 files changed, 6 insertions(+), 0 deletions(-)\n\ndiff --git a/diff.c b/diff.c\nindex 17873f3..20fc6db 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -3758,6 +3758,12 @@ static int diff_get_patch_id(struct diff_options *options, unsigned char *sha1)\n \t\t\t\t\tlen2, p->two->path);\n \t\tgit_SHA1_Update(&ctx, buffer, len1);\n \n+\t\tif (diff_filespec_is_binary(p->two)) {\n+\t\t\tlen1 = sprintf(buffer, \"%s\", sha1_to_hex(p->two->sha1));\n+\t\t\tgit_SHA1_Update(&ctx, buffer, len1);\n+\t\t\tcontinue;\n+\t\t}\n+\n \t\txpp.flags = 0;\n \t\txecfg.ctxlen = 3;\n \t\txecfg.flags = XDL_EMIT_FUNCNAMES;\n-- \n1.7.2.1.1.g202c\n\n"},{"id":"148017","messageId":"20100813200031.GD2003@burratino","threadId":"24727","inReplyTo":"20100813094027.GA20906@localhost","subject":"Re: [PATCH] hash binary sha1 into patch id","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-08-13T20:00:31Z","receivedAt":"2010-08-13T20:00:31Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Clemens Buchacher wrote:\n\n> Since commit 2f82f760 (Take binary diffs into account for \"git rebase\"), binary\n> files are included in patch ID computation. Binary files are diffed using the\n> text diff algorithm, however\n[...]\n> Instead of hashing the diff of binary files, use the post-image sha1, which is\n> just as unique. As a result, performance is much improved.\n\nMaybe it should use both the pre- and post-image?\n\n> diff --git a/diff.c b/diff.c\n> index 17873f3..20fc6db 100644\n> --- a/diff.c\n> +++ b/diff.c\n> @@ -3758,6 +3758,12 @@ static int diff_get_patch_id(struct diff_options *options, unsigned char *sha1)\n>  \t\t\t\t\tlen2, p->two->path);\n>  \t\tgit_SHA1_Update(&ctx, buffer, len1);\n>  \n> +\t\tif (diff_filespec_is_binary(p->two)) {\n> +\t\t\tlen1 = sprintf(buffer, \"%s\", sha1_to_hex(p->two->sha1));\n> +\t\t\tgit_SHA1_Update(&ctx, buffer, len1);\n\n\ni.e., maybe also\n\n\t\t\tgit_SHA1_Update(&ctx, sha1_to_hex(p->one->sha1), 40);\n\nLuckily this is after the filenames and so on have been incorporated,\nso there’s no need to add that specially.\n"},{"id":"148035","messageId":"20100813212331.GA24127@localhost","threadId":"24727","inReplyTo":"20100813200031.GD2003@burratino","subject":"Re: [PATCH] hash binary sha1 into patch id","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2010-08-13T21:23:31Z","receivedAt":"2010-08-13T21:23:31Z","isPatch":true,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"Hi Jonathan,\n\nOn Fri, Aug 13, 2010 at 03:00:31PM -0500, Jonathan Nieder wrote:\n> Clemens Buchacher wrote:\n> \n> > Since commit 2f82f760 (Take binary diffs into account for \"git rebase\"), binary\n> > files are included in patch ID computation. Binary files are diffed using the\n> > text diff algorithm, however\n> [...]\n> > Instead of hashing the diff of binary files, use the post-image sha1, which is\n> > just as unique. As a result, performance is much improved.\n> \n> Maybe it should use both the pre- and post-image?\n\nThat would make the patch ID more correct in that it will identify\na particular change. But ultimately, we want to know whether or not\na change has been applied already. If the contents of a binary file\nare the same in both commits, this is almost certainly true,\nregardless of whether or not the pre-images match.\n\nSo I think we get better behavior if we ignore the pre-image.\nAlthough the difference is probably minuscule.\n\n> \n> > diff --git a/diff.c b/diff.c\n> > index 17873f3..20fc6db 100644\n> > --- a/diff.c\n> > +++ b/diff.c\n> > @@ -3758,6 +3758,12 @@ static int diff_get_patch_id(struct diff_options *options, unsigned char *sha1)\n> >  \t\t\t\t\tlen2, p->two->path);\n> >  \t\tgit_SHA1_Update(&ctx, buffer, len1);\n> >  \n> > +\t\tif (diff_filespec_is_binary(p->two)) {\n> > +\t\t\tlen1 = sprintf(buffer, \"%s\", sha1_to_hex(p->two->sha1));\n> > +\t\t\tgit_SHA1_Update(&ctx, buffer, len1);\n> \n> \n> i.e., maybe also\n> \n> \t\t\tgit_SHA1_Update(&ctx, sha1_to_hex(p->one->sha1), 40);\n\nThanks.\n"},{"id":"148041","messageId":"20100813213726.GB2516@burratino","threadId":"24727","inReplyTo":"20100813212331.GA24127@localhost","subject":"Re: [PATCH] hash binary sha1 into patch id","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-08-13T21:37:26Z","receivedAt":"2010-08-13T21:37:26Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Clemens Buchacher wrote:\n> On Fri, Aug 13, 2010 at 03:00:31PM -0500, Jonathan Nieder wrote:\n\n>> Maybe it should use both the pre- and post-image?\n[...]\n> So I think we get better behavior if we ignore the pre-image.\n> Although the difference is probably minuscule.\n\nAs long as you’ve thought it over, I’m happy with it.  As you say, the\npostimage matching without the preimage matching should be a rare\nevent.\n\nFWIW what I was imagining was some structured binary format:\n\nWith A some long string, patch 1:\n\n A  --> AAA\n\nPatch 2:\n\n AA --> AAA\n\nIdeally one would want an attempt to apply patch 2 to result in a\nconflict.  Probably that is far-fetched.\n"},{"id":"148044","messageId":"20100813215801.GA24534@localhost","threadId":"24727","inReplyTo":"20100813213726.GB2516@burratino","subject":"Re: [PATCH] hash binary sha1 into patch id","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2010-08-13T21:58:01Z","receivedAt":"2010-08-13T21:58:01Z","isPatch":true,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"On Fri, Aug 13, 2010 at 04:37:26PM -0500, Jonathan Nieder wrote:\n> \n> FWIW what I was imagining was some structured binary format:\n> \n> With A some long string, patch 1:\n> \n>  A  --> AAA\n> \n> Patch 2:\n> \n>  AA --> AAA\n> \n> Ideally one would want an attempt to apply patch 2 to result in a\n> conflict.  Probably that is far-fetched.\n\nActually, rebase will try to merge the respective branches and it\nwill typically succeed, because the post-images are the same. It\nwill fail due to conflict only if yet another patch has been\napplied upstream on top of patch 1.\n\nBut that is also how textual changes behave. So for the sake of\nconsistency, it makes sense to require the pre-images to be the\nsame. I will resend an appropriate patch tomorrow.\n"},{"id":"148126","messageId":"20100815072043.GA368@localhost","threadId":"24727","inReplyTo":"20100813215801.GA24534@localhost","subject":"[PATCH v2] hash binary sha1 into patch id","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2010-08-15T07:20:43Z","receivedAt":"2010-08-15T07:20:43Z","isPatch":true,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"Since commit 2f82f760 (Take binary diffs into\naccount for \"git rebase\"), binary files are\nincluded in patch ID computation. Binary files are\ndiffed using the text diff algorithm, however,\nwhich has a huge impact on performance. The\nfollowing tests performance for a 50000 line file\nmarked as binary in .gitattributes.\n\n$ git format-patch --stdout --ignore-if-in-upstream master\n\nreal    0m0.367s\nuser    0m0.354s\nsys     0m0.010s\n\nInstead of diffing the binary files, hash the pre-\nand post-image sha1, which is just as unique. As a\nresult, performance is much improved.\n\n$ git format-patch --stdout --ignore-if-in-upstream master\n\nreal    0m0.016s\nuser    0m0.015s\nsys     0m0.001s\n\nSigned-off-by: Clemens Buchacher <drizzd@aon.at>\n---\n\nI am again attaching the corresponding test script. Since it mostly\ntests performance, I am not sure how to incorporate it into the\nmain test suite.\n\n diff.c |    7 +++++++\n 1 files changed, 7 insertions(+), 0 deletions(-)\n\ndiff --git a/diff.c b/diff.c\nindex 17873f3..f4a23ab 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -3758,6 +3758,13 @@ static int diff_get_patch_id(struct diff_options *options, unsigned char *sha1)\n \t\t\t\t\tlen2, p->two->path);\n \t\tgit_SHA1_Update(&ctx, buffer, len1);\n \n+\t\tif (diff_filespec_is_binary(p->one) ||\n+\t\t    diff_filespec_is_binary(p->two)) {\n+\t\t\tgit_SHA1_Update(&ctx, sha1_to_hex(p->one->sha1), 40);\n+\t\t\tgit_SHA1_Update(&ctx, sha1_to_hex(p->two->sha1), 40);\n+\t\t\tcontinue;\n+\t\t}\n+\n \t\txpp.flags = 0;\n \t\txecfg.ctxlen = 3;\n \t\txecfg.flags = XDL_EMIT_FUNCNAMES;\n-- \n1.7.2.1.1.g202c\n\n"},{"id":"148140","messageId":"20100815075631.GA25112@burratino","threadId":"24727","inReplyTo":"20100815072043.GA368@localhost","subject":"Re: [PATCH v2] hash binary sha1 into patch id","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-08-15T07:56:31Z","receivedAt":"2010-08-15T07:56:31Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Clemens Buchacher wrote:\n\n> Signed-off-by: Clemens Buchacher <drizzd@aon.at>\n\nNice. :)\n\n> I am again attaching the corresponding test script. Since it mostly\n> tests performance, I am not sure how to incorporate it into the\n> main test suite.\n\nMaybe t3302-notes-index-expensive.sh would be a good example to\ncompare.\n\nI haven’t looked carefully at your test script; is it possible\nto extract a non-expensive test (i.e., just for correctness)\nfrom it, too?\n\nJonathan\n"},{"id":"150426","messageId":"1284095850.1728.5.camel@n900.home.ru","threadId":"24727","inReplyTo":"20100815072043.GA368@localhost","subject":"Re: [PATCH v2] hash binary sha1 into patch id","fromName":"Marat Radchenko","fromEmail":"marat@slonopotamus.org","sentAt":"2010-09-10T05:17:30Z","receivedAt":"2010-09-10T05:17:30Z","isPatch":true,"sender":{"key":"marat@slonopotamus.org","avatar":"https://avatars.githubusercontent.com/u/92637?v=4"},"body":"As I see, this recently hit git master. I want to say big thanks since it improved git rebase from tens of minutes to just minutes here (warm disk caches).\n\nHowever, I can't say I'm completely satisfied with git rebase speed (I'd like it to be < 1 min). So, are there known performance hotspots in 'git rev-list --cherry-pick'/'git format-patch --ignore-if-in-upstream' (these are two flags have biggest impact on git rebase [-i] speed) or I should run some kind of profiles in order to determine what else could be improved?\n"},{"id":"150429","messageId":"20100910081626.GA30507@localhost","threadId":"24727","inReplyTo":"1284095850.1728.5.camel@n900.home.ru","subject":"Re: [PATCH v2] hash binary sha1 into patch id","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2010-09-10T08:16:26Z","receivedAt":"2010-09-10T08:16:26Z","isPatch":true,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"On Fri, Sep 10, 2010 at 09:17:30AM +0400, Marat Radchenko wrote:\n> \n> However, I can't say I'm completely satisfied with git rebase\n> speed (I'd like it to be < 1 min). So, are there known\n> performance hotspots in 'git rev-list --cherry-pick'/'git\n> format-patch --ignore-if-in-upstream' (these are two flags have\n> biggest impact on git rebase [-i] speed) or I should run some\n> kind of profiles in order to determine what else could be\n> improved?\n\ngit format-patch is still slow if you have large text files (>10000\nlines). This patch only helps for binary files or files marked as\nbinary in .gitattributes. There is also a patch\n\n http://mid.gmane.org/645d8a9bf671937c1a6962b49cf1c512e0af0d82.1279008702.git.git@drmicha.warpmail.net\n\nto turn off patch ID computation entirely.\n\nOther than that, I am not aware of performance issues with rebase\nthat would cause it to take more than a minute. Possibly you can\nuse 'perf' to profile your use case. I used it to test this patch\nin the script below (pass -p to enable). But it's only testing\nformat-patch right now, so you would have to modify it to profile\nrebase as a whole.\n\nClemens\n---\n\n#!/bin/bash\n\nset -e\n\nNLINES=50000\nNRAND=32768\n# probability of change in percent\nCHG_PROB=30\nperf=\nwhile test $# -gt 0\ndo\n\tcase $1 in\n\t-p)\n\t\tperf=t\n\t\t;;\n\t-n)\n\t\tshift\n\t\tNLINES=$1\n\t\t;;\n\t*)\n\t\tbreak\n\t\t;;\n\tesac\n\tshift\ndone\n\nif test $# -gt 0\nthen\n\texport PATH=\"$1:$PATH\"\n\tshift\nfi\n\nif test $# -gt 0\nthen\n\techo \"too many arguments\" >&2\n\texit 1\nfi\n\ndir=$(mktemp -d)\n\nscramble()\n{\n\twhile read x\n\tdo\n\t\tif test $RANDOM -lt $((($CHG_PROB * $NRAND)/100))\n\t\tthen\n\t\t\techo $RANDOM\n\t\telse\n\t\t\techo \"$x\"\n\t\tfi\n\tdone < \"$1\" > \"$1.new\"\n\tmv -f \"$1.new\" \"$1\"\n}\n\nrun()\n{\n\techo \\$ \"$@\"\n\tif test -n \"$perf\"\n\tthen\n\t\tperf record -g -f \"$@\" >/dev/null\n\t\tperf report -g\n\telse\n\t\ttime \"$@\" >/dev/null\n\tfi\n}\n\ncd \"$dir\"\ngit init -q\n\nfor i in $(seq $NLINES)\ndo\n\techo $i\ndone > file\ngit add file\necho \"file binary\" >.gitattributes\ngit add .gitattributes\ngit commit -q -m initial\ngit branch other\n\nscramble file\ngit add file\ngit commit -q -m 'change big file'\n\ngit checkout -q other\n: >newfile\ngit add newfile\ngit commit -q -m 'add small file'\n\ngfp=\"git format-patch --stdout\"\n\nrun $gfp master\nrun $gfp --ignore-if-in-upstream master\n\ngit cherry-pick master >/dev/null 2>&1\n\ngit checkout -q master\nscramble file\ngit add file\ngit commit -q -m 'change big file again'\n\ngit checkout -q other^{}\nrun git rebase master\nif test -n \"$(git rev-list master...HEAD~)\"\nthen\n\techo \"patch not identified\" >&2\n\texit 1\nfi\n\ngit checkout -q -b squashed master\ngit reset -q --soft HEAD~2\ngit commit -q -m squashed\ngit checkout -q other^{}\nif git rebase squashed >/dev/null\nthen\n\techo \"patch dropped\" >&2\n\texit 1\nfi\n\ncd - >/dev/null\nrm -rf \"$dir\"\n"},{"id":"153376","messageId":"1286956002591-5629905.post@n2.nabble.com","threadId":"24727","inReplyTo":"20100910081626.GA30507@localhost","subject":"Re: [PATCH v2] hash binary sha1 into patch id","fromName":"Marat Radchenko","fromEmail":"marat@slonopotamus.org","sentAt":"2010-10-13T07:46:42Z","receivedAt":"2010-10-13T07:46:42Z","isPatch":true,"sender":{"key":"marat@slonopotamus.org","avatar":"https://avatars.githubusercontent.com/u/92637?v=4"},"body":"\nSo, here's some gprof data of git-rev-list:\nhttp://git.661346.n2.nabble.com/file/n5629905/gprof_-p.txt gprof -p output \nhttp://git.661346.n2.nabble.com/file/n5629905/gprof_-q.txt gprof -q output \n-- \nView this message in context: http://git.661346.n2.nabble.com/PATCH-hash-binary-sha1-into-patch-id-tp5419375p5629905.html\nSent from the git mailing list archive at Nabble.com.\n"},{"id":"153379","messageId":"1286961452235-5630164.post@n2.nabble.com","threadId":"24727","inReplyTo":"1286956002591-5629905.post@n2.nabble.com","subject":"Re: [PATCH v2] hash binary sha1 into patch id","fromName":"Marat Radchenko","fromEmail":"marat@slonopotamus.org","sentAt":"2010-10-13T09:17:32Z","receivedAt":"2010-10-13T09:17:32Z","isPatch":true,"sender":{"key":"marat@slonopotamus.org","avatar":"https://avatars.githubusercontent.com/u/92637?v=4"},"body":"\nDoes diff_get_patch_id (in diff.c) really need to set xecfg.flags =\nXDL_EMIT_FUNCNAMES? Removing that makes git-rev-list (called by rebase) 2x\nfaster here. Not sure about consequences though.\n-- \nView this message in context: http://git.661346.n2.nabble.com/PATCH-hash-binary-sha1-into-patch-id-tp5419375p5630164.html\nSent from the git mailing list archive at Nabble.com.\n"},{"id":"153443","messageId":"20101013211011.GA2558@localhost","threadId":"24727","inReplyTo":"1286961452235-5630164.post@n2.nabble.com","subject":"Re: [PATCH v2] hash binary sha1 into patch id","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2010-10-13T21:10:11Z","receivedAt":"2010-10-13T21:10:11Z","isPatch":true,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"Hi Marat,\n\nOn Wed, Oct 13, 2010 at 02:17:32AM -0700, Marat Radchenko wrote:\n> \n> Does diff_get_patch_id (in diff.c) really need to set xecfg.flags =\n> XDL_EMIT_FUNCNAMES? Removing that makes git-rev-list (called by rebase) 2x\n> faster here. Not sure about consequences though.\n\nYes, this has already been fixed in ad14b450 (do not search\nfunctions for patch ID), which is currently in git.git's pu branch.\nFunction name search performance has also been improved for some\nobscure cases in c099789b (diff: avoid repeated scanning while\nlooking for funcname).\n\nThanks anyways. If you notice anything else, please let us know.\n\nI had a look at your gprof results, but I cannot make much sense of\nit. I do not understand why git rev-list would even do any diffs.\nFor me, rev-list spends more than 50% in libz.  Can you give more\ndetails on the kind of repository you have (binaries, memory size,\nhistory size, any special attributes or options?), which git\nversion you are using, and which options you are passing to\nrev-list?\n\nClemens\n"},{"id":"153492","messageId":"1287040761027-5633988.post@n2.nabble.com","threadId":"24727","inReplyTo":"20101013211011.GA2558@localhost","subject":"Re: [PATCH v2] hash binary sha1 into patch id","fromName":"Marat Radchenko","fromEmail":"marat@slonopotamus.org","sentAt":"2010-10-14T07:19:21Z","receivedAt":"2010-10-14T07:19:21Z","isPatch":true,"sender":{"key":"marat@slonopotamus.org","avatar":"https://avatars.githubusercontent.com/u/92637?v=4"},"body":"\nI'm running git-rev-list from git master in the form git rebase does:\ngit-rev-list --no-merges --cherry-pick --pretty=oneline --abbrev-commit\n--abbrev=7 --reverse --left-right --topo-order FOO...BAR\n\nNew gprof output (I compiled without -O2 to prevent function inlining and\nremoved xecfg.flags = XDL_EMIT_FUNCNAMES):\nhttp://git.661346.n2.nabble.com/file/n5633988/gprof_-p.txt gprof -p \nhttp://git.661346.n2.nabble.com/file/n5633988/gprof_-q.txt gprof -q \n\nThis thing takes ~3 minutes of cpu time.\n\nSo, it takes ~3 minutes of cpu time and looks like all time is spent in\nxdl_cleanup_records.\n\nRepo info: 80GB, 200K revisions (~200 per working day), 500K files (15GB) in\nmaster working copy, running git-rev-list to rebase ~5 commits over ~800\ncommits that happened upstream.\n-- \nView this message in context: http://git.661346.n2.nabble.com/PATCH-hash-binary-sha1-into-patch-id-tp5419375p5633988.html\nSent from the git mailing list archive at Nabble.com.\n"}]}