{"thread":{"id":"30263","subject":"gc --aggressive","startedAt":"2012-04-17T16:16:15Z","lastAt":"2012-05-01T20:02:57Z","messageCount":26,"participants":["Jay Soffian","Matthieu Moy","Jeff King","Junio C Hamano","Andreas Ericsson","Nicolas Pitre"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"189533","messageId":"CAG+J_DzO=UZ56PjnSCRaTdj8pBSYc5PFofw1QHy42c5pHMK_HQ@mail.gmail.com","threadId":"30263","inReplyTo":null,"subject":"gc --aggressive","fromName":"Jay Soffian","fromEmail":"jaysoffian@gmail.com","sentAt":"2012-04-17T16:16:15Z","receivedAt":"2012-04-17T16:16:15Z","isPatch":false,"sender":{"key":"jaysoffian@gmail.com","avatar":"https://avatars.githubusercontent.com/u/155970?v=4"},"body":"For a couple years now I've had a maintenance script which repacks all\nthe repos at @dayjob thusly:\n\n  git config repack.usedeltabaseoffset true\n  git config pack.compression 9\n  git config pack.indexversion 2\n  git config gc.autopacklimit 4\n  git config gc.packrefs true\n  git config gc.reflogexpire never\n  git config gc.reflogexpireunreachable never\n  git gc --auto --aggressive --prune\n\nThis has worked fine on repos large and small. However, starting a\ncouple days ago git started running out of memory on a relatively\nmodest repo[*] while repacking on a Linux box with 12GB memory (+ 12GB\nswap). I am able to gc the repo by either removing --aggressive or\n.keep'ing the oldest pack.\n\n[*] Stats:\n\n  du -hs objects\n  141M\tobjects\n\n  git count-objects -v\n  count: 0\n  size: 0\n  in-pack: 57656\n  packs: 37\n  size-pack: 143811\n  prune-packable: 0\n  garbage: 0\n\n  git version 1.7.10\n\nI've since found a message from Shawn recommending against using --aggressive:\n\n  http://groups.google.com/group/repo-discuss/msg/d2462eed67813571\n\n> Junio Hamano and I looked at things a few weeks ago; it turns out the\n> --aggressive flag doesn't generally provide a benefit like we thought\n> it would. It would be safe to remove from your GC script, and will\n> speed things up considerably.\n\nA couple questions:\n\n1) If --aggressive does not generally provide a benefit, should it be\nmade a no-op?\n\n2) Is it expected that gc --aggressive would run out of memory on this repo?\n\nI've posted the repo in case anyone wants to take a look:\n\n  http://dl.dropbox.com/u/2138120/WebKit-trimmed.git.zip\n\nj.\n"},{"id":"189540","messageId":"CAG+J_DyqvCxwd6+gzixQEk6SxMZF0qsXKcJPaU6imsJdFQ-64g@mail.gmail.com","threadId":"30263","inReplyTo":"CAG+J_DzO=UZ56PjnSCRaTdj8pBSYc5PFofw1QHy42c5pHMK_HQ@mail.gmail.com","subject":"Re: gc --aggressive","fromName":"Jay Soffian","fromEmail":"jaysoffian@gmail.com","sentAt":"2012-04-17T17:53:37Z","receivedAt":"2012-04-17T17:53:37Z","isPatch":false,"sender":{"key":"jaysoffian@gmail.com","avatar":"https://avatars.githubusercontent.com/u/155970?v=4"},"body":"On Tue, Apr 17, 2012 at 12:16 PM, Jay Soffian <jaysoffian@gmail.com> wrote:\n> This has worked fine on repos large and small. However, starting a\n> couple days ago git started running out of memory on a relatively\n> modest repo[*] while repacking on a Linux box with 12GB memory (+ 12GB\n> swap). I am able to gc the repo by either removing --aggressive or\n> .keep'ing the oldest pack.\n\nExperimentally, setting pack.windowMemory = 256m keeps git memory\nusage < 4.5 GB during an aggressive repack.\n\nIronically I end up with a slightly worse pack (63115590 bytes vs\n61518628 bytes) than not using --aggressive. I assume this is because\npack-objects found a better delta chain during the previous aggressive\nrepack when windowMemory was not set.\n\n> 1) If --aggressive does not generally provide a benefit, should it be\n> made a no-op?\n\nI guess I'll revise this question: perhaps --aggressive should be\nbetter explained/discouraged. I found a message from Jeff last month\nand stole his words for this patch:\n\n<snip>\ndiff --git i/Documentation/git-gc.txt w/Documentation/git-gc.txt\nindex 815afcb922..ca5bf8b51e 100644\n--- i/Documentation/git-gc.txt\n+++ w/Documentation/git-gc.txt\n@@ -37,9 +37,8 @@ OPTIONS\n \tUsually 'git gc' runs very quickly while providing good disk\n \tspace utilization and performance.  This option will cause\n \t'git gc' to more aggressively optimize the repository at the expense\n-\tof taking much more time.  The effects of this optimization are\n-\tpersistent, so this option only needs to be used occasionally; every\n-\tfew hundred changesets or so.\n+\tof taking much more time and potentially using greater memory. This\n+\toption is rarely needed. See Repacking below.\n\n --auto::\n \tWith this option, 'git gc' checks whether any housekeeping is\n@@ -138,6 +137,39 @@ If you are expecting some objects to be collected\nand they aren't, check\n all of those locations and decide whether it makes sense in your case to\n remove those references.\n\n+Repacking\n+---------\n+\n+Under the covers 'git gc' calls several commands to optimize the repository.\n+The most significant of these with respect to repository size and general\n+performance is linkgit:git-repack[1]. There are basically three levels of\n+'gc' with respect to repacking:\n+\n+ 1. `git gc --auto`; if there are too many loose objects (`gc.auto`), they\n+    all go into a new incremental pack. If there are already too many\n+    packs (`gc.autopacklimit`), all of the existing packs are re-packed\n+    together.\n+\n+    Making an incremental pack is by far the fastest because the speed is\n+    independent of the existing repository history. If git packs\n+    everything together, it should be more or less the same as (2).\n+\n+ 2. `git gc`; this packs everything into a single pack. It uses default\n+    window and depth parameters, but importantly, it reuses existing\n+    deltas. Doing so makes the delta compression phase much faster, and it\n+    often makes the writing phase faster (because for older objects, git\n+    is primarily streaming them right out of the existing pack). On a big\n+    repository though, this does do a lot of I/O, because git has to\n+    rewrite the whole pack.\n+\n+ 3. `git gc --aggressive`; this is often much slower than (2) because git\n+    throws out all of the existing deltas and recomputes them from\n+    scratch. It uses a higher window parameter meaning it will spend\n+    more time computing, and it may end up with a smaller pack. However,\n+    unless the repository is known to have initially been poorly packed,\n+    this option is not needed and will just cause git to perform\n+    extra work.\n+\n HOOKS\n -----\n\n@@ -147,6 +179,7 @@ linkgit:githooks[5] for more information.\n\n SEE ALSO\n --------\n+linkgit:git-pack-refs[1]\n linkgit:git-prune[1]\n linkgit:git-reflog[1]\n linkgit:git-repack[1]\n</snip>\n\nThoughts?\n"},{"id":"189569","messageId":"vpqbomqqdxo.fsf@bauges.imag.fr","threadId":"30263","inReplyTo":"CAG+J_DyqvCxwd6+gzixQEk6SxMZF0qsXKcJPaU6imsJdFQ-64g@mail.gmail.com","subject":"Re: gc --aggressive","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@grenoble-inp.fr","sentAt":"2012-04-17T20:52:03Z","receivedAt":"2012-04-17T20:52:03Z","isPatch":false,"sender":{"key":"matthieu.moy@grenoble-inp.fr","avatar":"https://gravatar.com/avatar/72c8a2705971a25dfaff23cece15130d405685845d911aedd5667ace277f3fc5?d=mp&s=160"},"body":"Jay Soffian <jaysoffian@gmail.com> writes:\n\n> + 3. `git gc --aggressive`; this is often much slower than (2) because git\n> +    throws out all of the existing deltas and recomputes them from\n> +    scratch. It uses a higher window parameter meaning it will spend\n> +    more time computing, and it may end up with a smaller pack. However,\n> +    unless the repository is known to have initially been poorly packed,\n> +    this option is not needed and will just cause git to perform\n> +    extra work.\n\nI like your patch.\n\nMaybe you should elaborate on \"unless the repository is known to have\ninitially been poorly packed\". My understanding is that --aggressive was\nimplemented to be called after an import from another VCS that would\nhave computed very poor deltas, but I'm not sure about the details.\n\n-- \nMatthieu Moy\nhttp://www-verimag.imag.fr/~moy/\n"},{"id":"189574","messageId":"20120417215801.GA10797@sigill.intra.peff.net","threadId":"30263","inReplyTo":"vpqbomqqdxo.fsf@bauges.imag.fr","subject":"Re: gc --aggressive","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-04-17T21:58:01Z","receivedAt":"2012-04-17T21:58:01Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Apr 17, 2012 at 10:52:03PM +0200, Matthieu Moy wrote:\n\n> Jay Soffian <jaysoffian@gmail.com> writes:\n> \n> > + 3. `git gc --aggressive`; this is often much slower than (2) because git\n> > +    throws out all of the existing deltas and recomputes them from\n> > +    scratch. It uses a higher window parameter meaning it will spend\n> > +    more time computing, and it may end up with a smaller pack. However,\n> > +    unless the repository is known to have initially been poorly packed,\n> > +    this option is not needed and will just cause git to perform\n> > +    extra work.\n> \n> I like your patch.\n\nMe too. I guess it is not surprising since I wrote the initial draft. ;)\n\n> Maybe you should elaborate on \"unless the repository is known to have\n> initially been poorly packed\". My understanding is that --aggressive was\n> implemented to be called after an import from another VCS that would\n> have computed very poor deltas, but I'm not sure about the details.\n\nYes, that's exactly it. fast-import will generate packs, but they are\noften not optimal. So if you have done a big import, you should\ndefinitely \"git gc --aggressive\" as the final step. I don't know how\nsomething like a remote-helper would work, where it is fast-importing\nlittle bits at a time. Probably a regular repack would be fine, since it\nwill be considering deltas between objects in different packs anyway.\n\n-Peff\n"},{"id":"189578","messageId":"20120417220838.GB10797@sigill.intra.peff.net","threadId":"30263","inReplyTo":"CAG+J_DzO=UZ56PjnSCRaTdj8pBSYc5PFofw1QHy42c5pHMK_HQ@mail.gmail.com","subject":"Re: gc --aggressive","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-04-17T22:08:38Z","receivedAt":"2012-04-17T22:08:38Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Apr 17, 2012 at 12:16:15PM -0400, Jay Soffian wrote:\n\n> For a couple years now I've had a maintenance script which repacks all\n> the repos at @dayjob thusly:\n> \n>   git config repack.usedeltabaseoffset true\n>   git config pack.compression 9\n>   git config pack.indexversion 2\n>   git config gc.autopacklimit 4\n>   git config gc.packrefs true\n>   git config gc.reflogexpire never\n>   git config gc.reflogexpireunreachable never\n>   git gc --auto --aggressive --prune\n> \n> This has worked fine on repos large and small. However, starting a\n> couple days ago git started running out of memory on a relatively\n> modest repo[*] while repacking on a Linux box with 12GB memory (+ 12GB\n> swap). I am able to gc the repo by either removing --aggressive or\n> .keep'ing the oldest pack.\n\nI wonder where the memory is going. In theory, the memory consumption\nfor packing comes from keeping all of the objects for a given window in\nmemory (so we are looking for a delta for object X, and we have a window\nof Y[0]..Y[$window] objects that we will consider). And for a\nmulti-threaded pack, that's per-thread.\n\nHow many cores are there on this box? Have you tried setting\npack.windowMemory to (12 / # of cores) or thereabouts?\n\n> 1) If --aggressive does not generally provide a benefit, should it be\n> made a no-op?\n\nIn your case, I think it is overkill. But it seems lame that git _can't_\ndo a full repack on such a beefy machine. You don't want to do it all\nthe time, but you might want to do it at least once.\n\n-Peff\n"},{"id":"189581","messageId":"7vr4vmm29z.fsf@alter.siamese.dyndns.org","threadId":"30263","inReplyTo":"20120417220838.GB10797@sigill.intra.peff.net","subject":"Re: gc --aggressive","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-17T22:17:28Z","receivedAt":"2012-04-17T22:17:28Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> ...\n> I wonder where the memory is going. In theory, the memory consumption\n> for packing comes from keeping all of the objects for a given window in\n> memory (so we are looking for a delta for object X, and we have a window\n> of Y[0]..Y[$window] objects that we will consider). And for a\n> multi-threaded pack, that's per-thread.\n>\n> How many cores are there on this box? Have you tried setting\n> pack.windowMemory to (12 / # of cores) or thereabouts?\n\nHrm, from the end-user's point of view, it appears that pack.windowMemory\nought to mean the total without having to worry about the division of it\nacross threads (which the implementation should be responsible for).\n\n> ... But it seems lame that git _can't_\n> do a full repack on such a beefy machine. You don't want to do it all\n> the time, but you might want to do it at least once.\n\nTrue.\n"},{"id":"189582","messageId":"20120417221849.GA11936@sigill.intra.peff.net","threadId":"30263","inReplyTo":"7vr4vmm29z.fsf@alter.siamese.dyndns.org","subject":"Re: gc --aggressive","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-04-17T22:18:49Z","receivedAt":"2012-04-17T22:18:49Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Apr 17, 2012 at 03:17:28PM -0700, Junio C Hamano wrote:\n\n> > How many cores are there on this box? Have you tried setting\n> > pack.windowMemory to (12 / # of cores) or thereabouts?\n> \n> Hrm, from the end-user's point of view, it appears that pack.windowMemory\n> ought to mean the total without having to worry about the division of it\n> across threads (which the implementation should be responsible for).\n\nAgreed. I had to look in the code to check which it meant. I'm not sure\nwe can change it without regressing existing users, though.\n\n-Peff\n"},{"id":"189586","messageId":"7vmx6am1h9.fsf@alter.siamese.dyndns.org","threadId":"30263","inReplyTo":"20120417221849.GA11936@sigill.intra.peff.net","subject":"Re: gc --aggressive","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-17T22:34:42Z","receivedAt":"2012-04-17T22:34:42Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Tue, Apr 17, 2012 at 03:17:28PM -0700, Junio C Hamano wrote:\n>\n>> > How many cores are there on this box? Have you tried setting\n>> > pack.windowMemory to (12 / # of cores) or thereabouts?\n>> \n>> Hrm, from the end-user's point of view, it appears that pack.windowMemory\n>> ought to mean the total without having to worry about the division of it\n>> across threads (which the implementation should be responsible for).\n>\n> Agreed. I had to look in the code to check which it meant. I'm not sure\n> we can change it without regressing existing users, though.\n\nThis is a tangent, but I noticed that the canned settings for \"aggressive\"\nuse an arbitrarily hardcoded value of depth=250 and window=250 (tweakable\nwith gc.aggressiveWindow).\n\nEven though a shallower depth does cause base candidates with too long a\nchain hanging to be evicted prematurely while it is still in window and\nwill lead to smaller memory consumption, I do not think the value of\n\"depth\" affects the pack-time memory consumption too much.  But the\nruntime performance of the resulting pack may not be great (in the worst\ncase you would have to undelta 249 times to get to the object data).  We\nmay want to loosen it a bit.\n\nAlso it might make sense to make the window size a bit more flexible\ndepending on the nature of your history (you would get bigger benefit with\nlarger window when your history has fine grained commits; if there are not\nmany few-liner commits, larger window may not help you that much).\n"},{"id":"189611","messageId":"4F8E8003.6000206@op5.se","threadId":"30263","inReplyTo":"20120417221849.GA11936@sigill.intra.peff.net","subject":"Re: gc --aggressive","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2012-04-18T08:49:07Z","receivedAt":"2012-04-18T08:49:07Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"On 04/18/2012 12:18 AM, Jeff King wrote:\n> On Tue, Apr 17, 2012 at 03:17:28PM -0700, Junio C Hamano wrote:\n> \n>>> How many cores are there on this box? Have you tried setting\n>>> pack.windowMemory to (12 / # of cores) or thereabouts?\n>>\n>> Hrm, from the end-user's point of view, it appears that pack.windowMemory\n>> ought to mean the total without having to worry about the division of it\n>> across threads (which the implementation should be responsible for).\n> \n> Agreed. I had to look in the code to check which it meant. I'm not sure\n> we can change it without regressing existing users, though.\n> \n\nIntroduce a new one.\n\ncore.maxmemoryusage = <something>, which acts as an upper bound in all\ncodepaths where we actually keep track.\n\n-- \nAndreas Ericsson                   andreas.ericsson@op5.se\nOP5 AB                             www.op5.se\nTel: +46 8-230225                  Fax: +46 8-230231\n\nConsidering the successes of the wars on alcohol, poverty, drugs and\nterror, I think we should give some serious thought to declaring war\non peace.\n"},{"id":"190234","messageId":"20120428122533.GA12098@sigill.intra.peff.net","threadId":"30263","inReplyTo":"vpqbomqqdxo.fsf@bauges.imag.fr","subject":"Re: gc --aggressive","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-04-28T12:25:33Z","receivedAt":"2012-04-28T12:25:33Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Apr 17, 2012 at 10:52:03PM +0200, Matthieu Moy wrote:\n\n> Jay Soffian <jaysoffian@gmail.com> writes:\n> \n> > + 3. `git gc --aggressive`; this is often much slower than (2) because git\n> > +    throws out all of the existing deltas and recomputes them from\n> > +    scratch. It uses a higher window parameter meaning it will spend\n> > +    more time computing, and it may end up with a smaller pack. However,\n> > +    unless the repository is known to have initially been poorly packed,\n> > +    this option is not needed and will just cause git to perform\n> > +    extra work.\n> \n> I like your patch.\n> \n> Maybe you should elaborate on \"unless the repository is known to have\n> initially been poorly packed\". My understanding is that --aggressive was\n> implemented to be called after an import from another VCS that would\n> have computed very poor deltas, but I'm not sure about the details.\n\nCoincidentally, I came across a case last week that shows --aggressive\nproviding a large improvement. And it's a public repo, so I was able to\ngrab a snapshot of the pre-packed state to experiment on and share.\n\nThe current packfile is ~246M. It was produced over time by pushes into\nthe repository, which were then eventually grouped into a single pack by\n\"git gc\" (I'm not sure of the exact history, but this may even have been\na set of \"gc --auto\" calls over time).\n\nHere's a list of commands and the pack sizes they yield on the repo:\n\n  1. `git repack -ad`: 246M\n  2. `git repack -ad -f`: 376M\n  3. `git repack -ad --window=250`: 246M\n  4. `git repack -ad -f --window=250`: 145M\n\nThe most interesting thing is (4): repacking with a larger window size\nyields a 100M (40%) space improvement. The other commands show that it\nis not that the current pack is simply bad; command (2) repacks from\nscratch and actually ends up with a worse pack. So the increased window\nsize really is important.\n\nI haven't been able to figure out what it is about this dataset that\nmakes the bigger window so much better. Certainly doing the same\ncommands on git.git does not yield as impressive a speedup.\n\nIf anybody is interested in the repository as a packing test case, you\ncan download it from:\n\n  https://gist.github.com/raw/2518074/d9c0244bf0ced690fee1edb2c88c522ecce102e4/phpmyadmin-network.tar\n\n-Peff\n"},{"id":"190235","messageId":"alpine.LFD.2.02.1204281151290.21030@xanadu.home","threadId":"30263","inReplyTo":"7vmx6am1h9.fsf@alter.siamese.dyndns.org","subject":"Re: gc --aggressive","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2012-04-28T16:42:26Z","receivedAt":"2012-04-28T16:42:26Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"[ coming late to this thread -- thanks to peff who pulled my attention ]\n\nOn Tue, 17 Apr 2012, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > On Tue, Apr 17, 2012 at 03:17:28PM -0700, Junio C Hamano wrote:\n> >\n> >> > How many cores are there on this box? Have you tried setting\n> >> > pack.windowMemory to (12 / # of cores) or thereabouts?\n> >> \n> >> Hrm, from the end-user's point of view, it appears that pack.windowMemory\n> >> ought to mean the total without having to worry about the division of it\n> >> across threads (which the implementation should be responsible for).\n> >\n> > Agreed. I had to look in the code to check which it meant. I'm not sure\n> > we can change it without regressing existing users, though.\n> \n> This is a tangent, but I noticed that the canned settings for \"aggressive\"\n> use an arbitrarily hardcoded value of depth=250 and window=250 (tweakable\n> with gc.aggressiveWindow).\n> \n> Even though a shallower depth does cause base candidates with too long a\n> chain hanging to be evicted prematurely while it is still in window and\n> will lead to smaller memory consumption, I do not think the value of\n> \"depth\" affects the pack-time memory consumption too much.  But the\n> runtime performance of the resulting pack may not be great (in the worst\n> case you would have to undelta 249 times to get to the object data).  We\n> may want to loosen it a bit.\n\nI think people are having misconceptions about the definition of the \nword \"aggressive\".\n\nThis option is, well, aggressive.  By definition this is not meant to be \n\"nice\".  This is not meant to be fast, or light on memory usage, etc.  \nThis means \"achieve as much damage you can\" to reduce the pack size.\n\nIf people are using it every night then they must be masochists, or \nattracted by violence, or getting a bit too casual with word \ndefinitions.\n\nSo if being --aggressive hurts, then don't do it.\n\nIf people want a loosened version, it would be more appropriate to \nintroduce a --mild, or --bold, or --disruptive option.  In the same \nvain, an --insane option could even be introduced to go even further \nthan --aggressive.\n\nThis being said, this is no excuse for regressions though.  If git is \neating up much more memory than it used to, provided with the same \nrepository and repacking parameters than before, then this certainly \nneeds fixing.  But making --aggressive less so is not a fix.\n\n> Also it might make sense to make the window size a bit more flexible\n> depending on the nature of your history (you would get bigger benefit with\n> larger window when your history has fine grained commits; if there are not\n> many few-liner commits, larger window may not help you that much).\n\nHow do you detect the history nature of a repository?  That's the hard \npart.  Because it should be auto detected as most users won't make a good \nguess for the best parameter value to use.\n\nAnyway, I think that the window size in terms of objects is a bad \nparameter.  Historically that is the first thing we implemented. But the \nwindow _memory_ usage is probably a better setting to use.  The delta \nsearch cost is directly proportional to the amount of data to process \nand that can be controlled with --window-memory, with the ability to \nscale up and down the number of objects in the window.  Keeping the \nnumber of objects constant makes memory usage totally random since this \ndepends on the repository content, and the computing cost to process it \nis highly unpredictable. This is very counter-intuitive for users.\n\nRight now the window is limited by default to 10 objects, and window \nmemory usage is unlimited.  This could be reworked so object number, \nwhile still being limited to avoid pathological cases, could be much \nhigher, and the window memory usage always limited by default.  That \ndefault memory usage could be scaled according to the available \nresources on the system.  But if the user wants to play with this, then \nusing a memory usage parameter is much easier to understand with more \ndirectly observable system load influence.\n\n\nNicolas\n"},{"id":"190236","messageId":"alpine.LFD.2.02.1204281243370.21030@xanadu.home","threadId":"30263","inReplyTo":"CAG+J_DyqvCxwd6+gzixQEk6SxMZF0qsXKcJPaU6imsJdFQ-64g@mail.gmail.com","subject":"Re: gc --aggressive","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2012-04-28T16:56:23Z","receivedAt":"2012-04-28T16:56:23Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 17 Apr 2012, Jay Soffian wrote:\n\n> On Tue, Apr 17, 2012 at 12:16 PM, Jay Soffian <jaysoffian@gmail.com> wrote:\n> > This has worked fine on repos large and small. However, starting a\n> > couple days ago git started running out of memory on a relatively\n> > modest repo[*] while repacking on a Linux box with 12GB memory (+ 12GB\n> > swap). I am able to gc the repo by either removing --aggressive or\n> > .keep'ing the oldest pack.\n> \n> Experimentally, setting pack.windowMemory = 256m keeps git memory\n> usage < 4.5 GB during an aggressive repack.\n\nHow many threads are used?  As mentioned elsewhere, the memory usage \nparameter should probably be made global rather than per thread, \nespecially with the ever growing number of CPU cores in a system.  But \nthis also pauses a balancing problem for optimally distributing memory \nbetween threads.\n\n> Ironically I end up with a slightly worse pack (63115590 bytes vs\n> 61518628 bytes) than not using --aggressive. I assume this is because\n> pack-objects found a better delta chain during the previous aggressive\n> repack when windowMemory was not set.\n\nExact.  When reusing delta data, you inherit the quality of the repack \nrun that created them in the first place.\n\n> > 1) If --aggressive does not generally provide a benefit, should it be\n> > made a no-op?\n\nAbsolutely not.  It does provide benefits, but it comes with a cost in \nresources.  If you don't pay that cost then results won't be there.\n\n> I guess I'll revise this question: perhaps --aggressive should be\n> better explained/discouraged. I found a message from Jeff last month\n> and stole his words for this patch:\n> \n> <snip>\n> diff --git i/Documentation/git-gc.txt w/Documentation/git-gc.txt\n> index 815afcb922..ca5bf8b51e 100644\n> --- i/Documentation/git-gc.txt\n> +++ w/Documentation/git-gc.txt\n> @@ -37,9 +37,8 @@ OPTIONS\n>  \tUsually 'git gc' runs very quickly while providing good disk\n>  \tspace utilization and performance.  This option will cause\n>  \t'git gc' to more aggressively optimize the repository at the expense\n> -\tof taking much more time.  The effects of this optimization are\n> -\tpersistent, so this option only needs to be used occasionally; every\n> -\tfew hundred changesets or so.\n> +\tof taking much more time and potentially using greater memory. This\n\nScratch \"potentially\" here. It definitely uses more memory.\n\n> +\toption is rarely needed. See Repacking below.\n> \n>  --auto::\n>  \tWith this option, 'git gc' checks whether any housekeeping is\n> @@ -138,6 +137,39 @@ If you are expecting some objects to be collected\n> and they aren't, check\n>  all of those locations and decide whether it makes sense in your case to\n>  remove those references.\n> \n> +Repacking\n> +---------\n> +\n> +Under the covers 'git gc' calls several commands to optimize the repository.\n> +The most significant of these with respect to repository size and general\n> +performance is linkgit:git-repack[1]. There are basically three levels of\n> +'gc' with respect to repacking:\n> +\n> + 1. `git gc --auto`; if there are too many loose objects (`gc.auto`), they\n> +    all go into a new incremental pack. If there are already too many\n> +    packs (`gc.autopacklimit`), all of the existing packs are re-packed\n> +    together.\n> +\n> +    Making an incremental pack is by far the fastest because the speed is\n> +    independent of the existing repository history. If git packs\n> +    everything together, it should be more or less the same as (2).\n> +\n> + 2. `git gc`; this packs everything into a single pack. It uses default\n> +    window and depth parameters, but importantly, it reuses existing\n> +    deltas. Doing so makes the delta compression phase much faster, and it\n> +    often makes the writing phase faster (because for older objects, git\n> +    is primarily streaming them right out of the existing pack). On a big\n> +    repository though, this does do a lot of I/O, because git has to\n> +    rewrite the whole pack.\n> +\n> + 3. `git gc --aggressive`; this is often much slower than (2) because git\n> +    throws out all of the existing deltas and recomputes them from\n> +    scratch. It uses a higher window parameter meaning it will spend\n> +    more time computing, and it may end up with a smaller pack. However,\n> +    unless the repository is known to have initially been poorly packed,\n> +    this option is not needed and will just cause git to perform\n> +    extra work.\n> +\n>  HOOKS\n>  -----\n> \n> @@ -147,6 +179,7 @@ linkgit:githooks[5] for more information.\n> \n>  SEE ALSO\n>  --------\n> +linkgit:git-pack-refs[1]\n>  linkgit:git-prune[1]\n>  linkgit:git-reflog[1]\n>  linkgit:git-repack[1]\n> </snip>\n> \n> Thoughts?\n\nFWIW, Acked-by: Nicolas Pitre <nico@fluxnic.net>\n\n\nNicolas\n"},{"id":"190237","messageId":"alpine.LFD.2.02.1204281258050.21030@xanadu.home","threadId":"30263","inReplyTo":"20120428122533.GA12098@sigill.intra.peff.net","subject":"Re: gc --aggressive","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2012-04-28T17:11:48Z","receivedAt":"2012-04-28T17:11:48Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 28 Apr 2012, Jeff King wrote:\n\n> On Tue, Apr 17, 2012 at 10:52:03PM +0200, Matthieu Moy wrote:\n> \n> > Jay Soffian <jaysoffian@gmail.com> writes:\n> > \n> > > + 3. `git gc --aggressive`; this is often much slower than (2) because git\n> > > +    throws out all of the existing deltas and recomputes them from\n> > > +    scratch. It uses a higher window parameter meaning it will spend\n> > > +    more time computing, and it may end up with a smaller pack. However,\n> > > +    unless the repository is known to have initially been poorly packed,\n> > > +    this option is not needed and will just cause git to perform\n> > > +    extra work.\n> > \n> > I like your patch.\n> > \n> > Maybe you should elaborate on \"unless the repository is known to have\n> > initially been poorly packed\". My understanding is that --aggressive was\n> > implemented to be called after an import from another VCS that would\n> > have computed very poor deltas, but I'm not sure about the details.\n\nThis is somewhat subjective of course.  But to be effective, you need \nsufficient resources to repack with --aggressive, otherwise you may \npotentially end up with a worse pack.\n\n> Coincidentally, I came across a case last week that shows --aggressive\n> providing a large improvement. And it's a public repo, so I was able to\n> grab a snapshot of the pre-packed state to experiment on and share.\n> \n> The current packfile is ~246M. It was produced over time by pushes into\n> the repository, which were then eventually grouped into a single pack by\n> \"git gc\" (I'm not sure of the exact history, but this may even have been\n> a set of \"gc --auto\" calls over time).\n> \n> Here's a list of commands and the pack sizes they yield on the repo:\n> \n>   1. `git repack -ad`: 246M\n>   2. `git repack -ad -f`: 376M\n>   3. `git repack -ad --window=250`: 246M\n>   4. `git repack -ad -f --window=250`: 145M\n> \n> The most interesting thing is (4): repacking with a larger window size\n> yields a 100M (40%) space improvement. The other commands show that it\n> is not that the current pack is simply bad; command (2) repacks from\n> scratch and actually ends up with a worse pack. So the increased window\n> size really is important.\n\nAbsolutely.  This doesn't surprises me.\n\n> I haven't been able to figure out what it is about this dataset that\n> makes the bigger window so much better. Certainly doing the same\n> commands on git.git does not yield as impressive a speedup.\n\nThe default window size of 10 objects is really really small (yet if \nyour objects are 150MB in size then it is probably too big, but I \ndigress).  When doing an incremental repack, the window is also limited \nby the fact that we don't redelta those already packed objects.\n\nMany things could explain the improvements with a larger window.  If a \nlot of files were renamed for example, the larger window would allow \nsimilar objects to still delta against each other, despite the fact that \nwe pull them in the search window according to their corresponding file \nnames.  With a smaller window this opportunity would be missed.\n\n\nNicolas\n"},{"id":"190245","messageId":"20120429113431.GA24254@sigill.intra.peff.net","threadId":"30263","inReplyTo":"alpine.LFD.2.02.1204281258050.21030@xanadu.home","subject":"Re: gc --aggressive","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-04-29T11:34:32Z","receivedAt":"2012-04-29T11:34:32Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Apr 28, 2012 at 01:11:48PM -0400, Nicolas Pitre wrote:\n\n> > Here's a list of commands and the pack sizes they yield on the repo:\n> > \n> >   1. `git repack -ad`: 246M\n> >   2. `git repack -ad -f`: 376M\n> >   3. `git repack -ad --window=250`: 246M\n> >   4. `git repack -ad -f --window=250`: 145M\n> > \n> > The most interesting thing is (4): repacking with a larger window size\n> > yields a 100M (40%) space improvement. The other commands show that it\n> > is not that the current pack is simply bad; command (2) repacks from\n> > scratch and actually ends up with a worse pack. So the increased window\n> > size really is important.\n> \n> Absolutely.  This doesn't surprises me.\n\nI was somewhat surprised, because this repo behaves very differently\nfrom other ones as the window size increases. Our default window of 10\nis somewhat arbitrary, but I think there was a sense from early tests\nthat you got diminishing returns from increasing it (this is my vague\nrecollection; I didn't actually search for old discussions). But here\nare some charts showing \"repack -adf\" with various window sizes on a few\nrepositories. The first column is the window size; the second is the\nresulting pack size (and its percentage of the window=10 case); the\nthird is the number of seconds of CPU time (and again, the percentage of\nthe window=10 case).\n\nHere's git.git:\n\n  10 | 31.3M (100%) |   54s (100%)\n  20 | 28.8M ( 92%) |   72s (133%)\n  40 | 27.4M ( 87%) |  101s (187%)\n  80 | 26.3M ( 84%) |  153s (282%)\n 160 | 25.7M ( 82%) |  247s (455%)\n 320 | 25.4M ( 81%) |  415s (763%)\n\nYou can see we get some benefit from increasing window size to 20 or\neven 40, but we hit an asymptote around 80%. Meanwhile, CPU time keeps\njumping. Something like 20 or 40 seems like it might be a nice\ncompromise.\n\nHere's linux-2.6:\n\n  10 | 564M (100%) |  990s (100%)\n  20 | 521M ( 92%) | 1323s (134%)\n  40 | 495M ( 88%) | 1855s (187%)\n  80 | 479M ( 85%) | 2743s (277%)\n 160 | 470M ( 83%) | 4284s (432%)\n 320 | 463M ( 82%) | 7064s (713%)\n\nIt's quite similar, asymptotically heading towards ~80%. And the CPU\nnumbers look quite similar, too.\n\nAnd here's the phpmyadmin repository (the one I linked to earlier):\n\n  10 | 386M (100%) | 1592s (100%)\n  20 | 280M ( 72%) | 1947s (122%)\n  40 | 209M ( 54%) | 2514s (158%)\n  80 | 169M ( 44%) | 3386s (213%)\n 160 | 151M ( 39%) | 4822s (303%)\n 320 | 142M ( 37%) | 6948s (436%)\n\nThe packfile size improvements go on for much longer as we increase the\nwindow size. For this repo, a window size of 80-100 is probably a good\nspot.\n\nThat leads me to a few questions:\n\n  1. Should we bump our default window size? The numbers above show that\n     typical repos would benefit from jumping to 20 or even 40.\n\n  2. Is there a heuristic or other metric we can figure out to\n     differentiate the first two repositories from the third, and use a\n     larger window size on the latter?\n\n  3. Does the phpmyadmin case give us any insight into whether we can\n     improve our window sorting algorithm? Looking at the repo, ~55K of\n     the ~75K commits are small changes in the po/ directory (it looks\n     like they were using a web-based tool to let non-committers tweak\n     the translation files). In particular, I see a lot of commits in\n     which most of the changes are simply line number changes as the po\n     files are refreshed from the source. I wonder if that is making the\n     size-sorting heuristics perform poorly, as we end up with many\n     files of the same size, and the good deltas get pushed further\n     along the window.\n\n  4. What is typical? I suspect that git.git and linux-2.6 are typical,\n     and the weird po-files in the phpmyadmin repository are not. But\n     I'd be happy to test more repos if people have suggestions. And the\n     scripts that generated the charts are included below if anybody\n     wants to try it themselves.\n\n-Peff\n\n-- >8 --\ncat >collect <<\\EOF\n#!/bin/sh\n# usage: collect /path/to/repo >foo.out\n\nwindows='10 20 40 80 160 320'\n\nfor i in $windows; do\n  echo >&2 \"Repacking with window $i...\"\n  rm -rf tmp && cp -a \"$1\" tmp && (\n    cd tmp &&\n    time=`time -f %U -o /dev/stdout git repack -adf --window=$i`\n    size=`du -bc objects/pack/pack-*.pack | tail -1 | awk '{print $1}'`\n    echo \"$i $size $time\"\n  )\ndone\nEOF\n\ncat >chart <<\\EOF\n#!/usr/bin/perl\n# usage: chart <foo.out\n\nuse strict;\n\nmy @base;\nwhile (<>) {\n  chomp;\n  my ($window, $size, $time) = split;\n\n  @base = ($size, $time) unless @base;\n\n  printf '%4s', $window;\n  print ' | ', humanize($size);\n  printf ' (%3d%%)', int($size / $base[0] * 100 + 0.5);\n  printf ' | %4ds', $time;\n  printf ' (%d%%)', int($time / $base[1] * 100 + 0.5);\n  print \"\\n\";\n}\n\nsub human_digits {\n  my $n = shift;\n  my $digits = $n >= 100 ? 0 :\n               $n >=  10 ? 1 :\n               2;\n  return sprintf '%.*f', $digits, $n;\n}\n\nsub humanize {\n  my $n = shift;\n  my $u;\n  foreach $u ('', qw(K M G)) {\n    return human_digits($n) . $u if $n < 900;\n    $n /= 1024;\n  }\n  return human_digits($n) . $u;\n}\nEOF\n"},{"id":"190248","messageId":"alpine.LFD.2.02.1204290917051.21030@xanadu.home","threadId":"30263","inReplyTo":"20120429113431.GA24254@sigill.intra.peff.net","subject":"Re: gc --aggressive","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2012-04-29T13:53:31Z","receivedAt":"2012-04-29T13:53:31Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 29 Apr 2012, Jeff King wrote:\n\n> On Sat, Apr 28, 2012 at 01:11:48PM -0400, Nicolas Pitre wrote:\n> \n> > > Here's a list of commands and the pack sizes they yield on the repo:\n> > > \n> > >   1. `git repack -ad`: 246M\n> > >   2. `git repack -ad -f`: 376M\n> > >   3. `git repack -ad --window=250`: 246M\n> > >   4. `git repack -ad -f --window=250`: 145M\n> > > \n> > > The most interesting thing is (4): repacking with a larger window size\n> > > yields a 100M (40%) space improvement. The other commands show that it\n> > > is not that the current pack is simply bad; command (2) repacks from\n> > > scratch and actually ends up with a worse pack. So the increased window\n> > > size really is important.\n> > \n> > Absolutely.  This doesn't surprises me.\n> \n> I was somewhat surprised, because this repo behaves very differently\n> from other ones as the window size increases. Our default window of 10\n> is somewhat arbitrary, but I think there was a sense from early tests\n> that you got diminishing returns from increasing it (this is my vague\n> recollection; I didn't actually search for old discussions). \n\nYes, your numbers are very interesting.\n\nBut my remark was related to the fact that you need to double the \naffected resources to gain marginal improvements at some point.  This is \ntrue about computing hardware too: eventually you need way more gates \nand spend much more $$$ to gain some performance, and the added \nperformance is never linear with the spending.\n\n> But here are some charts showing \"repack -adf\" with various window \n> sizes on a few repositories. The first column is the window size; the \n> second is the resulting pack size (and its percentage of the window=10 \n> case); the third is the number of seconds of CPU time (and again, the \n> percentage of the window=10 case).\n> \n> Here's git.git:\n> \n>   10 | 31.3M (100%) |   54s (100%)\n>   20 | 28.8M ( 92%) |   72s (133%)\n>   40 | 27.4M ( 87%) |  101s (187%)\n>   80 | 26.3M ( 84%) |  153s (282%)\n>  160 | 25.7M ( 82%) |  247s (455%)\n>  320 | 25.4M ( 81%) |  415s (763%)\n> \n> You can see we get some benefit from increasing window size to 20 or\n> even 40, but we hit an asymptote around 80%. Meanwhile, CPU time keeps\n> jumping. Something like 20 or 40 seems like it might be a nice\n> compromise.\n> \n> Here's linux-2.6:\n> \n>   10 | 564M (100%) |  990s (100%)\n>   20 | 521M ( 92%) | 1323s (134%)\n>   40 | 495M ( 88%) | 1855s (187%)\n>   80 | 479M ( 85%) | 2743s (277%)\n>  160 | 470M ( 83%) | 4284s (432%)\n>  320 | 463M ( 82%) | 7064s (713%)\n> \n> It's quite similar, asymptotically heading towards ~80%. And the CPU\n> numbers look quite similar, too.\n> \n> And here's the phpmyadmin repository (the one I linked to earlier):\n> \n>   10 | 386M (100%) | 1592s (100%)\n>   20 | 280M ( 72%) | 1947s (122%)\n>   40 | 209M ( 54%) | 2514s (158%)\n>   80 | 169M ( 44%) | 3386s (213%)\n>  160 | 151M ( 39%) | 4822s (303%)\n>  320 | 142M ( 37%) | 6948s (436%)\n> \n> The packfile size improvements go on for much longer as we increase the\n> window size. For this repo, a window size of 80-100 is probably a good\n> spot.\n> \n> That leads me to a few questions:\n> \n>   1. Should we bump our default window size? The numbers above show that\n>      typical repos would benefit from jumping to 20 or even 40.\n\nI think this might be a good indication that the number of objects is a \nbad metric to size the window, as I mentioned previously.\n\nGiven that you have the test repos already, could you re-run it with \n--window=1000 and play with --window-memory instead?  I would be curious \nto see if this provides more predictable results.\n\n>   2. Is there a heuristic or other metric we can figure out to\n>      differentiate the first two repositories from the third, and use a\n>      larger window size on the latter?\n\nMaybe we could look at the size reduction within the delta search loop.  \nIf the reduction quickly diminishes as tested objects are further away \nfrom the target one then the window doesn't have to be very large, \nwhereas if the reduction remains more or less constant then it might be \nworth searching further.  That could be used to dynamically size the \nwindow at run time.\n\n>   3. Does the phpmyadmin case give us any insight into whether we can\n>      improve our window sorting algorithm? Looking at the repo, ~55K of\n>      the ~75K commits are small changes in the po/ directory (it looks\n>      like they were using a web-based tool to let non-committers tweak\n>      the translation files). In particular, I see a lot of commits in\n>      which most of the changes are simply line number changes as the po\n>      files are refreshed from the source. I wonder if that is making the\n>      size-sorting heuristics perform poorly, as we end up with many\n>      files of the same size, and the good deltas get pushed further\n>      along the window.\n\nYou could test this theory by commenting out the size comparisons in \ntype_size_sort() and re-run the test.  Linus initially introduced that \ncriterion thinking that newer files tend to grow and it is cheaper to \ncreate a delta that removes data than one that adds data.  And given \nthat we wanted to prefer delta chains to start from newer objects this \nall made sense.  However the last comparison in that function is meant \nto handling the recency ordering, and therefore the size comparison \nmight be skewing things here.\n\n>   4. What is typical? I suspect that git.git and linux-2.6 are typical,\n>      and the weird po-files in the phpmyadmin repository are not. But\n>      I'd be happy to test more repos if people have suggestions. And the\n>      scripts that generated the charts are included below if anybody\n>      wants to try it themselves.\n\nI wouldn't give up on \"non typical\" data sets just yet though.\n\n\nNicolas\n"},{"id":"190427","messageId":"20120501162806.GA15614@sigill.intra.peff.net","threadId":"30263","inReplyTo":"alpine.LFD.2.02.1204290917051.21030@xanadu.home","subject":"Re: gc --aggressive","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-01T16:28:06Z","receivedAt":"2012-05-01T16:28:06Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Apr 29, 2012 at 09:53:31AM -0400, Nicolas Pitre wrote:\n\n> But my remark was related to the fact that you need to double the \n> affected resources to gain marginal improvements at some point.  This is \n> true about computing hardware too: eventually you need way more gates \n> and spend much more $$$ to gain some performance, and the added \n> performance is never linear with the spending.\n\nRight, I agree with that. The trick is just finding the right spot on\nthat curve for each repo to maximize the reward/effort ratio.\n\n> >   1. Should we bump our default window size? The numbers above show that\n> >      typical repos would benefit from jumping to 20 or even 40.\n> \n> I think this might be a good indication that the number of objects is a \n> bad metric to size the window, as I mentioned previously.\n> \n> Given that you have the test repos already, could you re-run it with \n> --window=1000 and play with --window-memory instead?  I would be curious \n> to see if this provides more predictable results.\n\nIt doesn't help. The git.git repo does well with about a 1m window\nlimit. linux-2.6 is somewhere between 1m and 2m. But the phpmyadmin repo\nwants more like 16m. So it runs into the same issue as using object\ncounts.\n\nBut it's much, much worse than that. Here are the actual numbers (same\nformat as before; left-hand column is either window size (if no unit) or\nwindow-memory limit (if k/m unit), followed by resulting pack size, its\npercentage of baseline --window=10 pack, the user CPU time and finally\nits percentage of the baseline):\n\n  git:\n    10 | 31.4M (100%) |   54s (100%)\n    20 | 28.8M ( 92%) |   72s (133%)\n  128k | 81.4M (260%) |   77s (142%)\n  256k | 59.1M (188%) |  106s (195%)\n  512k | 44.5M (142%) |  166s (306%)\n    1m | 28.7M ( 91%) |  267s (491%)\n    2m | 27.0M ( 86%) |  347s (637%)\n    4m | 26.0M ( 83%) |  417s (767%)\n\n  linux-2.6:\n    10 |  564M (100%) |  990s (100%)\n    20 |  521M ( 92%) | 1323s (134%)\n  128k | 1.41G (256%) | 1322s (133%)\n  256k | 1.08G (196%) | 1810s (183%)\n  512k |  783M (139%) | 2775s (280%)\n    1m |  579M (103%) | 4620s (466%)\n    2m |  504M ( 89%) | 6786s (685%)\n    4m |  479M ( 85%) | 8119s (819%)\n\n  phpmyadmin:\n    10 |  380M (100%) | 1617s (100%)\n    80 |  163M ( 43%) | 3410s (211%)\n  128k | 3.42G (921%) | 2367s (146%)\n  256k | 3.36G (904%) | 2437s (151%)\n  512k | 3.22G (865%) | 2589s (160%)\n    1m | 3.10G (833%) | 2746s (170%)\n    2m |  436M (115%) | 1674s (104%)\n    4m |  299M ( 78%) | 2140s (132%)\n    8m |  222M ( 58%) | 2751s (170%)\n   16m |  178M ( 47%) | 3334s (206%)\n\nI intentionally started with a too-small memory limit so we could see\nthe effect as the window size approached something reasonable. You can\nsee the pack sizes getting comparable for --window=20 around\n--window-memory=1m for the git and linux-2.6 cases. But look at the CPU\nusage. For a comparable resulting pack size, limiting the window memory\nuses 4-5x as much CPU.\n\nI'm not sure what is causing that behavior. I guess maybe for small\nobjects we end up with a really huge window (in terms of number of\nobjects), but it doesn't end up actually saving us a lot of space\nbecause there is not as much space to be saved with small objects. So we\nspend a lot of extra time looking at objects that don't yield big space\nsavings.\n\nFor some of the really tiny limits, the \"writing\" phase ended up\ndominating. For example, linux-2.6 at 128k ends up with a horribly large\npack that takes even longer to run than --window=10. These numbers don't\nreflect the split between the compression and writing phases, but I\nnoticed while watching the progress meter that the writing phase was\nquite slow in such cases. Mostly because we end up having to zlib\ndeflate a lot more data (which I confirmed via perf).\n\nInterestingly, the phpmyadmin script does not have the same issue. The\nCPU usage for the object and memory limits are about the same (probably\nthis is due to the fact that the history is dominated by similar-sized\n.po files, so the two limits end up equating to each other).\n\n> >   2. Is there a heuristic or other metric we can figure out to\n> >      differentiate the first two repositories from the third, and use a\n> >      larger window size on the latter?\n> \n> Maybe we could look at the size reduction within the delta search loop.  \n> If the reduction quickly diminishes as tested objects are further away \n> from the target one then the window doesn't have to be very large, \n> whereas if the reduction remains more or less constant then it might be \n> worth searching further.  That could be used to dynamically size the \n> window at run time.\n\nI really like the idea of dynamically sizing the window based on what we\nfind. If it works. I don't think there's any reason you couldn't have 50\nabsolutely terrible delta candidates followed by one really amazing\ndelta candidate. But maybe in practice the window tends to get\nprogressively worse due to the heuristics, and outliers are unlikely. I\nguess we'd have to experiment.\n\n> >   3. Does the phpmyadmin case give us any insight into whether we can\n> >      improve our window sorting algorithm?\n> [...]\n> \n>  You could test this theory by commenting out the size comparisons in \n> type_size_sort() and re-run the test.\n\nI'll try this next.\n\n-Peff\n\nPS Here's my updated collection script, just for reference.\n\n-- >8 --\n#!/bin/sh\n\nwindows='10 20 128k 256k 512k 1m 2m 4m'\nrepo=$1; shift\ntest $# -gt 0 && windows=\"$*\"\n\ncd \"$repo\" || exit\nfor i in $windows; do\n  case \"$i\" in\n  *[kmg])\n    opts=\"--window=1000 --window-memory=$i\" ;;\n  *)\n    opts=\"--window=$i\" ;;\n  esac\n\n  echo >&2 \"Repacking $repo with $opts...\"\n\n  time -f %U -o time.out \\\n    git pack-objects --stdout --all-progress-implied --all \\\n      --no-reuse-delta $opts </dev/null |\n    wc -c >size.out\n  echo \"$i `cat size.out` `cat time.out`\"\n  rm -f size.out time.out\ndone\n"},{"id":"190439","messageId":"20120501171640.GA16623@sigill.intra.peff.net","threadId":"30263","inReplyTo":"20120501162806.GA15614@sigill.intra.peff.net","subject":"Re: gc --aggressive","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-01T17:16:40Z","receivedAt":"2012-05-01T17:16:40Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, May 01, 2012 at 12:28:06PM -0400, Jeff King wrote:\n\n> >  You could test this theory by commenting out the size comparisons in \n> > type_size_sort() and re-run the test.\n> \n> I'll try this next.\n\nWow, it behaves horribly. I didn't even let the bigger tests run to\ncompletion. Here is the output for git.git (the first line is from the\noriginal, unmodified version of git with --window=10):\n\n  orig | 31.4M (100%) |   54s (100%)\n    10 | 44.0M (140%) |  169s (310%)\n    20 | 37.7M (120%) |  232s (428%)\n    40 | 33.6M (107%) |  331s (608%)\n    80 | 30.9M ( 99%) |  473s (868%)\n   160 | 29.4M ( 94%) |  696s (1279%)\n\nUnless the window is increased a lot, the packs end up quite a bit\nlarger (and even still we spend a lot more CPU time).\n\n-Peff\n"},{"id":"190440","messageId":"alpine.LFD.2.02.1205011259200.21030@xanadu.home","threadId":"30263","inReplyTo":"20120501162806.GA15614@sigill.intra.peff.net","subject":"Re: gc --aggressive","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2012-05-01T17:17:03Z","receivedAt":"2012-05-01T17:17:03Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 1 May 2012, Jeff King wrote:\n\n> On Sun, Apr 29, 2012 at 09:53:31AM -0400, Nicolas Pitre wrote:\n> \n> > But my remark was related to the fact that you need to double the \n> > affected resources to gain marginal improvements at some point.  This is \n> > true about computing hardware too: eventually you need way more gates \n> > and spend much more $$$ to gain some performance, and the added \n> > performance is never linear with the spending.\n> \n> Right, I agree with that. The trick is just finding the right spot on\n> that curve for each repo to maximize the reward/effort ratio.\n\nAbsolutely, at least for the default settings.  However this is not what \n--aggressive is meant to be.\n\n> > >   1. Should we bump our default window size? The numbers above show that\n> > >      typical repos would benefit from jumping to 20 or even 40.\n> > \n> > I think this might be a good indication that the number of objects is a \n> > bad metric to size the window, as I mentioned previously.\n> > \n> > Given that you have the test repos already, could you re-run it with \n> > --window=1000 and play with --window-memory instead?  I would be curious \n> > to see if this provides more predictable results.\n> \n> It doesn't help. The git.git repo does well with about a 1m window\n> limit. linux-2.6 is somewhere between 1m and 2m. But the phpmyadmin repo\n> wants more like 16m. So it runs into the same issue as using object\n> counts.\n> \n> But it's much, much worse than that. Here are the actual numbers (same\n> format as before; left-hand column is either window size (if no unit) or\n> window-memory limit (if k/m unit), followed by resulting pack size, its\n> percentage of baseline --window=10 pack, the user CPU time and finally\n> its percentage of the baseline):\n> [...]\n\nOuch!  Well... so much for good theory.  I'm still really surprised and \ndisappointed as I didn't expect such damage at all.\n\nHowever, this is possibly a good baseline to determine a default value \nfor window-memory though.  Given your number, we clearly see that good \npacking can be achieved with relatively little memory and therefore it \nmight be a good idea not to leave this parameter unbounded by default in \norder to catch potential pathological cases.  Maybe 64M would be a good \ndefault value?  Having a repack process eating up more than 16GB of RAM \nbecause its RAM usage is unbounded is certainly not nice.\n\n> > Maybe we could look at the size reduction within the delta search loop.  \n> > If the reduction quickly diminishes as tested objects are further away \n> > from the target one then the window doesn't have to be very large, \n> > whereas if the reduction remains more or less constant then it might be \n> > worth searching further.  That could be used to dynamically size the \n> > window at run time.\n> \n> I really like the idea of dynamically sizing the window based on what we\n> find. If it works. I don't think there's any reason you couldn't have 50\n> absolutely terrible delta candidates followed by one really amazing\n> delta candidate. But maybe in practice the window tends to get\n> progressively worse due to the heuristics, and outliers are unlikely. I\n> guess we'd have to experiment.\n\nYes.  The idea is to continue searching if results are not progressively \nbecoming worse fast enough.  Coming up with a good way to infer that is \nfar from obvious though.\n\n\nNicolas\n"},{"id":"190441","messageId":"20120501172201.GA23527@sigill.intra.peff.net","threadId":"30263","inReplyTo":"alpine.LFD.2.02.1205011259200.21030@xanadu.home","subject":"Re: gc --aggressive","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-01T17:22:01Z","receivedAt":"2012-05-01T17:22:01Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, May 01, 2012 at 01:17:03PM -0400, Nicolas Pitre wrote:\n\n> However, this is possibly a good baseline to determine a default value \n> for window-memory though.  Given your number, we clearly see that good \n> packing can be achieved with relatively little memory and therefore it \n> might be a good idea not to leave this parameter unbounded by default in \n> order to catch potential pathological cases.  Maybe 64M would be a good \n> default value?  Having a repack process eating up more than 16GB of RAM \n> because its RAM usage is unbounded is certainly not nice.\n\nWould that preclude a 65M object from being delta'd at all? If you are\nputting a limit of 64M and it means we look at 50 delta candidates\ninstead of 60, then that is probably not going to hurt our size too\nmuch. But if you have large objects that do happen to delta, the\ndifference between looking at 0 and 1 objects could have a big impact.\n\n-Peff\n"},{"id":"190447","messageId":"alpine.LFD.2.02.1205011342160.21030@xanadu.home","threadId":"30263","inReplyTo":"20120501172201.GA23527@sigill.intra.peff.net","subject":"Re: gc --aggressive","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2012-05-01T17:47:14Z","receivedAt":"2012-05-01T17:47:14Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 1 May 2012, Jeff King wrote:\n\n> On Tue, May 01, 2012 at 01:17:03PM -0400, Nicolas Pitre wrote:\n> \n> > However, this is possibly a good baseline to determine a default value \n> > for window-memory though.  Given your number, we clearly see that good \n> > packing can be achieved with relatively little memory and therefore it \n> > might be a good idea not to leave this parameter unbounded by default in \n> > order to catch potential pathological cases.  Maybe 64M would be a good \n> > default value?  Having a repack process eating up more than 16GB of RAM \n> > because its RAM usage is unbounded is certainly not nice.\n> \n> Would that preclude a 65M object from being delta'd at all? If you are\n> putting a limit of 64M and it means we look at 50 delta candidates\n> instead of 60, then that is probably not going to hurt our size too\n> much. But if you have large objects that do happen to delta, the\n> difference between looking at 0 and 1 objects could have a big impact.\n\nIf I remember correctly (long time ago since I wrote that code) there is \nalways a minimum of one object in the search window.  So with 32M \nobjects you'd have only 2 candidates, with 33M objects and bigger there \nwould be only one candidate.  Obviously the window could still be filled \nwith smaller objects if the total object size is less than 64M.\n\n\nNicolas\n"},{"id":"190453","messageId":"alpine.LFD.2.02.1205011348090.21030@xanadu.home","threadId":"30263","inReplyTo":"20120501171640.GA16623@sigill.intra.peff.net","subject":"Re: gc --aggressive","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2012-05-01T17:59:08Z","receivedAt":"2012-05-01T17:59:08Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 1 May 2012, Jeff King wrote:\n\n> On Tue, May 01, 2012 at 12:28:06PM -0400, Jeff King wrote:\n> \n> > >  You could test this theory by commenting out the size comparisons in \n> > > type_size_sort() and re-run the test.\n> > \n> > I'll try this next.\n> \n> Wow, it behaves horribly. I didn't even let the bigger tests run to\n> completion. Here is the output for git.git (the first line is from the\n> original, unmodified version of git with --window=10):\n> \n>   orig | 31.4M (100%) |   54s (100%)\n>     10 | 44.0M (140%) |  169s (310%)\n>     20 | 37.7M (120%) |  232s (428%)\n>     40 | 33.6M (107%) |  331s (608%)\n>     80 | 30.9M ( 99%) |  473s (868%)\n>    160 | 29.4M ( 94%) |  696s (1279%)\n> \n> Unless the window is increased a lot, the packs end up quite a bit\n> larger (and even still we spend a lot more CPU time).\n\nBleh.  Allright.\n\nOne final quick test if you feel like it: I've never been sure that \nthe last comparison in type_size_sort() is correct.  Maybe it should be \nthe other way around.  Currently it reads:\n\n\treturn a < b ? -1 : (a > b);\n\nWhile keeping the size comparison commented out, you could try to \nreplace this line with:\n\n\treturn b < a ? -1 : (b > a);\n\nIf this doesn't improve things then it would be clear that this avenue \nshould be abandoned.\n\n\nNicolas\n"},{"id":"190462","messageId":"7vr4v391s1.fsf@alter.siamese.dyndns.org","threadId":"30263","inReplyTo":"alpine.LFD.2.02.1205011348090.21030@xanadu.home","subject":"Re: gc --aggressive","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-01T18:47:26Z","receivedAt":"2012-05-01T18:47:26Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre <nico@fluxnic.net> writes:\n\n> One final quick test if you feel like it: I've never been sure that \n> the last comparison in type_size_sort() is correct.  Maybe it should be \n> the other way around.  Currently it reads:\n>\n> \treturn a < b ? -1 : (a > b);\n>\n> While keeping the size comparison commented out, you could try to \n> replace this line with:\n>\n> \treturn b < a ? -1 : (b > a);\n>\n> If this doesn't improve things then it would be clear that this avenue \n> should be abandoned.\n\nVery interesting.  The difference between the two should only matter if\nthere are many blobs with exactly the same size, and most of them delta\nhorribly with each other.  Does the problematic repository exhibit such\na characteristic?\n\nThe original tie-breaks based on the address (the earlier object we read\nin the original input comes earlier in the output) and yours make the\nobjects later we read (which in turn are from older parts of the history)\ncome early, but adjacency between two objects of the same type and the\nsame size would not change (if A and B were next to each other in this\norder, your updated sorter will give B and then A still next to each\nother), so I suspect not much would change in the candidate selection.\n"},{"id":"190465","messageId":"alpine.LFD.2.02.1205011504160.21030@xanadu.home","threadId":"30263","inReplyTo":"7vr4v391s1.fsf@alter.siamese.dyndns.org","subject":"Re: gc --aggressive","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2012-05-01T19:22:27Z","receivedAt":"2012-05-01T19:22:27Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 1 May 2012, Junio C Hamano wrote:\n\n> Nicolas Pitre <nico@fluxnic.net> writes:\n> \n> > One final quick test if you feel like it: I've never been sure that \n> > the last comparison in type_size_sort() is correct.  Maybe it should be \n> > the other way around.  Currently it reads:\n> >\n> > \treturn a < b ? -1 : (a > b);\n> >\n> > While keeping the size comparison commented out, you could try to \n> > replace this line with:\n> >\n> > \treturn b < a ? -1 : (b > a);\n> >\n> > If this doesn't improve things then it would be clear that this avenue \n> > should be abandoned.\n> \n> Very interesting.  The difference between the two should only matter if\n> there are many blobs with exactly the same size, and most of them delta\n> horribly with each other.  Does the problematic repository exhibit such\n> a characteristic?\n\nNot precisely.  This is just to verify some hypothesis that could \nexplain the difference in behavior with the phpmyadmin repo.\n\nMy hypothesis was that recency order could be skewed by the object size \nwhen many small changes are made to the same files without varying their \nsize much.  So I suggested that a repack run be performed with the \nobject size removed from the sort criteria.  However it is important \nthat the last comparison be done in the right direction.  Hence my \nsuggestion above.\n\n> The original tie-breaks based on the address (the earlier object we read\n> in the original input comes earlier in the output) and yours make the\n> objects later we read (which in turn are from older parts of the history)\n> come early, but adjacency between two objects of the same type and the\n> same size would not change (if A and B were next to each other in this\n> order, your updated sorter will give B and then A still next to each\n> other), so I suspect not much would change in the candidate selection.\n\nNote that the size comparison is commented out in those tests.  The idea \nwas to get pure recency order.\n\nEven for objects of the same size, the delta orientation would change \nwhich might or might not provide a clue.\n\nBut this is really just a wild guess without much thinking at this \npoint, before giving up on this approach.\n\n\nNicolas\n"},{"id":"190466","messageId":"20120501193537.GA26245@sigill.intra.peff.net","threadId":"30263","inReplyTo":"alpine.LFD.2.02.1205011348090.21030@xanadu.home","subject":"Re: gc --aggressive","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-01T19:35:37Z","receivedAt":"2012-05-01T19:35:37Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, May 01, 2012 at 01:59:08PM -0400, Nicolas Pitre wrote:\n\n> One final quick test if you feel like it: I've never been sure that \n> the last comparison in type_size_sort() is correct.  Maybe it should be \n> the other way around.  Currently it reads:\n> \n> \treturn a < b ? -1 : (a > b);\n\nI think it is right. At least it should put recent things near the\nfront of the array, just as we are putting bigger things there.\n\n> >   orig | 31.4M (100%) |   54s (100%)\n> >     10 | 44.0M (140%) |  169s (310%)\n> >     20 | 37.7M (120%) |  232s (428%)\n> >     40 | 33.6M (107%) |  331s (608%)\n> >     80 | 30.9M ( 99%) |  473s (868%)\n> >    160 | 29.4M ( 94%) |  696s (1279%)\n> [...]\n> While keeping the size comparison commented out, you could try to \n> replace this line with:\n> \n> \treturn b < a ? -1 : (b > a);\n\nNo, it's not better. A few of the pack sizes are better, but some of\nthem are worse. And the CPU times are still quite bad. Here are the\nnumbers:\n\n  orig | 31.4M (100%) |   54s (100%)\n    10 | 45.6M (145%) |  158s (292%)\n    20 | 39.2M (125%) |  205s (377%)\n    40 | 35.1M (112%) |  275s (505%)\n    80 | 32.4M (103%) |  388s (713%)\n   160 | 30.6M ( 98%) |  581s (1067%)\n\n-Peff\n"},{"id":"190472","messageId":"20120501200123.GB26245@sigill.intra.peff.net","threadId":"30263","inReplyTo":"7vr4v391s1.fsf@alter.siamese.dyndns.org","subject":"Re: gc --aggressive","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-01T20:01:23Z","receivedAt":"2012-05-01T20:01:23Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, May 01, 2012 at 11:47:26AM -0700, Junio C Hamano wrote:\n\n> > While keeping the size comparison commented out, you could try to \n> > replace this line with:\n> >\n> > \treturn b < a ? -1 : (b > a);\n> >\n> > If this doesn't improve things then it would be clear that this avenue \n> > should be abandoned.\n> \n> Very interesting.  The difference between the two should only matter if\n> there are many blobs with exactly the same size, and most of them delta\n> horribly with each other.  Does the problematic repository exhibit such\n> a characteristic?\n\nNo. Here are the objects with the same sizes:\n\n  $ git rev-list --objects --all |\n    cut -d' ' -f1 |\n    git cat-file --batch-check |\n    cut -d' ' -f2,3 |\n    sort | uniq -c | sort -rn | head\n\n  19722 tree 2222\n  14068 tree 4393\n  11418 tree 2156\n   9994 tree 4676\n   9479 tree 2189\n   7944 tree 2255\n   6454 commit 251\n   6437 tree 4611\n   5328 tree 4439\n   4586 commit 254\n\nSo it's mostly trees and commits (the first repeated blob size is on\nline 332 of the output). The commits aren't all that big even without\ndeltafication, but the trees are. They should be sorted by name_hash,\nbut within a single name, there are going to be a lot of repetitions (I\nthink each of those size clusters is just a repetition of the same \"po\"\ndirectory getting lots of tiny modifications).\n\nSo we are triggering that part of the sort quite a bit. But by your\nreasoning here:\n\n> The original tie-breaks based on the address (the earlier object we read\n> in the original input comes earlier in the output) and yours make the\n> objects later we read (which in turn are from older parts of the history)\n> come early, but adjacency between two objects of the same type and the\n> same size would not change (if A and B were next to each other in this\n> order, your updated sorter will give B and then A still next to each\n> other), so I suspect not much would change in the candidate selection.\n\nI don't think it makes a big difference (and indeed, switching it and\nrepacking the phpmyadmin repository yields the same-size pack, although\na lot more CPU time is spent).\n\n-Peff\n"},{"id":"190473","messageId":"alpine.LFD.2.02.1205011547060.21030@xanadu.home","threadId":"30263","inReplyTo":"20120501193537.GA26245@sigill.intra.peff.net","subject":"Re: gc --aggressive","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2012-05-01T20:02:57Z","receivedAt":"2012-05-01T20:02:57Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 1 May 2012, Jeff King wrote:\n\n> On Tue, May 01, 2012 at 01:59:08PM -0400, Nicolas Pitre wrote:\n> \n> > One final quick test if you feel like it: I've never been sure that \n> > the last comparison in type_size_sort() is correct.  Maybe it should be \n> > the other way around.  Currently it reads:\n> > \n> > \treturn a < b ? -1 : (a > b);\n> \n> I think it is right. At least it should put recent things near the\n> front of the array, just as we are putting bigger things there.\n\nRight.  In fact, it seems that _I_ did think about it *five* years ago \n(man... time flies by) given commit adcc70950e, and then I reversed the \nwhole order in commit b904166ccb to get what we have today.\n\n> > replace this line with:\n> > \n> > \treturn b < a ? -1 : (b > a);\n> \n> No, it's not better. A few of the pack sizes are better, but some of\n> them are worse. And the CPU times are still quite bad.\n\nOK.  We can scratch that.\n\n\nNicolas\n"}]}