{"thread":{"id":"2135","subject":"[CORRECTED PATCH] git-fetch-pack: avoid unnecessary zero packing","startedAt":"2005-10-18T17:52:45Z","lastAt":"2005-10-19T00:27:53Z","messageCount":7,"participants":["Linus Torvalds","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"10212","messageId":"Pine.LNX.4.64.0510181049050.17201@g5.osdl.org","threadId":"2135","inReplyTo":null,"subject":"[CORRECTED PATCH] git-fetch-pack: avoid unnecessary zero packing","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-10-18T17:52:45Z","receivedAt":"2005-10-18T17:52:45Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nIf everything is up-to-date locally, we don't need to even ask for a\npack-file from the remote, or try to unpack it.\n\nThis is especially important for tags - since the pack-file common commit\nlogic is based purely on the commit history, it will never be able to find\na common tag, and will thus always end up re-fetching them.\n\nEspecially notably, if the tag points to a non-commit (eg a tagged tree),\nthe pack-file would be unnecessarily big, just because it cannot any most\nrecent common point between commits for pruning.\n\nShort-circuiting the case where we already have that reference means that\nwe avoid a lot of these in the common case.\n\nNOTE! This only matches remote ref names against the same local name,\nwhich works well for tags, but is not as generic as it could be. If we\never need to, we could match against _any_ local ref (if we have it, we\nhave it), but this \"match against same name\" is simpler and more\nefficient, and covers the common case.\n\nRenaming of refs is common for branch heads, but since those are always\ncommits, the pack-file generation can optimize that case.\n\nIn some cases we might still end up fetching pack-files unnecessarily, but\nthis at least avoids the re-fetching of tags over and over if you use a\nregular\n\n\tgit fetch --tags ...\n\nwhich was the main reason behind the change.\n\nSigned-off-by: Linus Torvalds <torvalds@osdl.org>\n---\n\nOk, this should be the trivially fixed (famous last words) patch, which \nshould correct the case where we don't have a local name for the remote \nref at all.\n\nIf you already applied the previous patch, you just need to fix the\n\n\tif (read_ref(...) < 0)\n\t\tcontinue\n\tif (memcmp(..)) {\n\nto be one case (a failing read_ref should do the exact same thing as a \nfailed memcmp):\n\n\tif (read_ref(...) < 0 ||\n\t    memcmp(...) {\n\nand everything should be ok.\n\nThis has gotten _some_ testing, but obviously not enough ;)\n\n\t\tLinus\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 953c0cf..4597369 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -12,6 +12,7 @@ static const char *exec = \"git-upload-pa\n static int find_common(int fd[2], unsigned char *result_sha1,\n \t\t       struct ref *refs)\n {\n+\tint fetching;\n \tstatic char line[1000];\n \tint count = 0, flushes = 0, retval;\n \tFILE *revs;\n@@ -20,16 +21,19 @@ static int find_common(int fd[2], unsign\n \tif (!revs)\n \t\tdie(\"unable to run 'git-rev-list'\");\n \n-\twhile (refs) {\n+\tfetching = 0;\n+\tfor ( ; refs ; refs = refs->next) {\n \t\tunsigned char *remote = refs->old_sha1;\n-\t\tif (verbose)\n-\t\t\tfprintf(stderr,\n-\t\t\t\t\"want %s (%s)\\n\", sha1_to_hex(remote),\n-\t\t\t\trefs->name);\n+\t\tunsigned char *local = refs->new_sha1;\n+\n+\t\tif (!memcmp(remote, local, 20))\n+\t\t\tcontinue;\n \t\tpacket_write(fd[1], \"want %s\\n\", sha1_to_hex(remote));\n-\t\trefs = refs->next;\n+\t\tfetching++;\n \t}\n \tpacket_flush(fd[1]);\n+\tif (!fetching)\n+\t\treturn 1;\n \tflushes = 1;\n \tretval = -1;\n \twhile (fgets(line, sizeof(line), revs) != NULL) {\n@@ -74,6 +78,35 @@ static int find_common(int fd[2], unsign\n \treturn retval;\n }\n \n+static int everything_local(struct ref *refs)\n+{\n+\tint retval;\n+\n+\tfor (retval = 1; refs ; refs = refs->next) {\n+\t\tconst unsigned char *remote = refs->old_sha1;\n+\t\tunsigned char local[20];\n+\n+\t\tif (read_ref(git_path(\"%s\", refs->name), local) < 0 ||\n+\t\t    memcmp(remote, local, 20)) {\n+\t\t\tretval = 0;\n+\t\t\tif (!verbose)\n+\t\t\t\tcontinue;\n+\t\t\tfprintf(stderr,\n+\t\t\t\t\"want %s (%s)\\n\", sha1_to_hex(remote),\n+\t\t\t\trefs->name);\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tmemcpy(refs->new_sha1, local, 20);\n+\t\tif (!verbose)\n+\t\t\tcontinue;\n+\t\tfprintf(stderr,\n+\t\t\t\"already have %s (%s)\\n\", sha1_to_hex(remote),\n+\t\t\trefs->name);\n+\t}\n+\treturn retval;\n+}\n+\n static int fetch_pack(int fd[2], int nr_match, char **match)\n {\n \tstruct ref *ref;\n@@ -86,6 +119,10 @@ static int fetch_pack(int fd[2], int nr_\n \t\tpacket_flush(fd[1]);\n \t\tdie(\"no matching remote head\");\n \t}\n+\tif (everything_local(ref)) {\n+\t\tpacket_flush(fd[1]);\n+\t\tgoto all_done;\n+\t}\n \tif (find_common(fd, sha1, ref) < 0)\n \t\tfprintf(stderr, \"warning: no common commits\\n\");\n \tpid = fork();\n@@ -109,6 +146,7 @@ static int fetch_pack(int fd[2], int nr_\n \t\tint code = WEXITSTATUS(status);\n \t\tif (code)\n \t\t\tdie(\"git-unpack-objects died with error code %d\", code);\n+all_done:\n \t\twhile (ref) {\n \t\t\tprintf(\"%s %s\\n\",\n \t\t\t       sha1_to_hex(ref->old_sha1), ref->name);\n"},{"id":"10213","messageId":"7vr7air7e9.fsf@assigned-by-dhcp.cox.net","threadId":"2135","inReplyTo":"Pine.LNX.4.64.0510181049050.17201@g5.osdl.org","subject":"Re: [CORRECTED PATCH] git-fetch-pack: avoid unnecessary zero packing","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-10-18T18:45:34Z","receivedAt":"2005-10-18T18:45:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> If everything is up-to-date locally, we don't need to even ask for a\n> pack-file from the remote, or try to unpack it.\n>\n> This is especially important for tags - since the pack-file common commit\n> logic is based purely on the commit history, it will never be able to find\n> a common tag, and will thus always end up re-fetching them.\n>\n> Especially notably, if the tag points to a non-commit (eg a tagged tree),\n> the pack-file would be unnecessarily big, just because it cannot any most\n> recent common point between commits for pruning.\n>\n> Short-circuiting the case where we already have that reference means that\n> we avoid a lot of these in the common case.\n>\n> NOTE! This only matches remote ref names against the same local name,\n> which works well for tags, but is not as generic as it could be. If we\n> ever need to, we could match against _any_ local ref (if we have it, we\n> have it), but this \"match against same name\" is simpler and more\n> efficient, and covers the common case.\n>\n> Renaming of refs is common for branch heads, but since those are always\n> commits, the pack-file generation can optimize that case.\n>\n> In some cases we might still end up fetching pack-files unnecessarily, but\n> this at least avoids the re-fetching of tags over and over if you use a\n> regular\n>\n> \tgit fetch --tags ...\n>\n> which was the main reason behind the change.\n>\n> Signed-off-by: Linus Torvalds <torvalds@osdl.org>\n> ---\n>\n> Ok, this should be the trivially fixed (famous last words) patch, which \n> should correct the case where we don't have a local name for the remote \n> ref at all.\n>\n> If you already applied the previous patch, you just need to fix the\n>\n> \tif (read_ref(...) < 0)\n> \t\tcontinue\n> \tif (memcmp(..)) {\n>\n> to be one case (a failing read_ref should do the exact same thing as a \n> failed memcmp):\n>\n> \tif (read_ref(...) < 0 ||\n> \t    memcmp(...) {\n>\n> and everything should be ok.\n>\n> This has gotten _some_ testing, but obviously not enough ;)\n>\n> \t\tLinus\n>\n> diff --git a/fetch-pack.c b/fetch-pack.c\n> index 953c0cf..4597369 100644\n> --- a/fetch-pack.c\n> +++ b/fetch-pack.c\n> @@ -12,6 +12,7 @@ static const char *exec = \"git-upload-pa\n>  static int find_common(int fd[2], unsigned char *result_sha1,\n>  \t\t       struct ref *refs)\n>  {\n> +\tint fetching;\n>  \tstatic char line[1000];\n>  \tint count = 0, flushes = 0, retval;\n>  \tFILE *revs;\n> @@ -20,16 +21,19 @@ static int find_common(int fd[2], unsign\n>  \tif (!revs)\n>  \t\tdie(\"unable to run 'git-rev-list'\");\n>  \n> -\twhile (refs) {\n> +\tfetching = 0;\n> +\tfor ( ; refs ; refs = refs->next) {\n>  \t\tunsigned char *remote = refs->old_sha1;\n> -\t\tif (verbose)\n> -\t\t\tfprintf(stderr,\n> -\t\t\t\t\"want %s (%s)\\n\", sha1_to_hex(remote),\n> -\t\t\t\trefs->name);\n> +\t\tunsigned char *local = refs->new_sha1;\n> +\n> +\t\tif (!memcmp(remote, local, 20))\n> +\t\t\tcontinue;\n>  \t\tpacket_write(fd[1], \"want %s\\n\", sha1_to_hex(remote));\n> -\t\trefs = refs->next;\n> +\t\tfetching++;\n>  \t}\n>  \tpacket_flush(fd[1]);\n> +\tif (!fetching)\n> +\t\treturn 1;\n>  \tflushes = 1;\n>  \tretval = -1;\n>  \twhile (fgets(line, sizeof(line), revs) != NULL) {\n> @@ -74,6 +78,35 @@ static int find_common(int fd[2], unsign\n>  \treturn retval;\n>  }\n>  \n> +static int everything_local(struct ref *refs)\n> +{\n> +\tint retval;\n> +\n> +\tfor (retval = 1; refs ; refs = refs->next) {\n> +\t\tconst unsigned char *remote = refs->old_sha1;\n> +\t\tunsigned char local[20];\n> +\n> +\t\tif (read_ref(git_path(\"%s\", refs->name), local) < 0 ||\n> +\t\t    memcmp(remote, local, 20)) {\n> +\t\t\tretval = 0;\n> +\t\t\tif (!verbose)\n> +\t\t\t\tcontinue;\n> +\t\t\tfprintf(stderr,\n> +\t\t\t\t\"want %s (%s)\\n\", sha1_to_hex(remote),\n> +\t\t\t\trefs->name);\n> +\t\t\tcontinue;\n> +\t\t}\n> +\n> +\t\tmemcpy(refs->new_sha1, local, 20);\n> +\t\tif (!verbose)\n> +\t\t\tcontinue;\n> +\t\tfprintf(stderr,\n> +\t\t\t\"already have %s (%s)\\n\", sha1_to_hex(remote),\n> +\t\t\trefs->name);\n> +\t}\n> +\treturn retval;\n> +}\n> +\n>  static int fetch_pack(int fd[2], int nr_match, char **match)\n>  {\n>  \tstruct ref *ref;\n> @@ -86,6 +119,10 @@ static int fetch_pack(int fd[2], int nr_\n>  \t\tpacket_flush(fd[1]);\n>  \t\tdie(\"no matching remote head\");\n>  \t}\n> +\tif (everything_local(ref)) {\n> +\t\tpacket_flush(fd[1]);\n> +\t\tgoto all_done;\n> +\t}\n>  \tif (find_common(fd, sha1, ref) < 0)\n>  \t\tfprintf(stderr, \"warning: no common commits\\n\");\n>  \tpid = fork();\n> @@ -109,6 +146,7 @@ static int fetch_pack(int fd[2], int nr_\n>  \t\tint code = WEXITSTATUS(status);\n>  \t\tif (code)\n>  \t\t\tdie(\"git-unpack-objects died with error code %d\", code);\n> +all_done:\n>  \t\twhile (ref) {\n>  \t\t\tprintf(\"%s %s\\n\",\n>  \t\t\t       sha1_to_hex(ref->old_sha1), ref->name);\n"},{"id":"10214","messageId":"7vmzl6r78e.fsf@assigned-by-dhcp.cox.net","threadId":"2135","inReplyTo":"Pine.LNX.4.64.0510181049050.17201@g5.osdl.org","subject":"Re: [CORRECTED PATCH] git-fetch-pack: avoid unnecessary zero packing","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-10-18T18:49:05Z","receivedAt":"2005-10-18T18:49:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> Ok, this should be the trivially fixed (famous last words) patch, which \n> should correct the case where we don't have a local name for the remote \n> ref at all.\n>\n> If you already applied the previous patch, you just need to fix the\n\nNo, I haven't (not my git day today).\n\nIt strikes me that we could walk from our refs, depth reasonably\nlimited to say 20 or so commit chain and/or last 5 days of\ncommit time, to see if any of the remotes are reachable from our\nrefs and omit issuing \"want\" quite cheaply.  Do you think that\nwould be a worthy change to make things more efficient?\n"},{"id":"10215","messageId":"7vy84qpr8h.fsf@assigned-by-dhcp.cox.net","threadId":"2135","inReplyTo":"7vmzl6r78e.fsf@assigned-by-dhcp.cox.net","subject":"Re: [CORRECTED PATCH] git-fetch-pack: avoid unnecessary zero packing","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-10-18T19:19:58Z","receivedAt":"2005-10-18T19:19:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <junkio@cox.net> writes:\n\n> No, I haven't (not my git day today).\n>\n> It strikes me that we could walk from our refs, depth reasonably\n> limited to say 20 or so commit chain and/or last 5 days of\n> commit time, to see if any of the remotes are reachable from our\n> refs and omit issuing \"want\" quite cheaply.  Do you think that\n> would be a worthy change to make things more efficient?\n\nSomething like this on top of your second patch?\n\n ------------\nSubject: do not ask for objects known to be complete.\n\nOn top of optimization by Linus not to ask refs that already\nmatch, we can shallowly walk our refs and not issue \"want\" for\nthings that we know are reachable from them.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 4597369..212e00f 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -1,6 +1,9 @@\n #include \"cache.h\"\n #include \"refs.h\"\n #include \"pkt-line.h\"\n+#include \"commit.h\"\n+#include \"tag.h\"\n+#include <time.h>\n #include <sys/wait.h>\n \n static int quiet;\n@@ -78,16 +81,58 @@ static int find_common(int fd[2], unsign\n \treturn retval;\n }\n \n+#define COMPLETE\t(1U << 0)\n+\n+/*\n+ * 5 days - this should be configurable.\n+ */\n+#define RECENT\t\t(5 * 24 * 60 * 60)\n+\n+static struct commit_list *complete = NULL;\n+\n+static int mark_complete(const char *path, const unsigned char *sha1)\n+{\n+\tstruct object *o = parse_object(sha1);\n+\n+\twhile (o && o->type == tag_type) {\n+\t\to->flags |= COMPLETE;\n+\t\to = parse_object(((struct tag *)o)->tagged->sha1);\n+\t}\n+\tif (o->type == commit_type) {\n+\t\tstruct commit *commit = (struct commit *)o;\n+\t\tcommit->object.flags |= COMPLETE;\n+\t\tinsert_by_date(commit, &complete);\n+\t}\n+\treturn 0;\n+}\n+\n+static void mark_recent_complete_commits(unsigned long cutoff_date)\n+{\n+\twhile (complete && cutoff_date <= complete->item->date) {\n+\t\tif (verbose)\n+\t\t\tfprintf(stderr, \"Marking %s as complete\\n\",\n+\t\t\t\tsha1_to_hex(complete->item->object.sha1));\n+\t\tpop_most_recent_commit(&complete, COMPLETE);\n+\t}\n+}\n+\n static int everything_local(struct ref *refs)\n {\n \tint retval;\n+\ttime_t now;\n+\n+\ttime(&now);\n+\n+\tfor_each_ref(mark_complete);\n+\tmark_recent_complete_commits((unsigned long) now - RECENT);\n \n \tfor (retval = 1; refs ; refs = refs->next) {\n \t\tconst unsigned char *remote = refs->old_sha1;\n \t\tunsigned char local[20];\n+\t\tstruct object *o;\n \n-\t\tif (read_ref(git_path(\"%s\", refs->name), local) < 0 ||\n-\t\t    memcmp(remote, local, 20)) {\n+\t\to = parse_object(remote);\n+\t\tif (!o || !(o->flags & COMPLETE)) {\n \t\t\tretval = 0;\n \t\t\tif (!verbose)\n \t\t\t\tcontinue;\n"},{"id":"10220","messageId":"Pine.LNX.4.64.0510181333380.3369@g5.osdl.org","threadId":"2135","inReplyTo":"7vmzl6r78e.fsf@assigned-by-dhcp.cox.net","subject":"Re: [CORRECTED PATCH] git-fetch-pack: avoid unnecessary zero packing","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-10-18T20:38:31Z","receivedAt":"2005-10-18T20:38:31Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 18 Oct 2005, Junio C Hamano wrote:\n> \n> It strikes me that we could walk from our refs, depth reasonably\n> limited to say 20 or so commit chain and/or last 5 days of\n> commit time, to see if any of the remotes are reachable from our\n> refs and omit issuing \"want\" quite cheaply.  Do you think that\n> would be a worthy change to make things more efficient?\n\nProbably doesn't make a huge difference, but it might be worth trying.\n\nThere's a cheap test you can do _before_ you even start walking: check if \nyou have the object that is pointed to by the remote ref at all. If you \ndon't have it, then you know it can't be reachable from any of the local \nrefs. And if you do have it, the likelihood that it _is_ reachable is \nlikely pretty high. \n\n(I didn't do that for the current fetch-pack optimization, since just \ndoing the read_ref() is likely faster than even bothering with the object \nlookup. But if you start traversing commit lists, it suddenly becomes \nmore worthwhile).\n\nYou'd need to look up the object anyway in order to figure out that it's a \ncommit (or points to a commit).\n\nSo it might be wasting a bit of time, but the good news is that it wastes \ntime on the _client_ side, where we've got plenty.\n\nI'll see if I can come up with a good patch.\n\n\t\tLinus\n"},{"id":"10222","messageId":"Pine.LNX.4.64.0510181339220.3369@g5.osdl.org","threadId":"2135","inReplyTo":"Pine.LNX.4.64.0510181333380.3369@g5.osdl.org","subject":"Re: [CORRECTED PATCH] git-fetch-pack: avoid unnecessary zero packing","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-10-18T20:42:36Z","receivedAt":"2005-10-18T20:42:36Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 18 Oct 2005, Linus Torvalds wrote:\n> \n> I'll see if I can come up with a good patch.\n\nI see you already did. Looks fine. I'd suggest limiting the commits by \nnumber in mark_recent_commit_complete(), because\n\n (a) somebody might have their clock set wrong and you don't want to walk \n     a huge tree just because of something like that.\n (b) you might just have imported a huge history (badly) from somewhere \n     else\n (c) a _lot_ can happen in five days with automated things.\n\nbut yes, the approach looks very sane otherwise.\n\n\t\tLinus\n"},{"id":"10236","messageId":"7v7jcal59y.fsf@assigned-by-dhcp.cox.net","threadId":"2135","inReplyTo":"Pine.LNX.4.64.0510181339220.3369@g5.osdl.org","subject":"Re: [CORRECTED PATCH] git-fetch-pack: avoid unnecessary zero packing","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-10-19T00:27:53Z","receivedAt":"2005-10-19T00:27:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> I see you already did. Looks fine. I'd suggest limiting the commits by \n> number in mark_recent_commit_complete(), because\n>\n>  (a) somebody might have their clock set wrong and you don't want to walk \n>      a huge tree just because of something like that.\n>  (b) you might just have imported a huge history (badly) from somewhere \n>      else\n>  (c) a _lot_ can happen in five days with automated things.\n>\n> but yes, the approach looks very sane otherwise.\n\nWhen you have several dozen commits on top of a head you fetched\nfrom the remote last time you polled them, and the remote has\nnot updated that head since then, it may be worthwhile to have\nthe client dig deeper to avoid asking the server.\n\nWhat I am thinking is:\n\n    - For objects our refs directly refer to, mark them COMPLETE\n      as the patch I sent out.\n\n    - See if we have any objects the remote refs refer to\n      already; find the timestamp of the latest one if we have\n      commits among them, and use its time as the cutoff time.\n\n      It is likely that we have synched with them after that\n      timestamp (either upload or download).  walk the commits\n      from our ref, and mark *everything* that are newer than\n      that timestamp.  This can turn out to be a huge walking\n      but that happens on the client side.\n\nThis way I can get rid of the arbitrary 5-day window, and I do\nnot have to invent another arbitrary number to limit the commits\nwe walk.\n\nIn other words, let's put the burden on the client if its effort\npossibly can help the server.\n"}]}