{"thread":{"id":"3930","subject":"1.3.0 creating bigger packs than 1.2.3","startedAt":"2006-04-20T13:36:40Z","lastAt":"2006-04-21T03:07:25Z","messageCount":30,"participants":["Shawn Pearce","Linus Torvalds","Nicolas Pitre","Junio C Hamano","Jakub Narebski"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"18919","messageId":"20060420133640.GA31198@spearce.org","threadId":"3930","inReplyTo":null,"subject":"1.3.0 creating bigger packs than 1.2.3","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-04-20T13:36:40Z","receivedAt":"2006-04-20T13:36:40Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Apparently I have created a repository which v1.2.3 packs about 50%\nsmaller than 'next' does:\n\n  v1.2.3 (tag):\n   60M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n\n  1.2.3.gf3a4 (an older 'next'):\n  128M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n\n  1.3.0.rc4.g8060 (a fairly recent 'next'):\n  118M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n\nRepeated packing with 1.3.0.rc4.g8060 doesn't seem to change the\nsize of the pack file, its pretty consistent at 118M.\n\nGiven that disk is pretty cheap these days I'm not concerned about\nthe 2x increase but thought I'd let folks know that the packing\nimprovements in 1.3.0 seem to have taken a small step backwards\nwith regards to this particular dataset.\n\nI can make the repository available if somebody wants to look at it.\n\n-- \nShawn.\n"},{"id":"18922","messageId":"Pine.LNX.4.64.0604200745550.3701@g5.osdl.org","threadId":"3930","inReplyTo":"20060420133640.GA31198@spearce.org","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-04-20T14:47:45Z","receivedAt":"2006-04-20T14:47:45Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 20 Apr 2006, Shawn Pearce wrote:\n\n> Apparently I have created a repository which v1.2.3 packs about 50%\n> smaller than 'next' does:\n> \n>   v1.2.3 (tag):\n>    60M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n> \n>   1.2.3.gf3a4 (an older 'next'):\n>   128M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n> \n>   1.3.0.rc4.g8060 (a fairly recent 'next'):\n>   118M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n> \n> Repeated packing with 1.3.0.rc4.g8060 doesn't seem to change the\n> size of the pack file, its pretty consistent at 118M.\n\nFirst try \"git repack -a -d f\", where the \"-f\" is the magic one.\n\nWithout the -f, git repack will re-use old pack information, which is much \nmuch faster, but not as space-efficient.\n\nIf that doesn't help, it might be time to look at the actual repo, but try \nthat first.\n\n\t\tLinus\n"},{"id":"18925","messageId":"20060420150315.GB31198@spearce.org","threadId":"3930","inReplyTo":"Pine.LNX.4.64.0604200745550.3701@g5.osdl.org","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-04-20T15:03:15Z","receivedAt":"2006-04-20T15:03:15Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> wrote:\n> \n> On Thu, 20 Apr 2006, Shawn Pearce wrote:\n> \n> > Apparently I have created a repository which v1.2.3 packs about 50%\n> > smaller than 'next' does:\n> > \n> >   v1.2.3 (tag):\n> >    60M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n> > \n> >   1.2.3.gf3a4 (an older 'next'):\n> >   128M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n> > \n> >   1.3.0.rc4.g8060 (a fairly recent 'next'):\n> >   118M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n> > \n> > Repeated packing with 1.3.0.rc4.g8060 doesn't seem to change the\n> > size of the pack file, its pretty consistent at 118M.\n> \n> First try \"git repack -a -d f\", where the \"-f\" is the magic one.\n> \n> Without the -f, git repack will re-use old pack information, which is much \n> much faster, but not as space-efficient.\n> \n> If that doesn't help, it might be time to look at the actual repo, but try \n> that first.\n\nSo with 1.3.0.g56c1 \"git repack -a -d -f\" did worse:\n\n  Total 46391, written 46391 (delta 6649), reused 39742 (delta 0)\n  129M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n\nI just tried -f on v1.2.3 and it did slightly better then before:\n\n  Total 46391, written 46391 (delta 6847), reused 38012 (delta 0)\n   59M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n\n-- \nShawn.\n"},{"id":"18926","messageId":"Pine.LNX.4.64.0604200857460.3701@g5.osdl.org","threadId":"3930","inReplyTo":"20060420150315.GB31198@spearce.org","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-04-20T16:07:21Z","receivedAt":"2006-04-20T16:07:21Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 20 Apr 2006, Shawn Pearce wrote:\n> \n> So with 1.3.0.g56c1 \"git repack -a -d -f\" did worse:\n> \n>   Total 46391, written 46391 (delta 6649), reused 39742 (delta 0)\n>   129M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n> \n> I just tried -f on v1.2.3 and it did slightly better then before:\n> \n>   Total 46391, written 46391 (delta 6847), reused 38012 (delta 0)\n>    59M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n\nInteresting. The bigger packs do generate fewer deltas, but they don't \nseem to be _that_ much fewer. And the deltas themselves certainly \nshouldn't be bigger.\n\nIt almost sounds like there's a problem with choosing what to delta \nagainst, not necessarily a delta algorithm problem. Although that sounds a \nbit strange, because I wouldn't have thought we actually changed the \npacking algorithm noticeably since 1.2.3.\n\nHmm. Doing \"gitk v1.2.3.. -- pack-objects.c\" shows that I was wrong. Junio \ndid the \"hash basename and direname a bit differently\" thing, which would \nappear to change the \"find objects to delta against\" a lot. That could be \nit. \n\nYou could try to revert that change:\n\n\tgit revert eeef7135fed9b8784627c4c96e125241c06c65e1\n\nwhich needs a trivial manual fixup (remove the conflict entirely: \neverything between the \"<<<<\" and \">>>>>\" lines should go), and see if \nthat's it.\n\nYou can also try to see if\n\n\tgit repack -a -d -f --window=50\n\nmakes for a better pack (at the cost of a much slower repack). It makes \ngit try more objects to delta against, and can thus hide a bad sort order.\n\nJunio, any other suggestions?\n\n\t\tLinus\n"},{"id":"18927","messageId":"Pine.LNX.4.64.0604201206080.2215@localhost.localdomain","threadId":"3930","inReplyTo":"20060420133640.GA31198@spearce.org","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-20T16:09:22Z","receivedAt":"2006-04-20T16:09:22Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 20 Apr 2006, Shawn Pearce wrote:\n\n> Given that disk is pretty cheap these days I'm not concerned about\n> the 2x increase but thought I'd let folks know that the packing\n> improvements in 1.3.0 seem to have taken a small step backwards\n> with regards to this particular dataset.\n\n2x is a huge regression.\n\n> I can make the repository available if somebody wants to look at it.\n\nPlease.\n\n\nNicolas\n"},{"id":"18928","messageId":"20060420164351.GB31738@spearce.org","threadId":"3930","inReplyTo":"Pine.LNX.4.64.0604200857460.3701@g5.osdl.org","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-04-20T16:43:51Z","receivedAt":"2006-04-20T16:43:51Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> wrote:\n> \n> \n> On Thu, 20 Apr 2006, Shawn Pearce wrote:\n> > \n> > So with 1.3.0.g56c1 \"git repack -a -d -f\" did worse:\n> > \n> >   Total 46391, written 46391 (delta 6649), reused 39742 (delta 0)\n> >   129M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n> > \n> > I just tried -f on v1.2.3 and it did slightly better then before:\n> > \n> >   Total 46391, written 46391 (delta 6847), reused 38012 (delta 0)\n> >    59M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n\nOddly enough repacking the v1.2.3 pack using 1.3.0.g56c1 created an\neven smaller pack (\"git-repack -a -d\"):\n\n  Total 46391, written 46391 (delta 8253), reused 44985 (delta 6847)\n   49M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n\nand repacking again with \"git-repack -a -d\" chopped another 1M:\n\n  Total 46391, written 46391 (delta 8258), reused 46386 (delta 8253)\n   48M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pac\n  \nbut then adding -f definately gives us the 2x explosion again:\n\n  Total 46391, written 46391 (delta 6649), reused 37894 (delta 0)\n  129M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n\n> Interesting. The bigger packs do generate fewer deltas, but they don't \n> seem to be _that_ much fewer. And the deltas themselves certainly \n> shouldn't be bigger.\n> \n> It almost sounds like there's a problem with choosing what to delta \n> against, not necessarily a delta algorithm problem. Although that sounds a \n> bit strange, because I wouldn't have thought we actually changed the \n> packing algorithm noticeably since 1.2.3.\n> \n> Hmm. Doing \"gitk v1.2.3.. -- pack-objects.c\" shows that I was wrong. Junio \n> did the \"hash basename and direname a bit differently\" thing, which would \n> appear to change the \"find objects to delta against\" a lot. That could be \n> it. \n> \n> You could try to revert that change:\n> \n> \tgit revert eeef7135fed9b8784627c4c96e125241c06c65e1\n> \n> which needs a trivial manual fixup (remove the conflict entirely: \n> everything between the \"<<<<\" and \">>>>>\" lines should go), and see if \n> that's it.\n\nWhoa.  I did that revert and fixup on top of 'next'.  The pack\nfrom \"git-repack -a -d -f\" is now even larger due to even less\ndelta reuse:\n\n  Total 46391, written 46391 (delta 5148), reused 39565 (delta 0)\n  171M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n\n> You can also try to see if\n> \n> \tgit repack -a -d -f --window=50\n> \n> makes for a better pack (at the cost of a much slower repack). It makes \n> git try more objects to delta against, and can thus hide a bad sort order.\n\nWith --window=50 on 'next' (without the revert'):\n\n  Total 46391, written 46391 (delta 6666), reused 39723 (delta 0)\n  129M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n\nFor added measure I tried --window=100 and 500 with pretty much\nthe same result (slightly higher delta but still a 129M pack).\n\n-- \nShawn.\n"},{"id":"18930","messageId":"Pine.LNX.4.64.0604200954440.3701@g5.osdl.org","threadId":"3930","inReplyTo":"20060420164351.GB31738@spearce.org","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-04-20T17:03:31Z","receivedAt":"2006-04-20T17:03:31Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 20 Apr 2006, Shawn Pearce wrote:\n> \n> Oddly enough repacking the v1.2.3 pack using 1.3.0.g56c1 created an\n> even smaller pack (\"git-repack -a -d\"):\n\nThat's \"normal\". Repacking without -f will always pack _more_, never less. \nSo a different packing algorithm can only improve (of course, usually not \nby a huge margin, and it quickly diminishes).\n\n> but then adding -f definately gives us the 2x explosion again:\n> \n>   Total 46391, written 46391 (delta 6649), reused 37894 (delta 0)\n>   129M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n\nRight. Doing the -f will discard any old packing info, so if the new \npacking algorithm has problems (and it obviously does), then using -f will \nshow them.\n\n> > You could try to revert that change:\n> > \n> > \tgit revert eeef7135fed9b8784627c4c96e125241c06c65e1\n> \n> Whoa.  I did that revert and fixup on top of 'next'.  The pack\n> from \"git-repack -a -d -f\" is now even larger due to even less\n> delta reuse:\n\nOk, so that wasn't it, and the new sort order is superior.\n\nThat means that it probably _is_ the delta changes themselves (probably \ncommit c13c6bf7 \"diff-delta: bound hash list length to avoid O(m*n) \nbehavior\". You can try\n\n\tgit revert c13c6bf7\n\nto see if that's it. Although Nico already showed interest, and if you \nmake the archive available to him, he's sure to figure it out.\n\n> With --window=50 on 'next' (without the revert'):\n> \n>   Total 46391, written 46391 (delta 6666), reused 39723 (delta 0)\n>   129M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n\nYeah, that didn't do much. Slightly more deltas than without, but not a \nlot, and it didn't matter much size-wise.\n\nYou can try \"--depth=50\" (slogan: more \"hot delta on delta action\"), but \nit's looking less and less like a delta selection issue, and more and more \nlike the deltas themselves are deproved.\n\n\t\t\tLinus\n"},{"id":"18931","messageId":"7vk69kyxbj.fsf@assigned-by-dhcp.cox.net","threadId":"3930","inReplyTo":"Pine.LNX.4.64.0604200954440.3701@g5.osdl.org","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-20T17:24:32Z","receivedAt":"2006-04-20T17:24:32Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> You can try \"--depth=50\" (slogan: more \"hot delta on delta action\"), but \n> it's looking less and less like a delta selection issue, and more and more \n> like the deltas themselves are deproved.\n\nI do not think I have time to look into this today until late\nnight, but one thing I noticed is that trying to delta more\nthings sometimes tend to produce bigger result X-<.  \n\nAt the end of pack-objects.c::find_deltas(), there is a code\nthat is commented out, which is remnant from a failed\nexperiment.  What it tried to do was to avoid placing an object\nwhose delta depth is already window-size back into the\ncandidates list, which means the next object gets compared with\none object more than otherwise would be (the extra one being the\noldest one in the window -- which might not produce better delta\nthan the maxed out one, but the delta with the maxed out one\nwould not be used anyway).  The result was noticeably worse\noverall packsize with more deltified objects.\n\nWe might be better off favoring compressed undeltified\nrepresentation over deltified representation a bit more\naggressively.  Currently we allow delta as big as half the\nuncompressed size minus 20-byte overhead or something like that;\ntweaking that limit might show improvements.\n"},{"id":"18932","messageId":"20060420173131.GF31738@spearce.org","threadId":"3930","inReplyTo":"Pine.LNX.4.64.0604200954440.3701@g5.osdl.org","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-04-20T17:31:31Z","receivedAt":"2006-04-20T17:31:31Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"I just spent some time bisecting this issue and it looks like the\nfollowing change by Junio may be the culprit:\n\n  commit 1d6b38cc76c348e2477506ca9759fc241e3d0d46\n  Author: Junio C Hamano <junkio@cox.net>\n  Date:   Wed Feb 22 22:10:24 2006 -0800\n  \n      pack-objects: use full pathname to help hashing with \"thin\" pack.\n      \n      This uses the same hashing algorithm to the \"preferred base\n      tree\" objects and the incoming pathnames, to group the same\n      files from different revs together, while spreading files with\n      the same basename in different directories.\n      \n      Signed-off-by: Junio C Hamano <junkio@cox.net>\n  \n  :100644 100644 af3bdf5d358b8a47ed23bcb7e9721e956eb59d60 3a16b7e4ce25ec05c64817dfd92dd9d517ab9dd3 M      pack-objects.c\n\n\nLinus Torvalds <torvalds@osdl.org> wrote:\n> \n> \n> On Thu, 20 Apr 2006, Shawn Pearce wrote:\n> > \n> > Oddly enough repacking the v1.2.3 pack using 1.3.0.g56c1 created an\n> > even smaller pack (\"git-repack -a -d\"):\n> \n> That's \"normal\". Repacking without -f will always pack _more_, never less. \n> So a different packing algorithm can only improve (of course, usually not \n> by a huge margin, and it quickly diminishes).\n> \n> > but then adding -f definately gives us the 2x explosion again:\n> > \n> >   Total 46391, written 46391 (delta 6649), reused 37894 (delta 0)\n> >   129M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n> \n> Right. Doing the -f will discard any old packing info, so if the new \n> packing algorithm has problems (and it obviously does), then using -f will \n> show them.\n> \n> > > You could try to revert that change:\n> > > \n> > > \tgit revert eeef7135fed9b8784627c4c96e125241c06c65e1\n> > \n> > Whoa.  I did that revert and fixup on top of 'next'.  The pack\n> > from \"git-repack -a -d -f\" is now even larger due to even less\n> > delta reuse:\n> \n> Ok, so that wasn't it, and the new sort order is superior.\n> \n> That means that it probably _is_ the delta changes themselves (probably \n> commit c13c6bf7 \"diff-delta: bound hash list length to avoid O(m*n) \n> behavior\". You can try\n> \n> \tgit revert c13c6bf7\n> \n> to see if that's it. Although Nico already showed interest, and if you \n> make the archive available to him, he's sure to figure it out.\n> \n> > With --window=50 on 'next' (without the revert'):\n> > \n> >   Total 46391, written 46391 (delta 6666), reused 39723 (delta 0)\n> >   129M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n> \n> Yeah, that didn't do much. Slightly more deltas than without, but not a \n> lot, and it didn't matter much size-wise.\n> \n> You can try \"--depth=50\" (slogan: more \"hot delta on delta action\"), but \n> it's looking less and less like a delta selection issue, and more and more \n> like the deltas themselves are deproved.\n> \n> \t\t\tLinus\n\n-- \nShawn.\n"},{"id":"18934","messageId":"Pine.LNX.4.64.0604201337220.2215@localhost.localdomain","threadId":"3930","inReplyTo":"Pine.LNX.4.64.0604200954440.3701@g5.osdl.org","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-20T17:41:53Z","receivedAt":"2006-04-20T17:41:53Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 20 Apr 2006, Linus Torvalds wrote:\n\n> That means that it probably _is_ the delta changes themselves (probably \n> commit c13c6bf7 \"diff-delta: bound hash list length to avoid O(m*n) \n> behavior\". You can try\n> \n> \tgit revert c13c6bf7\n> \n> to see if that's it. Although Nico already showed interest, and if you \n> make the archive available to him, he's sure to figure it out.\n\nIt is not that.  With that code disabled there is still a 2x pack size.\n\nSubstituting diff-delta.c from the version in 1.2.3 doesn't solve the \nissue either.\n\n\nNicolas\n"},{"id":"18935","messageId":"Pine.LNX.4.64.0604201352330.2215@localhost.localdomain","threadId":"3930","inReplyTo":"20060420173131.GF31738@spearce.org","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-20T17:54:51Z","receivedAt":"2006-04-20T17:54:51Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 20 Apr 2006, Shawn Pearce wrote:\n\n> I just spent some time bisecting this issue and it looks like the\n> following change by Junio may be the culprit:\n> \n>   commit 1d6b38cc76c348e2477506ca9759fc241e3d0d46\n>   Author: Junio C Hamano <junkio@cox.net>\n>   Date:   Wed Feb 22 22:10:24 2006 -0800\n>   \n>       pack-objects: use full pathname to help hashing with \"thin\" pack.\n>       \n>       This uses the same hashing algorithm to the \"preferred base\n>       tree\" objects and the incoming pathnames, to group the same\n>       files from different revs together, while spreading files with\n>       the same basename in different directories.\n>       \n>       Signed-off-by: Junio C Hamano <junkio@cox.net>\n>   \n>   :100644 100644 af3bdf5d358b8a47ed23bcb7e9721e956eb59d60 3a16b7e4ce25ec05c64817dfd92dd9d517ab9dd3 M      pack-objects.c\n\nHmmm... This one is for Junio to fix I'd say.  Not sure what it does.\n\n\nNicolas\n"},{"id":"18936","messageId":"20060420175554.GH31738@spearce.org","threadId":"3930","inReplyTo":"Pine.LNX.4.64.0604200954440.3701@g5.osdl.org","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-04-20T17:55:54Z","receivedAt":"2006-04-20T17:55:54Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> wrote:\n> Ok, so that wasn't it, and the new sort order is superior.\n> \n> That means that it probably _is_ the delta changes themselves (probably \n> commit c13c6bf7 \"diff-delta: bound hash list length to avoid O(m*n) \n> behavior\". You can try\n> \n> \tgit revert c13c6bf7\n\nNo effect.\n \n> to see if that's it. Although Nico already showed interest, and if you \n> make the archive available to him, he's sure to figure it out.\n\nI sent the URL privately to Nico as I did not want the repository\nto be publically available before next Tuesday.\n\n> You can try \"--depth=50\" (slogan: more \"hot delta on delta action\"), but \n> it's looking less and less like a delta selection issue, and more and more \n> like the deltas themselves are deproved.\n\nNo effect at either 50 or 100.\n\nThe more that I think about it the more it seems possible that the\npathname hashing is what may be causing the problem.  Not only did\nbisect point to 1d6b38cc76c348e2477506ca9759fc241e3d0d46 but the\ndirectory which contains the bulk of the space has many files with\nthe same name located in different directories:\n\n\tresults/MT/Math/10000/0-11-AdjLite.deg\n\tresults/MT/Math/10000/0-12-AdjLite.deg\n\t...\n\tresults/MT/Math/30000/2-11-AdjLite.deg\n\tresults/MT/Math/30000/2-12-AdjLite.deg\n\t...\n\tresults/Rand48/Math/10000/2-11-AdjLite.deg\n\tresults/Rand48/Math/10000/2-12-AdjLite.deg\n\t...\n\tresults/Rand48/Math/30000/2-11-AdjLite.deg\n\tresults/Rand48/Math/30000/2-12-AdjLite.deg\n\t...\n\nFor example the name '0-11-AdjLite.deg' occurs in 63 directories and\nnone of those occurrances are likely to delta against one another\nvery well.  Also most of these files only have 1 or 2 revisions,\nso there is very little per-file history.\n\n-- \nShawn.\n"},{"id":"18938","messageId":"Pine.LNX.4.64.0604201414490.2215@localhost.localdomain","threadId":"3930","inReplyTo":"20060420175554.GH31738@spearce.org","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-20T18:24:34Z","receivedAt":"2006-04-20T18:24:34Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 20 Apr 2006, Shawn Pearce wrote:\n\n> The more that I think about it the more it seems possible that the\n> pathname hashing is what may be causing the problem.  Not only did\n> bisect point to 1d6b38cc76c348e2477506ca9759fc241e3d0d46 but the\n> directory which contains the bulk of the space has many files with\n> the same name located in different directories:\n[...]\n\nBut the bad commit according to your bisection talks about \"thin\" packs \nwhich are not involved in your case.  So something looks fishy with that \ncommit which should not have touched path hashing in the non-thin pack \ncase...  I think...\n\n\nNicolas\n"},{"id":"18939","messageId":"7v8xq0yteb.fsf@assigned-by-dhcp.cox.net","threadId":"3930","inReplyTo":"Pine.LNX.4.64.0604201414490.2215@localhost.localdomain","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-20T18:49:16Z","receivedAt":"2006-04-20T18:49:16Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre <nico@cam.org> writes:\n\n> On Thu, 20 Apr 2006, Shawn Pearce wrote:\n>\n>> The more that I think about it the more it seems possible that the\n>> pathname hashing is what may be causing the problem.  Not only did\n>> bisect point to 1d6b38cc76c348e2477506ca9759fc241e3d0d46 but the\n>> directory which contains the bulk of the space has many files with\n>> the same name located in different directories:\n> [...]\n>\n> But the bad commit according to your bisection talks about \"thin\" packs \n> which are not involved in your case.  So something looks fishy with that \n> commit which should not have touched path hashing in the non-thin pack \n> case...  I think...\n\nI think this explains it.  The new code hashes full-path, but\nplaces bins for the paths with the same basename next to each\nother, so before Makefile and doc/Makefile and t/Makefile were\nall in the same bin, but now they are in three different bins\nnext to each other.\n\nI originally thought, with one single notable exception of\nMakefile, having the identically named file in many different\ndirectories is not common nor sane, and the new code favors to\ndelta with the exact same path for deeper history over wasting\ndelta window for making delta with objects with the same name in\ndifferent places in more recent history.  I think I benched this\nwith kernel repository (git.git was too small for that).\n\nBut I suspect we have a built-in \"we sort bigger to smaller, and\nwe cut off when we switch bins\" somewhere in find_delta() loop,\nwhich I do not recall touching when I did that change, so that\nmay be interfering and preventing 0-11-AdjLite.deg from all over\nthe place to delta against each other.\n"},{"id":"18947","messageId":"Pine.LNX.4.64.0604201630320.2215@localhost.localdomain","threadId":"3930","inReplyTo":"7v8xq0yteb.fsf@assigned-by-dhcp.cox.net","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-20T21:02:25Z","receivedAt":"2006-04-20T21:02:25Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 20 Apr 2006, Junio C Hamano wrote:\n\n> Nicolas Pitre <nico@cam.org> writes:\n> \n> > On Thu, 20 Apr 2006, Shawn Pearce wrote:\n> >\n> >> The more that I think about it the more it seems possible that the\n> >> pathname hashing is what may be causing the problem.  Not only did\n> >> bisect point to 1d6b38cc76c348e2477506ca9759fc241e3d0d46 but the\n> >> directory which contains the bulk of the space has many files with\n> >> the same name located in different directories:\n> > [...]\n> >\n> > But the bad commit according to your bisection talks about \"thin\" packs \n> > which are not involved in your case.  So something looks fishy with that \n> > commit which should not have touched path hashing in the non-thin pack \n> > case...  I think...\n> \n> I think this explains it.  The new code hashes full-path, but\n> places bins for the paths with the same basename next to each\n> other, so before Makefile and doc/Makefile and t/Makefile were\n> all in the same bin, but now they are in three different bins\n> next to each other.\n\nThat is fine.  In fact I did try with a tweaked name_hash() that \ncompletely ignored all directory components and the resulting pack was \neven bigger, much bigger, when repacking Shawn's repo.\n\n> I originally thought, with one single notable exception of\n> Makefile, having the identically named file in many different\n> directories is not common nor sane,\n\nI'd tend to disagree with that but...\n\n> and the new code favors to\n> delta with the exact same path for deeper history over wasting\n> delta window for making delta with objects with the same name in\n> different places in more recent history.  I think I benched this\n> with kernel repository (git.git was too small for that).\n\nThis is obviously fine.  And if a file in a given directory has few \nrevisions then the delta window will consider objects for a file with \nthe same name in other directories as well, which is also sensible.  So \nif files of the same name are located in different directories they \nshould delta well against each other if they're similar enough.  This \nshould cover Shawn's repo layout.\n\n> But I suspect we have a built-in \"we sort bigger to smaller, and\n> we cut off when we switch bins\" somewhere in find_delta() loop,\n> which I do not recall touching when I did that change, so that\n> may be interfering and preventing 0-11-AdjLite.deg from all over\n> the place to delta against each other.\n\nI just cannot find something that would do that in the code.  When \n--no-reuse-delta is specified, the only things that will break the loop\nin find_delta() is when try_delta() returns -1, and that happens only \nwhen changing object type or when the size difference is too big, but \nnothing looks at the name hash.\n\nIt is also hard to corelate it with commit 1d6b38cc which is the one \nthat introduced the regression.\n\n\nNicolas\n"},{"id":"18949","messageId":"7vodywvsrq.fsf@assigned-by-dhcp.cox.net","threadId":"3930","inReplyTo":"20060420173131.GF31738@spearce.org","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-20T21:31:05Z","receivedAt":"2006-04-20T21:31:05Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce <spearce@spearce.org> writes:\n\n> I just spent some time bisecting this issue and it looks like the\n> following change by Junio may be the culprit:\n>\n>   commit 1d6b38cc76c348e2477506ca9759fc241e3d0d46\n>   Author: Junio C Hamano <junkio@cox.net>\n>   Date:   Wed Feb 22 22:10:24 2006 -0800\n>   \n>       pack-objects: use full pathname to help hashing with \"thin\" pack.\n>       \n>       This uses the same hashing algorithm to the \"preferred base\n>       tree\" objects and the incoming pathnames, to group the same\n>       files from different revs together, while spreading files with\n>       the same basename in different directories.\n>       \n>       Signed-off-by: Junio C Hamano <junkio@cox.net>\n>   \n\nUnfortunately, that is not the same hash we use in v1.3.0, so we\nneed to look elsewhere for interactions.\n\nv1.2.3 hash was base-name only.  doc/Makefile and t/Makefile\nwere thrown in the same bin and sorted by size.  When the\nhistory you are packing is deep, and doc/Makefile and t/Makefile\nare not related at all, this made effective size of delta window\n1/N where N is the number of such duplicates.\n\nThe one you found above uses a hash that is fully full-path.\nThe two are in completely different bins, and bins are totally\nrandom.  This was not a good strategy.\n\nv1.3.0 hash is base-name hash concatenated with leading-path\nhas.  t/Makefile and doc/Makefile go in separate bins, but the\nbins are close to each other; this avoids the problem in v1.2.3\nwhen you have deep history, but at the same time if you do not\nhave many many versions of t/Makefile to overflow the delta\nwindow, it gives t/Makefile a chance to delta with doc/Makefile.\n\nThe earlier observation by Linus on reverting eeef7135 is\nconsistent with it; that commit was the one that introduced\nv1.3.0 hash.\n\nYou could try this patch to resurrect the hash used in v1.2.3,\nand you may get better packing for your particular repository;\nbut I am not sure if it gives better results in the general\ncase.  I am running the test myself now while waiting for my\nday-job database to load X-<.\n\nNOTE NOTE NOTE.  The hash in v1.2.3 was done with the basename\n(relying on rev-list --objects to only show the basename) and\nhashed from front to back.  The current one uses the same hash\nscrambling function, but it hashes from back to front, and it\nknows rev-list --objects gives it a full path.\n\nWhat this patch does is to stop the hashing after we are done\nwith the basename part.  So it still gives different hash value\nto the same path from v1.2.3 version, but the distribution\nshould be equivalent.\n\nNOTE 2.  Feeding output from the current \"rev-list --objects\" to\nv1.2.3 pack-object is the same as \"hash full path and spread\nthings out\" intermediate version, which is the worst performer.\n\n-- >8 --\ngit diff\ndiff --git a/pack-objects.c b/pack-objects.c\nindex 09f4f2c..e58e169 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -492,6 +492,8 @@ static unsigned name_hash(struct name_pa\n \t\tname_hash = hash;\n \t\thash = 0;\n \t}\n+\treturn name_hash;\n+\n \tfor (p = path; p; p = p->up) {\n \t\thash = hash * 11 + '/';\n \t\tn = p->elem + p->len;\n"},{"id":"18950","messageId":"7vfyk8vscl.fsf@assigned-by-dhcp.cox.net","threadId":"3930","inReplyTo":"Pine.LNX.4.64.0604201630320.2215@localhost.localdomain","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-20T21:40:10Z","receivedAt":"2006-04-20T21:40:10Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre <nico@cam.org> writes:\n\n>> But I suspect we have a built-in \"we sort bigger to smaller, and\n>> we cut off when we switch bins\" somewhere in find_delta() loop,\n>> which I do not recall touching when I did that change, so that\n>> may be interfering and preventing 0-11-AdjLite.deg from all over\n>> the place to delta against each other.\n>\n> I just cannot find something that would do that in the code.  When \n> --no-reuse-delta is specified, the only things that will break the loop\n> in find_delta() is when try_delta() returns -1, and that happens only \n> when changing object type or when the size difference is too big, but \n> nothing looks at the name hash.\n\nThe list is sorted by type then hash then size (type_size_sort),\nso if you have t/Makefile that are big medium small too-small\nand then doc/Makefile that are big medium, once you see the\ntoo-small t/Makefile it would not consider the big doc/Makefile\nas a candidate X-<.\n\nThis _might_ improve things:\n\ndiff --git a/pack-objects.c b/pack-objects.c\nindex 09f4f2c..0c6abe9 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -1037,7 +1039,7 @@ static int try_delta(struct unpacked *cu\n \tsizediff = oldsize > size ? oldsize - size : size - oldsize;\n \n \tif (size < 50)\n-\t\treturn -1;\n+\t\treturn 0;\n \tif (old_entry->depth >= max_depth)\n \t\treturn 0;\n \n@@ -1052,7 +1054,7 @@ static int try_delta(struct unpacked *cu\n \tif (cur_entry->delta)\n \t\tmax_size = cur_entry->delta_size-1;\n \tif (sizediff >= max_size)\n-\t\treturn -1;\n+\t\treturn 0;\n \tdelta_buf = diff_delta(old->data, oldsize,\n \t\t\t       cur->data, size, &delta_size, max_size);\n \tif (!delta_buf)\n"},{"id":"18951","messageId":"20060420215346.GA32748@spearce.org","threadId":"3930","inReplyTo":"7vodywvsrq.fsf@assigned-by-dhcp.cox.net","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-04-20T21:53:46Z","receivedAt":"2006-04-20T21:53:46Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano <junkio@cox.net> wrote:\n> Shawn Pearce <spearce@spearce.org> writes:\n> \n> > I just spent some time bisecting this issue and it looks like the\n> > following change by Junio may be the culprit:\n> >\n> >   commit 1d6b38cc76c348e2477506ca9759fc241e3d0d46\n[snip]\n> Unfortunately, that is not the same hash we use in v1.3.0, so we\n> need to look elsewhere for interactions.\n\nPity.  Then either bisect goofed or there was a goof in meatspace\nwhile using bisect.  I honestly expected bisect to point at the\nproblem commit.  I tried reverting 1d6b38cc but it didn't apply\ncleanly and I didn't feel like working through all of the conflicts\nat the time.\n \n[snip]\n> The earlier observation by Linus on reverting eeef7135 is\n> consistent with it; that commit was the one that introduced\n> v1.3.0 hash.\n\nYet reverting that didn't help either.\n \n[snip]\n> You could try this patch to resurrect the hash used in v1.2.3,\n> and you may get better packing for your particular repository;\n> but I am not sure if it gives better results in the general\n> case.  I am running the test myself now while waiting for my\n> day-job database to load X-<.\n[snip]\n\nNope.  When applied to 'next' it didn't help very much:\n\n  Total 46391, written 46391 (delta 6466), reused 38662 (delta 0)\n  118M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n\n\nJust to note: the 1.3.0 packer is saving 1M in the GIT repository\nover the 1.2.3 packer.  So for a real project it does seem to have\nsome benefit.  And if you benchmarked the 1.3.0 packer against\nthe Linux kernel and found it to be better than the 1.2.3 packer\nthat's even better.\n\nI think this repository of mine may just be a degenerate case which\nGIT doesn't pack very well.  GIT can't be all things to all people!\n\n-- \nShawn.\n"},{"id":"18952","messageId":"e2902t$dnq$1@sea.gmane.org","threadId":"3930","inReplyTo":"7vodywvsrq.fsf@assigned-by-dhcp.cox.net","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-04-20T21:56:49Z","receivedAt":"2006-04-20T21:56:49Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Junio C Hamano wrote:\n\n> v1.2.3 hash was base-name only.  doc/Makefile and t/Makefile\n> were thrown in the same bin and sorted by size.  When the\n> history you are packing is deep, and doc/Makefile and t/Makefile\n> are not related at all, this made effective size of delta window\n> 1/N where N is the number of such duplicates.\n> \n> The one you found above uses a hash that is fully full-path.\n> The two are in completely different bins, and bins are totally\n> random.  This was not a good strategy.\n> \n> v1.3.0 hash is base-name hash concatenated with leading-path\n> has.  t/Makefile and doc/Makefile go in separate bins, but the\n> bins are close to each other; this avoids the problem in v1.2.3\n> when you have deep history, but at the same time if you do not\n> have many many versions of t/Makefile to overflow the delta\n> window, it gives t/Makefile a chance to delta with doc/Makefile.\n[...]\n> You could try this patch to resurrect the hash used in v1.2.3,\n> and you may get better packing for your particular repository;\n> but I am not sure if it gives better results in the general\n> case.  I am running the test myself now while waiting for my\n> day-job database to load X-<.\n\nPerhaps the packing code could check which version gives smaller pack, or at\nleast be instructed that one might want different packing heuristic for\nspecific repository? Surely 2x difference in size is worth considering (and\ncomplication)...\n\n-- \nJakub Narebski\nWarsaw, Poland\n"},{"id":"18953","messageId":"20060420220240.GB32748@spearce.org","threadId":"3930","inReplyTo":"7vfyk8vscl.fsf@assigned-by-dhcp.cox.net","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-04-20T22:02:40Z","receivedAt":"2006-04-20T22:02:40Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano <junkio@cox.net> wrote:\n> Nicolas Pitre <nico@cam.org> writes:\n> \n> >> But I suspect we have a built-in \"we sort bigger to smaller, and\n> >> we cut off when we switch bins\" somewhere in find_delta() loop,\n> >> which I do not recall touching when I did that change, so that\n> >> may be interfering and preventing 0-11-AdjLite.deg from all over\n> >> the place to delta against each other.\n> >\n> > I just cannot find something that would do that in the code.  When \n> > --no-reuse-delta is specified, the only things that will break the loop\n> > in find_delta() is when try_delta() returns -1, and that happens only \n> > when changing object type or when the size difference is too big, but \n> > nothing looks at the name hash.\n> \n> The list is sorted by type then hash then size (type_size_sort),\n> so if you have t/Makefile that are big medium small too-small\n> and then doc/Makefile that are big medium, once you see the\n> too-small t/Makefile it would not consider the big doc/Makefile\n> as a candidate X-<.\n> \n> This _might_ improve things:\n> \n> diff --git a/pack-objects.c b/pack-objects.c\n> index 09f4f2c..0c6abe9 100644\n> --- a/pack-objects.c\n> +++ b/pack-objects.c\n> @@ -1037,7 +1039,7 @@ static int try_delta(struct unpacked *cu\n>  \tsizediff = oldsize > size ? oldsize - size : size - oldsize;\n>  \n>  \tif (size < 50)\n> -\t\treturn -1;\n> +\t\treturn 0;\n>  \tif (old_entry->depth >= max_depth)\n>  \t\treturn 0;\n>  \n> @@ -1052,7 +1054,7 @@ static int try_delta(struct unpacked *cu\n>  \tif (cur_entry->delta)\n>  \t\tmax_size = cur_entry->delta_size-1;\n>  \tif (sizediff >= max_size)\n> -\t\treturn -1;\n> +\t\treturn 0;\n>  \tdelta_buf = diff_delta(old->data, oldsize,\n>  \t\t\t       cur->data, size, &delta_size, max_size);\n>  \tif (!delta_buf)\n\nHoly cow, it did:\n\n  Total 46391, written 46391 (delta 8391), reused 37774 (delta 0)\n   46M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n\nThat's the smallest packing I've seen yet.  And it doesn't have a\nnegative affect on repacking GIT either.\n\n-- \nShawn.\n"},{"id":"18954","messageId":"7vy7xzvpsg.fsf@assigned-by-dhcp.cox.net","threadId":"3930","inReplyTo":"20060420220240.GB32748@spearce.org","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-20T22:35:27Z","receivedAt":"2006-04-20T22:35:27Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce <spearce@spearce.org> writes:\n\n> Junio C Hamano <junkio@cox.net> wrote:\n>\n>> The list is sorted by type then hash then size (type_size_sort),\n>> so if you have t/Makefile that are big medium small too-small\n>> and then doc/Makefile that are big medium, once you see the\n>> too-small t/Makefile it would not consider the big doc/Makefile\n>> as a candidate X-<.\n>> \n>> This _might_ improve things:\n>>... \n>\n> Holy cow, it did:\n>\n>   Total 46391, written 46391 (delta 8391), reused 37774 (delta 0)\n>    46M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n>\n> That's the smallest packing I've seen yet.  And it doesn't have a\n> negative affect on repacking GIT either.\n\nThanks for trying.  Mind trying one more?\n\nI suspect the test patch makes pack-objects a lot more\nexpensive.\n\nThe code before the test patch said \"if the size is very small\nor size difference is too great, do not consider this, and do\nnot consider any more objects in the delta window, because we\nknow they are either even smaller of the same path, they have\ndifferent names, or they are of different type\".  The test patch\nyou tried was a quick and dirty hack that said \"under the\ntoo-small condition, skip this one, but keep trying the rest of\nthe delta window\".\n\nHere is a cleaned up patch.  What it does is \"under the\ntoo-small condition, see if the object has the same basename,\nand if so keep going, but otherwise skip the rest as before\".\n\nIf you have objects like this and are trying to pack the first\nobject (this list is sorted in the order pack-object tries):\n\n       (size)\t(path)\n\t1000\tt/0-11-AdjLite.deg\n          10\tt/0-11-AdjLite.deg\n         800\ts/0-11-AdjLite.deg\n\t  20\tt/0-12-AdjLite.deg\n\nthe current code stops after checking t/0-11-AdjLite.deg.  The\ntest patch tries all of them.  This patch skips that file, but\ntries \"s/0-11-AdjLite.deg\", and then stops at the next one.\n\n-- >8 --\n\ndiff --git a/pack-objects.c b/pack-objects.c\nindex 09f4f2c..2173709 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -1036,8 +1036,6 @@ static int try_delta(struct unpacked *cu\n \toldsize = old_entry->size;\n \tsizediff = oldsize > size ? oldsize - size : size - oldsize;\n \n-\tif (size < 50)\n-\t\treturn -1;\n \tif (old_entry->depth >= max_depth)\n \t\treturn 0;\n \n@@ -1048,20 +1046,27 @@ static int try_delta(struct unpacked *cu\n \t * more space-efficient (deletes don't have to say _what_ they\n \t * delete).\n \t */\n-\tmax_size = size / 2 - 20;\n-\tif (cur_entry->delta)\n-\t\tmax_size = cur_entry->delta_size-1;\n-\tif (sizediff >= max_size)\n-\t\treturn -1;\n-\tdelta_buf = diff_delta(old->data, oldsize,\n-\t\t\t       cur->data, size, &delta_size, max_size);\n-\tif (!delta_buf)\n+\tif (50 <= size) {\n+\t\tmax_size = size / 2 - 20;\n+\t\tif (cur_entry->delta)\n+\t\t\tmax_size = cur_entry->delta_size-1;\n+\t\tif (sizediff < max_size) {\n+\t\t\tdelta_buf = diff_delta(old->data, oldsize,\n+\t\t\t\t\t       cur->data, size,\n+\t\t\t\t\t       &delta_size, max_size);\n+\t\t\tif (!delta_buf)\n+\t\t\t\treturn 0;\n+\t\t\tcur_entry->delta = old_entry;\n+\t\t\tcur_entry->delta_size = delta_size;\n+\t\t\tcur_entry->depth = old_entry->depth + 1;\n+\t\t\tfree(delta_buf);\n+\t\t\treturn 0;\n+\t\t}\n+\t}\n+\t/* Keep going as long as the basename matches */\n+\tif (((cur_entry->hash ^ old_entry->hash) >>DIRBITS) == 0)\n \t\treturn 0;\n-\tcur_entry->delta = old_entry;\n-\tcur_entry->delta_size = delta_size;\n-\tcur_entry->depth = old_entry->depth + 1;\n-\tfree(delta_buf);\n-\treturn 0;\n+\treturn -1;\n }\n \n static void progress_interval(int signum)\n"},{"id":"18955","messageId":"Pine.LNX.4.64.0604201545190.3701@g5.osdl.org","threadId":"3930","inReplyTo":"20060420220240.GB32748@spearce.org","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-04-20T22:59:01Z","receivedAt":"2006-04-20T22:59:01Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 20 Apr 2006, Shawn Pearce wrote:\n\n> Junio C Hamano <junkio@cox.net> wrote:\n> > \n> > This _might_ improve things:\n> > \n> > diff --git a/pack-objects.c b/pack-objects.c\n> > index 09f4f2c..0c6abe9 100644\n> > --- a/pack-objects.c\n> > +++ b/pack-objects.c\n> > @@ -1037,7 +1039,7 @@ static int try_delta(struct unpacked *cu\n> >  \tsizediff = oldsize > size ? oldsize - size : size - oldsize;\n> >  \n> >  \tif (size < 50)\n> > -\t\treturn -1;\n> > +\t\treturn 0;\n> >  \tif (old_entry->depth >= max_depth)\n> >  \t\treturn 0;\n> >  \n> > @@ -1052,7 +1054,7 @@ static int try_delta(struct unpacked *cu\n> >  \tif (cur_entry->delta)\n> >  \t\tmax_size = cur_entry->delta_size-1;\n> >  \tif (sizediff >= max_size)\n> > -\t\treturn -1;\n> > +\t\treturn 0;\n> >  \tdelta_buf = diff_delta(old->data, oldsize,\n> >  \t\t\t       cur->data, size, &delta_size, max_size);\n> >  \tif (!delta_buf)\n> \n> Holy cow, it did:\n> \n>   Total 46391, written 46391 (delta 8391), reused 37774 (delta 0)\n>    46M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n> \n> That's the smallest packing I've seen yet.  And it doesn't have a\n> negative affect on repacking GIT either.\n\nI think I know what's going on, and why your bisection claimed it was the \nre-hashing change that was the problem, even though it really wasn't.\n\nThat\n\n\tif (sizediff >= max_size)\n\t\treturn -1;\n\ncheck is actually fairly _old_. It's from June 2005, ie it's from pretty \nmuch the first two days of that packing thing existing in the first place.\n\n(The initial repacking was done June 25th, with a lot of tweaking over the \nnext few days. That sizediff thing was part of the fairly early tweaking).\n\nThe thing is, that check made sense back then. Why? Because we sorted \nthings in decreasing size order back then (I think this was before we even \ndid any name-based heuristic sorting at all), so that when we tried the \ndelta algorithm, and the size diff was bigger than the last delta size, we \npretty much _knew_ the new delta would be bigger still, and there was no \npoint in continuing with try_delta.\n\nHOWEVER. We have since changed the sorting to sort according to name \nbefore it sorts according to size, so that old heuristic that depended on \nthe size being monotonically increasing simply doesn't make any sense any \nmore.\n\nSo I think at that second \"return -1\" really _should_ be changed to a \n\"return 0\", and not just because it helps your particular case. It's \nliterally a bug these days, because the assumptions that caused it to \nreturn -1 simply aren't true any more.\n\n(It wasn't _strictly_ true even originally: even if the sizediff is huge, \nthe _delta_ may not be huge, since we can delete data with a small delta. \nSo it's quite likely that we should compare the \"old is bigger than new\" \nand \"new is bigger than old\" separately and have different heuristics for \nthem. Again, that was simply not much of an issue back when we sorted just \nby size).\n\nSo even the \"return 0\" might not be completely right. We might actually \nwant to look at how big the delta is, and return only once that fails.\n\n\t\t\tLinus\n"},{"id":"18956","messageId":"7vr73rvoik.fsf@assigned-by-dhcp.cox.net","threadId":"3930","inReplyTo":"Pine.LNX.4.64.0604201630320.2215@localhost.localdomain","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-20T23:02:59Z","receivedAt":"2006-04-20T23:02:59Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre <nico@cam.org> writes:\n\n>> I originally thought, with one single notable exception of\n>> Makefile, having the identically named file in many different\n>> directories is not common nor sane,\n>\n> I'd tend to disagree with that but...\n\nI disagree with that myself now.  The kernel tree has many\nfiles with the same basename (e.g. arch/*/kernel/irq.c).\n\nIt is a different issue if they are good delta base candidates\nwith each other, though.\n"},{"id":"18959","messageId":"Pine.LNX.4.64.0604202050180.2215@localhost.localdomain","threadId":"3930","inReplyTo":"7vfyk8vscl.fsf@assigned-by-dhcp.cox.net","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-21T00:52:01Z","receivedAt":"2006-04-21T00:52:01Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 20 Apr 2006, Junio C Hamano wrote:\n\n> Nicolas Pitre <nico@cam.org> writes:\n> \n> >> But I suspect we have a built-in \"we sort bigger to smaller, and\n> >> we cut off when we switch bins\" somewhere in find_delta() loop,\n> >> which I do not recall touching when I did that change, so that\n> >> may be interfering and preventing 0-11-AdjLite.deg from all over\n> >> the place to delta against each other.\n> >\n> > I just cannot find something that would do that in the code.  When \n> > --no-reuse-delta is specified, the only things that will break the loop\n> > in find_delta() is when try_delta() returns -1, and that happens only \n> > when changing object type or when the size difference is too big, but \n> > nothing looks at the name hash.\n> \n> The list is sorted by type then hash then size (type_size_sort),\n> so if you have t/Makefile that are big medium small too-small\n> and then doc/Makefile that are big medium, once you see the\n> too-small t/Makefile it would not consider the big doc/Makefile\n> as a candidate X-<.\n\nBingo!  I didn't think it all through before.\n\n\nNicolas\n"},{"id":"18960","messageId":"20060421010146.GA819@spearce.org","threadId":"3930","inReplyTo":"7vy7xzvpsg.fsf@assigned-by-dhcp.cox.net","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-04-21T01:01:46Z","receivedAt":"2006-04-21T01:01:46Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano <junkio@cox.net> wrote:\n[snip]\n> I suspect the test patch makes pack-objects a lot more\n> expensive.\n\nWhich patch are you talking about the previous patch or the one in\nthe message I'm now replying to?\n\n> The code before the test patch said \"if the size is very small\n> or size difference is too great, do not consider this, and do\n> not consider any more objects in the delta window, because we\n> know they are either even smaller of the same path, they have\n> different names, or they are of different type\".  The test patch\n> you tried was a quick and dirty hack that said \"under the\n> too-small condition, skip this one, but keep trying the rest of\n> the delta window\".\n> \n> Here is a cleaned up patch.  What it does is \"under the\n> too-small condition, see if the object has the same basename,\n> and if so keep going, but otherwise skip the rest as before\".\n[snip]\n\nThe patch below does not help very much:\n\n  Total 46391, written 46391 (delta 6686), reused 37979 (delta 0)\n  129M pack-7f766f5af5547554bacb28c0294bd562589dc5e7.pack\n\n> diff --git a/pack-objects.c b/pack-objects.c\n> index 09f4f2c..2173709 100644\n> --- a/pack-objects.c\n> +++ b/pack-objects.c\n> @@ -1036,8 +1036,6 @@ static int try_delta(struct unpacked *cu\n>  \toldsize = old_entry->size;\n>  \tsizediff = oldsize > size ? oldsize - size : size - oldsize;\n>  \n> -\tif (size < 50)\n> -\t\treturn -1;\n>  \tif (old_entry->depth >= max_depth)\n>  \t\treturn 0;\n>  \n> @@ -1048,20 +1046,27 @@ static int try_delta(struct unpacked *cu\n>  \t * more space-efficient (deletes don't have to say _what_ they\n>  \t * delete).\n>  \t */\n> -\tmax_size = size / 2 - 20;\n> -\tif (cur_entry->delta)\n> -\t\tmax_size = cur_entry->delta_size-1;\n> -\tif (sizediff >= max_size)\n> -\t\treturn -1;\n> -\tdelta_buf = diff_delta(old->data, oldsize,\n> -\t\t\t       cur->data, size, &delta_size, max_size);\n> -\tif (!delta_buf)\n> +\tif (50 <= size) {\n> +\t\tmax_size = size / 2 - 20;\n> +\t\tif (cur_entry->delta)\n> +\t\t\tmax_size = cur_entry->delta_size-1;\n> +\t\tif (sizediff < max_size) {\n> +\t\t\tdelta_buf = diff_delta(old->data, oldsize,\n> +\t\t\t\t\t       cur->data, size,\n> +\t\t\t\t\t       &delta_size, max_size);\n> +\t\t\tif (!delta_buf)\n> +\t\t\t\treturn 0;\n> +\t\t\tcur_entry->delta = old_entry;\n> +\t\t\tcur_entry->delta_size = delta_size;\n> +\t\t\tcur_entry->depth = old_entry->depth + 1;\n> +\t\t\tfree(delta_buf);\n> +\t\t\treturn 0;\n> +\t\t}\n> +\t}\n> +\t/* Keep going as long as the basename matches */\n> +\tif (((cur_entry->hash ^ old_entry->hash) >>DIRBITS) == 0)\n>  \t\treturn 0;\n> -\tcur_entry->delta = old_entry;\n> -\tcur_entry->delta_size = delta_size;\n> -\tcur_entry->depth = old_entry->depth + 1;\n> -\tfree(delta_buf);\n> -\treturn 0;\n> +\treturn -1;\n>  }\n>  \n>  static void progress_interval(int signum)\n> \n\n-- \nShawn.\n"},{"id":"18961","messageId":"20060421012029.GB819@spearce.org","threadId":"3930","inReplyTo":"7vfyk8vscl.fsf@assigned-by-dhcp.cox.net","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-04-21T01:20:29Z","receivedAt":"2006-04-21T01:20:29Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Based on Linus' comment I changed your patch to just the following.\nIt still produced the 46M pack file, so the first hunk apears to\nnot have had much of an affect with this data.\n\n>From a running time perspective it appears as though this patch is\nmaking things slightly better, not worse.  I ran it a few times\nfor each case always using the 46M pack as input for\n \"git-repack -a -d -f\".\n\n  'next'       137.13 real        95.82 user        25.24 sys\n  'next'+patch 131.62 real        89.35 user        28.56 sys\n\nbut even if the running time was an extra 6 seconds I'd still rather\nspend 4% more running time to use 1/2 the storage space.\n\n\ndiff --git a/pack-objects.c b/pack-objects.c\nindex 09f4f2c..f7d6217 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -1052,7 +1052,7 @@ static int try_delta(struct unpacked *cu\n        if (cur_entry->delta)\n                max_size = cur_entry->delta_size-1;\n        if (sizediff >= max_size)\n-               return -1;\n+               return 0;\n        delta_buf = diff_delta(old->data, oldsize,\n                               cur->data, size, &delta_size, max_size);\n        if (!delta_buf)\n"},{"id":"18963","messageId":"Pine.LNX.4.64.0604202213470.2215@localhost.localdomain","threadId":"3930","inReplyTo":"20060421012029.GB819@spearce.org","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-21T02:28:40Z","receivedAt":"2006-04-21T02:28:40Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 20 Apr 2006, Shawn Pearce wrote:\n\n> Based on Linus' comment I changed your patch to just the following.\n> It still produced the 46M pack file, so the first hunk apears to\n> not have had much of an affect with this data.\n> \n> From a running time perspective it appears as though this patch is\n> making things slightly better, not worse.  I ran it a few times\n> for each case always using the 46M pack as input for\n>  \"git-repack -a -d -f\".\n> \n>   'next'       137.13 real        95.82 user        25.24 sys\n>   'next'+patch 131.62 real        89.35 user        28.56 sys\n> \n> but even if the running time was an extra 6 seconds I'd still rather\n> spend 4% more running time to use 1/2 the storage space.\n> \n> \n> diff --git a/pack-objects.c b/pack-objects.c\n> index 09f4f2c..f7d6217 100644\n> --- a/pack-objects.c\n> +++ b/pack-objects.c\n> @@ -1052,7 +1052,7 @@ static int try_delta(struct unpacked *cu\n>         if (cur_entry->delta)\n>                 max_size = cur_entry->delta_size-1;\n>         if (sizediff >= max_size)\n> -               return -1;\n> +               return 0;\n>         delta_buf = diff_delta(old->data, oldsize,\n>                                cur->data, size, &delta_size, max_size);\n>         if (!delta_buf)\n\nI can confirm this is indeed the best fix so far.  Any \"smarter\" \nsolution I could think of did increase the size of the final pack quite \nspectacularly and rather unexpectedly with Shawn's repository.\n\nOf course removing the if (sizediff >= max_size) entirely does produce a \nsmaller pack (39MB) but it takes about twice the CPU.\n\nWith the patch above the Linux kernel pack is 0.3% smaller with 1% more \nCPU usage.  But like for the diff-delta hash list limiting code this \nsmall overhead is certainly a good compromize to avoid big degradations \nin some other cases.\n\n\nNicolas\n"},{"id":"18964","messageId":"20060421023222.GA1117@spearce.org","threadId":"3930","inReplyTo":"20060421012029.GB819@spearce.org","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-04-21T02:32:22Z","receivedAt":"2006-04-21T02:32:22Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"I just tried the patch below on a couple-month-old Linux 2.6\nrepository from Linus (last commit: Feb 14 2006).  It did not\ndecrease the pack file size by much despite the higher delta:\n\n  'next'       Total 189435, written 189435 (delta 142093), reused 44057 (delta 0)\n  'next'+patch Total 189435, written 189435 (delta 142712), reused 43954 (delta 0)\n\n  'next'       104464297 bytes\n  'next'+patch 104092920 bytes (99.6% of 'next')\n\n  'next'       328.98 real       206.02 user        93.60 sys\n  'next'+patch 363.06 real       218.98 user        94.72 sys\n\nSo it looks like the patch is taking longer to run, and by about 10%.\nAn expensive price to pay for what amounts to only a 0.4% reduction\nin pack size on the kernel.\n\n\nShawn Pearce <spearce@spearce.org> wrote:\n> Based on Linus' comment I changed your patch to just the following.\n> It still produced the 46M pack file, so the first hunk apears to\n> not have had much of an affect with this data.\n> \n> From a running time perspective it appears as though this patch is\n> making things slightly better, not worse.  I ran it a few times\n> for each case always using the 46M pack as input for\n>  \"git-repack -a -d -f\".\n> \n>   'next'       137.13 real        95.82 user        25.24 sys\n>   'next'+patch 131.62 real        89.35 user        28.56 sys\n> \n> but even if the running time was an extra 6 seconds I'd still rather\n> spend 4% more running time to use 1/2 the storage space.\n> \n> \n> diff --git a/pack-objects.c b/pack-objects.c\n> index 09f4f2c..f7d6217 100644\n> --- a/pack-objects.c\n> +++ b/pack-objects.c\n> @@ -1052,7 +1052,7 @@ static int try_delta(struct unpacked *cu\n>         if (cur_entry->delta)\n>                 max_size = cur_entry->delta_size-1;\n>         if (sizediff >= max_size)\n> -               return -1;\n> +               return 0;\n>         delta_buf = diff_delta(old->data, oldsize,\n>                                cur->data, size, &delta_size, max_size);\n>         if (!delta_buf)\n\n-- \nShawn.\n"},{"id":"18965","messageId":"20060421024012.GA1213@spearce.org","threadId":"3930","inReplyTo":"Pine.LNX.4.64.0604202213470.2215@localhost.localdomain","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-04-21T02:40:12Z","receivedAt":"2006-04-21T02:40:12Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre <nico@cam.org> wrote:\n> On Thu, 20 Apr 2006, Shawn Pearce wrote:\n> \n> > Based on Linus' comment I changed your patch to just the following.\n> > It still produced the 46M pack file, so the first hunk apears to\n> > not have had much of an affect with this data.\n> > \n> > From a running time perspective it appears as though this patch is\n> > making things slightly better, not worse.  I ran it a few times\n> > for each case always using the 46M pack as input for\n> >  \"git-repack -a -d -f\".\n> > \n> >   'next'       137.13 real        95.82 user        25.24 sys\n> >   'next'+patch 131.62 real        89.35 user        28.56 sys\n> > \n> > but even if the running time was an extra 6 seconds I'd still rather\n> > spend 4% more running time to use 1/2 the storage space.\n> > \n> > \n> > diff --git a/pack-objects.c b/pack-objects.c\n> > index 09f4f2c..f7d6217 100644\n> > --- a/pack-objects.c\n> > +++ b/pack-objects.c\n> > @@ -1052,7 +1052,7 @@ static int try_delta(struct unpacked *cu\n> >         if (cur_entry->delta)\n> >                 max_size = cur_entry->delta_size-1;\n> >         if (sizediff >= max_size)\n> > -               return -1;\n> > +               return 0;\n> >         delta_buf = diff_delta(old->data, oldsize,\n> >                                cur->data, size, &delta_size, max_size);\n> >         if (!delta_buf)\n> \n> I can confirm this is indeed the best fix so far.  Any \"smarter\" \n> solution I could think of did increase the size of the final pack quite \n> spectacularly and rather unexpectedly with Shawn's repository.\n\nWow.  I'm such a trouble maker.  *grin*\n \n> Of course removing the if (sizediff >= max_size) entirely does produce a \n> smaller pack (39MB) but it takes about twice the CPU.\n\nEh, that's not worth it.  7M disk space saved for twice the work isn't\nthat good of a tradeoff.  I'm not in favor of that version.\n\n> With the patch above the Linux kernel pack is 0.3% smaller with 1% more \n> CPU usage.  But like for the diff-delta hash list limiting code this \n> small overhead is certainly a good compromize to avoid big degradations \n> in some other cases.\n\nHmm.  See the email I just sent. I was seeing a good 10% increase\nin my own tests on a Linux kernel repository.  But I guess I can\nhope that my test was flawed somehow and it really is closer to a 1%\nincrease in running time, making it more likely that the above fix\nmakes it into GIT.\n\n-- \nShawn.\n"},{"id":"18966","messageId":"Pine.LNX.4.64.0604202256510.2215@localhost.localdomain","threadId":"3930","inReplyTo":"20060421024012.GA1213@spearce.org","subject":"Re: 1.3.0 creating bigger packs than 1.2.3","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-21T03:07:25Z","receivedAt":"2006-04-21T03:07:25Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 20 Apr 2006, Shawn Pearce wrote:\n> Nicolas Pitre <nico@cam.org> wrote:\n> > With the patch above the Linux kernel pack is 0.3% smaller with 1% more \n> > CPU usage.  But like for the diff-delta hash list limiting code this \n> > small overhead is certainly a good compromize to avoid big degradations \n> > in some other cases.\n> \n> Hmm.  See the email I just sent. I was seeing a good 10% increase\n> in my own tests on a Linux kernel repository.  But I guess I can\n> hope that my test was flawed somehow and it really is closer to a 1%\n> increase in running time, making it more likely that the above fix\n> makes it into GIT.\n\nWell, I repeated the kernel run and this time it took 2.5% more CPU with \nthe patch.\n\nBut the thing is that I get a +/- 1% difference between successive runs.  \nSo while the patch does add a certain overhead, it appears to be in the \nsame range as noise here.\n\n\nNicolas\n"}]}