{"thread":{"id":"7506","subject":"Partitioned packs","startedAt":"2007-04-04T01:16:12Z","lastAt":"2007-04-04T02:52:56Z","messageCount":5,"participants":["Chris Lee","David Lang","Junio C Hamano","Linus Torvalds"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"38580","messageId":"Pine.LNX.4.63.0704031813100.21680@qynat.qvtvafvgr.pbz","threadId":"7506","inReplyTo":"db69205d0704031836u3b3dfc2pb9825dd649aca58@mail.gmail.com","subject":"Re: Partitioned packs","fromName":"David Lang","fromEmail":"david.lang@digitalinsight.com","sentAt":"2007-04-04T01:16:12Z","receivedAt":"2007-04-04T01:16:12Z","isPatch":false,"sender":{"key":"david.lang@digitalinsight.com","avatar":null},"body":"On Tue, 3 Apr 2007, Chris Lee wrote:\n\n> Date: Tue, 3 Apr 2007 18:36:44 -0700\n> From: Chris Lee <clee@kde.org>\n> To: git@vger.kernel.org\n> Subject: Partitioned packs\n> \n> I've been running some experiments, as hinted earlier by the\n> discussion about just how much git-index-pack sucks (which, really,\n> isn't much since the gaping memleak is gone now).\n>\n> These experiments include trying to see if there's a noticeable\n> performance improvement by splitting out objects of different types\n> into different packs. So far, it definitely seems to make a\n> difference, though not the one I was initially expecting. For all of\n> these tests, I did 'sysctl -w vm.drop_caches=3' before running, to\n> effectively simulate a cold-cache run.\n\nI wonder what order the packs ended up in. if git had to go through the wrong \npack completely first before finding the pack that it needed, that coudl account \nfor extra time.\n\nis it worth makeing up single packs that order the three different types of \nobject differently within the one pack to see what difference it makes to have \nto walk past all the blobs to get to the commits and trees?\n\nDavid Lang\n"},{"id":"38579","messageId":"db69205d0704031836u3b3dfc2pb9825dd649aca58@mail.gmail.com","threadId":"7506","inReplyTo":null,"subject":"Partitioned packs","fromName":"Chris Lee","fromEmail":"clee@kde.org","sentAt":"2007-04-04T01:36:44Z","receivedAt":"2007-04-04T01:36:44Z","isPatch":false,"sender":{"key":"clee@kde.org","avatar":"https://gravatar.com/avatar/c930bdc8cc6465094a5722188409ecb8955e0da2b188d7340137074b08f857e3?d=mp&s=160"},"body":"I've been running some experiments, as hinted earlier by the\ndiscussion about just how much git-index-pack sucks (which, really,\nisn't much since the gaping memleak is gone now).\n\nThese experiments include trying to see if there's a noticeable\nperformance improvement by splitting out objects of different types\ninto different packs. So far, it definitely seems to make a\ndifference, though not the one I was initially expecting. For all of\nthese tests, I did 'sysctl -w vm.drop_caches=3' before running, to\neffectively simulate a cold-cache run.\n\nSingle 3.1GB pack file containing all commits, blobs, and trees\nFirst run (cold cache):\ngit-rev-list --all > /dev/null  5.52s user 0.32s system 45% cpu 12.872 total\ngit-blame -- kdelibs/kdeui/kmenubar.cpp  0.00s user 0.01s system 0%\ncpu 40.218s total\ngit-archive --format=tar HEAD -- kdelibs >> /dev/null  0.48s user\n0.10s system 5% cpu 10.143 total\n\nSubsequent runs (warm cache):\ngit-rev-list --all > /dev/null  5.19s user 0.48s system 98% cpu 5.750 total\ngit-blame -- kdelibs/kdeui/kmenubar.cpp  0.00s user 0.00s system 0%\ncpu 11.960 total\ngit-archive --format=tar HEAD -- kdelibs >> /dev/null  0.43s user\n0.04s system 100% cpu 0.472 total\n\n\nSingle pack for commit objects and another pack for the rest\nFirst run (cold cache):\ngit-rev-list --all > /dev/null  5.84s user 0.34s system 31% cpu 19.427 total\ngit-blame -- kdelibs/kdeui/kmenubar.cpp  0.00s user 0.00s system 0%\ncpu 9:42.74 total\ngit-archive --format=tar HEAD -- kdelibs >> /dev/null  0.50s user\n0.26s system 0% cpu 1:35.44 total\n\nSubsequent runs (warm cache):\ngit-rev-list --all > /dev/null  5.94s user 0.26s system 99% cpu 6.204 total\ngit-blame -- kdelibs/kdeui/kmenubar.cpp  0.00s user 0.00s system 0%\ncpu 12.394 total\ngit-archive --format=tar HEAD -- kdelibs >> /dev/null  0.41s user\n0.07s system 98% cpu 0.486 total\n\nFully-partitioned separate packs for commit, tree, and blob objects\nFirst run (cold cache):\ngit-rev-list --all > /dev/null  6.24s user 0.32s system 25% cpu 25.689 total\ngit-blame -- kdelibs/kdeui/kmenubar.cpp  0.00s user 0.00s system 0%\ncpu 1:08.76 total\ngit-archive --format=tar HEAD -- kdelibs >> /dev/null  0.38s user\n0.30s system 0% cpu 1:35.89 total\n\nSubsequent runs (warm cache):\ngit-rev-list --all > /dev/null  6.28s user 0.24s system 99% cpu 6.527 total\ngit-blame -- kdelibs/kdeui/kmenubar.cpp  0.00s user 0.00s system 0%\ncpu 13.895 total\ngit-archive --format=tar HEAD -- kdelibs >> /dev/null  0.42s user\n0.06s system 99% cpu 0.476 total\n\nI packed all of these using --delta-base-offset, with a window of 100\nand a depth of 10.\n\n-clee\n"},{"id":"38582","messageId":"7vlkh8uci4.fsf@assigned-by-dhcp.cox.net","threadId":"7506","inReplyTo":"db69205d0704031836u3b3dfc2pb9825dd649aca58@mail.gmail.com","subject":"Re: Partitioned packs","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-04-04T01:58:11Z","receivedAt":"2007-04-04T01:58:11Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Chris Lee\" <clee@kde.org> writes:\n\n> I've been running some experiments, as hinted earlier by the\n> discussion about just how much git-index-pack sucks (which, really,\n> isn't much since the gaping memleak is gone now).\n>\n> These experiments include trying to see if there's a noticeable\n> performance improvement by splitting out objects of different types\n> into different packs. So far, it definitely seems to make a\n> difference, though not the one I was initially expecting. For all of\n> these tests, I did 'sysctl -w vm.drop_caches=3' before running, to\n> effectively simulate a cold-cache run.\n\nAre you running on a 64-bit machine or 32-bit?\n\nI wonder what the numbers would be if you partition into the\nsame number of packs of similar sizes as your experiment, but\npartitioning based on not by type but by age or other factors.\n\nWhat I am getting at is that you may not be seeing the effect of\naccess pattern based on the type at all.  For example, the\nperformance can be affected by other factors, such as necessity\nto use smaller number of pack_windows per pack.  use_pack()\niterates through the currently active windows on a linked list\nper pack, and a window is 32MB on 32-bit machines, so you would\nliterally need hundreds of them to access that 3GB pack (the\ntotal is limited to 256MB so 8 windows are recycled).  It is\npossible that simply using more packs and knowing which pack you\nneed to access upfront may be cutting down the cost of finding\nthe pack window to use.  A single pack would have a linked list\nof 8 active windows, while two packs would have one linked list\nof each, so the average linear search cost would be half.\n"},{"id":"38583","messageId":"Pine.LNX.4.64.0704031858470.6730@woody.linux-foundation.org","threadId":"7506","inReplyTo":"db69205d0704031836u3b3dfc2pb9825dd649aca58@mail.gmail.com","subject":"Re: Partitioned packs","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-04-04T02:14:33Z","receivedAt":"2007-04-04T02:14:33Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 3 Apr 2007, Chris Lee wrote:\n> \n> These experiments include trying to see if there's a noticeable\n> performance improvement by splitting out objects of different types\n> into different packs. So far, it definitely seems to make a\n> difference, though not the one I was initially expecting. For all of\n> these tests, I did 'sysctl -w vm.drop_caches=3' before running, to\n> effectively simulate a cold-cache run.\n\nOk, the wordwrap makes it a bit hard to read, but it looks like the \nsingle-pack always wins. Sometimes by a huge amount.\n\nThe reason is simple: not only are single packs well sorted anyway (so if \nyou only look at commits, it will only look at the head of the pack \nanyway), but a single pack is much faster to look things up in: you can do \na single binary lookup.\n\nIf you have multiple packs, you *may* be able to do a single binary \nlookup, but quite often you'll do one *failing* binary lookup, and then go \non to the next pack - in other words, you'll do a linear search over a set \nof binary lookups.\n\nSo trying to partition things doesn't help (because the objects are \nalready well sorted), and it does hurt.\n\nThat said, for most operations it's probably in the noise. Something bad \nhappened for your \"git-blame\" thing for the \"commits\" and \"everything \nelse\" case. Perhaps just unlucky ordering of packs.\n\n\t\tLinus\n"},{"id":"38584","messageId":"Pine.LNX.4.64.0704031944540.6730@woody.linux-foundation.org","threadId":"7506","inReplyTo":"Pine.LNX.4.64.0704031858470.6730@woody.linux-foundation.org","subject":"Re: Partitioned packs","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-04-04T02:52:56Z","receivedAt":"2007-04-04T02:52:56Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 3 Apr 2007, Linus Torvalds wrote:\n> \n> So trying to partition things doesn't help (because the objects are \n> already well sorted), and it does hurt.\n\nSide note: I think that there *are* cases where partitioned packs can do \nbetter, but I think that in order to do better you should\n\n - partition by \"recency\", ie put objects that are not reachable from any \n   recent point in older packs.\n\n - make sure that the \"packed_git\" list is always sorted so that the older \n   data packs are at the end.\n\nand that should actually speed up many loads, just because the recent \nobjects are all in one pack, and because it's smaller, that pack can be \nlooked up a bit faster.\n\nOn the other hand, the power of a log(n) function like a binary search is \nthat lookup in a big pack that is four times the size of four smaller \npacks is really not all that much more expensive, so the advantage is \nprobably pretty small.\n\nAnd for things that need old objects (and \"git blame\" does obviously very \nmuch tend to fall into that category), any partitioning is likely to be \nbad.\n\nSo I think partitioning is valid, but my suspicion is that you'd want to \npartition for *other* reasons than highest performance. Better reasons to \nhave multiple packs:\n\n - just because you haven't repacked ;)\n - to keep \"git repack\" times down by marking old big packs as \"keep\" once \n   they get big enough (the space advantage of packing eventually flattens \n   out, so there's no real overwhelming reason to repack old stuff if you \n   have \"enough\")\n - filesystem and pack-file limitations (ie the 2**31 limit)\n\nbut I doubt performance is ever going to be a really compelling one.\n\nYou can obviously always optimize for some very *particular* load by \npacking optimally for just that one (keep exactly the objects you need in \none particular pack, don't even touch any other packs), but I don't think \nany load is *so* special that you shouldn't think of other loads.\n\n\t\t\tLinus\n"}]}