{"thread":{"id":"38927","subject":"[PATCH] reachable: only mark local objects as recent","startedAt":"2015-03-27T11:32:41Z","lastAt":"2015-04-17T17:18:56Z","messageCount":4,"participants":["Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"258589","messageId":"20150327113240.GA7781@peff.net","threadId":"38927","inReplyTo":null,"subject":"[PATCH] reachable: only mark local objects as recent","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-03-27T11:32:41Z","receivedAt":"2015-03-27T11:32:41Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When pruning and repacking a repository that has an\nalternate object store configured, we may traverse a large\nnumber of objects in the alternate. This serves no purpose,\nand may be expensive to do. A longer explanation is below.\n\nCommits d3038d2 and abcb865 taught prune and pack-objects\n(respectively) to treat \"recent\" objects as tips for\nreachability, so that we keep whole chunks of history. They\nbuilt on the object traversal in 660c889 (sha1_file: add\nfor_each iterators for loose and packed objects,\n2014-10-15), which covers both local and alternate objects.\n\nIn both cases, covering alternate objects is unnecessary, as\nboth commands can only drop objects from the local\nrepository. In the case of prune, we traverse only the local\nobject directory. And in the case of repacking, while we may\nor may not include local objects in our pack, we will never\nreach into the alternate with \"repack -d\". The \"-l\" option\nis only a question of whether we are migrating objects from\nthe alternate into our repository, or leaving them\nuntouched.\n\nIt is possible that we may drop an object that is depended\nupon by another object in the alternate. For example,\nimagine two repositories, A and B, with A pointing to B as\nan alternate. Now imagine a commit that is in B which\nreferences a tree that is only in A. Traversing from recent\nobjects in B might prevent A from dropping that tree. But\nthis case isn't worth covering. Repo B should take\nresponsibility for its own objects. It would never have had\nthe commit in the first place if it did not also have the\ntree, and assuming it is using the same \"keep recent chunks\nof history\" scheme, then it would itself keep the tree, as\nwell.\n\nSo checking the alternate objects is not worth doing, and\ncome with a significant performance impact. In both cases,\nwe skip any recent objects that have already been marked\nSEEN (i.e., that we know are already reachable for prune, or\nincluded in the pack for a repack). So there is a slight\nwaste of time in opening the alternate packs at all, only to\nnotice that we have already considered each object. But much\nworse, the alternate repository may have a large number of\nobjects that are not reachable from the local repository at\nall, and we end up adding them to the traversal.\n\nWe can fix this by considering only local unseen objects.\n\nSigned-off-by: Jeff King \n---\nThe problem presumably started in v2.2.0, so this is not a high-priority\nregression for 2.4.0-rc0. Certainly I encountered some cases in the wild\nthat have a very serious slowdown (e.g., going from a few seconds to\nseveral minutes), but those were rather pathological and related to the\nway we use alternates at GitHub. So definitely worth fixing, but I'm not\nsure if anybody is as strongly affected as GitHub was.\n\nAlso, a keen observer may notice in the code below that all callers pass\nthe new LOCAL_ONLY flag. So it would also be fine to just change the\nsemantics of for_each_loose_object and for_each_packed_object. What I\nhave here is more flexible, but I don't know if that flexibility would\never be useful or not.\n\n cache.h | 8 +++++---\n reachable.c | 6 ++++--\n sha1_file.c | 9 +++++++--\n 3 files changed, 16 insertions(+), 7 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 3d3244b..2391c9f 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1289,14 +1289,16 @@ int for_each_loose_file_in_objdir_buf(struct strbuf *path,\n \n /*\n * Iterate over loose and packed objects in both the local\n- * repository and any alternates repositories.\n+ * repository and any alternates repositories (unless the\n+ * LOCAL_ONLY flag is set).\n */\n+#define FOR_EACH_OBJECT_LOCAL_ONLY 0x1\n typedef int each_packed_object_fn(const unsigned char *sha1,\n \t\t\t\t struct packed_git *pack,\n \t\t\t\t uint32_t pos,\n \t\t\t\t void *data);\n-extern int for_each_loose_object(each_loose_object_fn, void *);\n-extern int for_each_packed_object(each_packed_object_fn, void *);\n+extern int for_each_loose_object(each_loose_object_fn, void *, unsigned flags);\n+extern int for_each_packed_object(each_packed_object_fn, void *, unsigned flags);\n \n struct object_info {\n \t/* Request */\ndiff --git a/reachable.c b/reachable.c\nindex a647267..69fa685 100644\n--- a/reachable.c\n+++ b/reachable.c\n@@ -142,10 +142,12 @@ int add_unseen_recent_objects_to_traversal(struct rev_info *revs,\n \tdata.revs = revs;\n \tdata.timestamp = timestamp;\n \n-\tr = for_each_loose_object(add_recent_loose, &data);\n+\tr = for_each_loose_object(add_recent_loose, &data,\n+\t\t\t\t FOR_EACH_OBJECT_LOCAL_ONLY);\n \tif (r)\n \t\treturn r;\n-\treturn for_each_packed_object(add_recent_packed, &data);\n+\treturn for_each_packed_object(add_recent_packed, &data,\n+\t\t\t\t FOR_EACH_OBJECT_LOCAL_ONLY);\n }\n \n void mark_reachable_objects(struct rev_info *revs, int mark_reflog,\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 88f06ba..3e34eb5 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -3418,7 +3418,7 @@ static int loose_from_alt_odb(struct alternate_object_database *alt,\n \treturn r;\n }\n \n-int for_each_loose_object(each_loose_object_fn cb, void *data)\n+int for_each_loose_object(each_loose_object_fn cb, void *data, unsigned flags)\n {\n \tstruct loose_alt_odb_data alt;\n \tint r;\n@@ -3428,6 +3428,9 @@ int for_each_loose_object(each_loose_object_fn cb, void *data)\n \tif (r)\n \t\treturn r;\n \n+\tif (flags & FOR_EACH_OBJECT_LOCAL_ONLY)\n+\t\treturn 0;\n+\n \talt.cb = cb;\n \talt.data = data;\n \treturn foreach_alt_odb(loose_from_alt_odb, &alt);\n@@ -3452,13 +3455,15 @@ static int for_each_object_in_pack(struct packed_git *p, each_packed_object_fn c\n \treturn r;\n }\n \n-int for_each_packed_object(each_packed_object_fn cb, void *data)\n+int for_each_packed_object(each_packed_object_fn cb, void *data, unsigned flags)\n {\n \tstruct packed_git *p;\n \tint r = 0;\n \n \tprepare_packed_git();\n \tfor (p = packed_git; p; p = p->next) {\n+\t\tif ((flags & FOR_EACH_OBJECT_LOCAL_ONLY) && !p->pack_local)\n+\t\t\tcontinue;\n \t\tr = for_each_object_in_pack(p, cb, data);\n \t\tif (r)\n \t\t\tbreak;\n-- \n2.4.0.rc0.327.g6ec0264\n"},{"id":"258597","messageId":"xmqqa8yyw9je.fsf@gitster.dls.corp.google.com","threadId":"38927","inReplyTo":"20150327113240.GA7781@peff.net","subject":"Re: [PATCH] reachable: only mark local objects as recent","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-03-27T19:00:05Z","receivedAt":"2015-03-27T19:00:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> It is possible that we may drop an object that is depended\n> upon by another object in the alternate. For example,\n> imagine two repositories, A and B, with A pointing to B as\n> an alternate. Now imagine a commit that is in B which\n> references a tree that is only in A. Traversing from recent\n> objects in B might prevent A from dropping that tree. But\n> this case isn't worth covering. Repo B should take\n> responsibility for its own objects. It would never have had\n> the commit in the first place if it did not also have the\n> tree, and assuming it is using the same \"keep recent chunks\n> of history\" scheme, then it would itself keep the tree, as\n> well.\n\nIn other words, if you have a loop in dependency chain among\nalternate repositories, your set-up is broken by definition.\n\nWhich makes sense to me.\n\nThanks.\n"},{"id":"259561","messageId":"20150417132824.GA13192@peff.net","threadId":"38927","inReplyTo":"xmqqa8yyw9je.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] reachable: only mark local objects as recent","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-17T13:28:25Z","receivedAt":"2015-04-17T13:28:25Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Mar 27, 2015 at 12:00:05PM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > It is possible that we may drop an object that is depended\n> > upon by another object in the alternate. For example,\n> > imagine two repositories, A and B, with A pointing to B as\n> > an alternate. Now imagine a commit that is in B which\n> > references a tree that is only in A. Traversing from recent\n> > objects in B might prevent A from dropping that tree. But\n> > this case isn't worth covering. Repo B should take\n> > responsibility for its own objects. It would never have had\n> > the commit in the first place if it did not also have the\n> > tree, and assuming it is using the same \"keep recent chunks\n> > of history\" scheme, then it would itself keep the tree, as\n> > well.\n> \n> In other words, if you have a loop in dependency chain among\n> alternate repositories, your set-up is broken by definition.\n> \n> Which makes sense to me.\n> \n> Thanks.\n\nI don't see this patch in \"pu\" or \"What's Cooking\" at all. Did it get\ndropped?\n\nIt does fix a performance regression, but the problem is in v2.2, so I\ndon't think it's urgent for v2.4-rc.\n\n-Peff\n"},{"id":"259579","messageId":"xmqq618ur7un.fsf@gitster.dls.corp.google.com","threadId":"38927","inReplyTo":"20150417132824.GA13192@peff.net","subject":"Re: [PATCH] reachable: only mark local objects as recent","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-04-17T17:18:56Z","receivedAt":"2015-04-17T17:18:56Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Fri, Mar 27, 2015 at 12:00:05PM -0700, Junio C Hamano wrote:\n>\n>> Jeff King writes:\n>> \n>> > It is possible that we may drop an object that is depended\n>> > upon by another object in the alternate. For example,\n>> > imagine two repositories, A and B, with A pointing to B as\n>> > an alternate. Now imagine a commit that is in B which\n>> > references a tree that is only in A. Traversing from recent\n>> > objects in B might prevent A from dropping that tree. But\n>> > this case isn't worth covering. Repo B should take\n>> > responsibility for its own objects. It would never have had\n>> > the commit in the first place if it did not also have the\n>> > tree, and assuming it is using the same \"keep recent chunks\n>> > of history\" scheme, then it would itself keep the tree, as\n>> > well.\n>> \n>> In other words, if you have a loop in dependency chain among\n>> alternate repositories, your set-up is broken by definition.\n>> \n>> Which makes sense to me.\n>> \n>> Thanks.\n>\n> I don't see this patch in \"pu\" or \"What's Cooking\" at all. Did it get\n> dropped?\n\nIt appears that way (rather, \"never picked up\"). Thanks for\nreminding.\n\n\n\n\n>\n> It does fix a performance regression, but the problem is in v2.2, so I\n> don't think it's urgent for v2.4-rc.\n"}]}