{"thread":{"id":"18359","subject":"git repack: --depth=100000 causing larger not smaler pack file?","startedAt":"2009-03-17T19:05:25Z","lastAt":"2009-03-23T14:14:13Z","messageCount":6,"participants":["Kjetil Barvik","Nicolas Pitre","Mike Ralphson","Peter Harris"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"108274","messageId":"867i2ot1fu.fsf@broadpark.no","threadId":"18359","inReplyTo":null,"subject":"git repack: --depth=100000 causing larger not smaler pack file?","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-03-17T19:05:25Z","receivedAt":"2009-03-17T19:05:25Z","isPatch":false,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"  aloha!\n\n  Yesterday I run the following command on the updated GIT respository:\n\n    git repack -adf --window=250000 --depth=100000\n\n  After 280 minutes or so it finished, but the strange thing was that\n  the resulting pack-file was larger than before.  I had expected that\n  it should be smaler, or at least the same size as before.\n\n  kjetil git (my_next)$ ls -l .git/objects/pack/*\n-r-------- 1 kjetil kjetil  2757280 2009-03-16 15:18 .git/objects/pack/pack-c5f15d5c48d6b3902a49046d7e8a8d717e167051.idx\n-r-------- 1 kjetil kjetil 19961120 2009-03-16 15:18 .git/objects/pack/pack-c5f15d5c48d6b3902a49046d7e8a8d717e167051.pack\n\n  Before I started the pack file was around 19 250 000 bytes, and was\n  the result of the following commands:\n\n  1) git repack -adf --window=250000 --depth=20000\n          - not completly sure about the --window number here\n          - the resulting pack file was a litle less than 19 100 000\n\n  2) 'git fetch' to get the latest GIT patches\n\n  3) since 'git fetch' always make an extra new \"smal\" pack file, I run\n     the command 'git repack -ad --window=40000 --depth=10000' to be\n     able to get one singel pack file of 19 250 000 bytes or so.\n\n  I can think of one thing which is spesial with the \"--depth=100000\"\n  number, and that is that it is now larger than the total number of\n  objects in the pack, which is around 96000 to 97000, or so.\n\n  I have run 'git fsck --strict --full' on the pack with no resulting\n  error/debug output or change in the file size.\n\n  Any help on how to debug this?\n\n  -- kjetil\n"},{"id":"108280","messageId":"alpine.LFD.2.00.0903171608080.30483@xanadu.home","threadId":"18359","inReplyTo":"867i2ot1fu.fsf@broadpark.no","subject":"Re: git repack: --depth=100000 causing larger not smaler pack file?","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-03-17T20:38:45Z","receivedAt":"2009-03-17T20:38:45Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 17 Mar 2009, Kjetil Barvik wrote:\n\n>   aloha!\n> \n>   Yesterday I run the following command on the updated GIT respository:\n> \n>     git repack -adf --window=250000 --depth=100000\n> \n>   After 280 minutes or so it finished, but the strange thing was that\n>   the resulting pack-file was larger than before.  I had expected that\n>   it should be smaler, or at least the same size as before.\n> \n>   kjetil git (my_next)$ ls -l .git/objects/pack/*\n> -r-------- 1 kjetil kjetil  2757280 2009-03-16 15:18 .git/objects/pack/pack-c5f15d5c48d6b3902a49046d7e8a8d717e167051.idx\n> -r-------- 1 kjetil kjetil 19961120 2009-03-16 15:18 .git/objects/pack/pack-c5f15d5c48d6b3902a49046d7e8a8d717e167051.pack\n> \n>   Before I started the pack file was around 19 250 000 bytes, and was\n>   the result of the following commands:\n> \n>   1) git repack -adf --window=250000 --depth=20000\n>           - not completly sure about the --window number here\n>           - the resulting pack file was a litle less than 19 100 000\n> \n>   2) 'git fetch' to get the latest GIT patches\n> \n>   3) since 'git fetch' always make an extra new \"smal\" pack file, I run\n>      the command 'git repack -ad --window=40000 --depth=10000' to be\n>      able to get one singel pack file of 19 250 000 bytes or so.\n> \n>   I can think of one thing which is spesial with the \"--depth=100000\"\n>   number, and that is that it is now larger than the total number of\n>   objects in the pack, which is around 96000 to 97000, or so.\n\nNo, the depth should have zero negative influence on the pack size.  \nFor tight compression, the larger the better.  What this will impact \nthough is runtime access to the pack data afterward.  The deeper a \ngiven object is, the slower its access will be.  But since the object \nrecency order tend to put newer objects at the top of a delta chain, \nthis should impact older objects more than recent ones.\n\n>   I have run 'git fsck --strict --full' on the pack with no resulting\n>   error/debug output or change in the file size.\n\nThere shouldn't be any.\n\n>   Any help on how to debug this?\n\nI doubt there is anything to debug.  In this case the window size is \nused to evaluate a threshold slope for matching objects in the delta \nsearch.  What we want is a broader delta tree more than a deep one in \norder to have more deltas with a lower depth limit.  Therefore a size \nthreshold is applied, based on the object distance in the delta search \nwindow (see commit c83f032e and the other ones referenced therein).\n\nBy providing a big window value, the threshold slope becomes rather flat \nand ineffective, and this changes the delta match outcome.  While delta \nselection is based on the uncompressed delta result, the compressed size \nof different deltas with the same size may vary.  I suspect you might \nhave been unlucky in that regard and this could explain the negative \neffect on the pack size.\n\n\nNicolas\n"},{"id":"109024","messageId":"86y6uwzgzo.fsf@broadpark.no","threadId":"18359","inReplyTo":"alpine.LFD.2.00.0903171608080.30483@xanadu.home","subject":"Re: git repack: --depth=100000 causing larger not smaler pack file?","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-03-23T10:11:07Z","receivedAt":"2009-03-23T10:11:07Z","isPatch":false,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"Nicolas Pitre <nico@cam.org> writes:\n\n> On Tue, 17 Mar 2009, Kjetil Barvik wrote:\n>\n>>   aloha!\n>> \n>>   Yesterday I run the following command on the updated GIT respository:\n>> \n>>     git repack -adf --window=250000 --depth=100000\n>> \n>>   After 280 minutes or so it finished, but the strange thing was that\n>>   the resulting pack-file was larger than before.  I had expected that\n>>   it should be smaler, or at least the same size as before.\n  [snip]\n>>   I can think of one thing which is spesial with the \"--depth=100000\"\n>>   number, and that is that it is now larger than the total number of\n>>   objects in the pack, which is around 96000 to 97000, or so.\n>\n> No, the depth should have zero negative influence on the pack size.  \n> For tight compression, the larger the better.  What this will impact \n> though is runtime access to the pack data afterward.  The deeper a \n> given object is, the slower its access will be.  But since the object \n> recency order tend to put newer objects at the top of a delta chain, \n> this should impact older objects more than recent ones.\n\n  I have done some more tests, and have copied the whole git/ directory\n  to a new directory (such that I do not accidentally add or delete any\n  objects/commits), and have made the following table:\n\n  All pack file sizes, F, below was computed with the following git\n  command:\n\n      git repack -adf --window=250000 --depth=D\n\n     D   |     F      | (F - F_prev) / (D - D_prev)\n  -------|------------|----------------------------\n    5000 |  19129934  |\n   10000 |  19128956  |    -978 /  5000 =  -0.1956\n   15000 |  19126077  |   -2879 /  5000 =  -0.5758\n   20000 |  19126077  |       0 /  5000 =   0\n   25000 |  19126077  |       0 /  5000 =   0\n   30000 |  19197575  |   71498 /  5000 =  14.2996\n   45000 |  19312240  |  114665 / 15000 =   7.6443\n   60000 |  19560083  |  247843 / 15000 =  16.5229\n   75000 |  19803043  |  242960 / 15000 =  16.1973\n   90000 |  19669923  | -133120 / 15000 =  -8.8746\n   95000 |  20463780  |  793857 /  5000 = 155.7714\n\n  From the table it seems that you get the smallest pack file (for this\n  particular repository) when --depth value is somewhere between 15000\n  and 25000.  And, when the --depth value was 95000 the resulting pack\n  file was (- 20463780 19126077) = 1 337 703 bytes, 1.25 MiB, or 7%\n  larger than this.\n\n> I doubt there is anything to debug.  In this case the window size is \n> used to evaluate a threshold slope for matching objects in the delta \n> search.  What we want is a broader delta tree more than a deep one in \n> order to have more deltas with a lower depth limit.  Therefore a size \n> threshold is applied, based on the object distance in the delta search \n> window (see commit c83f032e and the other ones referenced therein).\n>\n> By providing a big window value, the threshold slope becomes rather flat \n> and ineffective, and this changes the delta match outcome.  While delta \n> selection is based on the uncompressed delta result, the compressed size \n> of different deltas with the same size may vary.  I suspect you might \n> have been unlucky in that regard and this could explain the negative \n> effect on the pack size.\n\n  From the table above it seems that I have been unlucky with _all_\n  --depth values above 25000 or so.\n\n  Question: is there some low level GIT command I can run to compare 2\n  pack files to maybe be able to see the reason behind the above table?\n  Maybe to see some details about how many delta's, how big each are,\n  total sizes, etc..\n\n  -- kjetil\n\n  PS!  I have the following in my $HOME/.gitconfig file:\n\n[repack]\n\tUseDeltaBaseOffset = true\n[gc]\n\tauto = 25\n\tautopacklimit = 1\n"},{"id":"109026","messageId":"e2b179460903230320x47d98bfdl614007bed7117b45@mail.gmail.com","threadId":"18359","inReplyTo":"86y6uwzgzo.fsf@broadpark.no","subject":"Re: git repack: --depth=100000 causing larger not smaler pack file?","fromName":"Mike Ralphson","fromEmail":"mike.ralphson@gmail.com","sentAt":"2009-03-23T10:20:55Z","receivedAt":"2009-03-23T10:20:55Z","isPatch":false,"sender":{"key":"mike.ralphson@gmail.com","avatar":"https://avatars.githubusercontent.com/u/21603?v=4"},"body":"2009/3/23 Kjetil Barvik <barvik@broadpark.no>:\n>  PS!  I have the following in my $HOME/.gitconfig file:\n>\n> [repack]\n>        UseDeltaBaseOffset = true\n> [gc]\n>        auto = 25\n>        autopacklimit = 1\n\nJust an aside, but from my reading of how it works, there's very\nlittle point in setting gc.auto to anything less than 257 and\nstatistically it won't kick in predictably unless set quite a bit\nhigher (say an order of magnitude).\n\nMike\n"},{"id":"109062","messageId":"eaa105840903230705i5c8bcd7ar363a6836d67be66@mail.gmail.com","threadId":"18359","inReplyTo":"86y6uwzgzo.fsf@broadpark.no","subject":"Re: git repack: --depth=100000 causing larger not smaler pack file?","fromName":"Peter Harris","fromEmail":"git@peter.is-a-geek.org","sentAt":"2009-03-23T14:05:14Z","receivedAt":"2009-03-23T14:05:14Z","isPatch":false,"sender":{"key":"git@peter.is-a-geek.org","avatar":null},"body":"On Mon, Mar 23, 2009 at 6:11 AM, Kjetil Barvik wrote:\n>  Question: is there some low level GIT command I can run to compare 2\n>  pack files to maybe be able to see the reason behind the above table?\n>  Maybe to see some details about how many delta's, how big each are,\n>  total sizes, etc..\n\ngit verify-pack -v <pack.idx>\n\nThe columns are: SHA1 type size size-in-packfile offset-in-packfile\ndepth base-SHA1\n(the last two columns are only present for deltified objects)\n\nPeter Harris\n"},{"id":"109067","messageId":"alpine.LFD.2.00.0903230929300.30483@xanadu.home","threadId":"18359","inReplyTo":"86y6uwzgzo.fsf@broadpark.no","subject":"Re: git repack: --depth=100000 causing larger not smaler pack file?","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-03-23T14:14:13Z","receivedAt":"2009-03-23T14:14:13Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 23 Mar 2009, Kjetil Barvik wrote:\n\n> Nicolas Pitre <nico@cam.org> writes:\n> \n> > On Tue, 17 Mar 2009, Kjetil Barvik wrote:\n> >\n> >>   aloha!\n> >> \n> >>   Yesterday I run the following command on the updated GIT respository:\n> >> \n> >>     git repack -adf --window=250000 --depth=100000\n> >> \n> >>   After 280 minutes or so it finished, but the strange thing was that\n> >>   the resulting pack-file was larger than before.  I had expected that\n> >>   it should be smaler, or at least the same size as before.\n>   [snip]\n> >>   I can think of one thing which is spesial with the \"--depth=100000\"\n> >>   number, and that is that it is now larger than the total number of\n> >>   objects in the pack, which is around 96000 to 97000, or so.\n> >\n> > No, the depth should have zero negative influence on the pack size.  \n> > For tight compression, the larger the better.  What this will impact \n> > though is runtime access to the pack data afterward.  The deeper a \n> > given object is, the slower its access will be.  But since the object \n> > recency order tend to put newer objects at the top of a delta chain, \n> > this should impact older objects more than recent ones.\n> \n>   I have done some more tests, and have copied the whole git/ directory\n>   to a new directory (such that I do not accidentally add or delete any\n>   objects/commits), and have made the following table:\n> \n>   All pack file sizes, F, below was computed with the following git\n>   command:\n> \n>       git repack -adf --window=250000 --depth=D\n> \n>      D   |     F      | (F - F_prev) / (D - D_prev)\n>   -------|------------|----------------------------\n>     5000 |  19129934  |\n>    10000 |  19128956  |    -978 /  5000 =  -0.1956\n>    15000 |  19126077  |   -2879 /  5000 =  -0.5758\n>    20000 |  19126077  |       0 /  5000 =   0\n>    25000 |  19126077  |       0 /  5000 =   0\n>    30000 |  19197575  |   71498 /  5000 =  14.2996\n>    45000 |  19312240  |  114665 / 15000 =   7.6443\n>    60000 |  19560083  |  247843 / 15000 =  16.5229\n>    75000 |  19803043  |  242960 / 15000 =  16.1973\n>    90000 |  19669923  | -133120 / 15000 =  -8.8746\n>    95000 |  20463780  |  793857 /  5000 = 155.7714\n> \n>   From the table it seems that you get the smallest pack file (for this\n>   particular repository) when --depth value is somewhere between 15000\n>   and 25000.  And, when the --depth value was 95000 the resulting pack\n>   file was (- 20463780 19126077) = 1 337 703 bytes, 1.25 MiB, or 7%\n>   larger than this.\n\nThis is a bit intriguing.\n\nOf course, before going any further, you must realize that having a \ndepth of 15000 is a bit excessive.  That means that, if you have a delta \nchain with a depth of 15000 that means access to the object at the end \nof the chain will require that 14999 other objects be accessed before \nthe 15000th one is retrieved.  This will have horrible runtime \nperformances for something like 10% reduction in the best cases which is \nprobably not a good tradeoff.\n\nThis being said, I still stand by my assertion that, in theory, greater \ndelta depth should not make the pack bigger.  And your table appears to \nconfirm that, even to the point of reaching a stable size as one would \nexpect, until a breaking point is reached after which results tend to \nbecome rather random.\n\nWhat I'm suspecting in that case is some computation overflow in \ntry_delta().  Consider for instance this piece:\n\n    max_size = max_size * (max_depth - src->depth) /\n                                            (max_depth - ref_depth + 1);\n\n[ This is the treshold slope I was talking about, but contrary to\n  what I said before, it is affected by the depth not the window size. ]\n\nIn this case, if you have a max_depth of 95000, then any object larger \nthan 90461 bytes will cause a multiplication overflow, and the resulting \nmax_size will be capped to some random smaller value than expected \ndepending on the remaining bits. For example, suppose max_size = 45211, \nmax_depth = 95000 and src->depth = 0 then you should have max_size still \nequal to 45211, but in this case it'll become 0 and no delta will be \nattempted at all.  The number of deltas reported at the end of the \nrepack process probably reflects that.\n\n> > I doubt there is anything to debug.  In this case the window size is \n> > used to evaluate a threshold slope for matching objects in the delta \n> > search.  What we want is a broader delta tree more than a deep one in \n> > order to have more deltas with a lower depth limit.  Therefore a size \n> > threshold is applied, based on the object distance in the delta search \n> > window (see commit c83f032e and the other ones referenced therein).\n> >\n> > By providing a big window value, the threshold slope becomes rather flat \n> > and ineffective, and this changes the delta match outcome.  While delta \n> > selection is based on the uncompressed delta result, the compressed size \n> > of different deltas with the same size may vary.  I suspect you might \n> > have been unlucky in that regard and this could explain the negative \n> > effect on the pack size.\n> \n>   From the table above it seems that I have been unlucky with _all_\n>   --depth values above 25000 or so.\n\nSee explanation (and self correction) above.\n\n>   Question: is there some low level GIT command I can run to compare 2\n>   pack files to maybe be able to see the reason behind the above table?\n>   Maybe to see some details about how many delta's, how big each are,\n>   total sizes, etc..\n\nYes -- see the -v option of 'git verify-pack'.\n\n\nNicolas\n"}]}