{"thread":{"id":"8371","subject":"[PATCH] always start looking up objects in the last used pack first","startedAt":"2007-05-31T02:48:13Z","lastAt":"2007-06-02T15:00:52Z","messageCount":6,"participants":["Nicolas Pitre","Shawn O. Pearce","Dana How"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"43672","messageId":"alpine.LFD.0.99.0705302152180.11491@xanadu.home","threadId":"8371","inReplyTo":null,"subject":"[PATCH] always start looking up objects in the last used pack first","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-05-31T02:48:13Z","receivedAt":"2007-05-31T02:48:13Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Jon Smirl said:\n\n| Once an object reference hits a pack file it is very likely that \n| following references will hit the same pack file. So first place to \n| look for an object is the same place the previous object was found.\n\nThis is indeed a good heuristic so here it is. The search always start\nwith the pack where the last object lookup succeeded. If the wanted \nobject is not available there then the search continues with the normal\npack ordering.\n\nTo test this I split the Linux repository into 66 packs and performed a\n\"time git-rev-list --objects --all > /dev/null\". Best results are as \nfollows:\n\n\tPack Sort\t\t\tw/o this patch\tw/ this patch\n\t-------------------------------------------------------------\n\trecent objects last\t\t26.4s\t\t20.9s\n\trecent objects first\t\t24.9s\t\t18.4s\n\nThis shows that the pack order based on object age has some influence, \nbut that the last-used-pack heuristic is even more significant in \nreducing object lookup.\n\nSigned-off-by: Nicolas Pitre --- Note: the \n--max-pack-size to git-repack currently produces packs with old objects \nafter those containing recent objects. The pack sort based on \nfilesystem timestamp is therefore backward for those. This needs to be \nfixed of course, but at least it made me think about this variable for \nthe test.\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex a3637d7..aa6d499 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1687,20 +1688,25 @@ static int matches_pack_name(struct packed_git *p, const char *ig)\n \n static int find_pack_entry(const unsigned char *sha1, struct pack_entry *e, const char **ignore_packed)\n {\n+\tstatic struct packed_git *last_found = (void *)1;\n \tstruct packed_git *p;\n \toff_t offset;\n \n \tprepare_packed_git();\n+\tif (!packed_git)\n+\t\treturn 0;\n+\tp = (last_found == (void *)1) ? packed_git : last_found;\n \n-\tfor (p = packed_git; p; p = p->next) {\n+\tdo {\n \t\tif (ignore_packed) {\n \t\t\tconst char **ig;\n \t\t\tfor (ig = ignore_packed; *ig; ig++)\n \t\t\t\tif (!matches_pack_name(p, *ig))\n \t\t\t\t\tbreak;\n \t\t\tif (*ig)\n-\t\t\t\tcontinue;\n+\t\t\t\tgoto next;\n \t\t}\n+\n \t\toffset = find_pack_entry_one(sha1, p);\n \t\tif (offset) {\n \t\t\t/*\n@@ -1713,14 +1719,23 @@ static int find_pack_entry(const unsigned char *sha1, struct pack_entry *e, cons\n \t\t\t */\n \t\t\tif (p->pack_fd == -1 && open_packed_git(p)) {\n \t\t\t\terror(\"packfile %s cannot be accessed\", p->pack_name);\n-\t\t\t\tcontinue;\n+\t\t\t\tgoto next;\n \t\t\t}\n \t\t\te->offset = offset;\n \t\t\te->p = p;\n \t\t\thashcpy(e->sha1, sha1);\n+\t\t\tlast_found = p;\n \t\t\treturn 1;\n \t\t}\n-\t}\n+\n+\t\tnext:\n+\t\tif (p == last_found)\n+\t\t\tp = packed_git;\n+\t\telse\n+\t\t\tp = p->next;\n+\t\tif (p == last_found)\n+\t\t\tp = p->next;\n+\t} while (p);\n \treturn 0;\n }\n \n"},{"id":"43673","messageId":"alpine.LFD.0.99.0705302320530.11491@xanadu.home","threadId":"8371","inReplyTo":"alpine.LFD.0.99.0705302152180.11491@xanadu.home","subject":"Re: [PATCH] always start looking up objects in the last used pack first","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-05-31T03:24:55Z","receivedAt":"2007-05-31T03:24:55Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 30 May 2007, Nicolas Pitre wrote:\n\n> To test this I split the Linux repository into 66 packs and performed a\n> \"time git-rev-list --objects --all > /dev/null\". Best results are as \n> follows:\n> \n> \tPack Sort\t\t\tw/o this patch\tw/ this patch\n> \t-------------------------------------------------------------\n> \trecent objects last\t\t26.4s\t\t20.9s\n> \trecent objects first\t\t24.9s\t\t18.4s\n> \n> This shows that the pack order based on object age has some influence, \n> but that the last-used-pack heuristic is even more significant in \n> reducing object lookup.\n\nFor reference, the same operation on a fully packed into a single pack \nrepository takes 17.1s. So this looks damn good to me.\n\n\nNicolas\n"},{"id":"43675","messageId":"20070531050211.GV7044@spearce.org","threadId":"8371","inReplyTo":"alpine.LFD.0.99.0705302152180.11491@xanadu.home","subject":"Re: [PATCH] always start looking up objects in the last used pack first","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-05-31T05:02:11Z","receivedAt":"2007-05-31T05:02:11Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre wrote:\n> \tPack Sort\t\t\tw/o this patch\tw/ this patch\n> \t-------------------------------------------------------------\n> \trecent objects last\t\t26.4s\t\t20.9s\n> \trecent objects first\t\t24.9s\t\t18.4s\n\nLooks pretty good.\n \n> +\t\tnext:\n> +\t\tif (p == last_found)\n> +\t\t\tp = packed_git;\n> +\t\telse\n> +\t\t\tp = p->next;\n> +\t\tif (p == last_found)\n> +\t\t\tp = p->next;\n> +\t} while (p);\n\nSo if we didn't find the object in the pack that we found the\nlast object in, we restart our search with the most recent pack?\nWhy not just go to p->next and loop around? If we missed in this\npack and the packs are sorted by recency, wouldn't we want to just\nsearch the next pack?\n\n-- \nShawn.\n"},{"id":"43687","messageId":"alpine.LFD.0.99.0705311015410.11491@xanadu.home","threadId":"8371","inReplyTo":"20070531050211.GV7044@spearce.org","subject":"Re: [PATCH] always start looking up objects in the last used pack first","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-05-31T15:39:29Z","receivedAt":"2007-05-31T15:39:29Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 31 May 2007, Shawn O. Pearce wrote:\n\n> Nicolas Pitre wrote:\n> > \tPack Sort\t\t\tw/o this patch\tw/ this patch\n> > \t-------------------------------------------------------------\n> > \trecent objects last\t\t26.4s\t\t20.9s\n> > \trecent objects first\t\t24.9s\t\t18.4s\n> \n> Looks pretty good.\n> \n> > +\t\tnext:\n> > +\t\tif (p == last_found)\n> > +\t\t\tp = packed_git;\n> > +\t\telse\n> > +\t\t\tp = p->next;\n> > +\t\tif (p == last_found)\n> > +\t\t\tp = p->next;\n> > +\t} while (p);\n> \n> So if we didn't find the object in the pack that we found the\n> last object in, we restart our search with the most recent pack?\n\nRight.\n\n> Why not just go to p->next and loop around? If we missed in this\n> pack and the packs are sorted by recency, wouldn't we want to just\n> search the next pack?\n\nTesting shows that with such a strategy the same operation went from \n18.4s to 19.8s. But this is with split packs resulting from a \ngit-repack -a -d --max-pack-size=...\n\nIf you search for an object and don't find it in the last used pack, \nthat doesn't mean that the object is necessarily in the pack next to the \nlast one. \n\nThe object recency order doesn't actually mean object age. Consider for \nexample 3 commits: the first with everything initially created, the \nsecond commit modifying only half the files, and the third modifying \nonly a quarter of the files. \n\nObject recency order means that the latest commit will see (almost) all \nits objects early and contiguously in the pack stream. The latest commit \nwill still reference between 1/4 to 1/2 of the objects that were created \nfrom the first commit though.\n\nObjects for the middle commit will appear after that, but only those \nthat were not referenced by the latest commit. This means that in this \nexample 3/4 of the needed objects for the middle commit will still be \nfound early in the pack stream.\n\nAnd the first commit will see its objects at the end of the pack stream, \nbut again only those objects that weren't referenced by younger commits \nalready. Up to 1/2 of those objects needed for the first commit might \nbe found in the early portion of the pack stream, or at worst 1/4 in the \nearly portion and 1/4 in the mid portion of the pack stream.\n\nIf a repack creates split packs more or less according to the commit \nseparation above then failure to find an object in the last used pack \nshould really continue to scan available packs from the beginning of the \nlist. Merely going on with the next available pack is a bad move in \nthis case.\n\nHOWEVER...\n\nIf the accumulation of packs is due to multiple fetches/pushes without a \nrepack then the situation is somewhat reversed and much less clear. \nConsidering the scenario above but with a fetch between commits you'd \nend up with this:\n\n1- a large pack with all objects for the first commit.\n\n2- a pack with only half the objects for the second commit (the other \n half is still available in pack #1).\n\n3- a pack with only 1/4 of the objects for the latest commit (the rest \n is shared between pack #1 and pack #2).\n\nHere it is not clear what to do. Given that the last-used-pack \nheuristic makes such a big difference in the split pack it will \ncertainly help a lot in this case too. But where to go when that \nheuristic fails is unclear. If you want to favorize speed for latest \ncommits then I'd argue that going back to the beginning of the list is \nstill the right thing to do. If you want to have a more balanced \nbehavior for all commits (think git-blame) then probably going to the \npack next to the last used would be the best thing to do in this case as \nyounger packs will never contain objects that older commits are \ninterested in.\n\n...\n\nWhich makes me wonder about a possible incremental improvement to my \npatch: on failure to find an object in the last used pack, the search \nshould then start again from the pack containing the commit from which \nthis object search is related to. In the split pack case all commit \nobjects will be located in the first pack so nothing will change there. \nIn the multiple-fetch case then the search will always reset to packs \nnot younger than the commit triggering those object lookups. Question \nis how to implement that nicely...\n\n\nNicolas\n"},{"id":"43806","messageId":"56b7f5510706020753r200fe608wf55a338870f9f1ea@mail.gmail.com","threadId":"8371","inReplyTo":"alpine.LFD.0.99.0705302152180.11491@xanadu.home","subject":"Re: [PATCH] always start looking up objects in the last used pack first","fromName":"Dana How","fromEmail":"danahow@gmail.com","sentAt":"2007-06-02T14:53:35Z","receivedAt":"2007-06-02T14:53:35Z","isPatch":true,"sender":{"key":"danahow@gmail.com","avatar":null},"body":"On 5/30/07, Nicolas Pitre wrote:\n> Jon Smirl said:\n> | Once an object reference hits a pack file it is very likely that\n> | following references will hit the same pack file. So first place to\n> | look for an object is the same place the previous object was found.\n>\n> This is indeed a good heuristic so here it is. The search always start\n> with the pack where the last object lookup succeeded. If the wanted\n> object is not available there then the search continues with the normal\n> pack ordering.\n\nNice numbers for performance,\nespecially your later email showing this makes\nsplit packs almost as quick as one pack.\n\n> Note: the\n> --max-pack-size to git-repack currently produces packs with old objects\n> after those containing recent objects. The pack sort based on\n> filesystem timestamp is therefore backward for those. This needs to be\n> fixed of course, but at least it made me think about this variable for\n> the test.\n\nYes, I was intending to submit a patch to builtin-pack-objects.c\nto reverse the timestamps when split packs were created.\nHaven't got around to it yet.\n-- \nDana L. How danahow@gmail.com +1 650 804 5991 cell\n"},{"id":"43807","messageId":"56b7f5510706020800o10541844t151cb82221d077d5@mail.gmail.com","threadId":"8371","inReplyTo":"alpine.LFD.0.99.0705311015410.11491@xanadu.home","subject":"Re: [PATCH] always start looking up objects in the last used pack first","fromName":"Dana How","fromEmail":"danahow@gmail.com","sentAt":"2007-06-02T15:00:52Z","receivedAt":"2007-06-02T15:00:52Z","isPatch":true,"sender":{"key":"danahow@gmail.com","avatar":null},"body":"On 5/31/07, Nicolas Pitre wrote:\n> Which makes me wonder about a possible incremental improvement to my\n> patch: on failure to find an object in the last used pack, the search\n> should then start again from the pack containing the commit from which\n> this object search is related to. In the split pack case all commit\n> objects will be located in the first pack so nothing will change there.\n> In the multiple-fetch case then the search will always reset to packs\n> not younger than the commit triggering those object lookups. Question\n> is how to implement that nicely...\n\nMy immediate reaction to this patch was that there should be\na last-used-pack per object type. Or perhaps one for commits,\nand one for trees+blobs [since the latter are intermingled]?\nUnfortunately the interface only specifies\nthe SHA-1, not the object type, and certainly not the \"commit\nthis is related to\". I think your related-commit idea could be\nvery useful, but it does require some extra info to be passed\naround which currently is not.\n-- \nDana L. How danahow@gmail.com +1 650 804 5991 cell\n"}]}