{"thread":{"id":"29866","subject":"[PATCH/RFC] Make the largest pack the first one in the pack search queue","startedAt":"2012-03-07T03:01:48Z","lastAt":"2012-03-07T03:21:17Z","messageCount":2,"participants":["Nguyễn Thái Ngọc Duy","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"186286","messageId":"1331089308-16706-1-git-send-email-pclouds@gmail.com","threadId":"29866","inReplyTo":null,"subject":"[PATCH/RFC] Make the largest pack the first one in the pack search queue","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-03-07T03:01:48Z","receivedAt":"2012-03-07T03:01:48Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"When git looks for an object in a pack, it has to go through all the\npack indexes. Pack order becomes important because if the pack is\nfound early, the search stops early. Git sorts packs by mostly by\nmtime, favoring recent packs.\n\nThis strategy however puts the main pack at the bottom because the\nmain pack is usually created at clone time and occasional \"repack -ad\",\nso likely the oldest. Though being the largest pack, this pack is\nlikely hit (even latest commits have unchanged parts, which is likely\nin the main pack).\n\nThis patch changes pack order a little bit, putting the main pack on\ntop, the rest is ordered as usual. When we look for latest changes,\nit'll likely miss the main pack. But after the first miss,\n\"last_found_pack\" optimization kicks in, thus reduce the miss cost.\n\nI modified find_pack_entry() to record pack misses, then do a few\ncommonly used commands like \"git diff\", \"git diff --cached\", \"git diff\nHEAD\", \"git status\", \"git branch -v\", \"git log\"... Pack miss decreased\nin all cases. So I think this might be a good heuristic. But this is\nmicro-optmization and probably does not give us any significant\nperformance gain.\n\nA probably better way to improve too-many-packs situation is create\nmeta-index in memory for small packs.\n\nAn implementation note, packed_git->num_objects should be used to\ndetermine the largest pack, but that field may not be available until\nopen_packed_git() is called. pack_size should be a good enough\napproximation.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n sha1_file.c |   21 ++++++++++++++++++++-\n 1 files changed, 20 insertions(+), 1 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 798cd46..05ece2d 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1072,6 +1072,24 @@ static int sort_pack(const void *a_, const void *b_)\n \treturn -1;\n }\n \n+static int sort_pack_by_size(const void *a_, const void *b_)\n+{\n+\tstruct packed_git *a = *((struct packed_git **)a_);\n+\tstruct packed_git *b = *((struct packed_git **)b_);\n+\tint st;\n+\n+\t/*\n+\t * Local packs tend to contain objects specific to our\n+\t * variant of the project than remote ones.  In addition,\n+\t * remote ones could be on a network mounted filesystem.\n+\t * Favor local ones for these reasons.\n+\t */\n+\tst = a->pack_local - b->pack_local;\n+\tif (st)\n+\t\treturn -st;\n+\treturn b->pack_size - a->pack_size;\n+}\n+\n static void rearrange_packed_git(void)\n {\n \tstruct packed_git **ary, *p;\n@@ -1087,7 +1105,8 @@ static void rearrange_packed_git(void)\n \tfor (n = 0, p = packed_git; p; p = p->next)\n \t\tary[n++] = p;\n \n-\tqsort(ary, n, sizeof(struct packed_git *), sort_pack);\n+\tqsort(ary, n, sizeof(struct packed_git *), sort_pack_by_size);\n+\tqsort(ary + 1, n - 1, sizeof(struct packed_git *), sort_pack);\n \n \t/* link them back again */\n \tfor (i = 0; i < n - 1; i++)\n-- \n1.7.3.1.256.g2539c.dirty\n"},{"id":"186287","messageId":"7vhay1p042.fsf@alter.siamese.dyndns.org","threadId":"29866","inReplyTo":"1331089308-16706-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH/RFC] Make the largest pack the first one in the pack search queue","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-03-07T03:21:17Z","receivedAt":"2012-03-07T03:21:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"As the expected pay off from this change seems to be only based on a\nhunch, it is hard for anybody to give useful comments on a patch\nlike this without benchmarks. As the implementation is more or less\ntrivial, the only thing anybody could say is \"if changing the search\norder is proved to be useful, the patch seems sane,\" but the \"if\"\npart poses a lot bigger question than the patch itself.\n\nAt this late in the cycle, I would rather see a contributor with\nmany in-flight topics to start sifting his own existing topics into\nthe ones to be polished for the next release and the others to be\npostponed for the next cycle, instead of adding yet more topics with\nuntied loose ends at this point.\n\nThanks.\n"}]}