{"thread":{"id":"39791","subject":"suboptimal behavior of fast-import in some cases with \"from\"","startedAt":"2015-07-06T22:07:46Z","lastAt":"2015-07-09T22:47:56Z","messageCount":9,"participants":["Mike Hommey","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"265632","messageId":"20150706220746.GA29367@glandium.org","threadId":"39791","inReplyTo":null,"subject":"suboptimal behavior of fast-import in some cases with \"from\"","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2015-07-06T22:07:46Z","receivedAt":"2015-07-06T22:07:46Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"Hi,\n\nI did something \"stupid\" with a script using fast-import, and that made\nthe whole process ~20% slower on Linux and 400~500% slower on Mac. The\nreason this happened is that the script was essentially adding a \"from\"\nto every \"commit\" command, even when the \"from\" commit is the current\nhead of the branch.\n\nOne of the first things parse_from does is unconditionally throw away\nthe tree for the given branch, and then the \"from\" tree is loaded. So\nwhen the \"from\" commit is the current head of the branch, that make\nfast-import do more work than necessary.\n\nEven more so when the pack flush code in gfi_unpack_entry is triggered,\nwhich, on mac, is extra slow (and explains the huge slow down there).\n\nNow, I do understand that my script is doing something stupid. So the\nquestion is whether it's worth fixing in fast-import or not. I already\nfixed my script anyways.\n\nMike\n"},{"id":"265633","messageId":"xmqq4mlgzyl0.fsf@gitster.dls.corp.google.com","threadId":"39791","inReplyTo":"20150706220746.GA29367@glandium.org","subject":"Re: suboptimal behavior of fast-import in some cases with \"from\"","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-07-06T22:54:35Z","receivedAt":"2015-07-06T22:54:35Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Mike Hommey writes:\n\n> One of the first things parse_from does is unconditionally throw away\n> the tree for the given branch, and then the \"from\" tree is loaded. So\n> when the \"from\" commit is the current head of the branch, that make\n> fast-import do more work than necessary.\n\nIf it is very common that the next commit the input stream wants to\ncreate is often on top of the commit that was just created, and if\nit is very common that the input stream producer knows what the\ncommit object name of the commit that was just created, then\noptimising for that case does not sound too bad. It really depends\non two factors:\n\n - How likely is it that other people make the same mistake?\n\n - How bad the damage to parse_from() would be if we wanted to\n optimize for this case?\n"},{"id":"265889","messageId":"20150709050314.GA6013@glandium.org","threadId":"39791","inReplyTo":"xmqq4mlgzyl0.fsf@gitster.dls.corp.google.com","subject":"Re: suboptimal behavior of fast-import in some cases with \"from\"","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2015-07-09T05:03:15Z","receivedAt":"2015-07-09T05:03:15Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Mon, Jul 06, 2015 at 03:54:35PM -0700, Junio C Hamano wrote:\n> Mike Hommey writes:\n> \n> > One of the first things parse_from does is unconditionally throw away\n> > the tree for the given branch, and then the \"from\" tree is loaded. So\n> > when the \"from\" commit is the current head of the branch, that make\n> > fast-import do more work than necessary.\n> \n> If it is very common that the next commit the input stream wants to\n> create is often on top of the commit that was just created, and if\n> it is very common that the input stream producer knows what the\n> commit object name of the commit that was just created, then\n> optimising for that case does not sound too bad. It really depends\n> on two factors:\n> \n> - How likely is it that other people make the same mistake?\n\nLooks like the answer is: very. Assuming my quick glance at the code is\nnot mistaken, the same mistake is made in at least git-p4.py (yes, the\none that comes with git), felipec's git-remote-hg, and hg-fast-export,\nand that's 100% of the sample I looked at.\n\nI won't claim to know what fast-import is doing, not having looked at\nmore than the parse_from* functions and the commit message for 4cabf858,\nbut it seems plausible this also skips making tree deltas for those\ntrees.\n\n> - How bad the damage to parse_from() would be if we wanted to\n> optimize for this case?\n\nI /think/ it would look like this (untested), which doesn't seem too\ndamaging:\n\ndiff --git a/fast-import.c b/fast-import.c\nindex e78ca10..cb232e0 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -2588,14 +2588,12 @@ static int parse_from(struct branch *b)\n {\n const char *from;\n struct branch *s;\n+ unsigned char sha1[20];\n \n if (!skip_prefix(command_buf.buf, \"from \", &from))\n return 0;\n \n- if (b->branch_tree.tree) {\n- release_tree_content_recursive(b->branch_tree.tree);\n- b->branch_tree.tree = NULL;\n- }\n+ hashcpy(sha1, b->branch_tree.versions[1].sha1);\n \n s = lookup_branch(from);\n if (b == s)\n@@ -2626,6 +2624,11 @@ static int parse_from(struct branch *b)\n else\n die(\"Invalid ref name or SHA1 expression: %s\", from);\n \n+ if (b->branch_tree.tree && hashcmp(sha1, b->branch_tree.versions[1].sha1)) {\n+ release_tree_content_recursive(b->branch_tree.tree);\n+ b->branch_tree.tree = NULL;\n+ }\n+\n read_next_command();\n return 1;\n }\n\nMike\n"},{"id":"265890","messageId":"20150709055227.GA32360@glandium.org","threadId":"39791","inReplyTo":"20150709050314.GA6013@glandium.org","subject":"Re: suboptimal behavior of fast-import in some cases with \"from\"","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2015-07-09T05:52:27Z","receivedAt":"2015-07-09T05:52:27Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Thu, Jul 09, 2015 at 02:03:15PM +0900, Mike Hommey wrote:\n> On Mon, Jul 06, 2015 at 03:54:35PM -0700, Junio C Hamano wrote:\n> > Mike Hommey writes:\n> > \n> > > One of the first things parse_from does is unconditionally throw away\n> > > the tree for the given branch, and then the \"from\" tree is loaded. So\n> > > when the \"from\" commit is the current head of the branch, that make\n> > > fast-import do more work than necessary.\n> > \n> > If it is very common that the next commit the input stream wants to\n> > create is often on top of the commit that was just created, and if\n> > it is very common that the input stream producer knows what the\n> > commit object name of the commit that was just created, then\n> > optimising for that case does not sound too bad. It really depends\n> > on two factors:\n> > \n> > - How likely is it that other people make the same mistake?\n> \n> Looks like the answer is: very. Assuming my quick glance at the code is\n> not mistaken, the same mistake is made in at least git-p4.py (yes, the\n> one that comes with git), felipec's git-remote-hg, and hg-fast-export,\n> and that's 100% of the sample I looked at.\n> \n> I won't claim to know what fast-import is doing, not having looked at\n> more than the parse_from* functions and the commit message for 4cabf858,\n> but it seems plausible this also skips making tree deltas for those\n> trees.\n\nIt doesn't /seem/ to be the case.\n\n> > - How bad the damage to parse_from() would be if we wanted to\n> > optimize for this case?\n> \n> I /think/ it would look like this (untested), which doesn't seem too\n> damaging:\n\nIt's actually not enough. It does avoid to reread trees, but it doesn't\navoid the pack to be closed/reopened.\n\nMike\n"},{"id":"265896","messageId":"1436424609-26159-1-git-send-email-mh@glandium.org","threadId":"39791","inReplyTo":"20150709055227.GA32360@glandium.org","subject":"[PATCH] fast-import: Do less work when given \"from\" matches current branch head","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2015-07-09T06:50:09Z","receivedAt":"2015-07-09T06:50:09Z","isPatch":true,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"When building a fast-import stream, it's easy to forget the fact that\nfor non-merge commits happening on top of the current branch head, there\nis no need for a \"from\" command. That is corroborated by the fact that\nat least git-p4, hg-fast-export and felipec's git-remote-hg all\nunconditionally use a \"from\" command.\n\nUnfortunately, giving a \"from\" command always resets the branch tree,\nforcing it to be re-read, and in many cases, the pack is also closed\nand reopened through gfi_unpack_entry. Both are extra unwanted overhead,\nand the latter is particularly slow at least on OSX.\n\nSo, avoid resetting the tree when it's unmodified, and avoid calling\ngfi_unpack_entry when the given mark points to the same commit as the\ncurrent branch head.\n\nSigned-off-by: Mike Hommey \n---\n fast-import.c | 29 +++++++++++++++++------------\n 1 file changed, 17 insertions(+), 12 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex e78ca10..372d63a 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -2588,14 +2588,12 @@ static int parse_from(struct branch *b)\n {\n \tconst char *from;\n \tstruct branch *s;\n+\tunsigned char sha1[20];\n \n \tif (!skip_prefix(command_buf.buf, \"from \", &from))\n \t\treturn 0;\n \n-\tif (b->branch_tree.tree) {\n-\t\trelease_tree_content_recursive(b->branch_tree.tree);\n-\t\tb->branch_tree.tree = NULL;\n-\t}\n+\thashcpy(sha1, b->branch_tree.versions[1].sha1);\n \n \ts = lookup_branch(from);\n \tif (b == s)\n@@ -2610,14 +2608,16 @@ static int parse_from(struct branch *b)\n \t\tstruct object_entry *oe = find_mark(idnum);\n \t\tif (oe->type != OBJ_COMMIT)\n \t\t\tdie(\"Mark :%\" PRIuMAX \" not a commit\", idnum);\n-\t\thashcpy(b->sha1, oe->idx.sha1);\n-\t\tif (oe->pack_id != MAX_PACK_ID) {\n-\t\t\tunsigned long size;\n-\t\t\tchar *buf = gfi_unpack_entry(oe, &size);\n-\t\t\tparse_from_commit(b, buf, size);\n-\t\t\tfree(buf);\n-\t\t} else\n-\t\t\tparse_from_existing(b);\n+\t\tif (hashcmp(b->sha1, oe->idx.sha1)) {\n+\t\t\thashcpy(b->sha1, oe->idx.sha1);\n+\t\t\tif (oe->pack_id != MAX_PACK_ID) {\n+\t\t\t\tunsigned long size;\n+\t\t\t\tchar *buf = gfi_unpack_entry(oe, &size);\n+\t\t\t\tparse_from_commit(b, buf, size);\n+\t\t\t\tfree(buf);\n+\t\t\t} else\n+\t\t\t\tparse_from_existing(b);\n+\t\t}\n \t} else if (!get_sha1(from, b->sha1)) {\n \t\tparse_from_existing(b);\n \t\tif (is_null_sha1(b->sha1))\n@@ -2626,6 +2626,11 @@ static int parse_from(struct branch *b)\n \telse\n \t\tdie(\"Invalid ref name or SHA1 expression: %s\", from);\n \n+\tif (b->branch_tree.tree && hashcmp(sha1, b->branch_tree.versions[1].sha1)) {\n+\t\trelease_tree_content_recursive(b->branch_tree.tree);\n+\t\tb->branch_tree.tree = NULL;\n+\t}\n+\n \tread_next_command();\n \treturn 1;\n }\n-- \n2.4.3.2.gf0a024e.dirty\n"},{"id":"265942","messageId":"xmqqk2u9uky9.fsf@gitster.dls.corp.google.com","threadId":"39791","inReplyTo":"1436424609-26159-1-git-send-email-mh@glandium.org","subject":"Re: [PATCH] fast-import: Do less work when given \"from\" matches current branch head","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-07-09T20:37:02Z","receivedAt":"2015-07-09T20:37:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Mike Hommey writes:\n\nCc'ed a few people who appear at the top of \"shortlog --no-merges\";\nI think the end result is not incorrect, but I want to hear second\nopinions on this one. I do not know Shawn still remembers this\ncode, but what is under discussion seems to have come mostly from\nea5e370a (fast-import: Support reusing 'from' and brown paper bag\nfix reset., 2007-02-12).\n\n> \tif (!skip_prefix(command_buf.buf, \"from \", &from))\n> \t\treturn 0;\n> \n> -\tif (b->branch_tree.tree) {\n> -\t\trelease_tree_content_recursive(b->branch_tree.tree);\n> -\t\tb->branch_tree.tree = NULL;\n> -\t}\n> +\thashcpy(sha1, b->branch_tree.versions[1].sha1);\n> \n> \ts = lookup_branch(from);\n> \tif (b == s)\n\nThe part that deals with a branch that is different from the current\none is not visible in the context (i.e. when s = lookup_branch(from)\nreturned a non-NULL result that is different from b) but it used to,\nand continues to with this patch, copy sha1 from branch_tree.sha1\nand branch_tree.versions[] from sha1 and branch_tree.versions[1] of\nthe specified branch.\n\nThat codepath used to release the contents of branch_tree.tree when\nit did so, but it no longer does so after this patch because of the\nremoval we see above.\n\nDoes that mean the original code was doing a release that was\nunnecessary? Or does it mean this patch changes what happens on\nthat codepath, namely (1) leaking resource, and/or (2) keeping a\ntree of the original 'b' that does not have anything to do with the\ntree of 's', preventing the later lazy-load code from reading the\ntree of 's' and instead of building on top of a wrong tree content?\n\n... me goes and reads on ...\n\n> @@ -2610,14 +2608,16 @@ static int parse_from(struct branch *b)\n> \t\tstruct object_entry *oe = find_mark(idnum);\n> \t\tif (oe->type != OBJ_COMMIT)\n> \t\t\tdie(\"Mark :%\" PRIuMAX \" not a commit\", idnum);\n> -\t\thashcpy(b->sha1, oe->idx.sha1);\n> -\t\tif (oe->pack_id != MAX_PACK_ID) {\n> -\t\t\tunsigned long size;\n> -\t\t\tchar *buf = gfi_unpack_entry(oe, &size);\n> -\t\t\tparse_from_commit(b, buf, size);\n> -\t\t\tfree(buf);\n> -\t\t} else\n> -\t\t\tparse_from_existing(b);\n> +\t\tif (hashcmp(b->sha1, oe->idx.sha1)) {\n> +\t\t\thashcpy(b->sha1, oe->idx.sha1);\n> +\t\t\tif (oe->pack_id != MAX_PACK_ID) {\n> +\t\t\t\tunsigned long size;\n> +\t\t\t\tchar *buf = gfi_unpack_entry(oe, &size);\n> +\t\t\t\tparse_from_commit(b, buf, size);\n> +\t\t\t\tfree(buf);\n> +\t\t\t} else\n> +\t\t\t\tparse_from_existing(b);\n> +\t\t}\n> \t} else if (!get_sha1(from, b->sha1)) {\n> \t\tparse_from_existing(b);\n> \t\tif (is_null_sha1(b->sha1))\n\nThis part is straight-forward.\n\n> @@ -2626,6 +2626,11 @@ static int parse_from(struct branch *b)\n> \telse\n> \t\tdie(\"Invalid ref name or SHA1 expression: %s\", from);\n> \n> +\tif (b->branch_tree.tree && hashcmp(sha1, b->branch_tree.versions[1].sha1)) {\n> +\t\trelease_tree_content_recursive(b->branch_tree.tree);\n> +\t\tb->branch_tree.tree = NULL;\n> +\t}\n> +\n\nThis looks like an attempt to compensate for that \"what happens if\n(s != NULL && s != b)?\" issue, and also for the surviving codepaths.\n\nAs both parse_from_commit() and parse_from_existing() only touch\nbranch_tree.versions[] and they do not seem to get affected if\nb->branch_tree.tree holds a stale and unrelated content, this looks\nOK to me from a cursory reading, but it does make me feel dirty that\nit has to put *b temporarily into an inconsistent state.\n"},{"id":"265949","messageId":"20150709223018.GA3403@glandium.org","threadId":"39791","inReplyTo":"xmqqk2u9uky9.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] fast-import: Do less work when given \"from\" matches current branch head","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2015-07-09T22:30:18Z","receivedAt":"2015-07-09T22:30:18Z","isPatch":true,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Thu, Jul 09, 2015 at 01:37:02PM -0700, Junio C Hamano wrote:\n> Mike Hommey writes:\n> \n> Cc'ed a few people who appear at the top of \"shortlog --no-merges\";\n> I think the end result is not incorrect, but I want to hear second\n> opinions on this one. I do not know Shawn still remembers this\n> code, but what is under discussion seems to have come mostly from\n> ea5e370a (fast-import: Support reusing 'from' and brown paper bag\n> fix reset., 2007-02-12).\n> \n> > \tif (!skip_prefix(command_buf.buf, \"from \", &from))\n> > \t\treturn 0;\n> > \n> > -\tif (b->branch_tree.tree) {\n> > -\t\trelease_tree_content_recursive(b->branch_tree.tree);\n> > -\t\tb->branch_tree.tree = NULL;\n> > -\t}\n> > +\thashcpy(sha1, b->branch_tree.versions[1].sha1);\n> > \n> > \ts = lookup_branch(from);\n> > \tif (b == s)\n> \n> The part that deals with a branch that is different from the current\n> one is not visible in the context (i.e. when s = lookup_branch(from)\n> returned a non-NULL result that is different from b) but it used to,\n> and continues to with this patch, copy sha1 from branch_tree.sha1\n> and branch_tree.versions[] from sha1 and branch_tree.versions[1] of\n> the specified branch.\n> \n> That codepath used to release the contents of branch_tree.tree when\n> it did so, but it no longer does so after this patch because of the\n> removal we see above.\n> \n> Does that mean the original code was doing a release that was\n> unnecessary? Or does it mean this patch changes what happens on\n> that codepath, namely (1) leaking resource, and/or (2) keeping a\n> tree of the original 'b' that does not have anything to do with the\n> tree of 's', preventing the later lazy-load code from reading the\n> tree of 's' and instead of building on top of a wrong tree content?\n\nI guess the question is whether branch_tree.tree can be in a state that\ndoesn't match that of branch_tree.versions[1].sha1. If not, then if s\nand b have the same branch_tree.versions[1].sha1 for some reason, then\nkeeping the old branch_tree.tree makes no practical difference from\nresetting it. Except it skips the busy-work.\n\nMike\n"},{"id":"265950","messageId":"xmqq7fq9uf1w.fsf@gitster.dls.corp.google.com","threadId":"39791","inReplyTo":"20150709223018.GA3403@glandium.org","subject":"Re: [PATCH] fast-import: Do less work when given \"from\" matches current branch head","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-07-09T22:44:27Z","receivedAt":"2015-07-09T22:44:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Mike Hommey writes:\n\n>> Does that mean the original code was doing a release that was\n>> unnecessary? Or does it mean this patch changes what happens on\n>> that codepath, namely (1) leaking resource, and/or (2) keeping a\n>> tree of the original 'b' that does not have anything to do with the\n>> tree of 's', preventing the later lazy-load code from reading the\n>> tree of 's' and instead of building on top of a wrong tree content?\n>\n> I guess the question is whether branch_tree.tree can be in a state that\n> doesn't match that of branch_tree.versions[1].sha1. If not, then if s\n> and b have the same branch_tree.versions[1].sha1 for some reason, then\n> keeping the old branch_tree.tree makes no practical difference from\n> resetting it. Except it skips the busy-work.\n\nPerhaps my comment was misleading. I _think_ the state at the end\nof this function (i.e. the latter hunk you added to the function\nmakes the above issue I raised go away). It just made me feel\nuneasy to leave branch_tree.tree and branch_tree.versions[] in an\ninconsistent state inside this function, while it calls a few helper\nfunctions (hence my comment on the fact that they do not seem to be\naffected by this inconsistency).\n"},{"id":"265951","messageId":"xmqq380xuew3.fsf@gitster.dls.corp.google.com","threadId":"39791","inReplyTo":"xmqq7fq9uf1w.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] fast-import: Do less work when given \"from\" matches current branch head","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-07-09T22:47:56Z","receivedAt":"2015-07-09T22:47:56Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Mike Hommey writes:\n>\n>>> Does that mean the original code was doing a release that was\n>>> unnecessary? Or does it mean this patch changes what happens on\n>>> that codepath, namely (1) leaking resource, and/or (2) keeping a\n>>> tree of the original 'b' that does not have anything to do with the\n>>> tree of 's', preventing the later lazy-load code from reading the\n>>> tree of 's' and instead of building on top of a wrong tree content?\n>>\n>> I guess the question is whether branch_tree.tree can be in a state that\n>> doesn't match that of branch_tree.versions[1].sha1. If not, then if s\n>> and b have the same branch_tree.versions[1].sha1 for some reason, then\n>> keeping the old branch_tree.tree makes no practical difference from\n>> resetting it. Except it skips the busy-work.\n>\n> Perhaps my comment was misleading. I _think_ the state at the end\n> of this function (i.e. the latter hunk you added to the function\n> makes the above issue I raised go away). It just made me feel\n\ns/this function (/this function is good (/;\n\n> uneasy to leave branch_tree.tree and branch_tree.versions[] in an\n> inconsistent state inside this function, while it calls a few helper\n> functions (hence my comment on the fact that they do not seem to be\n> affected by this inconsistency).\n"}]}