{"thread":{"id":"35455","subject":"Ideas to speed up repacking","startedAt":"2013-12-02T23:30:45Z","lastAt":"2013-12-03T19:26:51Z","messageCount":7,"participants":["Martin Fick","Junio C Hamano","Duy Nguyen"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"231397","messageId":"201312021630.45767.mfick@codeaurora.org","threadId":"35455","inReplyTo":null,"subject":"Ideas to speed up repacking","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2013-12-02T23:30:45Z","receivedAt":"2013-12-02T23:30:45Z","isPatch":false,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"I wanted to explore the idea of exploiting knowledge about \nprevious repacks to help speed up future repacks. \n\nI had various ideas that seemed like they might be good \nplaces to start, but things quickly got away from me. \nMainly I wanted to focus on reducing and even sometimes \neliminating reachability calculations since that seems to be \nbe the one major unsolved slow piece during repacking.\n\nMy first line of thinking goes like this: \"After a full \nrepack, reachability of the current refs is known. Exploit \nthat knowledge for future repacks.\" There are some very \nsimple scenarios where if we could figure out how to \nidentify them reliably, I think we could simply avoid \nreachability calculations entirely, and yet end up with the \nsame repacked files as if we had done the reachability \ncalculations. Let me outline some to see if they make sense \nas starting place for further discussion.\n\n-------------\n\n* Setup 1: \n\n Do a full repack. All loose and packed objects are added \nto a single pack file (assumes git config repack options do \nnot create multiple packs).\n\n* Scenario 1:\n\n Start with Setup 1. Nothing has changed on the repo \ncontents (no new object/packs, refs all the same), but \nrepacking config options have changed (for example \ncompression level has changed).\n\n* Scenario 2:\n\n Starts with Setup 1. Add one new pack file that was \npushed to the repo by adding a new ref to the repo (existing \nrefs did not change).\n\n* Scenario 3: \n\n Starts with Setup 1. Add one new pack file that was \npushed to the repo by updating an existing ref with a fast \nforward.\n\n* Scenario 4:\n\n Starts with Setup 1. Add some loose objects to the repo \nvia a local fast forward ref update (I am assuming this is \npossible without adding any new unreferenced objects?)\n\n\nIn all 4 scenarios, I believe we should be able to skip \nhistory traversal and simply grab all objects and repack \nthem into a new file?\n\n-------------\n\nOf the 4 scenarios above, it seems like #3 and #4 are very \ncommon operations (#2 is perhaps even more common for \nGerrit)? If these scenarios can be reliably identified \nsomehow, then perhaps they could be used to reduce repacking \ntime for these scenarios, and later used as building blocks \nto reduce repacking time for other related but slightly more \ncomplicated scenarios (with reduced history walking instead \nof none)?\n\nFor example to identify scenario 1, what if we kept a copy \nof all refs and their shas used during a full repack along \nwith the newly repacked file? A simplistic approach would \nstore them in the same format as the packed-refs file as \npack-.refs. During repacking, if none of the refs have \nchanged and there are no new objects... \n\nThen, if none of the refs have changed and there are new \nobjects, we can just throw the new objects away?\n\n...\n\nI am going to stop here because this email is long enough \nand I wanted to get some feedback on the ideas first before \noffering more solutions.\n\nThanks,\n\n-Martin\n\n-- \nThe Qualcomm Innovation Center, Inc. is a member of Code \nAurora Forum, hosted by The Linux Foundation\n \n"},{"id":"231407","messageId":"xmqqpppepxuu.fsf@gitster.dls.corp.google.com","threadId":"35455","inReplyTo":"201312021630.45767.mfick@codeaurora.org","subject":"Re: Ideas to speed up repacking","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-12-03T00:44:09Z","receivedAt":"2013-12-03T00:44:09Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Martin Fick writes:\n\n> I wanted to explore the idea of exploiting knowledge about \n> previous repacks to help speed up future repacks. \n>\n> I had various ideas that seemed like they might be good \n> places to start, but things quickly got away from me. \n> Mainly I wanted to focus on reducing and even sometimes \n> eliminating reachability calculations since that seems to be \n> be the one major unsolved slow piece during repacking.\n>\n> My first line of thinking goes like this: \"After a full \n> repack, reachability of the current refs is known. Exploit \n> that knowledge for future repacks.\" There are some very \n> simple scenarios where if we could figure out how to \n> identify them reliably, I think we could simply avoid \n> reachability calculations entirely, and yet end up with the \n> same repacked files as if we had done the reachability \n> calculations. Let me outline some to see if they make sense \n> as starting place for further discussion.\n>\n> -------------\n>\n> * Setup 1: \n>\n> Do a full repack. All loose and packed objects are added \n> to a single pack file (assumes git config repack options do \n> not create multiple packs).\n>\n> * Scenario 1:\n>\n> Start with Setup 1. Nothing has changed on the repo \n> contents (no new object/packs, refs all the same), but \n> repacking config options have changed (for example \n> compression level has changed).\n>\n> * Scenario 2:\n>\n> Starts with Setup 1. Add one new pack file that was \n> pushed to the repo by adding a new ref to the repo (existing \n> refs did not change).\n>\n> * Scenario 3: \n>\n> Starts with Setup 1. Add one new pack file that was \n> pushed to the repo by updating an existing ref with a fast \n> forward.\n>\n> * Scenario 4:\n>\n> Starts with Setup 1. Add some loose objects to the repo \n> via a local fast forward ref update (I am assuming this is \n> possible without adding any new unreferenced objects?)\n>\n>\n> In all 4 scenarios, I believe we should be able to skip \n> history traversal and simply grab all objects and repack \n> them into a new file?\n\nIf nothing else has happened in the repository, perhaps, but I\nsuspect that the real problem is how you would prove it. For\nexample, I am guessing that your Scenario 4 could be something like:\n\n : setup #1\n $ git repack -a -d -f\n $ git prune\n\n : scenario #4\n $ git commit --allow-empty -m 'new commit'\n\nwhich would add a single loose object to the repository, advancing\nthe current branch ref by one commit, fast-forwarding relative to\nthe state you were in after setup #1.\n\nBut how would you efficiently prove that it was the only thing that\nhappened? The user could have done this instead of a single commit:\n\n : scenario #4 look-alike\n $ git commit --allow-empty -m 'lost commit'\n $ git reset --hard HEAD^\n $ git commit --allow-empty -m 'new commit'\n\nand the reflog entry for HEAD or the current branch ref for that\nlost commit may be already ancient when you looked at this state.\nYour object database has two loose commits, and you would want to\nlose the older one 'lost commit' which is not reachable.\n\nAlso with Scenario #2, how would you prove that the new pack does\nnot contain any cruft that is not reachable? When receiving a pack\nand updating our refs, we only prove that we have all the objects\nneeded to complete updated refs---we do not reject packs with crufts\nthat are not necessary.\n\nThese two are only examples, and we might be able to convince\nourselves that not pruning (or ejecting cruft from packs) is OK, but\nthat is introducing a different mode of operation, not optimizing\nthe repacking without changing what \"repacking\" means (I am not\nsaying it is bad to change the meaning if we can make a good\nargument between pros-and-cons; a small bloat might be acceptable\nrelative to a good enough performance gain, but only unless the user\nis using repack && prune as a way to eradicate undesirable contents\nout of the object database).\n"},{"id":"231408","messageId":"CACsJy8DJU2YTE1iNdb=fvo0fVOgLUK2mKXUhjcoJh8Ac0wW_EA@mail.gmail.com","threadId":"35455","inReplyTo":"xmqqpppepxuu.fsf@gitster.dls.corp.google.com","subject":"Re: Ideas to speed up repacking","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-12-03T03:27:09Z","receivedAt":"2013-12-03T03:27:09Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Dec 3, 2013 at 7:44 AM, Junio C Hamano wrote:\n>> * Scenario 4:\n>>\n>> Starts with Setup 1. Add some loose objects to the repo\n>> via a local fast forward ref update (I am assuming this is\n>> possible without adding any new unreferenced objects?)\n>>\n>>\n>> In all 4 scenarios, I believe we should be able to skip\n>> history traversal and simply grab all objects and repack\n>> them into a new file?\n>\n> If nothing else has happened in the repository, perhaps, but I\n> suspect that the real problem is how you would prove it. For\n> example, I am guessing that your Scenario 4 could be something like:\n>\n> : setup #1\n> $ git repack -a -d -f\n> $ git prune\n>\n> : scenario #4\n> $ git commit --allow-empty -m 'new commit'\n>\n> which would add a single loose object to the repository, advancing\n> the current branch ref by one commit, fast-forwarding relative to\n> the state you were in after setup #1.\n>\n> But how would you efficiently prove that it was the only thing that\n> happened?\n\nShawn mentioned elsewhere that we could generate bundle header in and\nkeep it in pack-XXX.bh file at pack creation time. With that\ninformation we could verify if a ref has been reset, just fast\nforwarded or even deleted.\n\n> Also with Scenario #2, how would you prove that the new pack does\n> not contain any cruft that is not reachable? When receiving a pack\n> and updating our refs, we only prove that we have all the objects\n> needed to complete updated refs---we do not reject packs with crufts\n> that are not necessary.\n\nWe trust the pack producer to do it correctly, I guess. If a pack\nproducer guarantees not to store any cruft, it could mark the pack\nsomehow.\n-- \nDuy\n"},{"id":"231411","messageId":"xmqqli02pfnf.fsf@gitster.dls.corp.google.com","threadId":"35455","inReplyTo":"CACsJy8DJU2YTE1iNdb=fvo0fVOgLUK2mKXUhjcoJh8Ac0wW_EA@mail.gmail.com","subject":"Re: Ideas to speed up repacking","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-12-03T07:17:24Z","receivedAt":"2013-12-03T07:17:24Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Duy Nguyen writes:\n\n>> If nothing else has happened in the repository, perhaps, but I\n>> suspect that the real problem is how you would prove it. For\n>> example, I am guessing that your Scenario 4 could be something like:\n>>\n>> : setup #1\n>> $ git repack -a -d -f\n>> $ git prune\n>>\n>> : scenario #4\n>> $ git commit --allow-empty -m 'new commit'\n>>\n>> which would add a single loose object to the repository, advancing\n>> the current branch ref by one commit, fast-forwarding relative to\n>> the state you were in after setup #1.\n>>\n>> But how would you efficiently prove that it was the only thing that\n>> happened?\n>\n> Shawn mentioned elsewhere that we could generate bundle header in and\n> keep it in pack-XXX.bh file at pack creation time. With that\n> information we could verify if a ref has been reset, just fast\n> forwarded or even deleted.\n\nWith what information? If you keep the back-then-current information\nand nothing else, how would you differentiate between the simple\nscenario #4 above vs 'lost and new' two commit versions of the\nscenario? The endpoints should both show that one ref (and only one\nref) advanced by one commit, but one has cruft in the object\ndatabase while the other does not.\n\n>> Also with Scenario #2, how would you prove that the new pack does\n>> not contain any cruft that is not reachable? When receiving a pack\n>> and updating our refs, we only prove that we have all the objects\n>> needed to complete updated refs---we do not reject packs with crufts\n>> that are not necessary.\n>\n> We trust the pack producer to do it correctly, I guess. If a pack\n> producer guarantees not to store any cruft, it could mark the pack\n> somehow.\n\nThat is not an answer. Since when do we design to blindly trust\nanybody on the other end of the wire?\n"},{"id":"231420","messageId":"CACsJy8CBOp_5nwm=WWBG_AZ+h6M7L6WpdX4ACeJxwuJ0kqu0Gw@mail.gmail.com","threadId":"35455","inReplyTo":"xmqqli02pfnf.fsf@gitster.dls.corp.google.com","subject":"Re: Ideas to speed up repacking","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-12-03T10:17:57Z","receivedAt":"2013-12-03T10:17:57Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Dec 3, 2013 at 2:17 PM, Junio C Hamano wrote:\n> Duy Nguyen writes:\n>\n>>> If nothing else has happened in the repository, perhaps, but I\n>>> suspect that the real problem is how you would prove it. For\n>>> example, I am guessing that your Scenario 4 could be something like:\n>>>\n>>> : setup #1\n>>> $ git repack -a -d -f\n>>> $ git prune\n>>>\n>>> : scenario #4\n>>> $ git commit --allow-empty -m 'new commit'\n>>>\n>>> which would add a single loose object to the repository, advancing\n>>> the current branch ref by one commit, fast-forwarding relative to\n>>> the state you were in after setup #1.\n>>>\n>>> But how would you efficiently prove that it was the only thing that\n>>> happened?\n>>\n>> Shawn mentioned elsewhere that we could generate bundle header in and\n>> keep it in pack-XXX.bh file at pack creation time. With that\n>> information we could verify if a ref has been reset, just fast\n>> forwarded or even deleted.\n>\n> With what information? If you keep the back-then-current information\n> and nothing else, how would you differentiate between the simple\n> scenario #4 above vs 'lost and new' two commit versions of the\n> scenario? The endpoints should both show that one ref (and only one\n> ref) advanced by one commit, but one has cruft in the object\n> database while the other does not.\n\nYeah I was wrong. Reading Martin's mail again I wonder how we just\n\"grab all objects and skip history traversal\". Who will decide object\norder in the new pack if we don't traverse history and collect path\ninformation.\n-- \nDuy\n"},{"id":"231437","messageId":"xmqqhaapq0xc.fsf@gitster.dls.corp.google.com","threadId":"35455","inReplyTo":"CACsJy8CBOp_5nwm=WWBG_AZ+h6M7L6WpdX4ACeJxwuJ0kqu0Gw@mail.gmail.com","subject":"Re: Ideas to speed up repacking","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-12-03T17:50:07Z","receivedAt":"2013-12-03T17:50:07Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Duy Nguyen writes:\n\n> Reading Martin's mail again I wonder how we just\n> \"grab all objects and skip history traversal\". Who will decide object\n> order in the new pack if we don't traverse history and collect path\n> information.\n\nI vaguely recall raising a related topic for \"quick repack, assuming\neverything in existing packfiles are reachable, that only removes\nloose cruft\" several weeks ago. Once you decide that your quick\nrepack do not care about ejecting objects from existing packs, like\nhow I suspect Martin's outline will lead us to, we can repack the\nreachable loose ones on the recent surface of the history and then\nconcatenate the contents of existing packs, excluding duplicates and\npossibly adjusting the delta base offsets for some entries, without\ntraversing the bulk of the history.\n"},{"id":"231457","messageId":"201312031226.52033.mfick@codeaurora.org","threadId":"35455","inReplyTo":"xmqqhaapq0xc.fsf@gitster.dls.corp.google.com","subject":"Re: Ideas to speed up repacking","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2013-12-03T19:26:51Z","receivedAt":"2013-12-03T19:26:51Z","isPatch":false,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"> Martin Fick writes:\n> > * Setup 1:\n> > Do a full repack. All loose and packed objects are\n> > added\n...\n> > * Scenario 1:\n> > Start with Setup 1. Nothing has changed on the repo\n> > contents (no new object/packs, refs all the same), but\n> > repacking config options have changed (for example\n> > compression level has changed).\n\n\nOn Tuesday, December 03, 2013 10:50:07 am Junio C Hamano \nwrote:\n> Duy Nguyen writes:\n> > Reading Martin's mail again I wonder how we just\n> > \"grab all objects and skip history traversal\". Who will\n> > decide object order in the new pack if we don't\n> > traverse history and collect path information.\n> \n> I vaguely recall raising a related topic for \"quick\n> repack, assuming everything in existing packfiles are\n> reachable, that only removes loose cruft\" several weeks\n> ago. Once you decide that your quick repack do not care\n> about ejecting objects from existing packs, like how I\n> suspect Martin's outline will lead us to, we can repack\n> the reachable loose ones on the recent surface of the\n> history and then concatenate the contents of existing\n> packs, excluding duplicates and possibly adjusting the\n> delta base offsets for some entries, without traversing\n> the bulk of the history.\n\n>From this, it sounds like scenario 1 (a single pack being \nrepacked) might then be doable (just trying to establish a \nreally simple baseline)? Except that it would potentially \nnot result in the same ordering without traversing history? \nOr, would the current pack ordering be preserved and thus be \ncorrect?\n\n-Martin\n\n-- \nThe Qualcomm Innovation Center, Inc. is a member of Code \nAurora Forum, hosted by The Linux Foundation\n \n"}]}