{"thread":{"id":"14926","subject":"pack operation is thrashing my server","startedAt":"2008-08-10T19:47:37Z","lastAt":"2008-09-08T16:01:58Z","messageCount":80,"participants":["Ken Pratt","Martin Langhoff","Shawn O. Pearce","Avery Pennarun","Andi Kleen","Nicolas Pitre","Geert Bosch","Jakub Narebski","David Tweed","Johan Herland","Dana How","Andreas Ericsson","Thomas Rast","Linus Torvalds","Björn Steinbrink","Junio C Hamano","Jon Smirl","Mike Hommey"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"86713","messageId":"a6b6acf60808101247r4fea978ft6d2cdc53e1f99c0e@mail.gmail.com","threadId":"14926","inReplyTo":null,"subject":"pack operation is thrashing my server","fromName":"Ken Pratt","fromEmail":"ken@kenpratt.net","sentAt":"2008-08-10T19:47:37Z","receivedAt":"2008-08-10T19:47:37Z","isPatch":false,"sender":{"key":"ken@kenpratt.net","avatar":"https://gravatar.com/avatar/f8a3d5768018a18060a195801ef6ee483ff034d88293d73326cc593a2e595967?d=mp&s=160"},"body":"Hi,\n\nI'm having memory issues when trying to clone a remote git repository.\n\nI'm running: \"git clone git+ssh://user@foo.bar.com/var/git/foo\"\n\nThe remote repository is bare, and is 180MB in size (says du), with\n1824 objects. The remote (VPS) server is running git version 1.5.6.4\non Arch Linux on a x86_64 Opteron with 256MB of dedicated RAM.\n\nThe clone command fires off some packing operations that bring the\nserver to its knees:\n\nPID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND\n21782 kenpratt 20 0 444m 212m 272 D 3 83.0 0:04.98 git-pack-object\n\nThe clone also seems to hang forever. Progress stays at 0% for hours,\nand it never progresses past compressing the first object.\n\nI've tried very conservative pack settings:\n\n[pack]\n threads = 1\n windowmemory = 64M\n deltacachesize = 1M\n deltacachelimit = 1M\n\n[pack]\n threads = 1\n windowmemory = 16M\n deltacachesize = 16M\n deltacachelimit = 0\n\nI've tries many variations like those, but nothing seems to help.\n\nA \"git repack -a -d\" only takes 5 seconds to run on the same\nrepository on my laptop (a non-bare copy), and seems to peak at ~160MB\nof RAM usage.\n\nAny tips/help would be greatly appreciated. This repository is still\nsmall -- it will eventually grow to multiple GB in size, as it is a\nmix of small text files and binaries ranging in size from 2MB to\n200MB. Is it not feasible to clone repositories of that size that are\nhosted on a server with 256MB of RAM?\n\nThanks!\n\nKen\n"},{"id":"86730","messageId":"46a038f90808101606j7534b855j9205ae219c350c94@mail.gmail.com","threadId":"14926","inReplyTo":"a6b6acf60808101247r4fea978ft6d2cdc53e1f99c0e@mail.gmail.com","subject":"Re: pack operation is thrashing my server","fromName":"Martin Langhoff","fromEmail":"martin.langhoff@gmail.com","sentAt":"2008-08-10T23:06:16Z","receivedAt":"2008-08-10T23:06:16Z","isPatch":false,"sender":{"key":"martin.langhoff@gmail.com","avatar":"https://gravatar.com/avatar/1e3f311b6c4c15836501901ca58f8c0b0667246488084ba524d8bc9867e22fd9?d=mp&s=160"},"body":"On Mon, Aug 11, 2008 at 7:47 AM, Ken Pratt wrote:\n> A \"git repack -a -d\" only takes 5 seconds to run on the same\n> repository on my laptop (a non-bare copy), and seems to peak at ~160MB\n> of RAM usage.\n\nAs a workaround, if you repack on your laptop and rsync the pack+index\nto the server, it will work. This can be used to serve huge projects\nout of lightweight-ish servers. Yet another workaround is to perform\ninitial clones via rsync or http.\n\nIn your case, I agree that the repo doesn't seem large enough (or to\nhave large enough objects) to warrant having this problem. But that I\ncan't help much with myself - pack-machiner experts probably can.\n\ncheers,\n\n\nm\n-- \n martin.langhoff@gmail.com\n martin@laptop.org -- School Server Architect\n - ask interesting questions\n - don't get distracted with shiny stuff - working code first\n - http://wiki.laptop.org/go/User:Martinlanghoff\n"},{"id":"86734","messageId":"a6b6acf60808101612l300227e9od97e767fe4621dc5@mail.gmail.com","threadId":"14926","inReplyTo":"46a038f90808101606j7534b855j9205ae219c350c94@mail.gmail.com","subject":"Re: pack operation is thrashing my server","fromName":"Ken Pratt","fromEmail":"ken@kenpratt.net","sentAt":"2008-08-10T23:12:16Z","receivedAt":"2008-08-10T23:12:16Z","isPatch":false,"sender":{"key":"ken@kenpratt.net","avatar":"https://gravatar.com/avatar/f8a3d5768018a18060a195801ef6ee483ff034d88293d73326cc593a2e595967?d=mp&s=160"},"body":"Thanks for the tips, Martin.\n\nHow does git over rsync work? It is unauthenticated, like git over\nhttp? Or authenticated, like git+ssh?\n\nGreat ideas though. Unfortunately I don't think I'll be able to use\nthe repack locally and then upload strategy for this particular\nworkflow, but the rsync clone approach might do it.\n\n-Ken\n\nOn Sun, Aug 10, 2008 at 4:06 PM, Martin Langhoff\n wrote:\n> On Mon, Aug 11, 2008 at 7:47 AM, Ken Pratt wrote:\n>> A \"git repack -a -d\" only takes 5 seconds to run on the same\n>> repository on my laptop (a non-bare copy), and seems to peak at ~160MB\n>> of RAM usage.\n>\n> As a workaround, if you repack on your laptop and rsync the pack+index\n> to the server, it will work. This can be used to serve huge projects\n> out of lightweight-ish servers. Yet another workaround is to perform\n> initial clones via rsync or http.\n>\n> In your case, I agree that the repo doesn't seem large enough (or to\n> have large enough objects) to warrant having this problem. But that I\n> can't help much with myself - pack-machiner experts probably can.\n>\n> cheers,\n>\n>\n> m\n> --\n> martin.langhoff@gmail.com\n> martin@laptop.org -- School Server Architect\n> - ask interesting questions\n> - don't get distracted with shiny stuff - working code first\n> - http://wiki.laptop.org/go/User:Martinlanghoff\n>\n\n\n\n-- \nKen Pratt\nhttp://kenpratt.net/\n"},{"id":"86735","messageId":"46a038f90808101630k4bcdef91h64189a2991106174@mail.gmail.com","threadId":"14926","inReplyTo":"a6b6acf60808101612l300227e9od97e767fe4621dc5@mail.gmail.com","subject":"Re: pack operation is thrashing my server","fromName":"Martin Langhoff","fromEmail":"martin.langhoff@gmail.com","sentAt":"2008-08-10T23:30:04Z","receivedAt":"2008-08-10T23:30:04Z","isPatch":false,"sender":{"key":"martin.langhoff@gmail.com","avatar":"https://gravatar.com/avatar/1e3f311b6c4c15836501901ca58f8c0b0667246488084ba524d8bc9867e22fd9?d=mp&s=160"},"body":"On Mon, Aug 11, 2008 at 11:12 AM, Ken Pratt wrote:\n> Thanks for the tips, Martin.\n\nNP! :-)\n\n> How does git over rsync work? It is unauthenticated, like git over\n> http? Or authenticated, like git+ssh?\n\nI've always used it as rsync+ssh. Not sure about bare rsync.\n\n> Great ideas though. Unfortunately I don't think I'll be able to use\n> the repack locally and then upload strategy for this particular\n> workflow, but the rsync clone approach might do it.\n\nA few specific versions of git had bad repack cpu/memory usage\npatterns, so an update to git might help. In any case, the repack\nmachinery experts are probably asleep. Give it a bit of time and\nsmarter answers will probably materialise.\n\ncheers,\n\n\nm\n-- \n martin.langhoff@gmail.com\n martin@laptop.org -- School Server Architect\n - ask interesting questions\n - don't get distracted with shiny stuff - working code first\n - http://wiki.laptop.org/go/User:Martinlanghoff\n"},{"id":"86736","messageId":"a6b6acf60808101634n2d8c5610vdeeb17865457eb0f@mail.gmail.com","threadId":"14926","inReplyTo":"46a038f90808101630k4bcdef91h64189a2991106174@mail.gmail.com","subject":"Re: pack operation is thrashing my server","fromName":"Ken Pratt","fromEmail":"ken@kenpratt.net","sentAt":"2008-08-10T23:34:27Z","receivedAt":"2008-08-10T23:34:27Z","isPatch":false,"sender":{"key":"ken@kenpratt.net","avatar":"https://gravatar.com/avatar/f8a3d5768018a18060a195801ef6ee483ff034d88293d73326cc593a2e595967?d=mp&s=160"},"body":"Sounds good.\n\n>> How does git over rsync work? It is unauthenticated, like git over\n>> http? Or authenticated, like git+ssh?\n>\n> I've always used it as rsync+ssh. Not sure about bare rsync.\n\nDo you use file-level rsync+ssh? Or rsync+ssh with git?\n\nWhen I try a \"git clone rsync+ssh://foo.bar.com/var/git/bar\", I get a\n\"fatal: I don't handle protocol 'rsync+ssh'\" error.\n\nI know git supports the rsync protocol, but I don't think installing\nan rsync server and using bare rsync will be an option in this case.\n\nThanks again,\n\nKen\n"},{"id":"86745","messageId":"20080811030444.GC27195@spearce.org","threadId":"14926","inReplyTo":"a6b6acf60808101247r4fea978ft6d2cdc53e1f99c0e@mail.gmail.com","subject":"Re: pack operation is thrashing my server","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-11T03:04:44Z","receivedAt":"2008-08-11T03:04:44Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Ken Pratt wrote:\n> I'm having memory issues when trying to clone a remote git repository.\n> \n> The remote repository is bare, and is 180MB in size (says du), with\n> 1824 objects. The remote (VPS) server is running git version 1.5.6.4\n> on Arch Linux on a x86_64 Opteron with 256MB of dedicated RAM.\n> \n> PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND\n> 21782 kenpratt 20 0 444m 212m 272 D 3 83.0 0:04.98 git-pack-object\n\nWell, clearly the server is swapping at this point. 212m resident\nfor this git-pack-objects process leaves no room available for\nanything else. Git is using too much memory for this system.\n \n> I've tried very conservative pack settings:\n> \n> [pack]\n> threads = 1\n> windowmemory = 64M\n> deltacachesize = 1M\n> deltacachelimit = 1M\n\nHave you tried something like this?\n\n\t[core]\n\t\tpackedGitWindowSize = 16m\n\t\tpackedGitLimit = 64m\n\n\t[pack]\n\t\tthreads = 1\n\t\twindowMemory = 64m\n\t\tdeltaCacheSize = 1m\n\nOn a 64 bit system packedGitWindowSize and packedGitLimit have very\nlarge thresholds which will cause it to mmap in the entire pack file.\nYou may need to try even smaller settings than these; 256m physical\nmemory isn't a lot when dealing with a repository 180m in size.\nEspecially on a 64 bit system.\n\n-- \nShawn.\n"},{"id":"86753","messageId":"a6b6acf60808110043t76dc0ae6l428c5da473d79c71@mail.gmail.com","threadId":"14926","inReplyTo":"20080811030444.GC27195@spearce.org","subject":"Re: pack operation is thrashing my server","fromName":"Ken Pratt","fromEmail":"ken@kenpratt.net","sentAt":"2008-08-11T07:43:27Z","receivedAt":"2008-08-11T07:43:27Z","isPatch":false,"sender":{"key":"ken@kenpratt.net","avatar":"https://gravatar.com/avatar/f8a3d5768018a18060a195801ef6ee483ff034d88293d73326cc593a2e595967?d=mp&s=160"},"body":"> Have you tried something like this?\n>\n> [core]\n> packedGitWindowSize = 16m\n> packedGitLimit = 64m\n>\n> [pack]\n> threads = 1\n> windowMemory = 64m\n> deltaCacheSize = 1m\n>\n> On a 64 bit system packedGitWindowSize and packedGitLimit have very\n> large thresholds which will cause it to mmap in the entire pack file.\n> You may need to try even smaller settings than these; 256m physical\n> memory isn't a lot when dealing with a repository 180m in size.\n> Especially on a 64 bit system.\n\nI just went as low as:\n\n[core]\n packedGitWindowSize = 1m\n packedGitLimit = 4m\n[pack]\n threads = 1\n windowMemory = 4m\n deltaCacheSize = 128k\n\nAnd it didn't make a dent in memory usage. Server is still swapping\nwithin ~10 seconds of starting object compression.\n\nI'm starting to think repacking is just not feasible on a 64-bit\nserver with 256MB of RAM (which is a very popular configuration in the\nVPS market).\n\nThanks!\n\nKen\n"},{"id":"86773","messageId":"20080811150150.GC26363@spearce.org","threadId":"14926","inReplyTo":"a6b6acf60808110043t76dc0ae6l428c5da473d79c71@mail.gmail.com","subject":"Re: pack operation is thrashing my server","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-11T15:01:50Z","receivedAt":"2008-08-11T15:01:50Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Ken Pratt wrote:\n> I just went as low as:\n> \n> [core]\n> packedGitWindowSize = 1m\n> packedGitLimit = 4m\n> [pack]\n> threads = 1\n> windowMemory = 4m\n> deltaCacheSize = 128k\n> \n> And it didn't make a dent in memory usage. Server is still swapping\n> within ~10 seconds of starting object compression.\n> \n> I'm starting to think repacking is just not feasible on a 64-bit\n> server with 256MB of RAM (which is a very popular configuration in the\n> VPS market).\n\nWhat is the largest object in that repository? Do you have a\nrough guess? You said earlier:\n\n> The remote repository is bare, and is 180MB in size (says du), with\n> 1824 objects.\n\nThat implies there is at least one really large object in that\nrepository. The average of 101KB per object is not going to be\na correct figure here as most commits and trees are _very_ tiny.\nIt must be a large object. Those big objects are going to consume\na lot of memory if they get inflated in memory.\n\nYou may very well be right that this particular repository of\nyours is simply not packable on a 64 bit system with only 256M.\nPacking takes a good chunk of memory as we maintain data about\nevery single object, plus we need working space to unpack several\nobjects at once so we can perform diffs to find deltas.\n\nI'm not sure there are any more tunables you can try to tweak to\nreduce the memory usage further. The configuration above is pushed\ndown about as low as it will go. For the most part the code is\npretty good about not exploding memory usage.\n\nYou said earlier this was Git 1.5.6.4. I recently fixed a bug in\nthe code that reads data from packs to prevent it from blowing out\nmemory usage, but that bug fix was included in 1.5.6.4.\n\n\nOn the up side, packing should only be consuming huge memory like\nthis when it needs to move loose objects into a pack file. I think\nMartin Langhoff suggested packing this on your laptop then using\nrsync over SSH to copy the pack file and .idx file to the server, so\nthe server didn't have to spend time figuring out the deltas itself.\n\nEven though the clone command will fire off git-pack-objects the\npack-objects command will have a lot less work to do if the data\nit needs is already stored in existing pack files.\n\n-- \nShawn.\n"},{"id":"86780","messageId":"32541b130808110840p1287426fpeef967a9ff4fb094@mail.gmail.com","threadId":"14926","inReplyTo":"20080811150150.GC26363@spearce.org","subject":"Re: pack operation is thrashing my server","fromName":"Avery Pennarun","fromEmail":"apenwarr@gmail.com","sentAt":"2008-08-11T15:40:35Z","receivedAt":"2008-08-11T15:40:35Z","isPatch":false,"sender":{"key":"apenwarr@gmail.com","avatar":"https://avatars.githubusercontent.com/u/20592?v=4"},"body":"On Mon, Aug 11, 2008 at 11:01 AM, Shawn O. Pearce wrote:\n> On the up side, packing should only be consuming huge memory like\n> this when it needs to move loose objects into a pack file. I think\n> Martin Langhoff suggested packing this on your laptop then using\n> rsync over SSH to copy the pack file and .idx file to the server, so\n> the server didn't have to spend time figuring out the deltas itself.\n\nDo you need to also introduce a \".keep\" file to get the benefit from\nthis? I had a repo with some very large objects, and it was killing\nmy low-memory server *every* time I did \"git gc\", until I repacked on\nanother system, created the .keep file, and rsynced it back. Does\nthat make sense?\n\nThanks,\n\nAvery\n"},{"id":"86787","messageId":"20080811155959.GG26363@spearce.org","threadId":"14926","inReplyTo":"32541b130808110840p1287426fpeef967a9ff4fb094@mail.gmail.com","subject":"Re: pack operation is thrashing my server","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-11T15:59:59Z","receivedAt":"2008-08-11T15:59:59Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Avery Pennarun wrote:\n> On Mon, Aug 11, 2008 at 11:01 AM, Shawn O. Pearce wrote:\n> > On the up side, packing should only be consuming huge memory like\n> > this when it needs to move loose objects into a pack file. I think\n> > Martin Langhoff suggested packing this on your laptop then using\n> > rsync over SSH to copy the pack file and .idx file to the server, so\n> > the server didn't have to spend time figuring out the deltas itself.\n> \n> Do you need to also introduce a \".keep\" file to get the benefit from\n> this? I had a repo with some very large objects, and it was killing\n> my low-memory server *every* time I did \"git gc\", until I repacked on\n> another system, created the .keep file, and rsynced it back. Does\n> that make sense?\n\nNo, the \".keep\" file wouldn't have an impact. Delta reuse (the\nfeature I was alluding to) works whether or not there is a .keep\nfile present.\n\nI wonder if your \"git gc\" was using --aggressive?\n\n-- \nShawn.\n"},{"id":"86811","messageId":"87vdy71i6w.fsf@basil.nowhere.org","threadId":"14926","inReplyTo":"a6b6acf60808110043t76dc0ae6l428c5da473d79c71@mail.gmail.com","subject":"Re: pack operation is thrashing my server","fromName":"Andi Kleen","fromEmail":"andi@firstfloor.org","sentAt":"2008-08-11T19:10:31Z","receivedAt":"2008-08-11T19:10:31Z","isPatch":false,"sender":{"key":"andi@firstfloor.org","avatar":null},"body":"\"Ken Pratt\" writes:\n>\n> I'm starting to think repacking is just not feasible on a 64-bit\n> server with 256MB of RAM (which is a very popular configuration in the\n> VPS market).\n\nAs a quick workaround you could try it with a 32bit git executable?\n(assuming you have a distribution with proper multilib support) \n\nI think the right fix would be to make git throttle itself (not \nuse mmap, use very small defaults etc.) on low memory systems.\nIt could take a look a /proc/meminfo for this.\n\n-Andi\n"},{"id":"86812","messageId":"a6b6acf60808111213j78028c2ercc1199e080eaeccc@mail.gmail.com","threadId":"14926","inReplyTo":"20080811150150.GC26363@spearce.org","subject":"Re: pack operation is thrashing my server","fromName":"Ken Pratt","fromEmail":"ken@kenpratt.net","sentAt":"2008-08-11T19:13:00Z","receivedAt":"2008-08-11T19:13:00Z","isPatch":false,"sender":{"key":"ken@kenpratt.net","avatar":"https://gravatar.com/avatar/f8a3d5768018a18060a195801ef6ee483ff034d88293d73326cc593a2e595967?d=mp&s=160"},"body":"> What is the largest object in that repository? Do you have a\n> rough guess? You said earlier:\n>\n>> The remote repository is bare, and is 180MB in size (says du), with\n>> 1824 objects.\n>\n> That implies there is at least one really large object in that\n> repository. The average of 101KB per object is not going to be\n> a correct figure here as most commits and trees are _very_ tiny.\n> It must be a large object. Those big objects are going to consume\n> a lot of memory if they get inflated in memory.\n\nLargest object is ~150MB, and there are a couple 5-10MB objects as well.\n\n> You said earlier this was Git 1.5.6.4. I recently fixed a bug in\n> the code that reads data from packs to prevent it from blowing out\n> memory usage, but that bug fix was included in 1.5.6.4.\n\nI tried upgrading to 1.5.6.5 as well, but that didn't help.\n\n> On the up side, packing should only be consuming huge memory like\n> this when it needs to move loose objects into a pack file. I think\n> Martin Langhoff suggested packing this on your laptop then using\n> rsync over SSH to copy the pack file and .idx file to the server, so\n> the server didn't have to spend time figuring out the deltas itself.\n\nUnfortunately, that will only work as a band-aid solution for my\nworkflow. I think I'll have to limit the file size in the repository\nto something that the server can handle.\n"},{"id":"86813","messageId":"a6b6acf60808111215y45b261d2ra667ea8d9f5f76d2@mail.gmail.com","threadId":"14926","inReplyTo":"87vdy71i6w.fsf@basil.nowhere.org","subject":"Re: pack operation is thrashing my server","fromName":"Ken Pratt","fromEmail":"ken@kenpratt.net","sentAt":"2008-08-11T19:15:59Z","receivedAt":"2008-08-11T19:15:59Z","isPatch":false,"sender":{"key":"ken@kenpratt.net","avatar":"https://gravatar.com/avatar/f8a3d5768018a18060a195801ef6ee483ff034d88293d73326cc593a2e595967?d=mp&s=160"},"body":"> As a quick workaround you could try it with a 32bit git executable?\n> (assuming you have a distribution with proper multilib support)\n\nIn this case, I do have control over the server (running Arch Linux,\nwhich should do 32-bit multilib just fine), but for my workflow I\ncannot assume that the server will have 32-bit git support.\n\nI will use the previously mentioned solution of doing the packing\nelsewhere for now as a band-aid, with hopes that this will get fixed\nsometime soon.\n\nThanks!\n\n-Ken\n"},{"id":"86816","messageId":"20080811192208.GK26363@spearce.org","threadId":"14926","inReplyTo":"87vdy71i6w.fsf@basil.nowhere.org","subject":"Re: pack operation is thrashing my server","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-11T19:22:08Z","receivedAt":"2008-08-11T19:22:08Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Andi Kleen wrote:\n> \"Ken Pratt\" writes:\n> >\n> > I'm starting to think repacking is just not feasible on a 64-bit\n> > server with 256MB of RAM (which is a very popular configuration in the\n> > VPS market).\n> \n> I think the right fix would be to make git throttle itself (not \n> use mmap, use very small defaults etc.) on low memory systems.\n> It could take a look a /proc/meminfo for this.\n\nWell, we had thought it was already able to throttle itself, as\nwe did put code in to respond to mmap() and malloc() failures by\ntrying to release memory and retrying the failed operation again.\n\nHowever what we don't do is try to limit our heap usage to some\nlimit that is smaller than physical memory. We just assume that\nwhatever we need is available from the OS. This fails when what\nwe need exceeds physical memory and the OS tries to use swap.\nWe can get better performance by reducing what we mmap instead.\n\n:-|\n\nLooking at /proc/meminfo only works on Linux, and maybe some other\nOSes which support a /proc like design. But even then we don't\nreally know how much we are competing with other active processes\nand how much memory we can use.\n\n-- \nShawn.\n"},{"id":"86817","messageId":"a6b6acf60808111229u72ffad66kb7a253f2fef44654@mail.gmail.com","threadId":"14926","inReplyTo":"20080811192208.GK26363@spearce.org","subject":"Re: pack operation is thrashing my server","fromName":"Ken Pratt","fromEmail":"ken@kenpratt.net","sentAt":"2008-08-11T19:29:06Z","receivedAt":"2008-08-11T19:29:06Z","isPatch":false,"sender":{"key":"ken@kenpratt.net","avatar":"https://gravatar.com/avatar/f8a3d5768018a18060a195801ef6ee483ff034d88293d73326cc593a2e595967?d=mp&s=160"},"body":"> Looking at /proc/meminfo only works on Linux, and maybe some other\n> OSes which support a /proc like design. But even then we don't\n> really know how much we are competing with other active processes\n> and how much memory we can use.\n\nCould we create a git config variable to specify the maximumum amoung\nmemory to mmap? Any if that variable wasn't explicitly set, it would\nfall back on looking at /proc/meminfo?\n"},{"id":"86818","messageId":"20080811193423.GM26363@spearce.org","threadId":"14926","inReplyTo":"a6b6acf60808111229u72ffad66kb7a253f2fef44654@mail.gmail.com","subject":"Re: pack operation is thrashing my server","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-11T19:34:23Z","receivedAt":"2008-08-11T19:34:23Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Ken Pratt wrote:\n> > Looking at /proc/meminfo only works on Linux, and maybe some other\n> > OSes which support a /proc like design. But even then we don't\n> > really know how much we are competing with other active processes\n> > and how much memory we can use.\n> \n> Could we create a git config variable to specify the maximumum amoung\n> memory to mmap? Any if that variable wasn't explicitly set, it would\n> fall back on looking at /proc/meminfo?\n\nWell, core.packedGitLimit is supposed to be related to this limit\nyou are asking for. But it doesn't cover all memory usage as we\nmalloc other things. core.deltaBaseCacheLimit covers part of the\nmalloc'd area. pack.windowLimit I think covers another part of\nthe malloc'd area. Etc...\n\nThere really isn't a global \"malloc/mmap at most X bytes\".\n\n-- \nShawn.\n"},{"id":"86823","messageId":"20080811201049.GV9038@one.firstfloor.org","threadId":"14926","inReplyTo":"20080811193423.GM26363@spearce.org","subject":"Re: pack operation is thrashing my server","fromName":"Andi Kleen","fromEmail":"andi@firstfloor.org","sentAt":"2008-08-11T20:10:49Z","receivedAt":"2008-08-11T20:10:49Z","isPatch":false,"sender":{"key":"andi@firstfloor.org","avatar":null},"body":"> There really isn't a global \"malloc/mmap at most X bytes\".\n\nSure it can never be 100% accurate because other processes\ncan also steal memory.\n\nStill a 90+% heuristic can work pretty well. If memory < 512MB then don't\nuse mmap for example. If memory < 256MB do everything as tight\nas possible. gcc is using such heuristics quite successfully.\n\nThe only problem might be testing coverage for such options.\nIt might be useful to add options to force it and then run\nthe test suite with it.\n\n-Andi\n"},{"id":"86998","messageId":"alpine.LFD.1.10.0808122220500.9984@xanadu.home","threadId":"14926","inReplyTo":"a6b6acf60808111215y45b261d2ra667ea8d9f5f76d2@mail.gmail.com","subject":"Re: pack operation is thrashing my server","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-08-13T02:38:03Z","receivedAt":"2008-08-13T02:38:03Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 11 Aug 2008, Ken Pratt wrote:\n\n> > As a quick workaround you could try it with a 32bit git executable?\n> > (assuming you have a distribution with proper multilib support)\n> \n> In this case, I do have control over the server (running Arch Linux,\n> which should do 32-bit multilib just fine), but for my workflow I\n> cannot assume that the server will have 32-bit git support.\n> \n> I will use the previously mentioned solution of doing the packing\n> elsewhere for now as a band-aid, with hopes that this will get fixed\n> sometime soon.\n\nI'm afraid no fix is \"possible\" since you said:\n\n> Largest object is ~150MB, and there are a couple 5-10MB objects as \n> well.\n\nIf you have only 256 MB of RAM, I'm afraid the machine dives into swap \nthe moment it attempts to process that single 150-MB object during \nrepacking. Objects are always allocated entirely, including the \ndeflated and inflated copy at some point. Making git handle partial \nobjects in memory would add complexity all over the map so I don't think \nit'll ever be implemented nor be desirable.\n\nIf you do repack once with 'git repack -a -f -d' on a bigger machine \nthen 256 MB of RAM might be fine for serving clone and fetch requests \nthough.\n\n\nNicolas\n"},{"id":"86999","messageId":"20080813025027.GG1366@one.firstfloor.org","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0808122220500.9984@xanadu.home","subject":"Re: pack operation is thrashing my server","fromName":"Andi Kleen","fromEmail":"andi@firstfloor.org","sentAt":"2008-08-13T02:50:27Z","receivedAt":"2008-08-13T02:50:27Z","isPatch":false,"sender":{"key":"andi@firstfloor.org","avatar":null},"body":"> If you have only 256 MB of RAM, I'm afraid the machine dives into swap \n> the moment it attempts to process that single 150-MB object during \n> repacking. Objects are always allocated entirely, including the \n> deflated and inflated copy at some point. Making git handle partial \n> objects in memory would add complexity all over the map so I don't think \n> it'll ever be implemented nor be desirable.\n\nIf the access pattern is sequential and not much reuse it might be possible\nto madvise() strategically to do prefetch and early unmap of not used\nanymore data. I used that successfully in a few programs in the past that did\naggressive mmap on very large files.\n\n-Andi\n"},{"id":"87000","messageId":"20080813025749.GA5855@spearce.org","threadId":"14926","inReplyTo":"20080813025027.GG1366@one.firstfloor.org","subject":"Re: pack operation is thrashing my server","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-13T02:57:49Z","receivedAt":"2008-08-13T02:57:49Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Andi Kleen wrote:\n> > If you have only 256 MB of RAM, I'm afraid the machine dives into swap \n> > the moment it attempts to process that single 150-MB object during \n> > repacking. Objects are always allocated entirely, including the \n> > deflated and inflated copy at some point. Making git handle partial \n> > objects in memory would add complexity all over the map so I don't think \n> > it'll ever be implemented nor be desirable.\n> \n> If the access pattern is sequential and not much reuse it might be possible\n> to madvise() strategically to do prefetch and early unmap of not used\n> anymore data. I used that successfully in a few programs in the past that did\n> aggressive mmap on very large files.\n\nWe actually do something better where we can. However parts of\nGit assume that it can get back a contiguous block of memory which\ncontains the entire file content, decompressed. The data is stored\non disk compressed, so we cannot just mmap the data from disk.\n\n-- \nShawn.\n"},{"id":"87007","messageId":"1EE44425-6910-4C37-9242-54D0078FC377@adacore.com","threadId":"14926","inReplyTo":"87vdy71i6w.fsf@basil.nowhere.org","subject":"Re: pack operation is thrashing my server","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2008-08-13T03:12:58Z","receivedAt":"2008-08-13T03:12:58Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"\nOn Aug 11, 2008, at 15:10, Andi Kleen wrote:\n\n> As a quick workaround you could try it with a 32bit git executable?\n> (assuming you have a distribution with proper multilib support)\n>\n> I think the right fix would be to make git throttle itself (not\n> use mmap, use very small defaults etc.) on low memory systems.\n> It could take a look a /proc/meminfo for this.\n\nI've always felt that keeping largish objects (say anything >1MB)\nloose makes perfect sense. These objects are accessed infrequently,\noften binary or otherwise poor candidates for the delta algorithm.\n\nMany repositories are mostly well-behaved with large number of text\nfiles that aren't overly large and compress/diff well. However, often\na few huge files creep in. These might be a 30 MB Word or PDF documents\n(with lots of images of course), a bunch of artwork, some random .tgz \nfiles\nwith required tools or otherwise.\n\nRegardless of their origin, the presence of such files in real-world \nSCMs\nis a given and can ruin performance, even if they're hardly ever \naccessed\nor updated. If we would leave such oddball objects loose, the pack would\nbe much smaller, easier to generate, faster to use and there should be \nno\nmemory usage issues.\n\n -Geert\n"},{"id":"87001","messageId":"20080813031503.GC5855@spearce.org","threadId":"14926","inReplyTo":"1EE44425-6910-4C37-9242-54D0078FC377@adacore.com","subject":"Re: pack operation is thrashing my server","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-13T03:15:03Z","receivedAt":"2008-08-13T03:15:03Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Geert Bosch wrote:\n> I've always felt that keeping largish objects (say anything >1MB)\n> loose makes perfect sense. These objects are accessed infrequently,\n> often binary or otherwise poor candidates for the delta algorithm.\n\nSadly this causes huge problems with streaming a pack because the\nloose object has to be inflated and then delfated again to fit into\nthe pack stream.\n\nThe new style loose object format was meant to fix this problem,\nand it did, but the code was difficult to manage so it was backed\nout of the tree.\n\n-- \nShawn.\n"},{"id":"87010","messageId":"70550C21-8358-4BEF-A7BA-3A41C1ACB346@adacore.com","threadId":"14926","inReplyTo":"20080813031503.GC5855@spearce.org","subject":"Re: pack operation is thrashing my server","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2008-08-13T03:58:22Z","receivedAt":"2008-08-13T03:58:22Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"\nOn Aug 12, 2008, at 23:15, Shawn O. Pearce wrote:\n\n> Geert Bosch wrote:\n>> I've always felt that keeping largish objects (say anything >1MB)\n>> loose makes perfect sense. These objects are accessed infrequently,\n>> often binary or otherwise poor candidates for the delta algorithm.\n>\n> Sadly this causes huge problems with streaming a pack because the\n> loose object has to be inflated and then delfated again to fit into\n> the pack stream.\nSure, but that really is not that much of an issue. For people\nwith large systems connected by very fast networks, the current\nsituation is probably fine, and spending a lot of effort for\npacking often makes sense.\n\nHowever, for a random repository of Joe User, all the effort spent\non packing will probably never be gained back. Most people just\nsuck content from upstream and at most maintain a couple of local\nhacks on top of that. Little or nothing is ever pushed to other\nsystems.\n\nEven when pushing to other systems, this often is just a handful of \nobjects\nthough a slow line and compression/decompression speeds just don't \nmatter\nmuch.\n\n> The new style loose object format was meant to fix this problem,\n> and it did, but the code was difficult to manage so it was backed\n> out of the tree.\n\nOne nice optimization we could do for those pesky binary large objects\n(like PDF, JPG and GZIP-ed data), is to detect such files and revert\nto compression level 0. This should be especially beneficial\nsince already compressed data takes most time to compress again.\n\n -Geert\n"},{"id":"87045","messageId":"m3abfht7a9.fsf@localhost.localdomain","threadId":"14926","inReplyTo":"a6b6acf60808101247r4fea978ft6d2cdc53e1f99c0e@mail.gmail.com","subject":"Re: pack operation is thrashing my server","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2008-08-13T12:43:15Z","receivedAt":"2008-08-13T12:43:15Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"[...]\n\nIf I remember correctly there were on git mailing list some patches by\nDana How which put an upper bound on the size of individual objects\ngoing to pack; objects with size above threshold would be left as\nloose object (and shared via network drive).\n\nUnfortunately if I remember correctly they were not accepted in git.\nYou can try to pack large objects into separate pack, and .keep it,\nor try to ressurect the patches from git mailing list archive.\n\nHTH.\n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"87052","messageId":"alpine.LFD.1.10.0808131024460.4352@xanadu.home","threadId":"14926","inReplyTo":"1EE44425-6910-4C37-9242-54D0078FC377@adacore.com","subject":"Re: pack operation is thrashing my server","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-08-13T14:35:24Z","receivedAt":"2008-08-13T14:35:24Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 12 Aug 2008, Geert Bosch wrote:\n\n> I've always felt that keeping largish objects (say anything >1MB)\n> loose makes perfect sense. These objects are accessed infrequently,\n> often binary or otherwise poor candidates for the delta algorithm.\n\nOr, as I suggested in the past, they can be grouped into a separate \npack, or even occupy a pack of their own. As soon as you have more than \none revision of such largish objects then you lose again by keeping them \nloose.\n\n> Many repositories are mostly well-behaved with large number of text\n> files that aren't overly large and compress/diff well. However, often\n> a few huge files creep in. These might be a 30 MB Word or PDF documents\n> (with lots of images of course), a bunch of artwork, some random .tgz files\n> with required tools or otherwise.\n> \n> Regardless of their origin, the presence of such files in real-world SCMs\n> is a given and can ruin performance, even if they're hardly ever accessed\n> or updated. If we would leave such oddball objects loose, the pack would\n> be much smaller, easier to generate, faster to use and there should be no\n> memory usage issues.\n\nYou'll have memory usage issues whenever such objects are accessed, \nloose or not. However, once those big objects are packed once, they can \nbe repacked (or streamed over the net) without really \"accessing\" them. \nPacked object data is simply copied into a new pack in that case which \nis less of an issue on memory usage, irrespective of the original pack \nsize.\n\n\nNicolas\n"},{"id":"87053","messageId":"alpine.LFD.1.10.0808131036590.4352@xanadu.home","threadId":"14926","inReplyTo":"70550C21-8358-4BEF-A7BA-3A41C1ACB346@adacore.com","subject":"Re: pack operation is thrashing my server","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-08-13T14:37:50Z","receivedAt":"2008-08-13T14:37:50Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 12 Aug 2008, Geert Bosch wrote:\n\n> One nice optimization we could do for those pesky binary large objects\n> (like PDF, JPG and GZIP-ed data), is to detect such files and revert\n> to compression level 0. This should be especially beneficial\n> since already compressed data takes most time to compress again.\n\nThat would be a good thing indeed.\n\n\nNicolas\n"},{"id":"87056","messageId":"m363q5t152.fsf@localhost.localdomain","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0808131036590.4352@xanadu.home","subject":"Re: pack operation is thrashing my server","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2008-08-13T14:56:10Z","receivedAt":"2008-08-13T14:56:10Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Nicolas Pitre writes:\n\n> On Tue, 12 Aug 2008, Geert Bosch wrote:\n> \n> > One nice optimization we could do for those pesky binary large objects\n> > (like PDF, JPG and GZIP-ed data), is to detect such files and revert\n> > to compression level 0. This should be especially beneficial\n> > since already compressed data takes most time to compress again.\n> \n> That would be a good thing indeed.\n\nPerhaps take a sample of some given size and calculate entropy in it?\nOr just simply add gitattribute for per file compression ratio...\n\n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"87057","messageId":"20080813145944.GB3782@spearce.org","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0808131024460.4352@xanadu.home","subject":"Re: pack operation is thrashing my server","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-13T14:59:44Z","receivedAt":"2008-08-13T14:59:44Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre wrote:\n> You'll have memory usage issues whenever such objects are accessed, \n> loose or not. However, once those big objects are packed once, they can \n> be repacked (or streamed over the net) without really \"accessing\" them. \n> Packed object data is simply copied into a new pack in that case which \n> is less of an issue on memory usage, irrespective of the original pack \n> size.\n\nAnd fortunately here we actually do stream the objects we have\nchosen to reuse from the pack. We don't allocate the entire thing\nin memory. Its probably the only place in all of Git where we can\nhandle a 16 GB (after compression) object on a machine with only\n2 GB of memory and no swap.\n\nWhere little memory systems get into trouble with already packed\nrepositories is enumerating the objects to include in the pack.\nThis can still blow out their physical memory if the number of\nobjects to pack is high enough. We need something like 160 bytes\nof memory (my own memory is fuzzy on that estimate) per object.\nHave 500k objects and its suddenly something quite real in terms\nof memory usage.\n\n-- \nShawn.\n"},{"id":"87058","messageId":"20080813150425.GC3782@spearce.org","threadId":"14926","inReplyTo":"m363q5t152.fsf@localhost.localdomain","subject":"Re: pack operation is thrashing my server","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-13T15:04:25Z","receivedAt":"2008-08-13T15:04:25Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jakub Narebski wrote:\n> Nicolas Pitre writes:\n> > On Tue, 12 Aug 2008, Geert Bosch wrote:\n> > \n> > > One nice optimization we could do for those pesky binary large objects\n> > > (like PDF, JPG and GZIP-ed data), is to detect such files and revert\n> > > to compression level 0. This should be especially beneficial\n> > > since already compressed data takes most time to compress again.\n> > \n> > That would be a good thing indeed.\n> \n> Perhaps take a sample of some given size and calculate entropy in it?\n> Or just simply add gitattribute for per file compression ratio...\n\nEstimating the entropy would make it \"just magic\". Most of Git is\n\"just magic\" so that's a good direction to take. I'm not familiar\nenough with the PDF/JPG/GZIP/ZIP stream formats to know what the\nfirst 4-8k looks like to know if it would give a good indication\nof being already compressed.\n\nThough I'd imagine looking at the first 4k should be sufficient\nfor any compressed file. Having a header composed of 4k of _text_\nbefore binary compressed data would be nuts. Or a git-bundle with\na large refs listing. ;-)\n\nUsing a gitattribute inside of pack-objects is not \"simple\".\nWe currently only support reading attributes from the working\ndirectory if I recall correctly. pack-objects may not have a\nworking directory.\n\nHence, \"just magic\" is probably the better route.\n\n-- \nShawn.\n"},{"id":"87062","messageId":"e1dab3980808130826m4870df3ctf09ecf0062ef6e7c@mail.gmail.com","threadId":"14926","inReplyTo":"20080813150425.GC3782@spearce.org","subject":"Re: pack operation is thrashing my server","fromName":"David Tweed","fromEmail":"david.tweed@gmail.com","sentAt":"2008-08-13T15:26:48Z","receivedAt":"2008-08-13T15:26:48Z","isPatch":false,"sender":{"key":"david.tweed@gmail.com","avatar":null},"body":"On Wed, Aug 13, 2008 at 4:04 PM, Shawn O. Pearce wrote:\n> Jakub Narebski wrote:\n>> Nicolas Pitre writes:\n>> > On Tue, 12 Aug 2008, Geert Bosch wrote:\n>> >\n>> > > One nice optimization we could do for those pesky binary large objects\n>> > > (like PDF, JPG and GZIP-ed data), is to detect such files and revert\n>> > > to compression level 0. This should be especially beneficial\n>> > > since already compressed data takes most time to compress again.\n>> >\n>> > That would be a good thing indeed.\n>>\n>> Perhaps take a sample of some given size and calculate entropy in it?\n>> Or just simply add gitattribute for per file compression ratio...\n>\n> Estimating the entropy would make it \"just magic\". Most of Git is\n> \"just magic\" so that's a good direction to take. I'm not familiar\n> enough with the PDF/JPG/GZIP/ZIP stream formats to know what the\n> first 4-8k looks like to know if it would give a good indication\n> of being already compressed.\n>\n> Though I'd imagine looking at the first 4k should be sufficient\n> for any compressed file. Having a header composed of 4k of _text_\n> before binary compressed data would be nuts. Or a git-bundle with\n> a large refs listing. ;-)\n\nFWIW, PDF format is a mix of sections of uncompressed higher level\nASCII notation and sections of compressed actual glyph/location data\nfor individual pages, and I don't think the rules are very strict\nabout what goes where. Looking at some academic papers some contain\ncompressed data within the first hundred characters whilst I've got a\ncouple with the first compressed byte 1968 and 12304; I'm sure if I\nhad a longer pdf to look at I'd find one where compression data first\noccurred even later. I leave discussions of whether this is nuts to\nothers ;-) .\n\nJPG is pretty much guaranteed to contain compressed data after a\ncouple of metadata lines.\n\n-- \ncheers, dave tweed__________________________\ndavid.tweed@gmail.com\nRm 124, School of Systems Engineering, University of Reading.\n\"while having code so boring anyone can maintain it, use Python.\" --\nattempted insult seen on slashdot\n"},{"id":"87064","messageId":"alpine.LFD.1.10.0808131123221.4352@xanadu.home","threadId":"14926","inReplyTo":"20080813145944.GB3782@spearce.org","subject":"Re: pack operation is thrashing my server","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-08-13T15:43:38Z","receivedAt":"2008-08-13T15:43:38Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 13 Aug 2008, Shawn O. Pearce wrote:\n\n> Nicolas Pitre wrote:\n> > You'll have memory usage issues whenever such objects are accessed, \n> > loose or not. However, once those big objects are packed once, they can \n> > be repacked (or streamed over the net) without really \"accessing\" them. \n> > Packed object data is simply copied into a new pack in that case which \n> > is less of an issue on memory usage, irrespective of the original pack \n> > size.\n> \n> And fortunately here we actually do stream the objects we have\n> chosen to reuse from the pack. We don't allocate the entire thing\n> in memory. Its probably the only place in all of Git where we can\n> handle a 16 GB (after compression) object on a machine with only\n> 2 GB of memory and no swap.\n> \n> Where little memory systems get into trouble with already packed\n> repositories is enumerating the objects to include in the pack.\n> This can still blow out their physical memory if the number of\n> objects to pack is high enough. We need something like 160 bytes\n> of memory (my own memory is fuzzy on that estimate) per object.\n\nI'm counting something like 104 bytes on a 64-bit machine for\nstruct object_entry.\n\n> Have 500k objects and its suddenly something quite real in terms\n> of memory usage.\n\nWell, we are talking about 50MB which is not that bad.\n\nHowever there is a point where we should be realistic and just admit \nthat you need a sufficiently big machine if you have huge repositories \nto deal with. Git should be fine serving pull requests with relatively \nlittle memory usage, but anything else such as the initial repack simply \nrequire enough RAM to be effective.\n\n\nNicolas\n"},{"id":"87065","messageId":"20080813155016.GD3782@spearce.org","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0808131123221.4352@xanadu.home","subject":"Re: pack operation is thrashing my server","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-13T15:50:16Z","receivedAt":"2008-08-13T15:50:16Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre wrote:\n> On Wed, 13 Aug 2008, Shawn O. Pearce wrote:\n> > \n> > Where little memory systems get into trouble with already packed\n> > repositories is enumerating the objects to include in the pack.\n> \n> I'm counting something like 104 bytes on a 64-bit machine for\n> struct object_entry.\n\nDon't forget that we need not just struct object_entry, but\nalso the struct commit/tree/blob, their hash tables, and the\nstruct object_entry* in the sorted object list table, and\nthe pack reverse index table. It does add up.\n \n> > Have 500k objects and its suddenly something quite real in terms\n> > of memory usage.\n> \n> Well, we are talking about 50MB which is not that bad.\n\nI think we're closer to 100MB here due to the extra overheads\nI just alluded to above, and which weren't in your 104 byte\nper object figure.\n\n> However there is a point where we should be realistic and just admit \n> that you need a sufficiently big machine if you have huge repositories \n> to deal with. Git should be fine serving pull requests with relatively \n> little memory usage, but anything else such as the initial repack simply \n> require enough RAM to be effective.\n\nYea. But it would also be nice to be able to just concat packs\ntogether. Especially if the repository in question is an open source\none and everything published is already known to be in the wild,\nas say it is also available over dumb HTTP. Yea, I know people\nlike the 'security feature' of the packer not including objects\nwhich aren't reachable.\n\nBut how many times has Linus published something to his linux-2.6\ntree that he didn't mean to publish and had to rewind? I think\nthat may be \"never\". Yet how many times per day does his tree get\ncloned from scratch?\n\nThis is also true for many internal corporate repositories.\nUsers probably have full read access to the object database anyway,\nand maybe even have direct write access to it. Doing the object\nenumeration there is pointless as a security measure.\n\nI'm too busy to write a pack concat implementation proposal, so\nI'll just shutup now. But it wouldn't be hard if someone wanted\nto improve at least the initial clone serving case.\n\n-- \nShawn.\n"},{"id":"87067","messageId":"3E057C8D-FF72-47A2-BBA8-27A22AD67167@adacore.com","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0808131024460.4352@xanadu.home","subject":"Re: pack operation is thrashing my server","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2008-08-13T16:01:20Z","receivedAt":"2008-08-13T16:01:20Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"On Aug 13, 2008, at 10:35, Nicolas Pitre wrote:\n> On Tue, 12 Aug 2008, Geert Bosch wrote:\n>\n>> I've always felt that keeping largish objects (say anything >1MB)\n>> loose makes perfect sense. These objects are accessed infrequently,\n>> often binary or otherwise poor candidates for the delta algorithm.\n>\n> Or, as I suggested in the past, they can be grouped into a separate\n> pack, or even occupy a pack of their own.\n\nThis is fine, as long as we're not trying to create deltas\nof the large objects, or do other things that requires keeping\nthe inflated data in memory.\n\n> As soon as you have more than\n> one revision of such largish objects then you lose again by keeping \n> them\n> loose.\n\nYes, you lose potentially in terms of disk space, but you avoid the\nlarge memory footprint during pack generation. For very large blobs,\nit is best to degenerate to having each revision of each file on\nits own (whether we call it a single-file pack, loose object or \nwhatever).\nThat way, the large file can stay immutable on disk, and will only\nneed to be accessed during checkout. GIT will then scale with good\nperformance until we run out of disk space.\n\nThe alternative is that people need to keep large binary data out\nof their SCMs and handle it on the side. Consider a large web site\nwhere I have all scripts, HTML content, as well as a few movies\nto manage. The movies basically should be copied and stored, only\nto be accessed when a checkout (or push) is requested.\n\nIf we mix the very large movies with the 100,000 objects representing\nthe webpages, the resulting pack will become unwieldy and slow even\nto just copy around during repacks.\n\n> You'll have memory usage issues whenever such objects are accessed,\n> loose or not.\nWhy? The only time we'd need to access their contents for checkout\nor when pushing across the network. These should all be steaming \noperations\nwith small memory footprint.\n\n> However, once those big objects are packed once, they can\n> be repacked (or streamed over the net) without really \"accessing\" \n> them.\n> Packed object data is simply copied into a new pack in that case which\n> is less of an issue on memory usage, irrespective of the original pack\n> size.\nAgreed, but still, at least very large objects. If I have a 600MB\nfile in my repository, it should just not get in the way. If it gets\ncopied around during each repack, that just wastes I/O time for no\ngood reason. Even worse, it causes incremental backups or filesystem\ncheckpoints to become way more expensive. Just leaving large files\nalone as immutable objects on disk avoids all these issues.\n\n -Geert\n"},{"id":"87069","messageId":"200808131810.19914.johan@herland.net","threadId":"14926","inReplyTo":"20080813150425.GC3782@spearce.org","subject":"Re: pack operation is thrashing my server","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2008-08-13T16:10:19Z","receivedAt":"2008-08-13T16:10:19Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Wednesday 13 August 2008, Shawn O. Pearce wrote:\n> Jakub Narebski wrote:\n> > Nicolas Pitre writes:\n> > > On Tue, 12 Aug 2008, Geert Bosch wrote:\n> > > > One nice optimization we could do for those pesky binary large\n> > > > objects (like PDF, JPG and GZIP-ed data), is to detect such\n> > > > files and revert to compression level 0. This should be\n> > > > especially beneficial since already compressed data takes most\n> > > > time to compress again.\n> > >\n> > > That would be a good thing indeed.\n> >\n> > Perhaps take a sample of some given size and calculate entropy in\n> > it? Or just simply add gitattribute for per file compression\n> > ratio...\n>\n> Estimating the entropy would make it \"just magic\". Most of Git is\n> \"just magic\" so that's a good direction to take. I'm not familiar\n> enough with the PDF/JPG/GZIP/ZIP stream formats to know what the\n> first 4-8k looks like to know if it would give a good indication\n> of being already compressed.\n>\n> Though I'd imagine looking at the first 4k should be sufficient\n> for any compressed file. Having a header composed of 4k of _text_\n> before binary compressed data would be nuts. Or a git-bundle with\n> a large refs listing. ;-)\n\nAs for how to estimate entropy, isn't that just a matter of feeding it \nthrough zlib and compare the output size to the input size? Especially \nif we're already about to feed it through zlib anyway... In other \nwords, feed (an initial part of) the data through zlib, and if the \ncompression ratio so far looks good, keep going and write out the \ncompressed object, otherwise abort zlib and write out the original \nobject with compression level 0.\n\n> Hence, \"just magic\" is probably the better route.\n\nAgreed.\n\n\nHave fun!\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"87075","messageId":"alpine.LFD.1.10.0808131228270.4352@xanadu.home","threadId":"14926","inReplyTo":"20080813155016.GD3782@spearce.org","subject":"Re: pack operation is thrashing my server","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-08-13T17:04:03Z","receivedAt":"2008-08-13T17:04:03Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 13 Aug 2008, Shawn O. Pearce wrote:\n\n> Nicolas Pitre wrote:\n> > Well, we are talking about 50MB which is not that bad.\n> \n> I think we're closer to 100MB here due to the extra overheads\n> I just alluded to above, and which weren't in your 104 byte\n> per object figure.\n\nSure. That should still be workable on a machine with 256MB of RAM.\n\n> > However there is a point where we should be realistic and just admit \n> > that you need a sufficiently big machine if you have huge repositories \n> > to deal with. Git should be fine serving pull requests with relatively \n> > little memory usage, but anything else such as the initial repack simply \n> > require enough RAM to be effective.\n> \n> Yea. But it would also be nice to be able to just concat packs\n> together. Especially if the repository in question is an open source\n> one and everything published is already known to be in the wild,\n> as say it is also available over dumb HTTP. Yea, I know people\n> like the 'security feature' of the packer not including objects\n> which aren't reachable.\n\nIt is not only that, even if it is a point I consider important. If you \nend up with 10 packs, it is likely that a base object in each of those \npacks could simply be a delta against a single common base object, and \ntherefore the amount of data to transfer might be up to 10 times higher \nthan necessary.\n\n> But how many times has Linus published something to his linux-2.6\n> tree that he didn't mean to publish and had to rewind? I think\n> that may be \"never\". Yet how many times per day does his tree get\n> cloned from scratch?\n\nThat's not a good argument. Linus is a very disciplined git users, \nprobably more than average. We should not use that example to paper \nover technical issues.\n\n> This is also true for many internal corporate repositories.\n> Users probably have full read access to the object database anyway,\n> and maybe even have direct write access to it. Doing the object\n> enumeration there is pointless as a security measure.\n\nIt is good for network bandwidth efficiency as I mentioned.\n\n> I'm too busy to write a pack concat implementation proposal, so\n> I'll just shutup now. But it wouldn't be hard if someone wanted\n> to improve at least the initial clone serving case.\n\nA much better solution would consist of finding just _why_ object \nenumeration is so slow. This is indeed my biggest grip with git \nperformance at the moment.\n\n|nico@xanadu:linux-2.6> time git rev-list --objects --all > /dev/null\n|\n|real 0m21.742s\n|user 0m21.379s\n|sys 0m0.360s\n\nThat's way too long for 1030198 objects (roughly 48k objects/sec). And \nit gets even worse with the gcc repository:\n\n|nico@xanadu:gcc> time git rev-list --objects --all > /dev/null\n|\n|real 1m51.591s\n|user 1m50.757s\n|sys 0m0.810s\n\nThat's for 1267993 objects, or about 11400 objects/sec.\n\nClearly something is not scaling here.\n\n\nNicolas\n"},{"id":"87076","messageId":"56b7f5510808131013t4edfd31ar195177c82a91f93e@mail.gmail.com","threadId":"14926","inReplyTo":"3E057C8D-FF72-47A2-BBA8-27A22AD67167@adacore.com","subject":"Re: pack operation is thrashing my server","fromName":"Dana How","fromEmail":"danahow@gmail.com","sentAt":"2008-08-13T17:13:00Z","receivedAt":"2008-08-13T17:13:00Z","isPatch":false,"sender":{"key":"danahow@gmail.com","avatar":null},"body":"Hi Geert,\n\nI wrote the blob-size-threshold patch last year to which\nJakub Narebski referred.\n\nI think there will eventually be a way to better handle large\nobjects in Git. Some possible elements:\n* Loose objects have a format which can be streamed\n directly into or out of packs. This avoids a round-trip through zlib,\n which is a big deal for big objects. This was the effect of the \"new\"\n loose object format to which Shawn referred. This was\n removed apparently because it was ugly and/or difficult\n to maintain, which I didn't understand since I didn't personally\n suffer.\n* Loose objects actually _are_ singleton packs, but saved\n in .git/objects/xx. Workable, but would never happen due to\n the extra pack header at the beginning it would add. This\n takes advantage of the existing pack-to-pack streaming.\n* Large loose objects are never deltified and/or never packed.\n The latter was the focus of my patch.\n* Large loose objects are placed in their own packs in .git/packs .\n Doesn't work for me since I have too many large objects,\n thus slowing down _all_ pack operations.\nAll this is complicated by the dual nature of packfiles --\nthey are used as a \"wire format\" for serial transmission,\nas well as a database format for random access.\n\nThe \"magic\" entropy detection idea is cute, but probably not\nneeded -- using the blob size should be sufficient. Trying to\n(re)compress an incompressible _smallish_ blob is probably\nnot worth trying to avoid, and any computation on sufficiently large\nblobs should be avoided.\n\nHopefully I can return to this problem after New Year's. And\nperhaps with the expanding Git userbase, more people will have\n\"large blob\" problems ;-) and there will be more interest in\nbetter addressing this usage pattern.\n\nAt the moment, I am thinking about how to better structure\ngit's handling of very large repositories in a team entirely\nconnected by high-speed LAN. It seems a method where\neach user has a repository with deep history, but shallow\nblobs, would be ideal, but that's also very different from\nhow git does things now.\n\nHave fun,\n\nDana How\n\nOn Wed, Aug 13, 2008 at 9:01 AM, Geert Bosch wrote:\n> On Aug 13, 2008, at 10:35, Nicolas Pitre wrote:\n>>\n>> On Tue, 12 Aug 2008, Geert Bosch wrote:\n>>\n>>> I've always felt that keeping largish objects (say anything >1MB)\n>>> loose makes perfect sense. These objects are accessed infrequently,\n>>> often binary or otherwise poor candidates for the delta algorithm.\n>>\n>> Or, as I suggested in the past, they can be grouped into a separate\n>> pack, or even occupy a pack of their own.\n>\n> This is fine, as long as we're not trying to create deltas\n> of the large objects, or do other things that requires keeping\n> the inflated data in memory.\n>\n>> As soon as you have more than\n>> one revision of such largish objects then you lose again by keeping them\n>> loose.\n>\n> Yes, you lose potentially in terms of disk space, but you avoid the\n> large memory footprint during pack generation. For very large blobs,\n> it is best to degenerate to having each revision of each file on\n> its own (whether we call it a single-file pack, loose object or whatever).\n> That way, the large file can stay immutable on disk, and will only\n> need to be accessed during checkout. GIT will then scale with good\n> performance until we run out of disk space.\n>\n> The alternative is that people need to keep large binary data out\n> of their SCMs and handle it on the side. Consider a large web site\n> where I have all scripts, HTML content, as well as a few movies\n> to manage. The movies basically should be copied and stored, only\n> to be accessed when a checkout (or push) is requested.\n>\n> If we mix the very large movies with the 100,000 objects representing\n> the webpages, the resulting pack will become unwieldy and slow even\n> to just copy around during repacks.\n>\n>> You'll have memory usage issues whenever such objects are accessed,\n>> loose or not.\n>\n> Why? The only time we'd need to access their contents for checkout\n> or when pushing across the network. These should all be steaming operations\n> with small memory footprint.\n>\n>> However, once those big objects are packed once, they can\n>> be repacked (or streamed over the net) without really \"accessing\" them.\n>> Packed object data is simply copied into a new pack in that case which\n>> is less of an issue on memory usage, irrespective of the original pack\n>> size.\n>\n> Agreed, but still, at least very large objects. If I have a 600MB\n> file in my repository, it should just not get in the way. If it gets\n> copied around during each repack, that just wastes I/O time for no\n> good reason. Even worse, it causes incremental backups or filesystem\n> checkpoints to become way more expensive. Just leaving large files\n> alone as immutable objects on disk avoids all these issues.\n>\n> -Geert\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n>\n\n\n\n-- \nDana L. How danahow@gmail.com +1 650 804 5991 cell\n"},{"id":"87077","messageId":"20080813171921.GF3782@spearce.org","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0808131228270.4352@xanadu.home","subject":"Re: pack operation is thrashing my server","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-13T17:19:21Z","receivedAt":"2008-08-13T17:19:21Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre wrote:\n> On Wed, 13 Aug 2008, Shawn O. Pearce wrote:\n> > Doing the object\n> > enumeration is pointless as a security measure.\n> \n> It is good for network bandwidth efficiency as I mentioned.\n\nThe network bandwidth efficiency is the most valid argument for\nthe enumeration.\n\n> > I'm too busy to write a pack concat implementation proposal\n> \n> A much better solution would consist of finding just _why_ object \n> enumeration is so slow. This is indeed my biggest grip with git \n> performance at the moment.\n...\n> |nico@xanadu:gcc> time git rev-list --objects --all > /dev/null\n> |\n> |real 1m51.591s\n> |user 1m50.757s\n> |sys 0m0.810s\n> \n> That's for 1267993 objects, or about 11400 objects/sec.\n> \n> Clearly something is not scaling here.\n\nYikes. Last time I was looking at this sort of thing I think we\nspent around 60% of our time dealing with inflating, patching and\nparsing commit and tree objects. pack v4's formatting spawned\nout of that particular point, but we never really finished that.\nIts been years so I can't trust my memory enough to say pack v4 is\nthe solution to this, without redoing the profiling. But I think\nthat is what one would find.\n\nThough the decreasing objects/sec rate with increased total number\nof objects suggets the object hash isn't scaling.\n\n-- \nShawn.\n"},{"id":"87078","messageId":"alpine.LFD.1.10.0808131304560.4352@xanadu.home","threadId":"14926","inReplyTo":"3E057C8D-FF72-47A2-BBA8-27A22AD67167@adacore.com","subject":"Re: pack operation is thrashing my server","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-08-13T17:26:14Z","receivedAt":"2008-08-13T17:26:14Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 13 Aug 2008, Geert Bosch wrote:\n\n> On Aug 13, 2008, at 10:35, Nicolas Pitre wrote:\n> > On Tue, 12 Aug 2008, Geert Bosch wrote:\n> > \n> > > I've always felt that keeping largish objects (say anything >1MB)\n> > > loose makes perfect sense. These objects are accessed infrequently,\n> > > often binary or otherwise poor candidates for the delta algorithm.\n> > \n> > Or, as I suggested in the past, they can be grouped into a separate\n> > pack, or even occupy a pack of their own.\n> \n> This is fine, as long as we're not trying to create deltas\n> of the large objects, or do other things that requires keeping\n> the inflated data in memory.\n\nFirst, there is the delta attribute:\n\n|commit a74db82e15cd8a2c53a4a83e9a36dc7bf7a4c750\n|Author: Junio C Hamano \n|Date: Sat May 19 00:39:31 2007 -0700\n|\n| Teach \"delta\" attribute to pack-objects.\n|\n| This teaches pack-objects to use .gitattributes mechanism so\n| that the user can specify certain blobs are not worth spending\n| CPU cycles to attempt deltification.\n|\n| The name of the attrbute is \"delta\", and when it is set to\n| false, like this:\n|\n| == .gitattributes ==\n| *.jpg -delta\n|\n| they are always stored in the plain-compressed base object\n| representation.\n\nThis could probably be extended to take a size limit argument as well.\n\n> > As soon as you have more than\n> > one revision of such largish objects then you lose again by keeping them\n> > loose.\n> \n> Yes, you lose potentially in terms of disk space, but you avoid the\n> large memory footprint during pack generation. For very large blobs,\n> it is best to degenerate to having each revision of each file on\n> its own (whether we call it a single-file pack, loose object or whatever).\n> That way, the large file can stay immutable on disk, and will only\n> need to be accessed during checkout. GIT will then scale with good\n> performance until we run out of disk space.\n\nLoose objects, though, will always be selected for potential delta \ngeneration. Packed objects, deltified or not, are always streamed as is \nwhen serving pull requests. And by default delta compression is not \n(re)attempted between objects which are part of the same pack, the \nreason being that if they were not deltified on the first packing \nattempt then there is no point trying again when streaming them over the \nnet. So you always benefit from having your large objects packed with \nthe rest. This, plus the delta prevention mechanism above should cover \nmost cases.\n\n> > You'll have memory usage issues whenever such objects are accessed,\n> > loose or not.\n> Why? The only time we'd need to access their contents for checkout\n> or when pushing across the network. These should all be steaming operations\n> with small memory footprint.\n\nPushing across the network, or repacking without -f, is streamed. \nChecking out currently isn't (although it probably could). Repacking \nwith -f definitely isn't and probably shouldn't because of complexity \nissues.\n\n> > However, once those big objects are packed once, they can\n> > be repacked (or streamed over the net) without really \"accessing\" them.\n> > Packed object data is simply copied into a new pack in that case which\n> > is less of an issue on memory usage, irrespective of the original pack\n> > size.\n> Agreed, but still, at least very large objects. If I have a 600MB\n> file in my repository, it should just not get in the way. If it gets\n> copied around during each repack, that just wastes I/O time for no\n> good reason. Even worse, it causes incremental backups or filesystem\n> checkpoints to become way more expensive. Just leaving large files\n> alone as immutable objects on disk avoids all these issues.\n\nPack them in a pack of their own and stick a .keep file along with it. \nAt that point they will never be rewritten.\n\n\nNicolas\n"},{"id":"87082","messageId":"a6b6acf60808131038s1ae7fb69s2b703c25766a82c0@mail.gmail.com","threadId":"14926","inReplyTo":"200808131810.19914.johan@herland.net","subject":"Re: pack operation is thrashing my server","fromName":"Ken Pratt","fromEmail":"ken@kenpratt.net","sentAt":"2008-08-13T17:38:42Z","receivedAt":"2008-08-13T17:38:42Z","isPatch":false,"sender":{"key":"ken@kenpratt.net","avatar":"https://gravatar.com/avatar/f8a3d5768018a18060a195801ef6ee483ff034d88293d73326cc593a2e595967?d=mp&s=160"},"body":"> As for how to estimate entropy, isn't that just a matter of feeding it\n> through zlib and compare the output size to the input size? Especially\n> if we're already about to feed it through zlib anyway... In other\n> words, feed (an initial part of) the data through zlib, and if the\n> compression ratio so far looks good, keep going and write out the\n> compressed object, otherwise abort zlib and write out the original\n> object with compression level 0.\n\nThis if probably off topic now, but as the OP, I'd like to mention\nthat I tried setting pack.compression = 0 and it did not solve my\nmemory issues. So it seems to be that the packing itself that is\nsucking up all the memory -- not the compression.\n\nThanks for all the insightful replies!\n\n-Ken\n"},{"id":"87084","messageId":"alpine.LFD.1.10.0808131352260.4352@xanadu.home","threadId":"14926","inReplyTo":"a6b6acf60808131038s1ae7fb69s2b703c25766a82c0@mail.gmail.com","subject":"Re: pack operation is thrashing my server","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-08-13T17:57:59Z","receivedAt":"2008-08-13T17:57:59Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 13 Aug 2008, Ken Pratt wrote:\n\n> > As for how to estimate entropy, isn't that just a matter of feeding it\n> > through zlib and compare the output size to the input size? Especially\n> > if we're already about to feed it through zlib anyway... In other\n> > words, feed (an initial part of) the data through zlib, and if the\n> > compression ratio so far looks good, keep going and write out the\n> > compressed object, otherwise abort zlib and write out the original\n> > object with compression level 0.\n> \n> This is probably off topic now, but as the OP, I'd like to mention\n> that I tried setting pack.compression = 0 and it did not solve my\n> memory issues.\n\nYeah, the compression level is a tengential issue which has to do with \nspeed.\n\n> So it seems to be that the packing itself that is\n> sucking up all the memory -- not the compression.\n\nInitial packing requires enough memory. And if your repository is not \npacked, then every clone request will act just like a first packing. So \nfor git on a server to behave well, repositories have to be well packed.\n\n\nNicolas\n"},{"id":"87126","messageId":"46a038f90808131654r228a1b57y964f7cdb9c77be5f@mail.gmail.com","threadId":"14926","inReplyTo":"e1dab3980808130826m4870df3ctf09ecf0062ef6e7c@mail.gmail.com","subject":"Re: pack operation is thrashing my server","fromName":"Martin Langhoff","fromEmail":"martin.langhoff@gmail.com","sentAt":"2008-08-13T23:54:06Z","receivedAt":"2008-08-13T23:54:06Z","isPatch":false,"sender":{"key":"martin.langhoff@gmail.com","avatar":"https://gravatar.com/avatar/1e3f311b6c4c15836501901ca58f8c0b0667246488084ba524d8bc9867e22fd9?d=mp&s=160"},"body":"On Thu, Aug 14, 2008 at 3:26 AM, David Tweed wrote:\n> FWIW, PDF format is a mix of sections of uncompressed higher level\n> ASCII notation and sections of compressed actual glyph/location data\n\nThe PDF spec allows compression of the \"text\" sections - if a PDF is\nuncompressed, it's a good candidate for delta & compression.\nUnfortunately, within the same file you might have an embedded JPEG.\n\ncheers,\n\n\nm\n-- \n martin.langhoff@gmail.com\n martin@laptop.org -- School Server Architect\n - ask interesting questions\n - don't get distracted with shiny stuff - working code first\n - http://wiki.laptop.org/go/User:Martinlanghoff\n"},{"id":"87159","messageId":"48A3D1D7.5030805@op5.se","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0808131228270.4352@xanadu.home","subject":"Re: pack operation is thrashing my server","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2008-08-14T06:33:59Z","receivedAt":"2008-08-14T06:33:59Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Nicolas Pitre wrote:\n> On Wed, 13 Aug 2008, Shawn O. Pearce wrote:\n> \n>> Nicolas Pitre wrote:\n>>> Well, we are talking about 50MB which is not that bad.\n>> I think we're closer to 100MB here due to the extra overheads\n>> I just alluded to above, and which weren't in your 104 byte\n>> per object figure.\n> \n> Sure. That should still be workable on a machine with 256MB of RAM.\n> \n>>> However there is a point where we should be realistic and just admit \n>>> that you need a sufficiently big machine if you have huge repositories \n>>> to deal with. Git should be fine serving pull requests with relatively \n>>> little memory usage, but anything else such as the initial repack simply \n>>> require enough RAM to be effective.\n>> Yea. But it would also be nice to be able to just concat packs\n>> together. Especially if the repository in question is an open source\n>> one and everything published is already known to be in the wild,\n>> as say it is also available over dumb HTTP. Yea, I know people\n>> like the 'security feature' of the packer not including objects\n>> which aren't reachable.\n> \n> It is not only that, even if it is a point I consider important. If you \n> end up with 10 packs, it is likely that a base object in each of those \n> packs could simply be a delta against a single common base object, and \n> therefore the amount of data to transfer might be up to 10 times higher \n> than necessary.\n> \n\n[cut]\n\n>> This is also true for many internal corporate repositories.\n>> Users probably have full read access to the object database anyway,\n>> and maybe even have direct write access to it. Doing the object\n>> enumeration there is pointless as a security measure.\n> \n> It is good for network bandwidth efficiency as I mentioned.\n> \n\nAs a corporate git user, I can say that I'm very rarely worried\nabout how much data gets sent over our in-office gigabit network.\nMy primary concern wrt server side git is cpu- and IO-heavy\noperations, as we run the entire machine in a vmware guest os\nwhich just plain sucks at such things.\n\nWith that in mind, a config variable in /etc/gitconfig would\nwork wonderfully for that situation, as our central watering\nhole only ever serves locally.\n\n>> I'm too busy to write a pack concat implementation proposal, so\n>> I'll just shutup now. But it wouldn't be hard if someone wanted\n>> to improve at least the initial clone serving case.\n> \n> A much better solution would consist of finding just _why_ object \n> enumeration is so slow. This is indeed my biggest grip with git \n> performance at the moment.\n> \n> |nico@xanadu:linux-2.6> time git rev-list --objects --all > /dev/null\n> |\n> |real 0m21.742s\n> |user 0m21.379s\n> |sys 0m0.360s\n> \n> That's way too long for 1030198 objects (roughly 48k objects/sec). And \n> it gets even worse with the gcc repository:\n> \n> |nico@xanadu:gcc> time git rev-list --objects --all > /dev/null\n> |\n> |real 1m51.591s\n> |user 1m50.757s\n> |sys 0m0.810s\n> \n> That's for 1267993 objects, or about 11400 objects/sec.\n> \n> Clearly something is not scaling here.\n> \n\nWhat are the different packing options for the two repositories?\nA longer deltachain and larger packwindow would increase the\nenumeration time, wouldn't it?\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"87170","messageId":"e1dab3980808140204t29b56fa4h3b22e52fc576fb1e@mail.gmail.com","threadId":"14926","inReplyTo":"46a038f90808131654r228a1b57y964f7cdb9c77be5f@mail.gmail.com","subject":"Re: pack operation is thrashing my server","fromName":"David Tweed","fromEmail":"david.tweed@gmail.com","sentAt":"2008-08-14T09:04:55Z","receivedAt":"2008-08-14T09:04:55Z","isPatch":false,"sender":{"key":"david.tweed@gmail.com","avatar":null},"body":"On Thu, Aug 14, 2008 at 12:54 AM, Martin Langhoff\n wrote:\n> On Thu, Aug 14, 2008 at 3:26 AM, David Tweed wrote:\n>> FWIW, PDF format is a mix of sections of uncompressed higher level\n>> ASCII notation and sections of compressed actual glyph/location data\n>\n> The PDF spec allows compression of the \"text\" sections - if a PDF is\n> uncompressed, it's a good candidate for delta & compression.\n> Unfortunately, within the same file you might have an embedded JPEG.\n\nSure, all I was pointing out was that even pdfs with compressed page\ncontents can look like uncompressed text from looking at the entropy\nof the first 4k or 8k.\n\n-- \ncheers, dave tweed__________________________\ndavid.tweed@gmail.com\nRm 124, School of Systems Engineering, University of Reading.\n\"while having code so boring anyone can maintain it, use Python.\" --\nattempted insult seen on slashdot\n"},{"id":"87173","messageId":"200808141204.07530.trast@student.ethz.ch","threadId":"14926","inReplyTo":"48A3D1D7.5030805@op5.se","subject":"Re: pack operation is thrashing my server","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2008-08-14T10:04:01Z","receivedAt":"2008-08-14T10:04:01Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Andreas Ericsson wrote:\n> Nicolas Pitre wrote:\n> > |nico@xanadu:linux-2.6> time git rev-list --objects --all > /dev/null\n> > |\n> > |real 0m21.742s\n> > |user 0m21.379s\n> > |sys 0m0.360s\n> > \n> > That's way too long for 1030198 objects (roughly 48k objects/sec). And \n> > it gets even worse with the gcc repository:\n> > \n> > |nico@xanadu:gcc> time git rev-list --objects --all > /dev/null\n> > |\n> > |real 1m51.591s\n> > |user 1m50.757s\n> > |sys 0m0.810s\n> > \n> > That's for 1267993 objects, or about 11400 objects/sec.\n> > \n> > Clearly something is not scaling here.\n> > \n> \n> What are the different packing options for the two repositories?\n> A longer deltachain and larger packwindow would increase the\n> enumeration time, wouldn't it?\n\nFor the fun of it, I ran a test without deltas. Here's my normal\ngit.git:\n\n $ du -h .git/objects/pack\n 26M .git/objects/pack\n $ git rev-list --all | wc -l\n 17638\n $ git rev-list --all --objects | wc -l\n 82194\n\nOn a hot cache I get about 61800 objects/sec:\n\n $ /usr/bin/time git rev-list --all --objects >/dev/null\n 1.33user 0.04system 0:01.39elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k\n 0inputs+0outputs (0major+8087minor)pagefaults 0swaps\n\nI then made a copy of that and repacked it without deltas (remember to\nremove *.keep, I tripped over that twice):\n\n $ git repack --depth=0 --window=0 -a -f -d\n Counting objects: 82906, done.\n Writing objects: 100% (82906/82906), done.\n Total 82906 (delta 0), reused 0 (delta 0)\n $ du -h .git/objects/pack\n 339M .git/objects/pack\n\nWhich results in only 28739 objects/sec:\n\n $ /usr/bin/time git rev-list --all --objects >/dev/null\n 2.86user 0.11system 0:02.98elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n 0inputs+0outputs (0major+50162minor)pagefaults 0swaps\n\nSo maybe the GCC repository would need to be packed _better_?\n\nUnfortunately I cannot sensibly run the same test on linux-2.6.git,\nwhich is the next bigger git I have around: it inflates to about 3GB\nafter the repack, which does not fit into memory.\n\n- Thomas\n\n-- \nThomas Rast\ntrast@student.ethz.ch\n\n"},{"id":"87183","messageId":"48A405A6.7000405@op5.se","threadId":"14926","inReplyTo":"200808141204.07530.trast@student.ethz.ch","subject":"Re: pack operation is thrashing my server","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2008-08-14T10:15:02Z","receivedAt":"2008-08-14T10:15:02Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Thomas Rast wrote:\n> Andreas Ericsson wrote:\n>> Nicolas Pitre wrote:\n>>> |nico@xanadu:linux-2.6> time git rev-list --objects --all > /dev/null\n>>> |\n>>> |real 0m21.742s\n>>> |user 0m21.379s\n>>> |sys 0m0.360s\n>>>\n>>> That's way too long for 1030198 objects (roughly 48k objects/sec). And \n>>> it gets even worse with the gcc repository:\n>>>\n>>> |nico@xanadu:gcc> time git rev-list --objects --all > /dev/null\n>>> |\n>>> |real 1m51.591s\n>>> |user 1m50.757s\n>>> |sys 0m0.810s\n>>>\n>>> That's for 1267993 objects, or about 11400 objects/sec.\n>>>\n>>> Clearly something is not scaling here.\n>>>\n>> What are the different packing options for the two repositories?\n>> A longer deltachain and larger packwindow would increase the\n>> enumeration time, wouldn't it?\n> \n> For the fun of it, I ran a test without deltas. Here's my normal\n> git.git:\n> \n> $ du -h .git/objects/pack\n> 26M .git/objects/pack\n> $ git rev-list --all | wc -l\n> 17638\n> $ git rev-list --all --objects | wc -l\n> 82194\n> \n> On a hot cache I get about 61800 objects/sec:\n> \n> $ /usr/bin/time git rev-list --all --objects >/dev/null\n> 1.33user 0.04system 0:01.39elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k\n> 0inputs+0outputs (0major+8087minor)pagefaults 0swaps\n> \n> I then made a copy of that and repacked it without deltas (remember to\n> remove *.keep, I tripped over that twice):\n> \n> $ git repack --depth=0 --window=0 -a -f -d\n> Counting objects: 82906, done.\n> Writing objects: 100% (82906/82906), done.\n> Total 82906 (delta 0), reused 0 (delta 0)\n> $ du -h .git/objects/pack\n> 339M .git/objects/pack\n> \n> Which results in only 28739 objects/sec:\n> \n\nWell, if the objects are, on average, >twice the size, would that\nexplain it? I'd hate to see some of the sharper git minds hop off\non a wild goose chase if it's not necessary.\n\nHow does one go about getting the object sizes? rev-list appears\nto have no option for it.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"87190","messageId":"alpine.LFD.1.10.0808140954400.4352@xanadu.home","threadId":"14926","inReplyTo":"48A3D1D7.5030805@op5.se","subject":"Re: pack operation is thrashing my server","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-08-14T14:01:03Z","receivedAt":"2008-08-14T14:01:03Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 14 Aug 2008, Andreas Ericsson wrote:\n\n> As a corporate git user, I can say that I'm very rarely worried\n> about how much data gets sent over our in-office gigabit network.\n> My primary concern wrt server side git is cpu- and IO-heavy\n> operations, as we run the entire machine in a vmware guest os\n> which just plain sucks at such things.\n\nIn the general case, the amount of data sent over the network is \ndirectly proportional to disk IO.\n\n\nNicolas\n"},{"id":"87206","messageId":"alpine.LFD.1.10.0808141014410.3324@nehalem.linux-foundation.org","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0808131228270.4352@xanadu.home","subject":"Re: pack operation is thrashing my server","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-08-14T17:21:35Z","receivedAt":"2008-08-14T17:21:35Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 13 Aug 2008, Nicolas Pitre wrote:\n> \n> A much better solution would consist of finding just _why_ object \n> enumeration is so slow. This is indeed my biggest grip with git \n> performance at the moment.\n> \n> |nico@xanadu:linux-2.6> time git rev-list --objects --all > /dev/null\n> |\n> |real 0m21.742s\n> |user 0m21.379s\n> |sys 0m0.360s\n> \n> That's way too long for 1030198 objects (roughly 48k objects/sec).\n\nWhy do you think that's horribly slow?\n\nDoing a rev-list of all objects is a fairly rare operation, but even if \nyou want to clone/repack all of your archives the whole time, please \nrealize that listing objects is _not_ a simple operation. It opens up and \nparses every single tree in the whole history. That's a _lot_ of data to \nunpack.\n\nAnd trees also pack very efficiently (because they delta so well), so \nthere's a lot of complex ops there.\n\n> And it gets even worse with the gcc repository:\n\nI bet it's because gcc has a different directory structure. I don't have \nthe gcc sources in front of me, but I'd suspect something like a single \nlarge directory or other.\n\n> Clearly something is not scaling here.\n\nI don't agree. There's no \"clearly\" about it. Different data sets.\n\n\t\tLinus\n"},{"id":"87211","messageId":"alpine.LFD.1.10.0808141022500.3324@nehalem.linux-foundation.org","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0808141014410.3324@nehalem.linux-foundation.org","subject":"Re: pack operation is thrashing my server","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-08-14T17:58:01Z","receivedAt":"2008-08-14T17:58:01Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 14 Aug 2008, Linus Torvalds wrote:\n> \n> Doing a rev-list of all objects is a fairly rare operation, but even if \n> you want to clone/repack all of your archives the whole time, please \n> realize that listing objects is _not_ a simple operation. It opens up and \n> parses every single tree in the whole history. That's a _lot_ of data to \n> unpack.\n\nBtw, it's not that hard to run oprofile (link git statically to get better \nnumbers). For me, the answer to what is going on for a kernel rev-list is \npretty straightforward:\n\n\t263742 26.6009 lookup_object\n\t135945 13.7113 inflate\n\t110525 11.1475 inflate_fast\n\t75124 7.5770 inflate_table\n\t64676 6.5232 strlen\n\t48635 4.9053 memcpy\n\t47744 4.8154 find_pack_entry_one\n\t35265 3.5568 _int_malloc\n\t31579 3.1850 decode_tree_entry\n\t28388 2.8632 adler32\n\t19441 1.9608 process_tree\n\t10398 1.0487 patch_delta\n\t8925 0.9002 _int_free\n\t..\n\nso most of it is in inflate, but I suspect the cost of \"lookup_object()\" \nis so high becuase when we parse the trees we also have to look up every \nblob - even if they didn't change - just to see whether we already saw it \nor not.\n\nFor me, an instruction-level profile of lookup_object() shows that the \ncost is all in the hashcmp (53% of the profile is on that \"repz cmpsb\") \nand in the loading of the object pointer (26% of the profile is on the \ntest instruction after the \"obj_hash[i]\" load). I don't think we can \nreally improve that code much - the hash table is very efficient, and the \ncost is just in the fact that we have a lot of meory accesses.\n\nWe could try to use the (more memory-hungry) \"hash.c\" implementation for \nobject hashing, which actually includes a 32-bit key inside the hash \ntable, but while that will avoid the cost of fetching the object pointer \nfor the cases where we have collisions, most of the time the cost is not \nin the collision, but in the fact that we _hit_.\n\nI bet the hit percentage is 90+%, and the cost really is just that we \nencounter the same object hundreds or thousands of times.\n\nPlease realize that even if there may be \"only\" a million objects in the \nkernel, there are *MANY* more ways to _reach_ those objects, and that is \nwhat git-rev-list --objects does! It's not O(number-of-objects), it's \nO(number-of-object-linkages).\n\nFor my current kernel archive, for example, the number of objects is \nroughly 900k. However, think about how many times we'll actually reach a \nblob: that's roughly (blobs per commit)*(number of commits), which can be \napproximated with\n\n\techo $(( $(git ls-files | wc -l) * $(git rev-list --all | wc -l) ))\n\nwhich is 24324*108518=2639591832 ie about 2.5 _billion_ times.\n\nNow, we don't actually do anything close to that many lookups, because \nwhen a subdirectory doesn't change at all, we'll skip the whole tree after \nhaving seen it just once, so that will cut down on the number of objects \nwe have to look up by probably a couple of orders of magnitude.\n\nBut this is why the \"one large directory\" load performs worse: in the \nworst case, if you really have a totally flat directory tree, you'd \nliterally see that 2.5 billion object lookup case.\n\nSo it's not that git scales badly. It's that \"git rev-list --objects\" is \nreally a very expensive operation, and while some good practices (deep \ndirectory structures) makes it able to optimize the load away a lot, it's \nstill potentially very tough.\n\n\t\t\tLinus\n"},{"id":"87217","messageId":"alpine.LFD.1.10.0808141416540.4352@xanadu.home","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0808141014410.3324@nehalem.linux-foundation.org","subject":"Re: pack operation is thrashing my server","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-08-14T18:38:28Z","receivedAt":"2008-08-14T18:38:28Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 14 Aug 2008, Linus Torvalds wrote:\n\n> \n> \n> On Wed, 13 Aug 2008, Nicolas Pitre wrote:\n> > \n> > A much better solution would consist of finding just _why_ object \n> > enumeration is so slow. This is indeed my biggest grip with git \n> > performance at the moment.\n> > \n> > |nico@xanadu:linux-2.6> time git rev-list --objects --all > /dev/null\n> > |\n> > |real 0m21.742s\n> > |user 0m21.379s\n> > |sys 0m0.360s\n> > \n> > That's way too long for 1030198 objects (roughly 48k objects/sec).\n> \n> Why do you think that's horribly slow?\n\nCall it gut feeling. Or 60% CPU wasted in zlib.\n\n> Doing a rev-list of all objects is a fairly rare operation, but even if \n> you want to clone/repack all of your archives the whole time, please \n> realize that listing objects is _not_ a simple operation. It opens up and \n> parses every single tree in the whole history. That's a _lot_ of data to \n> unpack.\n\nI disagree. Well, right _now_ it is not a simple operation. But if you \nremember, I'm one of the co-investigator of the pack v4 format which \ngoal is to make history and tree walking much much cheaper, while making \ntheir packed representation denser too. Even with early prototypes of \nthe format with the overhead of converting objects back into the current \nformat on the fly in unpack_entry() the object enumeration was _faster_ \nthan current git.\n\nSo this might just be what was needed to bring back some incentive \nbehind the pack v4 effort.\n\n\nNicolas\n"},{"id":"87219","messageId":"alpine.LFD.1.10.0808141152210.3324@nehalem.linux-foundation.org","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0808141416540.4352@xanadu.home","subject":"Re: pack operation is thrashing my server","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-08-14T18:55:29Z","receivedAt":"2008-08-14T18:55:29Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 14 Aug 2008, Nicolas Pitre wrote:\n> \n> I disagree. Well, right _now_ it is not a simple operation. But if you \n> remember, I'm one of the co-investigator of the pack v4 format which \n> goal is to make history and tree walking much much cheaper, while making \n> their packed representation denser too.\n\nSee my other email with profile data and explanation.\n\nYes, zlib is high up, but it's not dominant to the point where a packfile \nformat change would maek a huge difference. You'd still need deltas for \ntrees, so even if you replaced zlib with something else, you'd still get a \nlarge hit.\n\nYou do realize that a lot of the zlib costs are due to cache misses, not \nzlib being fundamentally expensive in itself, right? Even if you made the \nzlib CPU costs be zero, you still couldn't avoid the _biggest_ cost.\n\n\t\t\tLinus\n"},{"id":"87220","messageId":"alpine.LFD.1.10.0808141442150.4352@xanadu.home","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0808141022500.3324@nehalem.linux-foundation.org","subject":"Re: pack operation is thrashing my server","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-08-14T19:04:13Z","receivedAt":"2008-08-14T19:04:13Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 14 Aug 2008, Linus Torvalds wrote:\n\n> Btw, it's not that hard to run oprofile (link git statically to get better \n> numbers). For me, the answer to what is going on for a kernel rev-list is \n> pretty straightforward:\n> \n> \t263742 26.6009 lookup_object\n> \t135945 13.7113 inflate\n> \t110525 11.1475 inflate_fast\n> \t75124 7.5770 inflate_table\n> \t64676 6.5232 strlen\n> \t48635 4.9053 memcpy\n> \t47744 4.8154 find_pack_entry_one\n> \t35265 3.5568 _int_malloc\n> \t31579 3.1850 decode_tree_entry\n> \t28388 2.8632 adler32\n> \t19441 1.9608 process_tree\n> \t10398 1.0487 patch_delta\n> \t8925 0.9002 _int_free\n> \t..\n\nOK, inflate went down since last time I profiled this, but that's \nprobably because lookup_object went up.\n\n> so most of it is in inflate,\n\nWhich, again, would be eliminated entirely by pack v4.\n\n> but I suspect the cost of \"lookup_object()\" \n> is so high becuase when we parse the trees we also have to look up every \n> blob - even if they didn't change - just to see whether we already saw it \n> or not.\n\nOne optimization with pack v4 was to have delta chunks aligned on tree \nrecords, and because tree objects are no longer compressed, parsing a \ntree object could be done by simply walking the delta chain directly. \nThen, another optimization would consist of simply skipping any part of \na tree object making a delta reference to a base object which has \nalready been parsed which would avoid a large bunch of lookup_object() \ncalls too.\n\nAnd because \ndelta base objects are normally seen first in recency order then this \nwould reduce the combinatorial complexity significantly.\n\n\nNicolas\n"},{"id":"87223","messageId":"alpine.LFD.1.10.0808141215520.3324@nehalem.linux-foundation.org","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0808141442150.4352@xanadu.home","subject":"Re: pack operation is thrashing my server","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-08-14T19:44:29Z","receivedAt":"2008-08-14T19:44:29Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 14 Aug 2008, Nicolas Pitre wrote:\n> \n> > so most of it is in inflate,\n> \n> Which, again, would be eliminated entirely by pack v4.\n\nI seriously doubt that.\n\nNico, it's really easy to say \"I wave my magic wand and nothing remains\".\n\nIt's hard to actually _do_.\n\n> One optimization with pack v4 was to have delta chunks aligned on tree \n> records, and because tree objects are no longer compressed, parsing a \n> tree object could be done by simply walking the delta chain directly. \n\nEven if you do that, please take a look at the performance characteristics \nof modern CPU's.\n\nHere's a hint: the cost of a cache miss is generally about a hundred times \nthe cost of just about anything else. \n\nSo to make a convincing argument, you'd have to show that the actual \nmemory access patterns are also much better.\n\nNo, zlib isn't perfect, and nope, inflate_fast() is no \"memcpy()\". And \nyes, I'm sure a pure memcpy would be much faster. But I seriously suspect \nthat a lot of the cost is literally in bringing in the source data to the \nCPU. Because we just mmap() the whole pack-file, the first access to the \ndata is going to see the cost of the cache misses.\n\n\t\t\tLinus\n"},{"id":"87237","messageId":"20080814213033.GE13814@one.firstfloor.org","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0808141215520.3324@nehalem.linux-foundation.org","subject":"Re: pack operation is thrashing my server","fromName":"Andi Kleen","fromEmail":"andi@firstfloor.org","sentAt":"2008-08-14T21:30:33Z","receivedAt":"2008-08-14T21:30:33Z","isPatch":false,"sender":{"key":"andi@firstfloor.org","avatar":null},"body":"> Here's a hint: the cost of a cache miss is generally about a hundred times \n\n100 times seems quite optimistic %)\n\n> \n> No, zlib isn't perfect, and nope, inflate_fast() is no \"memcpy()\". And \n> yes, I'm sure a pure memcpy would be much faster. But I seriously suspect \n> that a lot of the cost is literally in bringing in the source data to the \n> CPU. Because we just mmap() the whole pack-file, the first access to the \n> data is going to see the cost of the cache misses.\n\nI would have thought that zlib has a sequential access pattern that the\nCPU prefetchers have a easy time with hiding latency.\n\nBTW I always wonder why people reason about cache misses in oprofile\nlogs without actually using the cache miss counters.\n\n-Andi\n"},{"id":"87240","messageId":"alpine.LFD.1.10.0808141633080.4352@xanadu.home","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0808141215520.3324@nehalem.linux-foundation.org","subject":"Re: pack operation is thrashing my server","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-08-14T21:50:18Z","receivedAt":"2008-08-14T21:50:18Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 14 Aug 2008, Linus Torvalds wrote:\n\n> Here's a hint: the cost of a cache miss is generally about a hundred times \n> the cost of just about anything else. \n> \n> So to make a convincing argument, you'd have to show that the actual \n> memory access patterns are also much better.\n> \n> No, zlib isn't perfect, and nope, inflate_fast() is no \"memcpy()\". And \n> yes, I'm sure a pure memcpy would be much faster. But I seriously suspect \n> that a lot of the cost is literally in bringing in the source data to the \n> CPU. Because we just mmap() the whole pack-file, the first access to the \n> data is going to see the cost of the cache misses.\n\nPossible. However, the fact that both the \"Compressing objects\" and the \n\"Writing objects\" phases during a repack (without -f) together are \n_faster_ than the \"Counting objects\" phase is a sign that something is \nmore significant than cache misses here, especially when tree \ninformation is a small portion of the total pack data size.\n\nOf course we can do further profiling, say with core.compression set to \n0 and a full repack, or even hacking the pack-objects code to force a \ncompression level of 0 for tree objects, and possibly commits too since \npack v4 intend to deflate only the log text). Tree objects delta very \nwell, but they don't deflate well at all.\n\nOK, so I did, and the quick test for the kernel is:\n\n|nico@xanadu:linux-2.6> time git rev-list --all --objects > /dev/null\n|\n|real 0m14.737s\n|user 0m14.432s\n|sys 0m0.296s\n\nThat's for 1031404 objects, hence we're now talking around 70k \nobjects/sec instead of 48k objects/sec. _Only_ by removing zlib out of \nthe equation despite the fact that the pack is now larger. So I bet \nthat additional improvements from pack v4 could improve things even \nmore, including the object lookup avoidance optimization I mentioned \npreviously.\n\n\nNicolas\n"},{"id":"87256","messageId":"20080814223327.GV3782@spearce.org","threadId":"14926","inReplyTo":"48A405A6.7000405@op5.se","subject":"Re: pack operation is thrashing my server","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-14T22:33:27Z","receivedAt":"2008-08-14T22:33:27Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Andreas Ericsson wrote:\n> How does one go about getting the object sizes? rev-list appears\n> to have no option for it.\n\nWith great pain. You can use the output of verify-pack -v to\ntell you the size of the inflated portion of the object, but for\na delta this is the inflated size of the delta, not of the fully\nunpacked object.\n\n-- \nShawn.\n"},{"id":"87268","messageId":"alpine.LFD.1.10.0808141544150.3324@nehalem.linux-foundation.org","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0808141633080.4352@xanadu.home","subject":"Re: pack operation is thrashing my server","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-08-14T23:14:26Z","receivedAt":"2008-08-14T23:14:26Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nOn Thu, 14 Aug 2008, Nicolas Pitre wrote:\n> \n> Possible. However, the fact that both the \"Compressing objects\" and the \n> \"Writing objects\" phases during a repack (without -f) together are \n> _faster_ than the \"Counting objects\" phase is a sign that something is \n> more significant than cache misses here, especially when tree \n> information is a small portion of the total pack data size.\n\nHmm. I think I may have clue.\n\nThe size of the delta cache seems to be a sensitive parameter for this \nthing. Not so much for the git archive, but working on the kernel tree, \nraising it to 1024 seems to give a 20% performance improvement. That, in \nturn, implies that we may be unpacking things over and over again because \nof bad locality wrt delta generation. \n\nI'm not sure how easy something like that is to fix, though. We generate \nthe object list in \"recency\" order for a reason, but that also happens to \nbe the worst possible order for re-using the delta cache - by the time we \nget back to the next version of some tree entry, we'll have cycled through \nall the other trees, and blown all the caches, so we'll end up likely \nre-doing the whole delta chain.\n\nSo it's quite possible that what ends up happening is that some directory \nwith a deep delta chain will basically end up unpacking the whole chain - \nwhich obviously includes inflating each delta - over and over again.\n\nThat's what the delta cache was supposed to avoid..\n\nLooking at some call graphs, for the kernel I get:\n\n - process_tree() called 10 million times\n\n - causing parse_tree() called 479,466 times (whew, so 19 out of 20 trees \n have already been seen and can be discarded)\n\n - which in turn calls read_sha1_file() (total: 588,110 times, but there's \n a hundred thousand+ commits)\n\nbut that actually causes \n\n - 588,110 cals to cache_or_unpack_entry\n\nout of which 5,850 calls hit in the cache, and 582,260 do *not*.\n\nIOW, the delta cache effectively never triggers because the working set is \n_way_ bigger than the cache, and the patterns aren't good. So since most \ntrees are deltas, and the max delta depth is 10, the average depth is \nsoemthing like 5, and we actually get an ugly\n\n - 1,637,999 calls to unpack_compressed_entry\n\nwhich all results in a zlib inflate call.\n\nSo we actually have three times as many calls to inflate as we even have \nobjects parsed, due to the delta chains on the trees (the commits almost \nnever delta-chain at all, much less any deeper than a couple of entries).\n\nSo yeah, trees are the problem here, and yes, avoiding inflating them \nwould help - but mainly because we do it something like four times per \nobject on average!\n\nOuch. But we really can't just make the cache bigger, and the bad access \npatterns really are on purpose here. The delta cache was not meant for \nthis, it was really meant for the \"dig deeper into the history of a single \nfile\" kind of situation that gets very different patterns indeed.\n\nI'll see if I can think of anything simple to avoid all this unnecessary \nwork. But it doesn't look too good.\n\n\t\tLinus\n"},{"id":"87273","messageId":"20080814233958.GA31225@atjola.homenet","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0808141544150.3324@nehalem.linux-foundation.org","subject":"Re: pack operation is thrashing my server","fromName":"Björn Steinbrink","fromEmail":"b.steinbrink@gmx.de","sentAt":"2008-08-14T23:39:58Z","receivedAt":"2008-08-14T23:39:58Z","isPatch":false,"sender":{"key":"b.steinbrink@gmx.de","avatar":"https://avatars.githubusercontent.com/u/230962?v=4"},"body":"On 2008.08.14 16:14:26 -0700, Linus Torvalds wrote:\n> \n> On Thu, 14 Aug 2008, Nicolas Pitre wrote:\n> > \n> > Possible. However, the fact that both the \"Compressing objects\" and the \n> > \"Writing objects\" phases during a repack (without -f) together are \n> > _faster_ than the \"Counting objects\" phase is a sign that something is \n> > more significant than cache misses here, especially when tree \n> > information is a small portion of the total pack data size.\n> \n> Hmm. I think I may have clue.\n> \n> The size of the delta cache seems to be a sensitive parameter for this \n> thing. Not so much for the git archive, but working on the kernel tree, \n> raising it to 1024 seems to give a 20% performance improvement. That, in \n> turn, implies that we may be unpacking things over and over again because \n> of bad locality wrt delta generation. \n\nSince you mention the delta cache, uau (no idea about his real name) on\n#git was talking about some delta cache optimizations lately, although\nhe was dealing with \"git log -S\", maybe it affects rev-list in a similar\nway. Unfortunately, I can't seem to find any code for that, just a\ndescription of what he did and some numbers on the results in the IRC\nlogs.\n\nhttp://colabti.org/irclogger/irclogger_log/git?date=2008-08-04,Mon#l65\n\nMaybe that helps in some way.\n\nBjörn\n"},{"id":"87277","messageId":"alpine.LFD.1.10.0808141656120.3324@nehalem.linux-foundation.org","threadId":"14926","inReplyTo":"20080814233958.GA31225@atjola.homenet","subject":"Re: pack operation is thrashing my server","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-08-15T00:06:13Z","receivedAt":"2008-08-15T00:06:13Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 15 Aug 2008, Björn Steinbrink wrote:\n> \n> Since you mention the delta cache, uau (no idea about his real name) on\n> #git was talking about some delta cache optimizations lately, although\n> he was dealing with \"git log -S\", maybe it affects rev-list in a similar\n> way. Unfortunately, I can't seem to find any code for that, just a\n> description of what he did and some numbers on the results in the IRC\n> logs.\n\nYes, interesting.\n\nThe delta cache was really a huge hack that just turned out rather \nsuccessful. It's been hacked on further since (to do some half-way \nreasonable replacement with _another_ hack by adding an LRU on top of it), \nbut it really is very hacky indeed.\n\nThe \"hash\" we use for looking things up is also pretty much a joke, and it \nhas no overflow capability, it just replaces the old entry with a new one.\n\nI wonder how hard it would be to replace the whole table thing with our \ngeneric hash.c hash thing. I'll take a look.\n\n\t\t\tLinus\n"},{"id":"87283","messageId":"alpine.LFD.1.10.0808141720250.3324@nehalem.linux-foundation.org","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0808141656120.3324@nehalem.linux-foundation.org","subject":"Re: pack operation is thrashing my server","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-08-15T00:25:44Z","receivedAt":"2008-08-15T00:25:44Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 14 Aug 2008, Linus Torvalds wrote:\n> \n> I wonder how hard it would be to replace the whole table thing with our \n> generic hash.c hash thing. I'll take a look.\n\nOk, I did a quick version that didn't replace anything at all, and it \ndoesn't look like there is room for that helping much. Yes, I can speed \nthings up, but it didn't get much faster than just raising the delta cache \nto 1024 entries.\n\nAdmittedly my quick hack might have been fundamentally flawed, but it was \nsuch an ugly thing that I'm not even going to post it.\n\nAnd the added memory footprint makes it unacceptable, so it's going to be \nlimited by the cache size anyway, and not get a lot of hits in git \nrev-list, methinks.\n\n\t\tLinus\n"},{"id":"87287","messageId":"alpine.LFD.1.10.0808142139410.4352@xanadu.home","threadId":"14926","inReplyTo":"20080814223327.GV3782@spearce.org","subject":"Re: pack operation is thrashing my server","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-08-15T01:46:40Z","receivedAt":"2008-08-15T01:46:40Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 14 Aug 2008, Shawn O. Pearce wrote:\n\n> Andreas Ericsson wrote:\n> > How does one go about getting the object sizes? rev-list appears\n> > to have no option for it.\n> \n> With great pain. You can use the output of verify-pack -v to\n> tell you the size of the inflated portion of the object, but for\n> a delta this is the inflated size of the delta, not of the fully\n> unpacked object.\n\nDelta objects have the size of the final object in their header. There \nis get_size_from_delta() extracting that information already. There is \nsimply no interface exporting that info to external tools but that \nshouldn't be hard to add.\n\n\nNicolas\n"},{"id":"87323","messageId":"alpine.LFD.1.10.0808150907190.3324@nehalem.linux-foundation.org","threadId":"14926","inReplyTo":"20080814213033.GE13814@one.firstfloor.org","subject":"Re: pack operation is thrashing my server","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-08-15T16:15:52Z","receivedAt":"2008-08-15T16:15:52Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 14 Aug 2008, Andi Kleen wrote:\n> \n> I would have thought that zlib has a sequential access pattern that the\n> CPU prefetchers have a easy time with hiding latency.\n\nNo, the lookup tables for the patterns are quite non-sequential. It does \ndo a lot of indirect accesses, ie it loads data from the input stream and \nthen looks things up through that. \n\nBut it's quite possible that we should use different compression factors \nfor different object types. Right now we have different (configurable) \ncompression levels for loose objects and packs, but it might be \ninteresting to see what happens for just \"packed tree objects\".\n\nThe trees really end up having rather different access patterns in \npack-files. They also tend to be rather less compressible than other \nblobs, since the SHA1's in there are just random binary data. They also \ndelta very well - obviously regular blobs do that _too_, but regular blobs \nare seldom as performance-critical in git (ie once you actually unpack a \nblob, there are other things going on like actually generating a diff - \nbut trees get unpacked over and over for \"internal git reasons\")\n\n\t\tLinus\n"},{"id":"87354","messageId":"alpine.LFD.1.10.0808151729070.3324@nehalem.linux-foundation.org","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0808141544150.3324@nehalem.linux-foundation.org","subject":"Re: pack operation is thrashing my server","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-08-16T00:34:45Z","receivedAt":"2008-08-16T00:34:45Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 14 Aug 2008, Linus Torvalds wrote:\n> \n> So yeah, trees are the problem here, and yes, avoiding inflating them \n> would help - but mainly because we do it something like four times per \n> object on average!\n\nInterestingly, it turns out that git also hits a sad performance downside \nof using zlib.\n\nWe always tend to set \"stream.avail_out\" to the exact size of the expected \noutput. And it turns out that that means that the fast-path case of \ninffast.c doesn't trigger as often as it could. This (idiotic) patch \nactually seems to help performance on git rev-list by about 5%.\n\nBut maybe it's just me seeing things. But I did this because of the entry \nassumptions in inflate_fast(), that code only triggers for the case of \nstrm->avail_out >= 258.\n\nSad, if true.\n\n\t\tLinus\n\n---\n sha1_file.c | 4 ++--\n 1 files changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex a57155d..5ca7ce2 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1500,11 +1500,11 @@ static void *unpack_compressed_entry(struct packed_git *p,\n \tz_stream stream;\n \tunsigned char *buffer, *in;\n \n-\tbuffer = xmalloc(size + 1);\n+\tbuffer = xmalloc(size + 256 + 1);\n \tbuffer[size] = 0;\n \tmemset(&stream, 0, sizeof(stream));\n \tstream.next_out = buffer;\n-\tstream.avail_out = size;\n+\tstream.avail_out = size + 256;\n \n \tinflateInit(&stream);\n \tdo {\n"},{"id":"87375","messageId":"20080816124731.GA13444@atjola.homenet","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0808141656120.3324@nehalem.linux-foundation.org","subject":"Re: pack operation is thrashing my server","fromName":"Björn Steinbrink","fromEmail":"b.steinbrink@gmx.de","sentAt":"2008-08-16T12:47:31Z","receivedAt":"2008-08-16T12:47:31Z","isPatch":false,"sender":{"key":"b.steinbrink@gmx.de","avatar":"https://avatars.githubusercontent.com/u/230962?v=4"},"body":"On 2008.08.14 17:06:13 -0700, Linus Torvalds wrote:\n> The \"hash\" we use for looking things up is also pretty much a joke, and it \n> has no overflow capability, it just replaces the old entry with a new one.\n\nSo I added some stupid tracing to cache_or_unpack entry to see how often\nwe reread the same stuff. The whole thing just logs the base_offset in\ncase of a cache miss. I've gc'ed my linux-2.6.git before the run, so\nthat there's only a single packed_git around (at least I hope so), and I\ncan ignore that for the tracing.\n\nThe whole log for a \"git rev-list --objects HEAD\" has about 1.2M\nentries, while the output of the rev-list command has about 870k lines.\nSome postprocessing of the trace shows that the majority of objects is\nread only once or twice. A few percent are read three to ten times, and\nsome are read more than two hundred times.\n\nI'll attach the post-processed thing. The format is:\n x y\n\nMeaning that there were x base_offset values for which we had y cache\nmisses.\n\nBjörn\n\n\n 391805 1\n 110622 2\n 27830 3\n 13995 4\n 8583 5\n 5834 6\n 4275 7\n 3242 8\n 2514 9\n 2168 10\n 1632 11\n 1336 12\n 1197 13\n 947 14\n 788 15\n 704 16\n 565 17\n 514 18\n 422 19\n 348 20\n 304 21\n 276 22\n 227 23\n 233 24\n 180 25\n 160 26\n 145 27\n 106 28\n 123 29\n 109 30\n 86 31\n 91 32\n 72 33\n 63 34\n 55 35\n 73 36\n 61 37\n 56 38\n 48 39\n 44 40\n 47 41\n 36 42\n 44 43\n 47 44\n 32 45\n 36 46\n 27 47\n 19 48\n 34 49\n 28 50\n 22 51\n 21 52\n 26 53\n 18 54\n 19 55\n 16 56\n 22 57\n 16 58\n 16 59\n 11 60\n 13 61\n 19 62\n 17 63\n 8 64\n 21 65\n 8 66\n 8 67\n 16 68\n 9 69\n 12 70\n 11 71\n 8 72\n 5 73\n 6 74\n 9 75\n 6 76\n 9 77\n 7 78\n 8 79\n 7 80\n 8 81\n 6 82\n 5 83\n 13 84\n 9 85\n 8 86\n 4 87\n 5 89\n 6 90\n 3 91\n 7 92\n 4 93\n 5 94\n 5 95\n 5 96\n 4 97\n 3 98\n 7 99\n 2 100\n 4 101\n 4 102\n 7 103\n 4 104\n 4 105\n 5 106\n 3 107\n 1 108\n 4 109\n 1 110\n 1 111\n 1 112\n 6 113\n 5 114\n 2 115\n 5 116\n 2 117\n 2 118\n 2 119\n 7 120\n 1 121\n 4 122\n 3 123\n 3 124\n 3 125\n 4 126\n 1 127\n 2 128\n 2 129\n 2 130\n 1 131\n 4 132\n 1 133\n 4 134\n 1 135\n 2 136\n 4 137\n 1 139\n 3 140\n 3 141\n 5 142\n 5 143\n 4 144\n 1 148\n 2 149\n 3 150\n 1 151\n 2 152\n 6 153\n 1 154\n 2 155\n 2 156\n 3 157\n 2 158\n 1 159\n 3 160\n 2 161\n 4 162\n 2 163\n 5 164\n 2 165\n 2 166\n 2 169\n 2 170\n 1 171\n 1 172\n 1 173\n 1 176\n 2 177\n 2 178\n 2 179\n 1 180\n 3 181\n 3 182\n 1 183\n 1 184\n 1 186\n 1 187\n 1 190\n 1 192\n 1 194\n 2 195\n 3 196\n 1 197\n 1 200\n 1 201\n 1 202\n 1 208\n 2 214\n 2 216\n 2 217\n 3 224\n 1 225\n 1 228\n 1 230\n 2 232\n 2 233\n 1 234\n 2 236\n 1 239\n 1 241\n 1 245\n 1 246\n 2 249\n 2 250\n 1 252\n 1 259\n 1 261\n 2 263\n 1 266\n 2 268\n 1 272\n 1 282\n"},{"id":"89930","messageId":"7vk5dorclv.fsf@gitster.siamese.dyndns.org","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0808151729070.3324@nehalem.linux-foundation.org","subject":"Re: pack operation is thrashing my server","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-09-07T01:03:40Z","receivedAt":"2008-09-07T01:03:40Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> Interestingly, it turns out that git also hits a sad performance downside \n> of using zlib.\n>\n> We always tend to set \"stream.avail_out\" to the exact size of the expected \n> output. And it turns out that that means that the fast-path case of \n> inffast.c doesn't trigger as often as it could. This (idiotic) patch \n> actually seems to help performance on git rev-list by about 5%.\n>\n> But maybe it's just me seeing things. But I did this because of the entry \n> assumptions in inflate_fast(), that code only triggers for the case of \n> strm->avail_out >= 258.\n>\n> Sad, if true.\n\nThis is reproducible \"rev-list --objects --all\" in my copy of the kernel\nrepo takes around 47-48 seconds user time, and with the (idiotic) patch it\nis cut down to 41-42 seconds.\n\n(with patch)\n41.41user 0.51system 0:41.93elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+134411minor)pagefaults 0swaps\n\n(without patch)\n47.21user 0.64system 0:47.85elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+134935minor)pagefaults 0swaps\n\nOne funny thing about your patch is that it also reduces the number of\nminor faults; I would have expected that the additional memory wastage\n(even though most of the allocated object buffer memory would be freed\nimmediately as soon as the caller is done with it) would result in larger\nnumber of faults, not smaller, which is puzzling.\n"},{"id":"89931","messageId":"alpine.LFD.1.10.0809061812090.3117@nehalem.linux-foundation.org","threadId":"14926","inReplyTo":"7vk5dorclv.fsf@gitster.siamese.dyndns.org","subject":"Re: pack operation is thrashing my server","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-09-07T01:46:29Z","receivedAt":"2008-09-07T01:46:29Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 6 Sep 2008, Junio C Hamano wrote:\n> \n> This is reproducible \"rev-list --objects --all\" in my copy of the kernel\n> repo takes around 47-48 seconds user time, and with the (idiotic) patch it\n> is cut down to 41-42 seconds.\n\nSo I had forgotten about that patch since nobody reacted to it.\n\nI think the patch is wrong, please don't apply it, even though it does \nhelp performance.\n\nThe reason? \n\nRight now we depend on \"avail_out\" also making zlib understand to stop \nlooking at the input stream. Sad, but true - we don't know or care about \nthe compressed size of the object, only the uncompressed size. So in \nunpack_compressed_entry(), we simply set the output length, and expect \nzlib to stop when it's sufficient.\n\nWhich it does - but the patch kind of violates that whole design.\n\nNow, it so happens that things seem to work, probably because the zlib \nformat does have enough synchronization in it to not try to continue past \nthe end _anyway_, but I think this makes the patch be of debatable value.\n\nI'm starting to hate zlib. I actually spent almost a week trying to clean \nup the zlib source code and make it something that gcc can compile into \nclean code, but the fact is, zlib isn't amenable to that. The whole \"shift \n bits in from the buffer\" approach means that there is no way to make \nzlib generate good code unless you are an insanely competent assembly \nhacker or have tons of registers to keep all the temporaries live in.\n\nNow, I still do think that all my reasons for choosing zlib were pretty \nsolid (it's a well-tested piece of code and it is _everywhere_ and easy to \nuse), but boy do I wish there had been alternatives. \n\n\t\t\tLinus\n"},{"id":"89935","messageId":"7vbpz0r8gb.fsf@gitster.siamese.dyndns.org","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0809061812090.3117@nehalem.linux-foundation.org","subject":"Re: pack operation is thrashing my server","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-09-07T02:33:24Z","receivedAt":"2008-09-07T02:33:24Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> The reason? \n>\n> Right now we depend on \"avail_out\" also making zlib understand to stop \n> looking at the input stream. Sad, but true - we don't know or care about \n> the compressed size of the object, only the uncompressed size. So in \n> unpack_compressed_entry(), we simply set the output length, and expect \n> zlib to stop when it's sufficient.\n>\n> Which it does - but the patch kind of violates that whole design.\n>\n> Now, it so happens that things seem to work, probably because the zlib \n> format does have enough synchronization in it to not try to continue past \n> the end _anyway_, but I think this makes the patch be of debatable value.\n\nI thought the fact we do check the status with Z_STREAM_END means that we\ndo already expect and rely on zlib to know where the end of input stream\nis, and stop there (otherwise we say something fishy is going on and we\nerror out), and it was part of the design, not just \"so happens\" and \"has\nenough synch ... _anyway_\".\n\nIf input zlib stream were corrupted and it detected the end of stream too\nearly, then check of \"stream.total_out != size\" would fail even though we\nwould see \"st == Z_STREAM_END\". If input stream were corrupted and it\nwent past the end marker, we will read past the end and into some garbage\nthat is the in-pack header of the next object representation, but zlib\nshouldn't go berserk even in that case, and would stop after filling the\nslop you allocated in the buffer --- we would detect the situation from\nstream.total_out != size and most likely st != Z_STREAM_END in such a\ncase.\n\nWhile I think 5% is large enough, I'll leave this on the backburner for\nnow. I think it is more grave issue that we inflate the same object many\ntimes as you noticed during the discussion.\n"},{"id":"89936","messageId":"9e4733910809061950g6d9d2cf1g708f8faf0c06108@mail.gmail.com","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0809061812090.3117@nehalem.linux-foundation.org","subject":"Re: pack operation is thrashing my server","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2008-09-07T02:50:39Z","receivedAt":"2008-09-07T02:50:39Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/6/08, Linus Torvalds wrote:\n> I'm starting to hate zlib. I actually spent almost a week trying to clean\n> up the zlib source code and make it something that gcc can compile into\n> clean code, but the fact is, zlib isn't amenable to that. The whole \"shift\n> bits in from the buffer\" approach means that there is no way to make\n> zlib generate good code unless you are an insanely competent assembly\n> hacker or have tons of registers to keep all the temporaries live in.\n>\n> Now, I still do think that all my reasons for choosing zlib were pretty\n> solid (it's a well-tested piece of code and it is _everywhere_ and easy to\n> use), but boy do I wish there had been alternatives.\n\nSome alternative algorithms are here...\nhttp://cs.fit.edu/~mmahoney/compression\nIt is possible to beat zlib by 2x at the cost of CPU time and memory.\n\nOf course switching to these algorithms would involve a lot of testing\nand benchmarking. I'm also not sure how PAQ would fare on lots of\nsmall git objects instead of large files.\n\nTurning a 500MB packfile into a 250MB has lots of advantages in IO\nreduction so it is worth some CPU/memory to create it.\n\nYou can even win 50'000€ for a better algorithm.\nhttp://prize.hutter1.net/\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"89938","messageId":"alpine.LFD.1.10.0809061957320.3117@nehalem.linux-foundation.org","threadId":"14926","inReplyTo":"9e4733910809061950g6d9d2cf1g708f8faf0c06108@mail.gmail.com","subject":"Re: pack operation is thrashing my server","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-09-07T03:07:28Z","receivedAt":"2008-09-07T03:07:28Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 6 Sep 2008, Jon Smirl wrote:\n> \n> Some alternative algorithms are here...\n> http://cs.fit.edu/~mmahoney/compression\n> It is possible to beat zlib by 2x at the cost of CPU time and memory.\n\nJon, you're missing the point.\n\nThe problem with zlib isn't that it doesn't compress well. It's that it's \ntoo _SLOW_.\n\n> Turning a 500MB packfile into a 250MB has lots of advantages in IO\n> reduction so it is worth some CPU/memory to create it.\n\n..and secondly, there's no way you'll find a compressor that comes even \nclose to being twice as good. 10% better yes - but then generally much \nMUCH slower.\n\nTake a look at that web page you quote, and then sort things by \ndecompression speed. THAT is the issue. \n\nAnd no, LZO isn't even on that list. I haven't tested it, but looking at \nthe code, I do think LZO can be fast exactly because it seems to be \nbyte-based rather than bit-based, so I'd not be surprised if the claims \nfor its uncompression speed are true.\n\nThe constant bit-shifting/masking/extraction kills zlib performance (and \nplease realize that zlib is at the TOP of the list when looking at the \nthing you pointed to - that silly site seems to not care about compressor \nspeed at all, _only_ about size). So \"kills\" is a relative measure, but \nreally - we're looking for _faster_ algorithms, not slower ones!\n\n\t\t\tLinus\n"},{"id":"89939","messageId":"9e4733910809062043y661d2d54rcb034d4c70296727@mail.gmail.com","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0809061957320.3117@nehalem.linux-foundation.org","subject":"Re: pack operation is thrashing my server","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2008-09-07T03:43:35Z","receivedAt":"2008-09-07T03:43:35Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/6/08, Linus Torvalds wrote:\n>\n>\n> On Sat, 6 Sep 2008, Jon Smirl wrote:\n> >\n> > Some alternative algorithms are here...\n> > http://cs.fit.edu/~mmahoney/compression\n> > It is possible to beat zlib by 2x at the cost of CPU time and memory.\n>\n>\n> Jon, you're missing the point.\n>\n> The problem with zlib isn't that it doesn't compress well. It's that it's\n> too _SLOW_.\n\nWhen I was playing with those giant Mozilla packs speed of zlib wasn't\na big problem. Number one problem was the repack process exceeding 3GB\nwhich forced me to get 64b hardware and 8GB of memory. If you start\nswapping in a repack, kill it, it will probably take a month to\nfinish.\n\nI'm forgetting the numbers now but on a quad core machine (with git\nchanges to use all cores) and 8GB I believe I was able to repack the\nMozilla repo in under an hour. At that point I believe I was being\nlimited by disk IO.\n\nSize and speed are not unrelated. Buy reducing the pack size in half\nyou reduce the IO and memory demands (cache misses) a lot. For example\nif we went to no compression we'd be killed by memory and IO\nconsumption. It's not obvious to me what's the best trade off for git\nwithout trying several compression algorithms and comparing. They were\nfeeding 100MB into PAQ on that site, I don't know what PAQ would do\nwith a bunch of 2K objects.\n\nMost delta chains in the Mozilla data were easy to process. There was\na single 2000 delta chain that consumed 15% of the total CPU time to\nprocess. Something causes performance to fall apart on really long\nchains.\n\n> > Turning a 500MB packfile into a 250MB has lots of advantages in IO\n> > reduction so it is worth some CPU/memory to create it.\n>\n>\n> ..and secondly, there's no way you'll find a compressor that comes even\n> close to being twice as good. 10% better yes - but then generally much\n> MUCH slower.\n>\n> Take a look at that web page you quote, and then sort things by\n> decompression speed. THAT is the issue.\n>\n> And no, LZO isn't even on that list. I haven't tested it, but looking at\n> the code, I do think LZO can be fast exactly because it seems to be\n> byte-based rather than bit-based, so I'd not be surprised if the claims\n> for its uncompression speed are true.\n>\n> The constant bit-shifting/masking/extraction kills zlib performance (and\n> please realize that zlib is at the TOP of the list when looking at the\n> thing you pointed to - that silly site seems to not care about compressor\n> speed at all, _only_ about size). So \"kills\" is a relative measure, but\n> really - we're looking for _faster_ algorithms, not slower ones!\n>\n>\n> Linus\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"89942","messageId":"alpine.LFD.1.10.0809062148110.3117@nehalem.linux-foundation.org","threadId":"14926","inReplyTo":"9e4733910809062043y661d2d54rcb034d4c70296727@mail.gmail.com","subject":"Re: pack operation is thrashing my server","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-09-07T04:50:34Z","receivedAt":"2008-09-07T04:50:34Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 6 Sep 2008, Jon Smirl wrote:\n> \n> When I was playing with those giant Mozilla packs speed of zlib wasn't\n> a big problem. Number one problem was the repack process exceeding 3GB\n> which forced me to get 64b hardware and 8GB of memory. If you start\n> swapping in a repack, kill it, it will probably take a month to\n> finish.\n\n.. and you'd make things much much WORSE?\n\n> Size and speed are not unrelated.\n\nJon, go away.\n\nGo and _look_ at those damn numbers you tried to point me to.\n\nThose \"better\" compression models you pointed at are not only hundreds of \ntimes slower than zlib, they take hundreds of times more memory too!\n\nYes, size and speed are definitely not unrelated. And in this situation, \nwhen it comes to compression algorithms, the relationship is _very_ clear:\n\n - better compression takes more memory and is slower\n\nReally. You're trying to argue for something, but you don't seem to \nrealize that you argue _against_ the thing you think you are arguing for.\n\n\t\tLinus\n"},{"id":"89955","messageId":"20080907074544.GA23488@glandium.org","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0809061812090.3117@nehalem.linux-foundation.org","subject":"Re: pack operation is thrashing my server","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2008-09-07T07:45:44Z","receivedAt":"2008-09-07T07:45:44Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Sat, Sep 06, 2008 at 06:46:29PM -0700, Linus Torvalds wrote:\n> \n> \n> On Sat, 6 Sep 2008, Junio C Hamano wrote:\n> > \n> > This is reproducible \"rev-list --objects --all\" in my copy of the kernel\n> > repo takes around 47-48 seconds user time, and with the (idiotic) patch it\n> > is cut down to 41-42 seconds.\n> \n> So I had forgotten about that patch since nobody reacted to it.\n> \n> I think the patch is wrong, please don't apply it, even though it does \n> help performance.\n> \n> The reason? \n> \n> Right now we depend on \"avail_out\" also making zlib understand to stop \n> looking at the input stream. Sad, but true - we don't know or care about \n> the compressed size of the object, only the uncompressed size. So in \n> unpack_compressed_entry(), we simply set the output length, and expect \n> zlib to stop when it's sufficient.\n> \n> Which it does - but the patch kind of violates that whole design.\n> \n> Now, it so happens that things seem to work, probably because the zlib \n> format does have enough synchronization in it to not try to continue past \n> the end _anyway_, but I think this makes the patch be of debatable value.\n> \n> I'm starting to hate zlib. I actually spent almost a week trying to clean \n> up the zlib source code and make it something that gcc can compile into \n> clean code, but the fact is, zlib isn't amenable to that. The whole \"shift \n> bits in from the buffer\" approach means that there is no way to make \n> zlib generate good code unless you are an insanely competent assembly \n> hacker or have tons of registers to keep all the temporaries live in.\n> \n> Now, I still do think that all my reasons for choosing zlib were pretty \n> solid (it's a well-tested piece of code and it is _everywhere_ and easy to \n> use), but boy do I wish there had been alternatives. \n\nI know at least 7-zip has its own gzip compression/decompression code\n(though it's C++). Maybe some other tools have theirs too.\n\nAnyways, if it can make a speed difference, it might be worth having a\nminimalist custom gzip compression/decompression \"library\" embedded\nwithing git.\n\nMike\n"},{"id":"89956","messageId":"48C38E64.5010204@op5.se","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0809061957320.3117@nehalem.linux-foundation.org","subject":"Re: pack operation is thrashing my server","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2008-09-07T08:18:44Z","receivedAt":"2008-09-07T08:18:44Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Linus Torvalds wrote:\n> \n> Take a look at that web page you quote, and then sort things by \n> decompression speed. THAT is the issue. \n> \n> And no, LZO isn't even on that list. I haven't tested it, but looking at \n> the code, I do think LZO can be fast exactly because it seems to be \n> byte-based rather than bit-based, so I'd not be surprised if the claims \n> for its uncompression speed are true.\n> \n\nSome lzo vs zlib benchmark figures (for git) are available here:\nhttp://www.gelato.unsw.edu.au/archives/git/0504/1700.html\n\nLZO also ships their \"minilzo.[ch]\" fileset for easy inclusion in other\nprojects. I've used it a couple of times with decent results.\n\nAs for testing, both have been thoroughly vetted by NASA. LZO is used for\ncommunication with satellites and that spacestation thing they had some\ntime ago, while zlib is being used for sending data back from Hubble and\nother large data gatherers.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"89971","messageId":"9e4733910809070658k66e0481fx758e9a365229cf18@mail.gmail.com","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0809062148110.3117@nehalem.linux-foundation.org","subject":"Re: pack operation is thrashing my server","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2008-09-07T13:58:11Z","receivedAt":"2008-09-07T13:58:11Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/7/08, Linus Torvalds wrote:\n>\n>\n> On Sat, 6 Sep 2008, Jon Smirl wrote:\n> >\n>\n> > When I was playing with those giant Mozilla packs speed of zlib wasn't\n> > a big problem. Number one problem was the repack process exceeding 3GB\n> > which forced me to get 64b hardware and 8GB of memory. If you start\n> > swapping in a repack, kill it, it will probably take a month to\n> > finish.\n>\n>\n> .. and you'd make things much much WORSE?\n\nMy observations on the Mozilla packs indicated that the problems were\nelsewhere in git, not in the decompression algorithms. Why does a\nsingle 2000 delta chain take 15% of the entire pack time? Something\nisn't right when long chains are processed which triggers far more\ndecompressions than needed.\n\n\n>\n>\n> > Size and speed are not unrelated.\n>\n>\n> Jon, go away.\n>\n> Go and _look_ at those damn numbers you tried to point me to.\n>\n> Those \"better\" compression models you pointed at are not only hundreds of\n> times slower than zlib, they take hundreds of times more memory too!\n>\n> Yes, size and speed are definitely not unrelated. And in this situation,\n> when it comes to compression algorithms, the relationship is _very_ clear:\n>\n> - better compression takes more memory and is slower\n>\n> Really. You're trying to argue for something, but you don't seem to\n> realize that you argue _against_ the thing you think you are arguing for.\n>\n>\n> Linus\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"89981","messageId":"alpine.LFD.1.10.0809071304130.23787@xanadu.home","threadId":"14926","inReplyTo":"9e4733910809070658k66e0481fx758e9a365229cf18@mail.gmail.com","subject":"Re: pack operation is thrashing my server","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-09-07T17:08:02Z","receivedAt":"2008-09-07T17:08:02Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 7 Sep 2008, Jon Smirl wrote:\n\n> On 9/7/08, Linus Torvalds wrote:\n> >\n> >\n> > On Sat, 6 Sep 2008, Jon Smirl wrote:\n> > >\n> >\n> > > When I was playing with those giant Mozilla packs speed of zlib wasn't\n> > > a big problem. Number one problem was the repack process exceeding 3GB\n> > > which forced me to get 64b hardware and 8GB of memory. If you start\n> > > swapping in a repack, kill it, it will probably take a month to\n> > > finish.\n> >\n> >\n> > .. and you'd make things much much WORSE?\n> \n> My observations on the Mozilla packs indicated that the problems were\n> elsewhere in git, not in the decompression algorithms. Why does a\n> single 2000 delta chain take 15% of the entire pack time? Something\n> isn't right when long chains are processed which triggers far more\n> decompressions than needed.\n\nPlease have a look at commit eac12e2d4d7f. This fix improved things for \nmy gcc repack tests.\n\n\nNicolas\n"},{"id":"89983","messageId":"alpine.LFD.1.10.0809071310030.23787@xanadu.home","threadId":"14926","inReplyTo":"7vbpz0r8gb.fsf@gitster.siamese.dyndns.org","subject":"Re: pack operation is thrashing my server","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-09-07T17:11:36Z","receivedAt":"2008-09-07T17:11:36Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 6 Sep 2008, Junio C Hamano wrote:\n\n> Linus Torvalds writes:\n> \n> > The reason? \n> >\n> > Right now we depend on \"avail_out\" also making zlib understand to stop \n> > looking at the input stream. Sad, but true - we don't know or care about \n> > the compressed size of the object, only the uncompressed size. So in \n> > unpack_compressed_entry(), we simply set the output length, and expect \n> > zlib to stop when it's sufficient.\n> >\n> > Which it does - but the patch kind of violates that whole design.\n> >\n> > Now, it so happens that things seem to work, probably because the zlib \n> > format does have enough synchronization in it to not try to continue past \n> > the end _anyway_, but I think this makes the patch be of debatable value.\n> \n> I thought the fact we do check the status with Z_STREAM_END means that we\n> do already expect and rely on zlib to know where the end of input stream\n> is, and stop there (otherwise we say something fishy is going on and we\n> error out), and it was part of the design, not just \"so happens\" and \"has\n> enough synch ... _anyway_\".\n> \n> If input zlib stream were corrupted and it detected the end of stream too\n> early, then check of \"stream.total_out != size\" would fail even though we\n> would see \"st == Z_STREAM_END\". If input stream were corrupted and it\n> went past the end marker, we will read past the end and into some garbage\n> that is the in-pack header of the next object representation, but zlib\n> shouldn't go berserk even in that case, and would stop after filling the\n> slop you allocated in the buffer --- we would detect the situation from\n> stream.total_out != size and most likely st != Z_STREAM_END in such a\n> case.\n\nUnless I'm missing something, I think your analysis is right and \neverything should be safe.\n\n\nNicolas\n"},{"id":"89988","messageId":"7vljy3n99c.fsf@gitster.siamese.dyndns.org","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0809071310030.23787@xanadu.home","subject":"Re: pack operation is thrashing my server","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-09-07T17:41:51Z","receivedAt":"2008-09-07T17:41:51Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> On Sat, 6 Sep 2008, Junio C Hamano wrote:\n>\n>> Linus Torvalds writes:\n>> ...\n>> > Which it does - but the patch kind of violates that whole design.\n>> >\n>> > Now, it so happens that things seem to work, probably because the zlib \n>> > format does have enough synchronization in it to not try to continue past \n>> > the end _anyway_, but I think this makes the patch be of debatable value.\n>> \n>> I thought the fact we do check the status with Z_STREAM_END means that we\n>> do already expect and rely on zlib to know where the end of input stream\n>> is, and stop there (otherwise we say something fishy is going on and we\n>> error out), and it was part of the design, not just \"so happens\" and \"has\n>> enough synch ... _anyway_\".\n>> \n>> If input zlib stream were corrupted and it detected the end of stream too\n>> early, then check of \"stream.total_out != size\" would fail even though we\n>> would see \"st == Z_STREAM_END\". If input stream were corrupted and it\n>> went past the end marker, we will read past the end and into some garbage\n>> that is the in-pack header of the next object representation, but zlib\n>> shouldn't go berserk even in that case, and would stop after filling the\n>> slop you allocated in the buffer --- we would detect the situation from\n>> stream.total_out != size and most likely st != Z_STREAM_END in such a\n>> case.\n>\n> Unless I'm missing something, I think your analysis is right and \n> everything should be safe.\n\nI obviously agree with you but what I forgot to mention in the above is\nthat we also make sure stream.avail_in is set not to overrun the end of\nthe current pack window (or the entire loose object data that is\nmmapped).\n"},{"id":"90005","messageId":"9e4733910809071333t57d03257m34fd6a752e40177e@mail.gmail.com","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0809071304130.23787@xanadu.home","subject":"Re: pack operation is thrashing my server","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2008-09-07T20:33:28Z","receivedAt":"2008-09-07T20:33:28Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/7/08, Nicolas Pitre wrote:\n> On Sun, 7 Sep 2008, Jon Smirl wrote:\n>\n> > On 9/7/08, Linus Torvalds wrote:\n> > >\n> > >\n> > > On Sat, 6 Sep 2008, Jon Smirl wrote:\n> > > >\n> > >\n> > > > When I was playing with those giant Mozilla packs speed of zlib wasn't\n> > > > a big problem. Number one problem was the repack process exceeding 3GB\n> > > > which forced me to get 64b hardware and 8GB of memory. If you start\n> > > > swapping in a repack, kill it, it will probably take a month to\n> > > > finish.\n> > >\n> > >\n> > > .. and you'd make things much much WORSE?\n> >\n> > My observations on the Mozilla packs indicated that the problems were\n> > elsewhere in git, not in the decompression algorithms. Why does a\n> > single 2000 delta chain take 15% of the entire pack time? Something\n> > isn't right when long chains are processed which triggers far more\n> > decompressions than needed.\n>\n>\n> Please have a look at commit eac12e2d4d7f. This fix improved things for\n> my gcc repack tests.\n\nDo you have any test numbers for something like a 2000 delta chain\nbefore and after?\n\nYou can get to Mozilla CVS with rsync.\nhttps://wiki.mozilla.org/How_to_Create_a_CVS_Mirror\nI think it was the master Mozilla makefile with the 2000 deltas.\nThe whole repo is 15GB so you probably just want the Makefile,v\n\nThere's no point in working with Mozilla except for testing purposes\nsince they went with Mercurial and abandoned their history.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"90082","messageId":"alpine.LFD.1.10.0809081008330.23787@xanadu.home","threadId":"14926","inReplyTo":"9e4733910809071333t57d03257m34fd6a752e40177e@mail.gmail.com","subject":"Re: pack operation is thrashing my server","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-09-08T14:17:40Z","receivedAt":"2008-09-08T14:17:40Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 7 Sep 2008, Jon Smirl wrote:\n\n> On 9/7/08, Nicolas Pitre wrote:\n> > Please have a look at commit eac12e2d4d7f. This fix improved things for\n> > my gcc repack tests.\n> \n> Do you have any test numbers for something like a 2000 delta chain\n> before and after?\n\nWhat kind of number do you want?\n\nBefore that change I wasn't able to repack an already tightly packed \n(about 340MB) gcc repository on my machine while the same but sparsely \npacked (3GB or so) repository could be repacked just fine.\n\n> You can get to Mozilla CVS with rsync.\n> https://wiki.mozilla.org/How_to_Create_a_CVS_Mirror\n> I think it was the master Mozilla makefile with the 2000 deltas.\n> The whole repo is 15GB so you probably just want the Makefile,v\n\nI have a test Mozilla repo dating back to the time you were playing with \nit too (I think). Its directory date is 2007-04-12. It was quite \ntightly packed already, but I just ran a \"git repack -a -d -f \n--window=100 --depth=2000\" on it and now have a 380MB pack file for it.\n\n\nNicolas\n"},{"id":"90090","messageId":"9e4733910809080812g4a7e5916l82bd3bf496f16324@mail.gmail.com","threadId":"14926","inReplyTo":"alpine.LFD.1.10.0809081008330.23787@xanadu.home","subject":"Re: pack operation is thrashing my server","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2008-09-08T15:12:19Z","receivedAt":"2008-09-08T15:12:19Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/8/08, Nicolas Pitre wrote:\n> On Sun, 7 Sep 2008, Jon Smirl wrote:\n>\n> > On 9/7/08, Nicolas Pitre wrote:\n>\n> > > Please have a look at commit eac12e2d4d7f. This fix improved things for\n> > > my gcc repack tests.\n> >\n> > Do you have any test numbers for something like a 2000 delta chain\n> > before and after?\n>\n>\n> What kind of number do you want?\n\nSee if repacking a 2000 chain delta still takes 30 minutes. It can be\nany 2000 chain delta.\n\n> Before that change I wasn't able to repack an already tightly packed\n> (about 340MB) gcc repository on my machine while the same but sparsely\n> packed (3GB or so) repository could be repacked just fine.\n>\n>\n> > You can get to Mozilla CVS with rsync.\n> > https://wiki.mozilla.org/How_to_Create_a_CVS_Mirror\n> > I think it was the master Mozilla makefile with the 2000 deltas.\n> > The whole repo is 15GB so you probably just want the Makefile,v\n>\n>\n> I have a test Mozilla repo dating back to the time you were playing with\n> it too (I think). Its directory date is 2007-04-12. It was quite\n> tightly packed already, but I just ran a \"git repack -a -d -f\n> --window=100 --depth=2000\" on it and now have a 380MB pack file for it.\n>\n>\n>\n> Nicolas\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"90100","messageId":"9e4733910809080901g5f9c9c11ia7c291125bf52776@mail.gmail.com","threadId":"14926","inReplyTo":"9e4733910809080812g4a7e5916l82bd3bf496f16324@mail.gmail.com","subject":"Re: pack operation is thrashing my server","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2008-09-08T16:01:58Z","receivedAt":"2008-09-08T16:01:58Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/8/08, Jon Smirl wrote:\n> On 9/8/08, Nicolas Pitre wrote:\n> > On Sun, 7 Sep 2008, Jon Smirl wrote:\n> >\n> > > On 9/7/08, Nicolas Pitre wrote:\n> >\n> > > > Please have a look at commit eac12e2d4d7f. This fix improved things for\n> > > > my gcc repack tests.\n> > >\n> > > Do you have any test numbers for something like a 2000 delta chain\n> > > before and after?\n> >\n> >\n> > What kind of number do you want?\n>\n>\n> See if repacking a 2000 chain delta still takes 30 minutes. It can be\n> any 2000 chain delta.\n\nTime for repacking a 2000 chain delta would be a good thing to monitor\nas part of the testing process. It amplifies any small performance\nproblems and makes them obvious.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"}]}