{"thread":{"id":"9493","subject":"performance on repack","startedAt":"2007-08-11T21:12:24Z","lastAt":"2007-09-01T21:54:31Z","messageCount":30,"participants":["Jon Smirl","David Kastrup","Linus Torvalds","Martin Koegler","Shawn O. Pearce","Nicolas Pitre"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"50505","messageId":"9e4733910708111412t48c1beaahfbaa2c68a02f64f1@mail.gmail.com","threadId":"9493","inReplyTo":null,"subject":"performance on repack","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-08-11T21:12:24Z","receivedAt":"2007-08-11T21:12:24Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"If anyone is bored and looking for something to do, making the delta\ncode in git repack multithreaded would help. Yesterday I did a big\nrepack that took 20 minutes and it only used one of my four cores. It\nwas compute bound the entire time.\n\nDell had 2GB quad core boxes on sale for $620 last week. I just had to\nbuy one. I'm surprised, it's quieter than my old P4 box.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"50512","messageId":"85ps1tsozb.fsf@lola.goethe.zz","threadId":"9493","inReplyTo":"9e4733910708111412t48c1beaahfbaa2c68a02f64f1@mail.gmail.com","subject":"Re: performance on repack","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2007-08-11T22:09:12Z","receivedAt":"2007-08-11T22:09:12Z","isPatch":false,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"\"Jon Smirl\" writes:\n\n> If anyone is bored and looking for something to do, making the delta\n> code in git repack multithreaded would help.\n\nI severely doubt that. It is like the \"coding stuff in assembly\nlanguage will make it faster\" myth. The problem is that of manageable\ncomplexity. Making the stuff multithreaded or coded in assembly means\nthat it becomes inaccessible for a sound algorithmic redesign.\n\nAnd anything that takes this long on today's machines has lots of room\nfor algorithmic improvement, usually resulting in a speedup from one\nto several orders of magnitude.\n\n-- \nDavid Kastrup, Kriemhildstr. 15, 44793 Bochum\n"},{"id":"50515","messageId":"alpine.LFD.0.999.0708111529310.30176@woody.linux-foundation.org","threadId":"9493","inReplyTo":"85ps1tsozb.fsf@lola.goethe.zz","subject":"Re: performance on repack","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-11T22:34:31Z","receivedAt":"2007-08-11T22:34:31Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 12 Aug 2007, David Kastrup wrote:\n\n> \"Jon Smirl\" writes:\n> \n> > If anyone is bored and looking for something to do, making the delta\n> > code in git repack multithreaded would help.\n> \n> I severely doubt that. It is like the \"coding stuff in assembly\n> language will make it faster\" myth. The problem is that of manageable\n> complexity. Making the stuff multithreaded or coded in assembly means\n> that it becomes inaccessible for a sound algorithmic redesign.\n\nI have to admit that I'm not a huge fan of threading: the complexity and \nlocking often kills you, if memory bandwidth constraints do not, and the \nend result is often really really hard to debug.\n\nThat said, I suspect we could some some *simple* form of this by just \npartitioning the problem space up - we could have a MT repack that \ngenerates four *different* packs on four different CPU's: each thread \ntaking one quarter of the objects. At that point, you wouldn't even need \nthreads, you could do it with regular processes, since the problem set is \nfully partitioned ocne you've generated the list of objects!\n\nThen, after you've generated four different packs, doing a \"git gc\" \n(without any threading) will repack them into one big pack, and mostly \njust re-use the existing deltas.\n\nSo this would not be a generic thing, but it could be somethign that is \nuseful for the forced full-repack after importing a large repository with \nfast-import, for example.\n\nSo while I agree with David in general about the problem of threading, I \nthink that we can possibly simplify the special case of repacking into \nsomething less complicated than a \"real\" multi-threading problem.\n\n\t\tLinus\n"},{"id":"50518","messageId":"9e4733910708111621j6a9ba950i114be8b84d7fb1bb@mail.gmail.com","threadId":"9493","inReplyTo":"alpine.LFD.0.999.0708111529310.30176@woody.linux-foundation.org","subject":"Re: performance on repack","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-08-11T23:21:05Z","receivedAt":"2007-08-11T23:21:05Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/11/07, Linus Torvalds wrote:\n> On Sun, 12 Aug 2007, David Kastrup wrote:\n> > \"Jon Smirl\" writes:\n> >\n> > > If anyone is bored and looking for something to do, making the delta\n> > > code in git repack multithreaded would help.\n\nTo put this perspective, monotone takes 40hrs on the same box to\nrepack a repository of similar size.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"50545","messageId":"20070812103338.GA7763@auto.tuwien.ac.at","threadId":"9493","inReplyTo":"9e4733910708111412t48c1beaahfbaa2c68a02f64f1@mail.gmail.com","subject":"Re: performance on repack","fromName":"Martin Koegler","fromEmail":"mkoegler@auto.tuwien.ac.at","sentAt":"2007-08-12T10:33:38Z","receivedAt":"2007-08-12T10:33:38Z","isPatch":false,"sender":{"key":"mkoegler@auto.tuwien.ac.at","avatar":null},"body":"On Sat, Aug 11, 2007 at 05:12:24PM -0400, Jon Smirl wrote:\n> If anyone is bored and looking for something to do, making the delta\n> code in git repack multithreaded would help. Yesterday I did a big\n> repack that took 20 minutes and it only used one of my four cores. It\n> was compute bound the entire time.\n\nFirst, how much time is used by the write and how much by the deltify\nphase?\n\nIf the writing phase uses too much time and you have enough free\nmemory, you can try to raise the config variable pack.deltacachelimit\n(default 1000). It will save an additional delta operation for all\nobject, whose delta is smaller than pack.deltacachelimit by caching\nthe delta.\n\nHave you considered the impact on memory usage, if there are large\nblobs in the repository?\n\nWhile repacking, git keeps $window_size (default: 10) objects unpacked\nin memory. For all (except one), it additionally stores the delta\nindex, which has about the same size as the object.\n\nSo the worst case memory usage is \"sizeof(biggest object)*(2*$window_size - 1)\".\nIf you have blobs >=100 MB, you need some GB of memory.\n\nPartitioning the problem is not trivial:\n\n* To get not worse packing resultes, we must first sort all objects by\n type, path, size. Then we can split split the list (for each task\n one part), which we can deltify individually.\n\n The problems are:\n\n - We need more memory, as each tasks keeps its own window of\n $window_size objects (+ delta indexes) in memory.\n\n - The list must be split in parts, which require the same amount of\n time. This is difficult, as it depends on the size of the objects as\n well as how they are stored (delta chain length).\n\n* On the other hand, we could run all try_delta operations for one object\n parallel. This way, we would need not very much more memory, but\n require more synchronisation (and more complex code).\n\nmfg Martin Kögler\n"},{"id":"50555","messageId":"9e4733910708120649g5a5e0f48pa71bd983f2bc2945@mail.gmail.com","threadId":"9493","inReplyTo":"20070812103338.GA7763@auto.tuwien.ac.at","subject":"Re: performance on repack","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-08-12T13:49:32Z","receivedAt":"2007-08-12T13:49:32Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/12/07, Martin Koegler wrote:\n> On Sat, Aug 11, 2007 at 05:12:24PM -0400, Jon Smirl wrote:\n> > If anyone is bored and looking for something to do, making the delta\n> > code in git repack multithreaded would help. Yesterday I did a big\n> > repack that took 20 minutes and it only used one of my four cores. It\n> > was compute bound the entire time.\n>\n> First, how much time is used by the write and how much by the deltify\n> phase?\n\n95% in deltify\n\n>\n> If the writing phase uses too much time and you have enough free\n> memory, you can try to raise the config variable pack.deltacachelimit\n> (default 1000). It will save an additional delta operation for all\n> object, whose delta is smaller than pack.deltacachelimit by caching\n> the delta.\n\nI have 4GB RAM and fast RAID 10 disk, writing happens very quickly.\nPretty much everything is in RAM.\n\n> Have you considered the impact on memory usage, if there are large\n> blobs in the repository?\n\nThe process size maxed at 650MB. I'm in 64b mode so there is no\nvirtual memory limit.\n\nOn 32b there's windowing code for accessing the packfile since we can\nrun out of address space, does this code get turned off for 64b?\n\n>\n> While repacking, git keeps $window_size (default: 10) objects unpacked\n> in memory. For all (except one), it additionally stores the delta\n> index, which has about the same size as the object.\n>\n> So the worst case memory usage is \"sizeof(biggest object)*(2*$window_size - 1)\".\n> If you have blobs >=100 MB, you need some GB of memory.\n>\n> Partitioning the problem is not trivial:\n>\n> * To get not worse packing resultes, we must first sort all objects by\n> type, path, size. Then we can split split the list (for each task\n> one part), which we can deltify individually.\n>\n> The problems are:\n>\n> - We need more memory, as each tasks keeps its own window of\n> $window_size objects (+ delta indexes) in memory.\n>\n> - The list must be split in parts, which require the same amount of\n> time. This is difficult, as it depends on the size of the objects as\n> well as how they are stored (delta chain length).\n>\n> * On the other hand, we could run all try_delta operations for one object\n> parallel. This way, we would need not very much more memory, but\n> require more synchronization (and more complex code).\n\nThis solution was my first thought too. Use the main thread to get\neverything needed for the object into RAM, then multi-thread the\ncompute bound, in-memory delta search operation. Shared CPU caches\nmight make this very fast.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"50671","messageId":"20070814031236.GC27913@spearce.org","threadId":"9493","inReplyTo":"9e4733910708120649g5a5e0f48pa71bd983f2bc2945@mail.gmail.com","subject":"Re: performance on repack","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-08-14T03:12:36Z","receivedAt":"2007-08-14T03:12:36Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jon Smirl wrote:\n> On 8/12/07, Martin Koegler wrote:\n> > Have you considered the impact on memory usage, if there are large\n> > blobs in the repository?\n> \n> The process size maxed at 650MB. I'm in 64b mode so there is no\n> virtual memory limit.\n> \n> On 32b there's windowing code for accessing the packfile since we can\n> run out of address space, does this code get turned off for 64b?\n\nThe windowing code you are talking about defaults as follows:\n\n Parameter 32b 64b\n -----------------------------------------\n core.packedGitWindowSize 32M 1G\n core.packedGitLimit 256M 8G\n\nSo I doubt you are having issues with the windowing code on a 64b\nsystem, unless your repository is just *huge*. I did not think that\nanyone had a Git repository that exceeded 8G, though the window\nsize of 1G might be a tad too small if there are many packfiles\nand they are each larger than 1G.\n \n> > * On the other hand, we could run all try_delta operations for one object\n> > parallel. This way, we would need not very much more memory, but\n> > require more synchronization (and more complex code).\n> \n> This solution was my first thought too. Use the main thread to get\n> everything needed for the object into RAM, then multi-thread the\n> compute bound, in-memory delta search operation. Shared CPU caches\n> might make this very fast.\n\nI have been thinking about doing this, especially now that the\ndefault window size is much larger. I think the default is up as\nhigh as 50, which means we'd keep that shiny new UltraSPARC T2 busy.\nNot that I have one... so anyone from Sun is welcome to send me\none if they want. ;-)\n\nI'm not sure its that complex to run all try_delta calls of the\ncurrent window in parallel. Might be a simple enough change that\nits actually worth the extra complexity, especially with these\nmulti-core systems being so readily available. Repacking is the\nmost CPU intensive operation Git performs, and the one that is also\nthe easiest to make parallel.\n\nMaybe someone else will beat me to it, but if not I might give such\na patch a shot in a few weeks.\n\n-- \nShawn.\n"},{"id":"50674","messageId":"9e4733910708132110u6cdf5e6bg10417317c70b82f1@mail.gmail.com","threadId":"9493","inReplyTo":"20070814031236.GC27913@spearce.org","subject":"Re: performance on repack","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-08-14T04:10:31Z","receivedAt":"2007-08-14T04:10:31Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/13/07, Shawn O. Pearce wrote:\n> > On 32b there's windowing code for accessing the packfile since we can\n> > run out of address space, does this code get turned off for 64b?\n>\n> The windowing code you are talking about defaults as follows:\n>\n> Parameter 32b 64b\n> -----------------------------------------\n> core.packedGitWindowSize 32M 1G\n> core.packedGitLimit 256M 8G\n>\n> So I doubt you are having issues with the windowing code on a 64b\n> system, unless your repository is just *huge*. I did not think that\n> anyone had a Git repository that exceeded 8G, though the window\n> size of 1G might be a tad too small if there are many packfiles\n> and they are each larger than 1G.\n\nWhy use windows on 64b? Default core.packedGitWindowSize equal to\ncore.packedGitLimit\n\nI haven't measured it but I suspect the OS calls for moving the\nwindows are are quite slow on a relative basis since they have to\nrewrite a bunch of page tables. Why is the window so small on 32b? I\nthought we were up to about a 1GB packfile before running out of\naddress space with Mozilla. Shouldn't the window simply be set as\nlarge as possible on 32b, this size being a function of the available\naddress space, not the amount of physical memory?\n\n\n> > > * On the other hand, we could run all try_delta operations for one object\n> > > parallel. This way, we would need not very much more memory, but\n> > > require more synchronization (and more complex code).\n> >\n> > This solution was my first thought too. Use the main thread to get\n> > everything needed for the object into RAM, then multi-thread the\n> > compute bound, in-memory delta search operation. Shared CPU caches\n> > might make this very fast.\n>\n> I have been thinking about doing this, especially now that the\n> default window size is much larger. I think the default is up as\n> high as 50, which means we'd keep that shiny new UltraSPARC T2 busy.\n> Not that I have one... so anyone from Sun is welcome to send me\n> one if they want. ;-)\n>\n> I'm not sure its that complex to run all try_delta calls of the\n> current window in parallel. Might be a simple enough change that\n> its actually worth the extra complexity, especially with these\n> multi-core systems being so readily available. Repacking is the\n> most CPU intensive operation Git performs, and the one that is also\n> the easiest to make parallel.\n>\n> Maybe someone else will beat me to it, but if not I might give such\n> a patch a shot in a few weeks.\n\nI'll test it. But my assignment this week is to figure out how to\nprogram the BestComm DMA engine in a PowerPC chip. It's oh so much fun\ntrying to figure out how to program these \"engines\" that ASIC\ndesigners love to build and never fully document.\n\n>\n> --\n> Shawn.\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"50678","messageId":"20070814051321.GG27913@spearce.org","threadId":"9493","inReplyTo":"9e4733910708132110u6cdf5e6bg10417317c70b82f1@mail.gmail.com","subject":"Re: performance on repack","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-08-14T05:13:21Z","receivedAt":"2007-08-14T05:13:21Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jon Smirl wrote:\n> On 8/13/07, Shawn O. Pearce wrote:\n> > > On 32b there's windowing code for accessing the packfile since we can\n> > > run out of address space, does this code get turned off for 64b?\n> >\n> > The windowing code you are talking about defaults as follows:\n> >\n> > Parameter 32b 64b\n> > -----------------------------------------\n> > core.packedGitWindowSize 32M 1G\n> > core.packedGitLimit 256M 8G\n> >\n> > So I doubt you are having issues with the windowing code on a 64b\n> > system, unless your repository is just *huge*. I did not think that\n> > anyone had a Git repository that exceeded 8G, though the window\n> > size of 1G might be a tad too small if there are many packfiles\n> > and they are each larger than 1G.\n> \n> Why use windows on 64b? Default core.packedGitWindowSize equal to\n> core.packedGitLimit\n\nThat's *not* a good idea when you have more than one packfile.\n\nThe limit is for the sum of all packfiles. The settings above allow\nup to 8 packfiles to be opened and mapped at once on 64b systems,\nwith each packfile being up to 1G in size before we start shifting\nthe window(s) around. Doing as you suggest would reduce the number\nof open packfiles to 1, which would severely hurt performance\nwhen there is more than one packfile and Git keeps bouncing around\nbetween them to satisfy the current process' demands.\n\nOne could probably argue that the defaults for 64b are too small;\nperhaps they should be closer to 4G/24G seeing as how the 64b address\nspace is so huge that we're unlikely to run into issues with being\nable to use >24G of virtual address at once.\n\n> I haven't measured it but I suspect the OS calls for moving the\n> windows are are quite slow on a relative basis since they have to\n> rewrite a bunch of page tables.\n\nMaybe. Add a call to pack_report() at the end of the program you\nare interested in and run it. We keep track of how often we move\nwindows around; you may find that we don't move them often enough\n(or at all) to cause problems here. Or just run it under strace\nand watch mmap() activity, filtering out the uninteresting bits.\n\n> Why is the window so small on 32b? I\n> thought we were up to about a 1GB packfile before running out of\n> address space with Mozilla. Shouldn't the window simply be set as\n> large as possible on 32b, this size being a function of the available\n> address space, not the amount of physical memory?\n\nBecause programs need to malloc() stuff to work. And we need\nstack space. And we need to let the runtime linker mmap() in the\nshared libraries we are linked to. All in all we do get tight in\nsome 32b cases. The above defaults for 32b were chosen based on\nthe Linux kernel repository (its under 256M) and based on some\n(crude) performance testing on Linux (which seemed to say the\n32M packedGitWindowSize wasn't really hurting us). They were\nbasically set to give us maximum address space for working heap\nand yet not have a negative impact on one of our (at the time)\nlargest user groups.\n\nIn particular repack (aka git-pack-objects) is a real memory pig,\nespecially now with its various caches. The more address space we\ncan let it use in a 32b case the better off we probably are.\n\nIf someone can show that increasing these 32b defaults is the\nright thing to do even in very large repositories, *especially*\nwith something really brutal like `git-blame` on a very busy file or\n`git repack -f -a` then please submit a patch to boost them. ;-)\n\n-- \nShawn.\n"},{"id":"50682","messageId":"9e4733910708132257xfa7e1b5md77198c7ed80488d@mail.gmail.com","threadId":"9493","inReplyTo":"20070814051321.GG27913@spearce.org","subject":"Re: performance on repack","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-08-14T05:57:04Z","receivedAt":"2007-08-14T05:57:04Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/14/07, Shawn O. Pearce wrote:\n> Jon Smirl wrote:\n\n> One could probably argue that the defaults for 64b are too small;\n> perhaps they should be closer to 4G/24G seeing as how the 64b address\n> space is so huge that we're unlikely to run into issues with being\n> able to use >24G of virtual address at once.\n\nWe've got 24,000GB of address space to play with. Why not set them\n64G/512GB and forget about them for a decade?\n\n\n> > I haven't measured it but I suspect the OS calls for moving the\n> > windows are are quite slow on a relative basis since they have to\n> > rewrite a bunch of page tables.\n>\n> Maybe. Add a call to pack_report() at the end of the program you\n> are interested in and run it. We keep track of how often we move\n> windows around; you may find that we don't move them often enough\n> (or at all) to cause problems here. Or just run it under strace\n> and watch mmap() activity, filtering out the uninteresting bits.\n>\n> > Why is the window so small on 32b? I\n> > thought we were up to about a 1GB packfile before running out of\n> > address space with Mozilla. Shouldn't the window simply be set as\n> > large as possible on 32b, this size being a function of the available\n> > address space, not the amount of physical memory?\n>\n> Because programs need to malloc() stuff to work. And we need\n> stack space. And we need to let the runtime linker mmap() in the\n> shared libraries we are linked to. All in all we do get tight in\n> some 32b cases. The above defaults for 32b were chosen based on\n> the Linux kernel repository (its under 256M) and based on some\n> (crude) performance testing on Linux (which seemed to say the\n> 32M packedGitWindowSize wasn't really hurting us). They were\n> basically set to give us maximum address space for working heap\n> and yet not have a negative impact on one of our (at the time)\n> largest user groups.\n\nKernel is barely under 256M.\n\nDo we need two limits, could we just start with the big one and assign\nfirst packfile fully to it, then start dividing it up dynamically as\nmore pack files are opened?\n\ncore.packedGitLimit\ncore.packedGitWindowSize\n\nThe real question is, what's the access pattern into the windows? If\nit is random then the windows get moved around continuously. If is it\nmore or less sequential the windows will hardly get moved at all.\n\n\nOf course multi-threading the diff computation is going to do far more\nfor me than playing with the window size.\n\n\n> In particular repack (aka git-pack-objects) is a real memory pig,\n> especially now with its various caches. The more address space we\n> can let it use in a 32b case the better off we probably are.\n>\n> If someone can show that increasing these 32b defaults is the\n> right thing to do even in very large repositories, *especially*\n> with something really brutal like `git-blame` on a very busy file or\n> `git repack -f -a` then please submit a patch to boost them. ;-)\n>\n> --\n> Shawn.\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"50709","messageId":"alpine.LFD.0.999.0708141037020.5415@xanadu.home","threadId":"9493","inReplyTo":"20070814031236.GC27913@spearce.org","subject":"Re: performance on repack","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-08-14T14:52:35Z","receivedAt":"2007-08-14T14:52:35Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 13 Aug 2007, Shawn O. Pearce wrote:\n\n> Jon Smirl wrote:\n> > This solution was my first thought too. Use the main thread to get\n> > everything needed for the object into RAM, then multi-thread the\n> > compute bound, in-memory delta search operation. Shared CPU caches\n> > might make this very fast.\n> \n> I have been thinking about doing this, especially now that the\n> default window size is much larger. I think the default is up as\n> high as 50, which means we'd keep that shiny new UltraSPARC T2 busy.\n> Not that I have one... so anyone from Sun is welcome to send me\n> one if they want. ;-)\n\nNote that the default of 50 applies to the maximum delta depth, not the \ndelta search window. And the delta depth limit is costless on the \npacking side. I, too, wouldn't mind the UltraSPARC T2 though.\n\n\nNicolas\n"},{"id":"50730","messageId":"alpine.LFD.0.999.0708141634160.5415@xanadu.home","threadId":"9493","inReplyTo":"20070814031236.GC27913@spearce.org","subject":"Re: performance on repack","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-08-14T21:41:57Z","receivedAt":"2007-08-14T21:41:57Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 13 Aug 2007, Shawn O. Pearce wrote:\n\n> I'm not sure its that complex to run all try_delta calls of the\n> current window in parallel. Might be a simple enough change that\n> its actually worth the extra complexity, especially with these\n> multi-core systems being so readily available. Repacking is the\n> most CPU intensive operation Git performs, and the one that is also\n> the easiest to make parallel.\n> \n> Maybe someone else will beat me to it, but if not I might give such\n> a patch a shot in a few weeks.\n\nWell, here's my quick attempt at it. Unfortunately, performance isn't \nas good as I'd expected, especially with relatively small blobs like \nthose found in the linux kernel repo. It looks like the overhead of \nthread creation/joining might be significant compared to the actual \ndelta computation. I have a P4 with HT which might behave differently \nfrom a real SMP machine, or whatever, but the CPU usage never exceeded \n110% according to top (sometimes it even dropped below 95%). Actually, a \ngit-repack gets much slower due to 2m27s of system time compared to \n0m03s without threads. And this is with NPTL.\n\nWith a repo containing big blobs it is different though. CPU usage \nfirmly gets to 200% hence all cores are saturated with work.\n\nSo clearly the naive approach of spawning a thread for each combination \nin the delta window doesn't work.\n\nRemains the approach of calling find_deltas() n times with 1/n of the \ndelta_list, one call per thread, for the bulk of the delta search work. \nThis might even be much simpler than my current patch is. However this \napproach will require n times the memory for the delta window data. \nThread creation overhead will occur only once.\n\nAlso... read_sha1_file() is currently not thread safe, and threaded \ndelta searching would requires that its usage be serialized with a \nglobal mutex (not done in this patch which is a bug), or ideally be made \nthread aware.\n\n\nNicolas\n\n---\n\ndiff --git a/Makefile b/Makefile\nindex 4eb4637..c3c6e68 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -122,6 +122,9 @@ all::\n # If not set it defaults to the bare 'wish'. If it is set to the empty\n # string then NO_TCLTK will be forced (this is used by configure script).\n #\n+# Define THREADED_DELTA_SEARCH if you have pthreads and wish to exploit\n+# parallel delta searching when packing objects.\n+#\n \n GIT-VERSION-FILE: .FORCE-GIT-VERSION-FILE\n \t@$(SHELL_PATH) ./GIT-VERSION-GEN\n@@ -662,6 +665,11 @@ ifdef NO_HSTRERROR\n \tCOMPAT_OBJS += compat/hstrerror.o\n endif\n \n+ifdef THREADED_DELTA_SEARCH\n+\tBASIC_CFLAGS += -DTHREADED_DELTA_SEARCH\n+\tEXTLIBS += -lpthread\n+endif\n+\n ifeq ($(TCLTK_PATH),)\n NO_TCLTK=NoThanks\n endif\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 5e9d1fd..142b6dd 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -15,6 +15,10 @@\n #include \"list-objects.h\"\n #include \"progress.h\"\n \n+#ifdef THREADED_DELTA_SEARCH\n+#include \n+#endif\n+\n static const char pack_usage[] = \"\\\n git-pack-objects [{ -q | --progress | --all-progress }] \\n\\\n \t[--max-pack-size=N] [--local] [--incremental] \\n\\\n@@ -1273,6 +1277,12 @@ struct unpacked {\n \tvoid *data;\n \tstruct delta_index *index;\n \tunsigned depth;\n+#ifdef THREADED_DELTA_SEARCH\n+\tpthread_t thread;\n+\tpthread_mutex_t mutex;\n+\tstruct unpacked *trg;\n+\tunsigned trg_max_depth;\n+#endif\n };\n \n static int delta_cacheable(struct unpacked *trg, struct unpacked *src,\n@@ -1292,6 +1302,18 @@ static int delta_cacheable(struct unpacked *trg, struct unpacked *src,\n \treturn 0;\n }\n \n+#ifdef THREADED_DELTA_SEARCH\n+#define delta_lock_init(e)\tpthread_mutex_init(&(e)->mutex, NULL)\n+#define delta_lock_destroy(e)\tpthread_mutex_destroy(&(e)->mutex)\n+#define delta_lock(e)\t\tpthread_mutex_lock(&(e)->mutex)\n+#define delta_unlock(e)\t\tpthread_mutex_unlock(&(e)->mutex)\n+#else\n+#define delta_lock_init(e)\t0\n+#define delta_lock_destroy(e)\t0\n+#define delta_lock(e)\t\t0\n+#define delta_unlock(e)\t\t0\n+#endif\n+\n /*\n * We search for deltas _backwards_ in a list sorted by type and\n * by size, so that we see progressively smaller and smaller files.\n@@ -1335,6 +1357,7 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t\treturn 0;\n \n \t/* Now some size filtering heuristics. */\n+\tdelta_lock(trg);\n \ttrg_size = trg_entry->size;\n \tif (!trg_entry->delta) {\n \t\tmax_size = trg_size/2 - 20;\n@@ -1343,6 +1366,7 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t\tmax_size = trg_entry->delta_size;\n \t\tref_depth = trg->depth;\n \t}\n+\tdelta_unlock(trg);\n \tmax_size = max_size * (max_depth - src->depth) /\n \t\t\t\t\t\t(max_depth - ref_depth + 1);\n \tif (max_size == 0)\n@@ -1355,6 +1379,8 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t\treturn 0;\n \n \t/* Load data if not already done */\n+\n+\tdelta_lock(trg);\n \tif (!trg->data) {\n \t\ttrg->data = read_sha1_file(trg_entry->idx.sha1, &type, &sz);\n \t\tif (sz != trg_size)\n@@ -1362,6 +1388,9 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t\t\t sha1_to_hex(trg_entry->idx.sha1), sz, trg_size);\n \t\twindow_memory_usage += sz;\n \t}\n+\tdelta_unlock(trg);\n+\n+\tdelta_lock(src);\n \tif (!src->data) {\n \t\tsrc->data = read_sha1_file(src_entry->idx.sha1, &type, &sz);\n \t\tif (sz != src_size)\n@@ -1375,20 +1404,30 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t\t\tstatic int warned = 0;\n \t\t\tif (!warned++)\n \t\t\t\twarning(\"suboptimal pack - out of memory\");\n+\t\t\tdelta_unlock(src);\n \t\t\treturn 0;\n \t\t}\n \t\twindow_memory_usage += sizeof_delta_index(src->index);\n \t}\n+\tdelta_unlock(src);\n \n \tdelta_buf = create_delta(src->index, trg->data, trg_size, &delta_size, max_size);\n \tif (!delta_buf)\n \t\treturn 0;\n \n+\tdelta_lock(trg);\n \tif (trg_entry->delta_data) {\n-\t\t/* Prefer only shallower same-sized deltas. */\n-\t\tif (delta_size == trg_entry->delta_size &&\n-\t\t src->depth + 1 >= trg->depth) {\n+#ifdef THREADED_DELTA_SEARCH\n+\t\t/* A better match might have been found in the mean time */\n+\t\tmax_size = trg_entry->delta_size * (max_depth - src->depth) /\n+\t\t\t\t\t\t(max_depth - trg->depth + 1);\n+#endif\n+\t\t/* ... also prefer only shallower same-sized deltas. */\n+\t\tif (delta_size > max_size ||\n+\t\t (delta_size == trg_entry->delta_size &&\n+\t\t src->depth + 1 >= trg->depth)) {\n \t\t\tfree(delta_buf);\n+\t\t\tdelta_unlock(trg);\n \t\t\treturn 0;\n \t\t}\n \t\tdelta_cache_size -= trg_entry->delta_size;\n@@ -1404,9 +1443,21 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t\tdelta_cache_size += trg_entry->delta_size;\n \t} else\n \t\tfree(delta_buf);\n+\tdelta_unlock(trg);\n \treturn 1;\n }\n \n+#ifdef THREADED_DELTA_SEARCH\n+\n+static void *threaded_try_delta(void *arg)\n+{\n+\tstruct unpacked *src = arg;\n+\tint ret = try_delta(src->trg, src, src->trg_max_depth);\n+\treturn (void *)ret;\n+}\n+\n+#endif\n+\n static unsigned int check_delta_limit(struct object_entry *me, unsigned int n)\n {\n \tstruct object_entry *child = me->delta_child;\n@@ -1439,19 +1490,20 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n \tuint32_t i = nr_objects, idx = 0, count = 0, processed = 0;\n \tunsigned int array_size = window * sizeof(struct unpacked);\n \tstruct unpacked *array;\n-\tint max_depth;\n+\tint j, max_depth;\n \n \tif (!nr_objects)\n \t\treturn;\n \tarray = xmalloc(array_size);\n \tmemset(array, 0, array_size);\n+\tfor (j = 0; j < window; j++)\n+\t\tdelta_lock_init(&array[j]);\n \tif (progress)\n \t\tstart_progress(&progress_state, \"Deltifying %u objects...\", \"\", nr_result);\n \n \tdo {\n \t\tstruct object_entry *entry = list[--i];\n \t\tstruct unpacked *n = array + idx;\n-\t\tint j;\n \n \t\tif (!entry->preferred_base)\n \t\t\tprocessed++;\n@@ -1494,6 +1546,38 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n \t\t\t\tgoto next;\n \t\t}\n \n+#ifdef THREADED_DELTA_SEARCH\n+\t\t/* Create all threads ... */\n+\t\tj = window;\n+\t\twhile (--j > 0) {\n+\t\t\tint ret;\n+\t\t\tuint32_t other_idx = idx + j;\n+\t\t\tstruct unpacked *m;\n+\t\t\tif (other_idx >= window)\n+\t\t\t\tother_idx -= window;\n+\t\t\tm = array + other_idx;\n+\t\t\tif (!m->entry)\n+\t\t\t\tbreak;\n+\t\t\tm->trg = n;\n+\t\t\tm->trg_max_depth= max_depth;\n+\t\t\tret = pthread_create(&m->thread, NULL,\n+\t\t\t\t\t threaded_try_delta, m);\n+\t\t\tif (ret)\n+\t\t\t\tdie(\"unable to create thread: %s\", strerror(ret));\n+\t\t}\n+\t\t/* ... then join them. */\n+\t\twhile (++j < window) {\n+\t\t\tint ret;\n+\t\t\tuint32_t other_idx = idx + j;\n+\t\t\tstruct unpacked *m;\n+\t\t\tif (other_idx >= window)\n+\t\t\t\tother_idx -= window;\n+\t\t\tm = array + other_idx;\n+\t\t\tret = pthread_join(m->thread, NULL);\n+\t\t\tif (ret)\n+\t\t\t\tdie(\"unable to join thread: %s\", strerror(ret));\n+\t\t}\n+#else\n \t\tj = window;\n \t\twhile (--j > 0) {\n \t\t\tuint32_t other_idx = idx + j;\n@@ -1506,6 +1590,7 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n \t\t\tif (try_delta(n, m, max_depth) < 0)\n \t\t\t\tbreak;\n \t\t}\n+#endif\n \n \t\t/* if we made n a delta, and if n is already at max\n \t\t * depth, leaving it in the window is pointless. we\n@@ -1528,6 +1613,7 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n \tfor (i = 0; i < window; ++i) {\n \t\tfree_delta_index(array[i].index);\n \t\tfree(array[i].data);\n+\t\tdelta_lock_destroy(&array[i]);\n \t}\n \tfree(array);\n }\n"},{"id":"50741","messageId":"9e4733910708141820n9a09f08h6e104b7469f63375@mail.gmail.com","threadId":"9493","inReplyTo":"alpine.LFD.0.999.0708141634160.5415@xanadu.home","subject":"Re: performance on repack","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-08-15T01:20:46Z","receivedAt":"2007-08-15T01:20:46Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/14/07, Nicolas Pitre wrote:\n> On Mon, 13 Aug 2007, Shawn O. Pearce wrote:\n>\n> > I'm not sure its that complex to run all try_delta calls of the\n> > current window in parallel. Might be a simple enough change that\n> > its actually worth the extra complexity, especially with these\n> > multi-core systems being so readily available. Repacking is the\n> > most CPU intensive operation Git performs, and the one that is also\n> > the easiest to make parallel.\n> >\n> > Maybe someone else will beat me to it, but if not I might give such\n> > a patch a shot in a few weeks.\n>\n> Well, here's my quick attempt at it. Unfortunately, performance isn't\n> as good as I'd expected, especially with relatively small blobs like\n> those found in the linux kernel repo. It looks like the overhead of\n> thread creation/joining might be significant compared to the actual\n> delta computation. I have a P4 with HT which might behave differently\n> from a real SMP machine, or whatever, but the CPU usage never exceeded\n> 110% according to top (sometimes it even dropped below 95%). Actually, a\n> git-repack gets much slower due to 2m27s of system time compared to\n> 0m03s without threads. And this is with NPTL.\n\nThread creation/destruction overhead is way too high to make these\nthreads for every delta.\n\nAnother strategy is to create four worker threads once when the\nprocess is loaded. Then use synchronization primitives to feed the\nthreads lumps of work. The threads persist for the life of the\nprocess.\n\n\n>\n> With a repo containing big blobs it is different though. CPU usage\n> firmly gets to 200% hence all cores are saturated with work.\n>\n> So clearly the naive approach of spawning a thread for each combination\n> in the delta window doesn't work.\n>\n> Remains the approach of calling find_deltas() n times with 1/n of the\n> delta_list, one call per thread, for the bulk of the delta search work.\n> This might even be much simpler than my current patch is. However this\n> approach will require n times the memory for the delta window data.\n> Thread creation overhead will occur only once.\n>\n> Also... read_sha1_file() is currently not thread safe, and threaded\n> delta searching would requires that its usage be serialized with a\n> global mutex (not done in this patch which is a bug), or ideally be made\n> thread aware.\n>\n>\n> Nicolas\n>\n> ---\n>\n> diff --git a/Makefile b/Makefile\n> index 4eb4637..c3c6e68 100644\n> --- a/Makefile\n> +++ b/Makefile\n> @@ -122,6 +122,9 @@ all::\n> # If not set it defaults to the bare 'wish'. If it is set to the empty\n> # string then NO_TCLTK will be forced (this is used by configure script).\n> #\n> +# Define THREADED_DELTA_SEARCH if you have pthreads and wish to exploit\n> +# parallel delta searching when packing objects.\n> +#\n>\n> GIT-VERSION-FILE: .FORCE-GIT-VERSION-FILE\n> @$(SHELL_PATH) ./GIT-VERSION-GEN\n> @@ -662,6 +665,11 @@ ifdef NO_HSTRERROR\n> COMPAT_OBJS += compat/hstrerror.o\n> endif\n>\n> +ifdef THREADED_DELTA_SEARCH\n> + BASIC_CFLAGS += -DTHREADED_DELTA_SEARCH\n> + EXTLIBS += -lpthread\n> +endif\n> +\n> ifeq ($(TCLTK_PATH),)\n> NO_TCLTK=NoThanks\n> endif\n> diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\n> index 5e9d1fd..142b6dd 100644\n> --- a/builtin-pack-objects.c\n> +++ b/builtin-pack-objects.c\n> @@ -15,6 +15,10 @@\n> #include \"list-objects.h\"\n> #include \"progress.h\"\n>\n> +#ifdef THREADED_DELTA_SEARCH\n> +#include \n> +#endif\n> +\n> static const char pack_usage[] = \"\\\n> git-pack-objects [{ -q | --progress | --all-progress }] \\n\\\n> [--max-pack-size=N] [--local] [--incremental] \\n\\\n> @@ -1273,6 +1277,12 @@ struct unpacked {\n> void *data;\n> struct delta_index *index;\n> unsigned depth;\n> +#ifdef THREADED_DELTA_SEARCH\n> + pthread_t thread;\n> + pthread_mutex_t mutex;\n> + struct unpacked *trg;\n> + unsigned trg_max_depth;\n> +#endif\n> };\n>\n> static int delta_cacheable(struct unpacked *trg, struct unpacked *src,\n> @@ -1292,6 +1302,18 @@ static int delta_cacheable(struct unpacked *trg, struct unpacked *src,\n> return 0;\n> }\n>\n> +#ifdef THREADED_DELTA_SEARCH\n> +#define delta_lock_init(e) pthread_mutex_init(&(e)->mutex, NULL)\n> +#define delta_lock_destroy(e) pthread_mutex_destroy(&(e)->mutex)\n> +#define delta_lock(e) pthread_mutex_lock(&(e)->mutex)\n> +#define delta_unlock(e) pthread_mutex_unlock(&(e)->mutex)\n> +#else\n> +#define delta_lock_init(e) 0\n> +#define delta_lock_destroy(e) 0\n> +#define delta_lock(e) 0\n> +#define delta_unlock(e) 0\n> +#endif\n> +\n> /*\n> * We search for deltas _backwards_ in a list sorted by type and\n> * by size, so that we see progressively smaller and smaller files.\n> @@ -1335,6 +1357,7 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n> return 0;\n>\n> /* Now some size filtering heuristics. */\n> + delta_lock(trg);\n> trg_size = trg_entry->size;\n> if (!trg_entry->delta) {\n> max_size = trg_size/2 - 20;\n> @@ -1343,6 +1366,7 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n> max_size = trg_entry->delta_size;\n> ref_depth = trg->depth;\n> }\n> + delta_unlock(trg);\n> max_size = max_size * (max_depth - src->depth) /\n> (max_depth - ref_depth + 1);\n> if (max_size == 0)\n> @@ -1355,6 +1379,8 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n> return 0;\n>\n> /* Load data if not already done */\n> +\n> + delta_lock(trg);\n> if (!trg->data) {\n> trg->data = read_sha1_file(trg_entry->idx.sha1, &type, &sz);\n> if (sz != trg_size)\n> @@ -1362,6 +1388,9 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n> sha1_to_hex(trg_entry->idx.sha1), sz, trg_size);\n> window_memory_usage += sz;\n> }\n> + delta_unlock(trg);\n> +\n> + delta_lock(src);\n> if (!src->data) {\n> src->data = read_sha1_file(src_entry->idx.sha1, &type, &sz);\n> if (sz != src_size)\n> @@ -1375,20 +1404,30 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n> static int warned = 0;\n> if (!warned++)\n> warning(\"suboptimal pack - out of memory\");\n> + delta_unlock(src);\n> return 0;\n> }\n> window_memory_usage += sizeof_delta_index(src->index);\n> }\n> + delta_unlock(src);\n>\n> delta_buf = create_delta(src->index, trg->data, trg_size, &delta_size, max_size);\n> if (!delta_buf)\n> return 0;\n>\n> + delta_lock(trg);\n> if (trg_entry->delta_data) {\n> - /* Prefer only shallower same-sized deltas. */\n> - if (delta_size == trg_entry->delta_size &&\n> - src->depth + 1 >= trg->depth) {\n> +#ifdef THREADED_DELTA_SEARCH\n> + /* A better match might have been found in the mean time */\n> + max_size = trg_entry->delta_size * (max_depth - src->depth) /\n> + (max_depth - trg->depth + 1);\n> +#endif\n> + /* ... also prefer only shallower same-sized deltas. */\n> + if (delta_size > max_size ||\n> + (delta_size == trg_entry->delta_size &&\n> + src->depth + 1 >= trg->depth)) {\n> free(delta_buf);\n> + delta_unlock(trg);\n> return 0;\n> }\n> delta_cache_size -= trg_entry->delta_size;\n> @@ -1404,9 +1443,21 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n> delta_cache_size += trg_entry->delta_size;\n> } else\n> free(delta_buf);\n> + delta_unlock(trg);\n> return 1;\n> }\n>\n> +#ifdef THREADED_DELTA_SEARCH\n> +\n> +static void *threaded_try_delta(void *arg)\n> +{\n> + struct unpacked *src = arg;\n> + int ret = try_delta(src->trg, src, src->trg_max_depth);\n> + return (void *)ret;\n> +}\n> +\n> +#endif\n> +\n> static unsigned int check_delta_limit(struct object_entry *me, unsigned int n)\n> {\n> struct object_entry *child = me->delta_child;\n> @@ -1439,19 +1490,20 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n> uint32_t i = nr_objects, idx = 0, count = 0, processed = 0;\n> unsigned int array_size = window * sizeof(struct unpacked);\n> struct unpacked *array;\n> - int max_depth;\n> + int j, max_depth;\n>\n> if (!nr_objects)\n> return;\n> array = xmalloc(array_size);\n> memset(array, 0, array_size);\n> + for (j = 0; j < window; j++)\n> + delta_lock_init(&array[j]);\n> if (progress)\n> start_progress(&progress_state, \"Deltifying %u objects...\", \"\", nr_result);\n>\n> do {\n> struct object_entry *entry = list[--i];\n> struct unpacked *n = array + idx;\n> - int j;\n>\n> if (!entry->preferred_base)\n> processed++;\n> @@ -1494,6 +1546,38 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n> goto next;\n> }\n>\n> +#ifdef THREADED_DELTA_SEARCH\n> + /* Create all threads ... */\n> + j = window;\n> + while (--j > 0) {\n> + int ret;\n> + uint32_t other_idx = idx + j;\n> + struct unpacked *m;\n> + if (other_idx >= window)\n> + other_idx -= window;\n> + m = array + other_idx;\n> + if (!m->entry)\n> + break;\n> + m->trg = n;\n> + m->trg_max_depth= max_depth;\n> + ret = pthread_create(&m->thread, NULL,\n> + threaded_try_delta, m);\n> + if (ret)\n> + die(\"unable to create thread: %s\", strerror(ret));\n> + }\n> + /* ... then join them. */\n> + while (++j < window) {\n> + int ret;\n> + uint32_t other_idx = idx + j;\n> + struct unpacked *m;\n> + if (other_idx >= window)\n> + other_idx -= window;\n> + m = array + other_idx;\n> + ret = pthread_join(m->thread, NULL);\n> + if (ret)\n> + die(\"unable to join thread: %s\", strerror(ret));\n> + }\n> +#else\n> j = window;\n> while (--j > 0) {\n> uint32_t other_idx = idx + j;\n> @@ -1506,6 +1590,7 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n> if (try_delta(n, m, max_depth) < 0)\n> break;\n> }\n> +#endif\n>\n> /* if we made n a delta, and if n is already at max\n> * depth, leaving it in the window is pointless. we\n> @@ -1528,6 +1613,7 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n> for (i = 0; i < window; ++i) {\n> free_delta_index(array[i].index);\n> free(array[i].data);\n> + delta_lock_destroy(&array[i]);\n> }\n> free(array);\n> }\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"50745","messageId":"alpine.LFD.0.999.0708142127350.5415@xanadu.home","threadId":"9493","inReplyTo":"9e4733910708141820n9a09f08h6e104b7469f63375@mail.gmail.com","subject":"Re: performance on repack","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-08-15T01:59:36Z","receivedAt":"2007-08-15T01:59:36Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 14 Aug 2007, Jon Smirl wrote:\n\n> On 8/14/07, Nicolas Pitre wrote:\n> > On Mon, 13 Aug 2007, Shawn O. Pearce wrote:\n> >\n> > > I'm not sure its that complex to run all try_delta calls of the\n> > > current window in parallel. Might be a simple enough change that\n> > > its actually worth the extra complexity, especially with these\n> > > multi-core systems being so readily available. Repacking is the\n> > > most CPU intensive operation Git performs, and the one that is also\n> > > the easiest to make parallel.\n> > >\n> > > Maybe someone else will beat me to it, but if not I might give such\n> > > a patch a shot in a few weeks.\n> >\n> > Well, here's my quick attempt at it. Unfortunately, performance isn't\n> > as good as I'd expected, especially with relatively small blobs like\n> > those found in the linux kernel repo. It looks like the overhead of\n> > thread creation/joining might be significant compared to the actual\n> > delta computation. I have a P4 with HT which might behave differently\n> > from a real SMP machine, or whatever, but the CPU usage never exceeded\n> > 110% according to top (sometimes it even dropped below 95%). Actually, a\n> > git-repack gets much slower due to 2m27s of system time compared to\n> > 0m03s without threads. And this is with NPTL.\n> \n> Thread creation/destruction overhead is way too high to make these\n> threads for every delta.\n> \n> Another strategy is to create four worker threads once when the\n> process is loaded. Then use synchronization primitives to feed the\n> threads lumps of work. The threads persist for the life of the\n> process.\n\nStill, those synchronization primitives would have to be activated for \nevery delta which might also add some overhead.\n\nBut there is another issue to consider: delta searching is limited by \nprevious results for the same delta. If first attempt for a delta \nproduces a 10x reduction, then the next delta computation has to produce \nless than 1/10 the original object size or it is aborted early. And so \non for subsequent attempts. When performing delta computations in \nparallel for the same target then early delta computation abort cannot \noccur since no result is initially available to further limit delta \nprocessing.\n\nSegmenting the list of objects to deltify into sub-lists for individual \nthreads solves both issues.\n\n\nNicolas\n"},{"id":"50750","messageId":"20070815053231.GJ27913@spearce.org","threadId":"9493","inReplyTo":"alpine.LFD.0.999.0708141634160.5415@xanadu.home","subject":"Re: performance on repack","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-08-15T05:32:31Z","receivedAt":"2007-08-15T05:32:31Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre wrote:\n> On Mon, 13 Aug 2007, Shawn O. Pearce wrote:\n> \n> > I'm not sure its that complex to run all try_delta calls of the\n> > current window in parallel.\n> \n> Well, here's my quick attempt at it. Unfortunately, performance isn't \n> as good as I'd expected, especially with relatively small blobs like \n> those found in the linux kernel repo. It looks like the overhead of \n> thread creation/joining might be significant compared to the actual \n> delta computation. I have a P4 with HT which might behave differently \n> from a real SMP machine, or whatever, but the CPU usage never exceeded \n> 110% according to top (sometimes it even dropped below 95%). Actually, a \n> git-repack gets much slower due to 2m27s of system time compared to \n> 0m03s without threads. And this is with NPTL.\n\nYea, I'm not surprised. This is quick and dirty but is really the\nwrong approach. The kernel is spending lots of time setting up the\nthread and its stack, then scheduling it onto a CPU, only to likely\nfind it finish before it even yields the CPU or is interrupted off.\nSo I'd expect to get huge system times here.\n\nEven Linux with its pretty amazing NPTL isn't up to the task.\nNo threading package really is.\n \n> With a repo containing big blobs it is different though. CPU usage \n> firmly gets to 200% hence all cores are saturated with work.\n\nRight, that's what we want to see. ;-)\n\nWhat makes this bloody complex (yes, I just did disagree with\nmyself) is you need to use a pool of threads, one per core, keep\nthem running for the life of the delta phase (so we amortize the\nthread start/stop time) and also give them large enough bursts of\ndata that they can almost always use their full time slice before\nbeing interrupted by the kernel.\n\n> Remains the approach of calling find_deltas() n times with 1/n of the \n> delta_list, one call per thread, for the bulk of the delta search work. \n> This might even be much simpler than my current patch is. However this \n> approach will require n times the memory for the delta window data. \n> Thread creation overhead will occur only once.\n\nYea, that I agree with. The other thing is the main thread may need\nto push a couple of windows worth of work into the threads, so that\nif this window's 1/n unit goes really fast on that thread it doesn't\nstall out waiting for the main thread to get it more data.\n \n> Also... read_sha1_file() is currently not thread safe, and threaded \n> delta searching would requires that its usage be serialized with a \n> global mutex (not done in this patch which is a bug), or ideally be made \n> thread aware.\n\nYea, that's a problem. From the Git library perspective that Luiz\nCapitulino has been working on for GSOC this summer being able to\ncompile/link Git with -lpthreads and have it actually be thread\nsafe would be useful. Unfortunately its waaaay more than just\nmaking read_sha1_file() threadsafe. :-/\n\nread_sha1_file() is actually a reasonably critical part of the\nmajor functions of Git. Slowing that down by making it go through\npthread_mutex_{lock,unlock} is going to hurt. I tried something\nlike the following, and its a bit slower, and really ain't a great\nmulti-thread aware implementation.\n\n# unmodified v1.5.3-rc4-91-g9fa3465 from Junio\n/usr/bin/time ../rl-master/git-rev-list HEAD . >/dev/null\n 1.67 real 1.42 user 0.20 sys\n 1.65 real 1.36 user 0.17 sys\n 1.67 real 1.35 user 0.16 sys\n 1.70 real 1.35 user 0.16 sys\n 1.64 real 1.35 user 0.16 sys\n\n# v1.5.3-rc4-91-g9fa3465 + patch below\n/usr/bin/time ../rl-pthread/git-rev-list HEAD . >/dev/null\n 2.86 real 1.48 user 0.29 sys\n 1.68 real 1.37 user 0.17 sys\n 1.59 real 1.37 user 0.16 sys\n 1.66 real 1.37 user 0.17 sys\n 1.68 real 1.37 user 0.17 sys\n\nThat's on Mac OS X. I guess NPTL would probably be faster at this,\nbut not so much faster as to make it not be an increase.\n\n-->8--\ndiff --git a/Makefile b/Makefile\nindex 4eb4637..f31811b 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -710,7 +710,7 @@ SHELL_PATH_SQ = $(subst ','\\'',$(SHELL_PATH))\n PERL_PATH_SQ = $(subst ','\\'',$(PERL_PATH))\n TCLTK_PATH_SQ = $(subst ','\\'',$(TCLTK_PATH))\n \n-LIBS = $(GITLIBS) $(EXTLIBS)\n+LIBS = $(GITLIBS) $(EXTLIBS) -lpthread\n \n BASIC_CFLAGS += -DSHA1_HEADER='$(SHA1_HEADER_SQ)' \\\n \t-DETC_GITCONFIG='\"$(ETC_GITCONFIG_SQ)\"' $(COMPAT_CFLAGS)\ndiff --git a/sha1_file.c b/sha1_file.c\nindex aca741b..c239789 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -6,6 +6,7 @@\n * This handles basic git sha1 object files - packing, unpacking,\n * creation etc.\n */\n+#include \n #include \"cache.h\"\n #include \"delta.h\"\n #include \"pack.h\"\n@@ -1862,10 +1863,12 @@ int pretend_sha1_file(void *buf, unsigned long len, enum object_type type,\n void *read_sha1_file(const unsigned char *sha1, enum object_type *type,\n \t\t unsigned long *size)\n {\n+\tstatic pthread_mutex_t locky = PTHREAD_MUTEX_INITIALIZER;\n \tunsigned long mapsize;\n \tvoid *map, *buf;\n \tstruct cached_object *co;\n \n+\tpthread_mutex_lock(&locky);\n \tco = find_cached_object(sha1);\n \tif (co) {\n \t\tbuf = xmalloc(co->size + 1);\n@@ -1873,20 +1876,26 @@ void *read_sha1_file(const unsigned char *sha1, enum object_type *type,\n \t\t((char*)buf)[co->size] = 0;\n \t\t*type = co->type;\n \t\t*size = co->size;\n+\t\tpthread_mutex_unlock(&locky);\n \t\treturn buf;\n \t}\n \n \tbuf = read_packed_sha1(sha1, type, size);\n-\tif (buf)\n+\tif (buf) {\n+\t\tpthread_mutex_unlock(&locky);\n \t\treturn buf;\n+\t}\n \tmap = map_sha1_file(sha1, &mapsize);\n \tif (map) {\n \t\tbuf = unpack_sha1_file(map, mapsize, type, size, sha1);\n \t\tmunmap(map, mapsize);\n+\t\tpthread_mutex_unlock(&locky);\n \t\treturn buf;\n \t}\n \treprepare_packed_git();\n-\treturn read_packed_sha1(sha1, type, size);\n+\tbuf = read_packed_sha1(sha1, type, size);\n+\tpthread_mutex_unlock(&locky);\n+\treturn buf;\n }\n \n void *read_object_with_reference(const unsigned char *sha1,\n-- \nShawn.\n"},{"id":"50780","messageId":"9e4733910708150808x39241071j1a4012f16cd26ef8@mail.gmail.com","threadId":"9493","inReplyTo":"20070815053231.GJ27913@spearce.org","subject":"Re: performance on repack","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-08-15T15:08:38Z","receivedAt":"2007-08-15T15:08:38Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/15/07, Shawn O. Pearce wrote:\n> Nicolas Pitre wrote:\n> > On Mon, 13 Aug 2007, Shawn O. Pearce wrote:\n> Even Linux with its pretty amazing NPTL isn't up to the task.\n> No threading package really is.\n\nYou need something like fibers instead of threads for task that small.\n\n> Yea, that I agree with. The other thing is the main thread may need\n> to push a couple of windows worth of work into the threads, so that\n> if this window's 1/n unit goes really fast on that thread it doesn't\n> stall out waiting for the main thread to get it more data.\n>\n> > Also... read_sha1_file() is currently not thread safe, and threaded\n> > delta searching would requires that its usage be serialized with a\n> > global mutex (not done in this patch which is a bug), or ideally be made\n> > thread aware.\n\nYou can avoid making all the low level calls thread safe by using the\nmain thread to get everything into RAM before starting to search for\nthe deltas. The worker threads would only deal with things completely\nin memory. You may need to ref count these in-memory objects if they\nare shared between worker threads. For simplicity the in-memory input\nobjects should be read only by the threads. The worker threads create\nnew structures to hand their results back to the main thread for\nwriting to disk.\n\nA typical solution is to use a queue protected by locks. Main thread\nfaults in all the needed objects to cache. Main thread builds a queue\nentry and increments reference count on all referenced objects. Main\nthread uses locks to add entry to queue, while queue is locked it\nremoves any finished jobs. Main thread writes finished results to\ndisks, decrements ref counts. Cache logic can then take over about\nwhen objects are actually deleted.\n\nWorker threads wait on the queue. When something is placed in the\nqueue a waiting worker thread removes it, processes it, puts the\nresults in RAM, and places the object back on the finished queue. Then\nwaits for another object. It doesn't call into the main body of code.\n\nInitially I would just ignore very large objects while getting the\nbasic code to work. After the basic code is working if a very large\nobject is encountered when the main thread is faulting objects in, the\nmain thread should just process this object on the spot using the\nexisting low memory code.\n\nHopefully the new adaptive read ahead code in the kernel will detect\nthe pattern of the main thread faulting objects in and make good\nguesses about where to read ahead. This is key to not getting stuck\nwaiting on IO to complete. If not the main thread could use ADVISE to\ngive kernel read ahead clues about where it is going to read next.\n\n> Yea, that's a problem. From the Git library perspective that Luiz\n> Capitulino has been working on for GSOC this summer being able to\n> compile/link Git with -lpthreads and have it actually be thread\n> safe would be useful. Unfortunately its waaaay more than just\n> making read_sha1_file() threadsafe. :-/\n>\n> read_sha1_file() is actually a reasonably critical part of the\n> major functions of Git. Slowing that down by making it go through\n> pthread_mutex_{lock,unlock} is going to hurt. I tried something\n> like the following, and its a bit slower, and really ain't a great\n> multi-thread aware implementation.\n>\n> # unmodified v1.5.3-rc4-91-g9fa3465 from Junio\n> /usr/bin/time ../rl-master/git-rev-list HEAD . >/dev/null\n> 1.67 real 1.42 user 0.20 sys\n> 1.65 real 1.36 user 0.17 sys\n> 1.67 real 1.35 user 0.16 sys\n> 1.70 real 1.35 user 0.16 sys\n> 1.64 real 1.35 user 0.16 sys\n>\n> # v1.5.3-rc4-91-g9fa3465 + patch below\n> /usr/bin/time ../rl-pthread/git-rev-list HEAD . >/dev/null\n> 2.86 real 1.48 user 0.29 sys\n> 1.68 real 1.37 user 0.17 sys\n> 1.59 real 1.37 user 0.16 sys\n> 1.66 real 1.37 user 0.17 sys\n> 1.68 real 1.37 user 0.17 sys\n>\n> That's on Mac OS X. I guess NPTL would probably be faster at this,\n> but not so much faster as to make it not be an increase.\n>\n> -->8--\n> diff --git a/Makefile b/Makefile\n> index 4eb4637..f31811b 100644\n> --- a/Makefile\n> +++ b/Makefile\n> @@ -710,7 +710,7 @@ SHELL_PATH_SQ = $(subst ','\\'',$(SHELL_PATH))\n> PERL_PATH_SQ = $(subst ','\\'',$(PERL_PATH))\n> TCLTK_PATH_SQ = $(subst ','\\'',$(TCLTK_PATH))\n>\n> -LIBS = $(GITLIBS) $(EXTLIBS)\n> +LIBS = $(GITLIBS) $(EXTLIBS) -lpthread\n>\n> BASIC_CFLAGS += -DSHA1_HEADER='$(SHA1_HEADER_SQ)' \\\n> -DETC_GITCONFIG='\"$(ETC_GITCONFIG_SQ)\"' $(COMPAT_CFLAGS)\n> diff --git a/sha1_file.c b/sha1_file.c\n> index aca741b..c239789 100644\n> --- a/sha1_file.c\n> +++ b/sha1_file.c\n> @@ -6,6 +6,7 @@\n> * This handles basic git sha1 object files - packing, unpacking,\n> * creation etc.\n> */\n> +#include \n> #include \"cache.h\"\n> #include \"delta.h\"\n> #include \"pack.h\"\n> @@ -1862,10 +1863,12 @@ int pretend_sha1_file(void *buf, unsigned long len, enum object_type type,\n> void *read_sha1_file(const unsigned char *sha1, enum object_type *type,\n> unsigned long *size)\n> {\n> + static pthread_mutex_t locky = PTHREAD_MUTEX_INITIALIZER;\n> unsigned long mapsize;\n> void *map, *buf;\n> struct cached_object *co;\n>\n> + pthread_mutex_lock(&locky);\n> co = find_cached_object(sha1);\n> if (co) {\n> buf = xmalloc(co->size + 1);\n> @@ -1873,20 +1876,26 @@ void *read_sha1_file(const unsigned char *sha1, enum object_type *type,\n> ((char*)buf)[co->size] = 0;\n> *type = co->type;\n> *size = co->size;\n> + pthread_mutex_unlock(&locky);\n> return buf;\n> }\n>\n> buf = read_packed_sha1(sha1, type, size);\n> - if (buf)\n> + if (buf) {\n> + pthread_mutex_unlock(&locky);\n> return buf;\n> + }\n> map = map_sha1_file(sha1, &mapsize);\n> if (map) {\n> buf = unpack_sha1_file(map, mapsize, type, size, sha1);\n> munmap(map, mapsize);\n> + pthread_mutex_unlock(&locky);\n> return buf;\n> }\n> reprepare_packed_git();\n> - return read_packed_sha1(sha1, type, size);\n> + buf = read_packed_sha1(sha1, type, size);\n> + pthread_mutex_unlock(&locky);\n> + return buf;\n> }\n>\n> void *read_object_with_reference(const unsigned char *sha1,\n> --\n> Shawn.\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"50797","messageId":"20070815171152.GA15155@auto.tuwien.ac.at","threadId":"9493","inReplyTo":"9e4733910708150808x39241071j1a4012f16cd26ef8@mail.gmail.com","subject":"Re: performance on repack","fromName":"Martin Koegler","fromEmail":"mkoegler@auto.tuwien.ac.at","sentAt":"2007-08-15T17:11:52Z","receivedAt":"2007-08-15T17:11:52Z","isPatch":false,"sender":{"key":"mkoegler@auto.tuwien.ac.at","avatar":null},"body":"On Wed, Aug 15, 2007 at 11:08:38AM -0400, Jon Smirl wrote:\n> On 8/15/07, Shawn O. Pearce wrote:\n> > > Also... read_sha1_file() is currently not thread safe, and threaded\n> > > delta searching would requires that its usage be serialized with a\n> > > global mutex (not done in this patch which is a bug), or ideally be made\n> > > thread aware.\n> \n> You can avoid making all the low level calls thread safe by using the\n> main thread to get everything into RAM before starting to search for\n> the deltas. The worker threads would only deal with things completely\n> in memory. You may need to ref count these in-memory objects if they\n> are shared between worker threads. For simplicity the in-memory input\n> objects should be read only by the threads. The worker threads create\n> new structures to hand their results back to the main thread for\n> writing to disk.\n\ngit-pack-objects knows the order, in which it will use the objects. A\nseperate thread could pre-read the next object and wait until the main\nthread starts processing it. After the read is complete, another\nthread could start computing the delta index.\n\ngit-pack-objects currently reads an object (and computes the delta\nindex), if it is really necessary. With the pre-read, unnecessary\noperations would happen.\n\n> Initially I would just ignore very large objects while getting the\n> basic code to work. After the basic code is working if a very large\n> object is encountered when the main thread is faulting objects in, the\n> main thread should just process this object on the spot using the\n> existing low memory code.\n\nI expect that the biggest gain will be for big objects, as they\nrequire more time to read+unpack the source objects and compute the\ndelta index as well as the delta.\n\n> > @@ -1862,10 +1863,12 @@ int pretend_sha1_file(void *buf, unsigned long len, enum object_type type,\n> > void *read_sha1_file(const unsigned char *sha1, enum object_type *type,\n> > unsigned long *size)\n> > {\n> > + static pthread_mutex_t locky = PTHREAD_MUTEX_INITIALIZER;\n> > unsigned long mapsize;\n> > void *map, *buf;\n> > struct cached_object *co;\n> >\n> > + pthread_mutex_lock(&locky);\n> > co = find_cached_object(sha1);\n> > if (co) {\n> > buf = xmalloc(co->size + 1);\n> > @@ -1873,20 +1876,26 @@ void *read_sha1_file(const unsigned char *sha1, enum object_type *type,\n> > ((char*)buf)[co->size] = 0;\n> > *type = co->type;\n> > *size = co->size;\n> > + pthread_mutex_unlock(&locky);\n> > return buf;\n> > }\n> >\n> > buf = read_packed_sha1(sha1, type, size);\n\nCouldn't we release the mutex at this point?\n\nWhy do we need to protect from concurrent access, when we are reading\na loose object?\n\n> > - if (buf)\n> > + if (buf) {\n> > + pthread_mutex_unlock(&locky);\n> > return buf;\n> > + }\n> > map = map_sha1_file(sha1, &mapsize);\n> > if (map) {\n> > buf = unpack_sha1_file(map, mapsize, type, size, sha1);\n> > munmap(map, mapsize);\n> > + pthread_mutex_unlock(&locky);\n> > return buf;\n> > }\n> > reprepare_packed_git();\n> > - return read_packed_sha1(sha1, type, size);\n> > + buf = read_packed_sha1(sha1, type, size);\n> > + pthread_mutex_unlock(&locky);\n> > + return buf;\n> > }\n\nmfg Martin Kögler\n"},{"id":"50806","messageId":"9e4733910708151138x2b267dc6w27c1bc8d948e5633@mail.gmail.com","threadId":"9493","inReplyTo":"20070815171152.GA15155@auto.tuwien.ac.at","subject":"Re: performance on repack","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-08-15T18:38:15Z","receivedAt":"2007-08-15T18:38:15Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/15/07, Martin Koegler wrote:\n> git-pack-objects knows the order, in which it will use the objects. A\n> seperate thread could pre-read the next object and wait until the main\n> thread starts processing it. After the read is complete, another\n> thread could start computing the delta index.\n\nThe hope is that the new adaptive read ahead code in the kernel will\nget this right and you won't need the second thread. Letting the\nkernel handle the read ahead will dynamically scale as other demands\nare made on the host. There's effectively only one read ahead cache in\nthe system, only the kernel really knows how to divide it up between\ncompeting apps.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"50808","messageId":"alpine.LFD.0.999.0708151453390.5415@xanadu.home","threadId":"9493","inReplyTo":"9e4733910708151138x2b267dc6w27c1bc8d948e5633@mail.gmail.com","subject":"Re: performance on repack","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-08-15T19:00:14Z","receivedAt":"2007-08-15T19:00:14Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 15 Aug 2007, Jon Smirl wrote:\n\n> On 8/15/07, Martin Koegler wrote:\n> > git-pack-objects knows the order, in which it will use the objects. A\n> > seperate thread could pre-read the next object and wait until the main\n> > thread starts processing it. After the read is complete, another\n> > thread could start computing the delta index.\n> \n> The hope is that the new adaptive read ahead code in the kernel will\n> get this right and you won't need the second thread. Letting the\n> kernel handle the read ahead will dynamically scale as other demands\n> are made on the host. There's effectively only one read ahead cache in\n> the system, only the kernel really knows how to divide it up between\n> competing apps.\n\nNo read ahead will ever help the delta search phase. Objects listed for \ndeltification against each other are sorted in a way that results in \nreads from completely random location in the object store.\n\nNormally the delta search phase is so compute intensive that the read \nshouldn't matter much.\n\n\nNicolas\n"},{"id":"50813","messageId":"9e4733910708151242q5ba020adkbe5d207f93be0f4c@mail.gmail.com","threadId":"9493","inReplyTo":"alpine.LFD.0.999.0708151453390.5415@xanadu.home","subject":"Re: performance on repack","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-08-15T19:42:51Z","receivedAt":"2007-08-15T19:42:51Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/15/07, Nicolas Pitre wrote:\n> On Wed, 15 Aug 2007, Jon Smirl wrote:\n>\n> > On 8/15/07, Martin Koegler wrote:\n> > > git-pack-objects knows the order, in which it will use the objects. A\n> > > seperate thread could pre-read the next object and wait until the main\n> > > thread starts processing it. After the read is complete, another\n> > > thread could start computing the delta index.\n> >\n> > The hope is that the new adaptive read ahead code in the kernel will\n> > get this right and you won't need the second thread. Letting the\n> > kernel handle the read ahead will dynamically scale as other demands\n> > are made on the host. There's effectively only one read ahead cache in\n> > the system, only the kernel really knows how to divide it up between\n> > competing apps.\n>\n> No read ahead will ever help the delta search phase. Objects listed for\n> deltification against each other are sorted in a way that results in\n> reads from completely random location in the object store.\n>\n> Normally the delta search phase is so compute intensive that the read\n> shouldn't matter much.\n\nI agree, I am compute bound for 20 min, disk light occasionally dimly flickers.\n\nBesides, the main thread that is preparing the queue effectively\nfunctions as a read ahead thread. It will overlap with the compute\nbound delta searches.\n\n>\n>\n> Nicolas\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"50817","messageId":"alpine.LFD.0.999.0708151500510.5415@xanadu.home","threadId":"9493","inReplyTo":"20070815053231.GJ27913@spearce.org","subject":"Re: performance on repack","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-08-15T20:49:30Z","receivedAt":"2007-08-15T20:49:30Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 15 Aug 2007, Shawn O. Pearce wrote:\n\n> Nicolas Pitre wrote:\n> > On Mon, 13 Aug 2007, Shawn O. Pearce wrote:\n> > \n> > > I'm not sure its that complex to run all try_delta calls of the\n> > > current window in parallel.\n> > \n> > Well, here's my quick attempt at it. Unfortunately, performance isn't \n> > as good as I'd expected, especially with relatively small blobs like \n> > those found in the linux kernel repo. It looks like the overhead of \n> > thread creation/joining might be significant compared to the actual \n> > delta computation. I have a P4 with HT which might behave differently \n> > from a real SMP machine, or whatever, but the CPU usage never exceeded \n> > 110% according to top (sometimes it even dropped below 95%). Actually, a \n> > git-repack gets much slower due to 2m27s of system time compared to \n> > 0m03s without threads. And this is with NPTL.\n> \n> Yea, I'm not surprised. This is quick and dirty but is really the\n> wrong approach. The kernel is spending lots of time setting up the\n> thread and its stack, then scheduling it onto a CPU, only to likely\n> find it finish before it even yields the CPU or is interrupted off.\n> So I'd expect to get huge system times here.\n\nSo... Here's a variation on the previous attempt. A thread is created \nfor each delta window slot and it is awakened when there is a delta to \ncompute. Now top is reporting an average of 175% CPU usage when delta \nsearching on the linux repo. The threading overhead when down a lot, \nfrom 2m of system time to 42s. Still a far cry from the usual 3s when \nno threads are used though.\n\n> > With a repo containing big blobs it is different though. CPU usage \n> > firmly gets to 200% hence all cores are saturated with work.\n> \n> Right, that's what we want to see. ;-)\n> \n> What makes this bloody complex (yes, I just did disagree with\n> myself) is you need to use a pool of threads, one per core, keep\n> them running for the life of the delta phase (so we amortize the\n> thread start/stop time) and also give them large enough bursts of\n> data that they can almost always use their full time slice before\n> being interrupted by the kernel.\n\nThis is still way suboptimal. The thread synchronization that has to be \ninvolved for _each_ delta attempt simply puts too much overhead.\n\nAlso, all threads have to be done before sliding the window to the \nnext object since deltification of the new object depends on the results \nfrom the previous window position. However, it is highly unlikely that \nall threads will be done with their share of work at the same time and \ntherefore there will always be a certain amount of time when most \nthreads will be idle while the last ones are still busy, up to the point \nwhere there is only one thread to wait after before moving the window \nforward. This is what explains why I get around 175% CPU usage instead \nof 200% when repacking the linux kernel repo.\n\nAnd still, the total amount of CPU cycles spent on the whole task is far \ngreater than without any thread because, as I mentioned before, running \ndelta computations in parallel doesn't allow early abort of \ncreate_delta() calls based on a good max_size value from a previous \ndelta results because there is no such previous results when everything \nis computed in parallel. So, while the repack might be faster from a \nwall clock point of view, it wastes more CPU cycles in the end which is \nnot really nice.\n\n> > Remains the approach of calling find_deltas() n times with 1/n of the \n> > delta_list, one call per thread, for the bulk of the delta search work. \n> > This might even be much simpler than my current patch is. However this \n> > approach will require n times the memory for the delta window data. \n> > Thread creation overhead will occur only once.\n> \n> Yea, that I agree with. The other thing is the main thread may need\n> to push a couple of windows worth of work into the threads, so that\n> if this window's 1/n unit goes really fast on that thread it doesn't\n> stall out waiting for the main thread to get it more data.\n\nIt is easier to keep 4 threads busy with 100000 objects each to deal \nwith in a conventional way than keeping 10 threads busy when processing \na single delta window in parallel. Or the delta_list can be partitioned \nin smaller chunks and anytime one of the find_deltas() thread is done \nthen it is fed another chunk.\n\nThe side effect of that is that no delta will cross chunk boundaries. \nBut just like when repacking multiple existing packs into one with \ndelta data reuse, the actual chunk boundaries can be re-fed to \nfind_deltas() in order to find more deltas across chunks.\n\nThis approach will require less code than the patch below, it will have \nalmost zero threading overhead and each thread will be sure to be busy \nfor a long period of time. And the early create_delta() abort will just \nwork too.\n\n> > Also... read_sha1_file() is currently not thread safe, and threaded \n> > delta searching would requires that its usage be serialized with a \n> > global mutex (not done in this patch which is a bug), or ideally be made \n> > thread aware.\n> \n> Yea, that's a problem. From the Git library perspective that Luiz\n> Capitulino has been working on for GSOC this summer being able to\n> compile/link Git with -lpthreads and have it actually be thread\n> safe would be useful. Unfortunately its waaaay more than just\n> making read_sha1_file() threadsafe. :-/\n> \n> read_sha1_file() is actually a reasonably critical part of the\n> major functions of Git. Slowing that down by making it go through\n> pthread_mutex_{lock,unlock} is going to hurt. I tried something\n> like the following, and its a bit slower, and really ain't a great\n> multi-thread aware implementation.\n\nI'd say that, since almost none of the GIT code currently need thread \naware read_sha1_file(), it is best to only serialize its usage at the \ncaller level where it is actually needed.\n\n\nNicolas\n\n---\n\ndiff --git a/Makefile b/Makefile\nindex 4eb4637..c3c6e68 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -122,6 +122,9 @@ all::\n # If not set it defaults to the bare 'wish'. If it is set to the empty\n # string then NO_TCLTK will be forced (this is used by configure script).\n #\n+# Define THREADED_DELTA_SEARCH if you have pthreads and wish to exploit\n+# parallel delta searching when packing objects.\n+#\n \n GIT-VERSION-FILE: .FORCE-GIT-VERSION-FILE\n \t@$(SHELL_PATH) ./GIT-VERSION-GEN\n@@ -662,6 +665,11 @@ ifdef NO_HSTRERROR\n \tCOMPAT_OBJS += compat/hstrerror.o\n endif\n \n+ifdef THREADED_DELTA_SEARCH\n+\tBASIC_CFLAGS += -DTHREADED_DELTA_SEARCH\n+\tEXTLIBS += -lpthread\n+endif\n+\n ifeq ($(TCLTK_PATH),)\n NO_TCLTK=NoThanks\n endif\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 5e9d1fd..449f9f3 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -15,6 +15,10 @@\n #include \"list-objects.h\"\n #include \"progress.h\"\n \n+#ifdef THREADED_DELTA_SEARCH\n+#include \n+#endif\n+\n static const char pack_usage[] = \"\\\n git-pack-objects [{ -q | --progress | --all-progress }] \\n\\\n \t[--max-pack-size=N] [--local] [--incremental] \\n\\\n@@ -1273,6 +1277,14 @@ struct unpacked {\n \tvoid *data;\n \tstruct delta_index *index;\n \tunsigned depth;\n+#ifdef THREADED_DELTA_SEARCH\n+\tpthread_t thread;\n+\tpthread_mutex_t mutex;\n+\tpthread_mutex_t wait;\n+\tpthread_mutex_t done;\n+\tstruct unpacked *trg;\n+\tunsigned trg_max_depth;\n+#endif\n };\n \n static int delta_cacheable(struct unpacked *trg, struct unpacked *src,\n@@ -1292,6 +1304,24 @@ static int delta_cacheable(struct unpacked *trg, struct unpacked *src,\n \treturn 0;\n }\n \n+#ifdef THREADED_DELTA_SEARCH\n+\n+static pthread_mutex_t read_sha1_file_mutex = PTHREAD_MUTEX_INITIALIZER;\n+\n+#define read_lock()\t\tpthread_mutex_lock(&read_sha1_file_mutex)\n+#define read_unlock()\t\tpthread_mutex_unlock(&read_sha1_file_mutex)\n+#define delta_lock(e)\t\tpthread_mutex_lock(&(e)->mutex)\n+#define delta_unlock(e)\t\tpthread_mutex_unlock(&(e)->mutex)\n+\n+#else\n+\n+#define read_lock()\t\t0\n+#define read_unlock()\t\t0\n+#define delta_lock(e)\t\t0\n+#define delta_unlock(e)\t\t0\n+\n+#endif\n+\n /*\n * We search for deltas _backwards_ in a list sorted by type and\n * by size, so that we see progressively smaller and smaller files.\n@@ -1335,6 +1365,7 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t\treturn 0;\n \n \t/* Now some size filtering heuristics. */\n+\tdelta_lock(trg);\n \ttrg_size = trg_entry->size;\n \tif (!trg_entry->delta) {\n \t\tmax_size = trg_size/2 - 20;\n@@ -1343,6 +1374,7 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t\tmax_size = trg_entry->delta_size;\n \t\tref_depth = trg->depth;\n \t}\n+\tdelta_unlock(trg);\n \tmax_size = max_size * (max_depth - src->depth) /\n \t\t\t\t\t\t(max_depth - ref_depth + 1);\n \tif (max_size == 0)\n@@ -1355,19 +1387,28 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t\treturn 0;\n \n \t/* Load data if not already done */\n+\n+\tdelta_lock(trg);\n \tif (!trg->data) {\n+\t\tread_lock();\n \t\ttrg->data = read_sha1_file(trg_entry->idx.sha1, &type, &sz);\n \t\tif (sz != trg_size)\n \t\t\tdie(\"object %s inconsistent object length (%lu vs %lu)\",\n \t\t\t sha1_to_hex(trg_entry->idx.sha1), sz, trg_size);\n \t\twindow_memory_usage += sz;\n+\t\tread_unlock();\n \t}\n+\tdelta_unlock(trg);\n+\n+\tdelta_lock(src);\n \tif (!src->data) {\n+\t\tread_lock();\n \t\tsrc->data = read_sha1_file(src_entry->idx.sha1, &type, &sz);\n \t\tif (sz != src_size)\n \t\t\tdie(\"object %s inconsistent object length (%lu vs %lu)\",\n \t\t\t sha1_to_hex(src_entry->idx.sha1), sz, src_size);\n \t\twindow_memory_usage += sz;\n+\t\tread_unlock();\n \t}\n \tif (!src->index) {\n \t\tsrc->index = create_delta_index(src->data, src_size);\n@@ -1375,20 +1416,32 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t\t\tstatic int warned = 0;\n \t\t\tif (!warned++)\n \t\t\t\twarning(\"suboptimal pack - out of memory\");\n+\t\t\tdelta_unlock(src);\n \t\t\treturn 0;\n \t\t}\n+\t\tread_lock();\n \t\twindow_memory_usage += sizeof_delta_index(src->index);\n+\t\tread_unlock();\n \t}\n+\tdelta_unlock(src);\n \n \tdelta_buf = create_delta(src->index, trg->data, trg_size, &delta_size, max_size);\n \tif (!delta_buf)\n \t\treturn 0;\n \n+\tdelta_lock(trg);\n \tif (trg_entry->delta_data) {\n-\t\t/* Prefer only shallower same-sized deltas. */\n-\t\tif (delta_size == trg_entry->delta_size &&\n-\t\t src->depth + 1 >= trg->depth) {\n+#ifdef THREADED_DELTA_SEARCH\n+\t\t/* A better match might have been found in the mean time */\n+\t\tmax_size = trg_entry->delta_size * (max_depth - src->depth) /\n+\t\t\t\t\t\t(max_depth - trg->depth + 1);\n+#endif\n+\t\t/* ... also prefer only shallower same-sized deltas. */\n+\t\tif (delta_size > max_size ||\n+\t\t (delta_size == trg_entry->delta_size &&\n+\t\t src->depth + 1 >= trg->depth)) {\n \t\t\tfree(delta_buf);\n+\t\t\tdelta_unlock(trg);\n \t\t\treturn 0;\n \t\t}\n \t\tdelta_cache_size -= trg_entry->delta_size;\n@@ -1404,9 +1457,27 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t\tdelta_cache_size += trg_entry->delta_size;\n \t} else\n \t\tfree(delta_buf);\n+\tdelta_unlock(trg);\n \treturn 1;\n }\n \n+#ifdef THREADED_DELTA_SEARCH\n+\n+static void *threaded_try_delta(void *arg)\n+{\n+\tstruct unpacked *src = arg;\n+\tfor (;;) {\n+\t\tpthread_mutex_lock(&src->wait);\n+\t\tif (!src->trg)\n+\t\t\tbreak;\n+\t\ttry_delta(src->trg, src, src->trg_max_depth);\n+\t\tpthread_mutex_unlock(&src->done);\n+\t}\n+\treturn NULL;\n+}\n+\n+#endif\n+\n static unsigned int check_delta_limit(struct object_entry *me, unsigned int n)\n {\n \tstruct object_entry *child = me->delta_child;\n@@ -1439,19 +1510,32 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n \tuint32_t i = nr_objects, idx = 0, count = 0, processed = 0;\n \tunsigned int array_size = window * sizeof(struct unpacked);\n \tstruct unpacked *array;\n-\tint max_depth;\n+\tint j, max_depth;\n \n \tif (!nr_objects)\n \t\treturn;\n \tarray = xmalloc(array_size);\n \tmemset(array, 0, array_size);\n+#ifdef THREADED_DELTA_SEARCH\n+\tfor (j = 0; j < window; j++) {\n+\t\tint ret;\n+\t\tpthread_mutex_init(&array[j].mutex, NULL);\n+\t\tpthread_mutex_init(&array[j].wait, NULL);\n+\t\tpthread_mutex_init(&array[j].done, NULL);\n+\t\tpthread_mutex_lock(&array[j].wait);\n+\t\tpthread_mutex_lock(&array[j].done);\n+\t\tret = pthread_create(&array[j].thread, NULL,\n+\t\t\t\t threaded_try_delta, &array[j]);\n+\t\t\tif (ret)\n+\t\t\t\tdie(\"unable to create thread: %s\", strerror(ret));\n+\t}\n+#endif\n \tif (progress)\n \t\tstart_progress(&progress_state, \"Deltifying %u objects...\", \"\", nr_result);\n \n \tdo {\n \t\tstruct object_entry *entry = list[--i];\n \t\tstruct unpacked *n = array + idx;\n-\t\tint j;\n \n \t\tif (!entry->preferred_base)\n \t\t\tprocessed++;\n@@ -1494,6 +1578,31 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n \t\t\t\tgoto next;\n \t\t}\n \n+#ifdef THREADED_DELTA_SEARCH\n+\t\t/* Unlock all threads ... */\n+\t\tj = window;\n+\t\twhile (--j > 0) {\n+\t\t\tuint32_t other_idx = idx + j;\n+\t\t\tstruct unpacked *m;\n+\t\t\tif (other_idx >= window)\n+\t\t\t\tother_idx -= window;\n+\t\t\tm = array + other_idx;\n+\t\t\tif (!m->entry)\n+\t\t\t\tbreak;\n+\t\t\tm->trg = n;\n+\t\t\tm->trg_max_depth= max_depth;\n+\t\t\tpthread_mutex_unlock(&m->wait);\n+\t\t}\n+\t\t/* ... then wait for their completion. */\n+\t\twhile (++j < window) {\n+\t\t\tuint32_t other_idx = idx + j;\n+\t\t\tstruct unpacked *m;\n+\t\t\tif (other_idx >= window)\n+\t\t\t\tother_idx -= window;\n+\t\t\tm = array + other_idx;\n+\t\t\tpthread_mutex_lock(&m->done);\n+\t\t}\n+#else\n \t\tj = window;\n \t\twhile (--j > 0) {\n \t\t\tuint32_t other_idx = idx + j;\n@@ -1506,6 +1615,7 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n \t\t\tif (try_delta(n, m, max_depth) < 0)\n \t\t\t\tbreak;\n \t\t}\n+#endif\n \n \t\t/* if we made n a delta, and if n is already at max\n \t\t * depth, leaving it in the window is pointless. we\n@@ -1528,6 +1638,16 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n \tfor (i = 0; i < window; ++i) {\n \t\tfree_delta_index(array[i].index);\n \t\tfree(array[i].data);\n+#ifdef THREADED_DELTA_SEARCH\n+\t\tarray[i].trg = NULL;\n+\t\tpthread_mutex_unlock(&array[i].wait);\n+\t\tpthread_join(array[i].thread, NULL);\n+\t\tpthread_mutex_unlock(&array[i].wait);\n+\t\tpthread_mutex_unlock(&array[i].done);\n+\t\tpthread_mutex_destroy(&array[i].mutex);\n+\t\tpthread_mutex_destroy(&array[i].wait);\n+\t\tpthread_mutex_destroy(&array[i].done);\n+#endif\n \t}\n \tfree(array);\n }\n"},{"id":"50818","messageId":"alpine.LFD.0.999.0708151650270.5415@xanadu.home","threadId":"9493","inReplyTo":"9e4733910708150808x39241071j1a4012f16cd26ef8@mail.gmail.com","subject":"Re: performance on repack","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-08-15T21:05:47Z","receivedAt":"2007-08-15T21:05:47Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 15 Aug 2007, Jon Smirl wrote:\n\n> You can avoid making all the low level calls thread safe by using the\n> main thread to get everything into RAM before starting to search for\n> the deltas. The worker threads would only deal with things completely\n> in memory. You may need to ref count these in-memory objects if they\n> are shared between worker threads. For simplicity the in-memory input\n> objects should be read only by the threads. The worker threads create\n> new structures to hand their results back to the main thread for\n> writing to disk.\n> \n> A typical solution is to use a queue protected by locks. Main thread\n> faults in all the needed objects to cache. Main thread builds a queue\n> entry and increments reference count on all referenced objects. Main\n> thread uses locks to add entry to queue, while queue is locked it\n> removes any finished jobs. Main thread writes finished results to\n> disks, decrements ref counts. Cache logic can then take over about\n> when objects are actually deleted.\n> \n> Worker threads wait on the queue. When something is placed in the\n> queue a waiting worker thread removes it, processes it, puts the\n> results in RAM, and places the object back on the finished queue. Then\n> waits for another object. It doesn't call into the main body of code.\n\nWay too complex and rather unpractical with the current algorithms.\n\nCurrently, information on objects is gathered (the \"Counting objects\" \nphase) and that hardly can be paralleled.\n\nOnce objects are known then a sorted list is created so deltification of \nobject x might be optimally attempted on objects x-1 through to x-10. \nCreating that list cannot be paralleled either, but it is quick \nanyway.\n\nThen comes the actual deltification phase where the huge cost is. The \nproblem simply has to be partitioned into a few threads, where thread 1 \ndeals with object 1 to 100000 from that sorted list, thread 2 has \nobjects 100001 to 200000, etc. etc. This is now a partitioning problem \nwhere the thread synchronization is dealt with from a higher and non \nperformance critical level.\n\n\nNicolas\n"},{"id":"50859","messageId":"86d4xn5287.fsf@lola.quinscape.zz","threadId":"9493","inReplyTo":"alpine.LFD.0.999.0708151453390.5415@xanadu.home","subject":"Re: performance on repack","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2007-08-16T08:10:32Z","receivedAt":"2007-08-16T08:10:32Z","isPatch":false,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Nicolas Pitre writes:\n\n> On Wed, 15 Aug 2007, Jon Smirl wrote:\n>\n>> On 8/15/07, Martin Koegler wrote:\n>> > git-pack-objects knows the order, in which it will use the objects. A\n>> > seperate thread could pre-read the next object and wait until the main\n>> > thread starts processing it. After the read is complete, another\n>> > thread could start computing the delta index.\n>> \n>> The hope is that the new adaptive read ahead code in the kernel will\n>> get this right and you won't need the second thread. Letting the\n>> kernel handle the read ahead will dynamically scale as other demands\n>> are made on the host. There's effectively only one read ahead cache in\n>> the system, only the kernel really knows how to divide it up between\n>> competing apps.\n>\n> No read ahead will ever help the delta search phase.\n\nWell, the delta search phase consists of computing a delta index and\nthen matching against it. If I understand correctly, delta indices\nfor the search window are kept, and the current file is compared\nagainst them. Locality might be better if just one delta index gets\ncalculated and then compared with all _upcoming_ delta candidates in\none go.\n\nNo idea whether it would pay off the complications.\n\n-- \nDavid Kastrup\n"},{"id":"50890","messageId":"alpine.LFD.0.999.0708161103080.16727@xanadu.home","threadId":"9493","inReplyTo":"86d4xn5287.fsf@lola.quinscape.zz","subject":"Re: performance on repack","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-08-16T15:34:19Z","receivedAt":"2007-08-16T15:34:19Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 16 Aug 2007, David Kastrup wrote:\n\n> Nicolas Pitre writes:\n> \n> > On Wed, 15 Aug 2007, Jon Smirl wrote:\n> >\n> >> On 8/15/07, Martin Koegler wrote:\n> >> > git-pack-objects knows the order, in which it will use the objects. A\n> >> > seperate thread could pre-read the next object and wait until the main\n> >> > thread starts processing it. After the read is complete, another\n> >> > thread could start computing the delta index.\n> >> \n> >> The hope is that the new adaptive read ahead code in the kernel will\n> >> get this right and you won't need the second thread. Letting the\n> >> kernel handle the read ahead will dynamically scale as other demands\n> >> are made on the host. There's effectively only one read ahead cache in\n> >> the system, only the kernel really knows how to divide it up between\n> >> competing apps.\n> >\n> > No read ahead will ever help the delta search phase.\n> \n> Well, the delta search phase consists of computing a delta index and\n> then matching against it.\n\nNo, what I mean is what happens at a higher level where one object is \ndeltified against several base object candidates to find the best match. \nThose several objects are presorted according to a combination of \nheuristics that makes their actual access completely random, hence no \nkernel read ahead might help here.\n\n> If I understand correctly, delta indices\n> for the search window are kept, and the current file is compared\n> against them. Locality might be better if just one delta index gets\n> calculated and then compared with all _upcoming_ delta candidates in\n> one go.\n\nThis appears so obvious that I attempted that a while ago already.\n\nThe idea turned up to be so complex to implement correctly and produced \nsuboptimal results in practice that I abandoned it.\n\nSee http://marc.info/?l=git&m=114610715706599&w=2 for the details if \nyou're interested.\n\nPS: please at least CC me when replying to my mails\n\n\nNicolas\n"},{"id":"50895","messageId":"9e4733910708160913i29e18e80v107bcc3732e9db95@mail.gmail.com","threadId":"9493","inReplyTo":"alpine.LFD.0.999.0708161103080.16727@xanadu.home","subject":"Re: performance on repack","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-08-16T16:13:28Z","receivedAt":"2007-08-16T16:13:28Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/16/07, Nicolas Pitre wrote:\n> On Thu, 16 Aug 2007, David Kastrup wrote:\n> > If I understand correctly, delta indices\n> > for the search window are kept, and the current file is compared\n> > against them. Locality might be better if just one delta index gets\n> > calculated and then compared with all _upcoming_ delta candidates in\n> > one go.\n>\n> This appears so obvious that I attempted that a while ago already.\n>\n> The idea turned up to be so complex to implement correctly and produced\n> suboptimal results in practice that I abandoned it.\n\nIn practice it doesn't really matter what you do. Most developers have\na decent amount of RAM. Disks run at 50MB/sec or more. The entire pack\nfile ends up in the kernel disk cache within a few seconds.\n\nTurning the twenty minute delta search into 6-7 minutes is a much more\nobvious win.\n\n\n>\n> See http://marc.info/?l=git&m=114610715706599&w=2 for the details if\n> you're interested.\n>\n> PS: please at least CC me when replying to my mails\n>\n>\n> Nicolas\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-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"50896","messageId":"alpine.LFD.0.999.0708161219340.16727@xanadu.home","threadId":"9493","inReplyTo":"9e4733910708160913i29e18e80v107bcc3732e9db95@mail.gmail.com","subject":"Re: performance on repack","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-08-16T16:21:51Z","receivedAt":"2007-08-16T16:21:51Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 16 Aug 2007, Jon Smirl wrote:\n\n> On 8/16/07, Nicolas Pitre wrote:\n> > On Thu, 16 Aug 2007, David Kastrup wrote:\n> > > If I understand correctly, delta indices\n> > > for the search window are kept, and the current file is compared\n> > > against them. Locality might be better if just one delta index gets\n> > > calculated and then compared with all _upcoming_ delta candidates in\n> > > one go.\n> >\n> > This appears so obvious that I attempted that a while ago already.\n> >\n> > The idea turned up to be so complex to implement correctly and produced\n> > suboptimal results in practice that I abandoned it.\n> \n> In practice it doesn't really matter what you do. Most developers have\n> a decent amount of RAM. Disks run at 50MB/sec or more. The entire pack\n> file ends up in the kernel disk cache within a few seconds.\n> \n> Turning the twenty minute delta search into 6-7 minutes is a much more\n> obvious win.\n\nAnd your point in relation with what was just said is ?\n\n\nNicolas\n"},{"id":"51870","messageId":"alpine.LFD.0.999.0708300005110.16727@xanadu.home","threadId":"9493","inReplyTo":"alpine.LFD.0.999.0708151500510.5415@xanadu.home","subject":"Re: performance on repack","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-08-30T04:27:50Z","receivedAt":"2007-08-30T04:27:50Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 15 Aug 2007, Nicolas Pitre wrote:\n\n> On Wed, 15 Aug 2007, Shawn O. Pearce wrote:\n> \n> > Nicolas Pitre wrote:\n> >\n> > > Remains the approach of calling find_deltas() n times with 1/n of the \n> > > delta_list, one call per thread, for the bulk of the delta search work. \n> > > This might even be much simpler than my current patch is. However this \n> > > approach will require n times the memory for the delta window data. \n> > > Thread creation overhead will occur only once.\n> > \n> > Yea, that I agree with. The other thing is the main thread may need\n> > to push a couple of windows worth of work into the threads, so that\n> > if this window's 1/n unit goes really fast on that thread it doesn't\n> > stall out waiting for the main thread to get it more data.\n> \n> It is easier to keep 4 threads busy with 100000 objects each to deal \n> with in a conventional way than keeping 10 threads busy when processing \n> a single delta window in parallel. Or the delta_list can be partitioned \n> in smaller chunks and anytime one of the find_deltas() thread is done \n> then it is fed another chunk.\n> \n> The side effect of that is that no delta will cross chunk boundaries. \n> But just like when repacking multiple existing packs into one with \n> delta data reuse, the actual chunk boundaries can be re-fed to \n> find_deltas() in order to find more deltas across chunks.\n\nWell, here is a quick implementation of this idea for those who would \nlike to give it a try. Performance is indeed much better. The delta \nprogress status is however fscked up at the moment, so don't pay too \nmuch attention to it. Partitioning is also extremely crude. But the \nidea looks promizing.\n\n---\n\ndiff --git a/Makefile b/Makefile\nindex 4eb4637..c3c6e68 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -122,6 +122,9 @@ all::\n # If not set it defaults to the bare 'wish'. If it is set to the empty\n # string then NO_TCLTK will be forced (this is used by configure script).\n #\n+# Define THREADED_DELTA_SEARCH if you have pthreads and wish to exploit\n+# parallel delta searching when packing objects.\n+#\n \n GIT-VERSION-FILE: .FORCE-GIT-VERSION-FILE\n \t@$(SHELL_PATH) ./GIT-VERSION-GEN\n@@ -662,6 +665,11 @@ ifdef NO_HSTRERROR\n \tCOMPAT_OBJS += compat/hstrerror.o\n endif\n \n+ifdef THREADED_DELTA_SEARCH\n+\tBASIC_CFLAGS += -DTHREADED_DELTA_SEARCH\n+\tEXTLIBS += -lpthread\n+endif\n+\n ifeq ($(TCLTK_PATH),)\n NO_TCLTK=NoThanks\n endif\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex e917e8e..7d68f82 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -15,6 +15,10 @@\n #include \"list-objects.h\"\n #include \"progress.h\"\n \n+#ifdef THREADED_DELTA_SEARCH\n+#include \n+#endif\n+\n static const char pack_usage[] = \"\\\n git-pack-objects [{ -q | --progress | --all-progress }] \\n\\\n \t[--max-pack-size=N] [--local] [--incremental] \\n\\\n@@ -1290,6 +1294,20 @@ static int delta_cacheable(unsigned long src_size, unsigned long trg_size,\n \treturn 0;\n }\n \n+#ifdef THREADED_DELTA_SEARCH\n+\n+static pthread_mutex_t read_sha1_file_mutex = PTHREAD_MUTEX_INITIALIZER;\n+\n+#define read_lock()\t\tpthread_mutex_lock(&read_sha1_file_mutex)\n+#define read_unlock()\t\tpthread_mutex_unlock(&read_sha1_file_mutex)\n+\n+#else\n+\n+#define read_lock()\t\t0\n+#define read_unlock()\t\t0\n+\n+#endif\n+\n /*\n * We search for deltas _backwards_ in a list sorted by type and\n * by size, so that we see progressively smaller and smaller files.\n@@ -1348,7 +1366,9 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \n \t/* Load data if not already done */\n \tif (!trg->data) {\n+\t\tread_lock();\n \t\ttrg->data = read_sha1_file(trg_entry->idx.sha1, &type, &sz);\n+\t\tread_unlock();\n \t\tif (!trg->data)\n \t\t\tdie(\"object %s cannot be read\",\n \t\t\t sha1_to_hex(trg_entry->idx.sha1));\n@@ -1358,7 +1378,9 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t\t*mem_usage += sz;\n \t}\n \tif (!src->data) {\n+\t\tread_lock();\n \t\tsrc->data = read_sha1_file(src_entry->idx.sha1, &type, &sz);\n+\t\tread_unlock();\n \t\tif (!src->data)\n \t\t\tdie(\"object %s cannot be read\",\n \t\t\t sha1_to_hex(src_entry->idx.sha1));\n@@ -1521,6 +1543,56 @@ static void find_deltas(struct object_entry **list, unsigned list_size,\n \tfree(array);\n }\n \n+#ifdef THREADED_DELTA_SEARCH\n+\n+struct thread_params {\n+\tpthread_t thread;\n+\tstruct object_entry **list;\n+\tunsigned list_size;\n+\tunsigned nr_deltas;\n+\tint window;\n+\tint depth;\n+};\n+\n+static void *threaded_find_deltas(void *arg)\n+{\n+\tstruct thread_params *p = arg;\n+\tif (p->list_size)\n+\t\tfind_deltas(p->list, p->list_size, p->nr_deltas,\n+\t\t\t p->window, p->depth);\n+\treturn NULL;\n+}\n+\n+static void ll_find_deltas(struct object_entry **list, unsigned list_size,\n+\t\t\t unsigned nr_deltas, int window, int depth)\n+{\n+\tstruct thread_params p[4];\n+\tint i, ret;\n+\n+\tfor (i = 0; i < 4; i++) {\n+\t\tunsigned sublist_size = list_size / (4 - i);\n+\t\tp[i].list = list;\n+\t\tp[i].list_size = sublist_size;\n+\t\tp[i].nr_deltas = nr_deltas;\n+\t\tp[i].window = window;\n+\t\tp[i].depth = depth;\n+\t\tret = pthread_create(&p[i].thread, NULL,\n+\t\t\t\t threaded_find_deltas, &p[i]);\n+\t\tif (ret)\n+\t\t\tdie(\"unable to create thread: %s\", strerror(ret));\n+\t\tlist += sublist_size;\n+\t\tlist_size -= sublist_size;\n+\t}\n+\n+\tfor (i = 0; i < 4; i++) {\n+\t\tpthread_join(p[i].thread, NULL);\n+\t}\n+}\n+\n+#else\n+#define ll_find_deltas find_deltas\n+#endif\n+\n static void prepare_pack(int window, int depth)\n {\n \tstruct object_entry **delta_list;\n@@ -1557,7 +1629,7 @@ static void prepare_pack(int window, int depth)\n \n \tif (nr_deltas) {\n \t\tqsort(delta_list, n, sizeof(*delta_list), type_size_sort);\n-\t\tfind_deltas(delta_list, n, nr_deltas, window+1, depth);\n+\t\tll_find_deltas(delta_list, n, nr_deltas, window+1, depth);\n \t}\n \tfree(delta_list);\n }\n"},{"id":"51871","messageId":"alpine.LFD.0.999.0708300033540.16727@xanadu.home","threadId":"9493","inReplyTo":"alpine.LFD.0.999.0708300005110.16727@xanadu.home","subject":"Re: performance on repack","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-08-30T04:36:13Z","receivedAt":"2007-08-30T04:36:13Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 30 Aug 2007, Nicolas Pitre wrote:\n\n> Well, here is a quick implementation of this idea for those who would \n> like to give it a try.\n[...]\n\nWell, that would help if I provided the full diff of course.\n\n---\n\ndiff --git a/Makefile b/Makefile\nindex 4eb4637..c3c6e68 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -122,6 +122,9 @@ all::\n # If not set it defaults to the bare 'wish'. If it is set to the empty\n # string then NO_TCLTK will be forced (this is used by configure script).\n #\n+# Define THREADED_DELTA_SEARCH if you have pthreads and wish to exploit\n+# parallel delta searching when packing objects.\n+#\n \n GIT-VERSION-FILE: .FORCE-GIT-VERSION-FILE\n \t@$(SHELL_PATH) ./GIT-VERSION-GEN\n@@ -662,6 +665,11 @@ ifdef NO_HSTRERROR\n \tCOMPAT_OBJS += compat/hstrerror.o\n endif\n \n+ifdef THREADED_DELTA_SEARCH\n+\tBASIC_CFLAGS += -DTHREADED_DELTA_SEARCH\n+\tEXTLIBS += -lpthread\n+endif\n+\n ifeq ($(TCLTK_PATH),)\n NO_TCLTK=NoThanks\n endif\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 9b3ef94..7d68f82 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -15,6 +15,10 @@\n #include \"list-objects.h\"\n #include \"progress.h\"\n \n+#ifdef THREADED_DELTA_SEARCH\n+#include \n+#endif\n+\n static const char pack_usage[] = \"\\\n git-pack-objects [{ -q | --progress | --all-progress }] \\n\\\n \t[--max-pack-size=N] [--local] [--incremental] \\n\\\n@@ -78,7 +82,6 @@ static unsigned long delta_cache_size = 0;\n static unsigned long max_delta_cache_size = 0;\n static unsigned long cache_max_small_delta_size = 1000;\n \n-static unsigned long window_memory_usage = 0;\n static unsigned long window_memory_limit = 0;\n \n /*\n@@ -1291,6 +1294,20 @@ static int delta_cacheable(unsigned long src_size, unsigned long trg_size,\n \treturn 0;\n }\n \n+#ifdef THREADED_DELTA_SEARCH\n+\n+static pthread_mutex_t read_sha1_file_mutex = PTHREAD_MUTEX_INITIALIZER;\n+\n+#define read_lock()\t\tpthread_mutex_lock(&read_sha1_file_mutex)\n+#define read_unlock()\t\tpthread_mutex_unlock(&read_sha1_file_mutex)\n+\n+#else\n+\n+#define read_lock()\t\t0\n+#define read_unlock()\t\t0\n+\n+#endif\n+\n /*\n * We search for deltas _backwards_ in a list sorted by type and\n * by size, so that we see progressively smaller and smaller files.\n@@ -1300,7 +1317,7 @@ static int delta_cacheable(unsigned long src_size, unsigned long trg_size,\n * one.\n */\n static int try_delta(struct unpacked *trg, struct unpacked *src,\n-\t\t unsigned max_depth)\n+\t\t unsigned max_depth, unsigned long *mem_usage)\n {\n \tstruct object_entry *trg_entry = trg->entry;\n \tstruct object_entry *src_entry = src->entry;\n@@ -1313,12 +1330,6 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \tif (trg_entry->type != src_entry->type)\n \t\treturn -1;\n \n-\t/* We do not compute delta to *create* objects we are not\n-\t * going to pack.\n-\t */\n-\tif (trg_entry->preferred_base)\n-\t\treturn -1;\n-\n \t/*\n \t * We do not bother to try a delta that we discarded\n \t * on an earlier try, but only when reusing delta data.\n@@ -1355,24 +1366,28 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \n \t/* Load data if not already done */\n \tif (!trg->data) {\n+\t\tread_lock();\n \t\ttrg->data = read_sha1_file(trg_entry->idx.sha1, &type, &sz);\n+\t\tread_unlock();\n \t\tif (!trg->data)\n \t\t\tdie(\"object %s cannot be read\",\n \t\t\t sha1_to_hex(trg_entry->idx.sha1));\n \t\tif (sz != trg_size)\n \t\t\tdie(\"object %s inconsistent object length (%lu vs %lu)\",\n \t\t\t sha1_to_hex(trg_entry->idx.sha1), sz, trg_size);\n-\t\twindow_memory_usage += sz;\n+\t\t*mem_usage += sz;\n \t}\n \tif (!src->data) {\n+\t\tread_lock();\n \t\tsrc->data = read_sha1_file(src_entry->idx.sha1, &type, &sz);\n+\t\tread_unlock();\n \t\tif (!src->data)\n \t\t\tdie(\"object %s cannot be read\",\n \t\t\t sha1_to_hex(src_entry->idx.sha1));\n \t\tif (sz != src_size)\n \t\t\tdie(\"object %s inconsistent object length (%lu vs %lu)\",\n \t\t\t sha1_to_hex(src_entry->idx.sha1), sz, src_size);\n-\t\twindow_memory_usage += sz;\n+\t\t*mem_usage += sz;\n \t}\n \tif (!src->index) {\n \t\tsrc->index = create_delta_index(src->data, src_size);\n@@ -1382,7 +1397,7 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t\t\t\twarning(\"suboptimal pack - out of memory\");\n \t\t\treturn 0;\n \t\t}\n-\t\twindow_memory_usage += sizeof_delta_index(src->index);\n+\t\t*mem_usage += sizeof_delta_index(src->index);\n \t}\n \n \tdelta_buf = create_delta(src->index, trg->data, trg_size, &delta_size, max_size);\n@@ -1425,68 +1440,59 @@ static unsigned int check_delta_limit(struct object_entry *me, unsigned int n)\n \treturn m;\n }\n \n-static void free_unpacked(struct unpacked *n)\n+static unsigned long free_unpacked(struct unpacked *n)\n {\n-\twindow_memory_usage -= sizeof_delta_index(n->index);\n+\tunsigned long freed_mem = sizeof_delta_index(n->index);\n \tfree_delta_index(n->index);\n \tn->index = NULL;\n \tif (n->data) {\n+\t\tfreed_mem += n->entry->size;\n \t\tfree(n->data);\n \t\tn->data = NULL;\n-\t\twindow_memory_usage -= n->entry->size;\n \t}\n \tn->entry = NULL;\n \tn->depth = 0;\n+\treturn freed_mem;\n }\n \n-static void find_deltas(struct object_entry **list, int window, int depth)\n+static void find_deltas(struct object_entry **list, unsigned list_size,\n+\t\t\tunsigned nr_deltas, int window, int depth)\n {\n-\tuint32_t i = nr_objects, idx = 0, count = 0, processed = 0;\n+\tuint32_t i = list_size, idx = 0, count = 0, processed = 0;\n \tunsigned int array_size = window * sizeof(struct unpacked);\n \tstruct unpacked *array;\n-\tint max_depth;\n+\tunsigned long mem_usage = 0;\n \n-\tif (!nr_objects)\n-\t\treturn;\n \tarray = xmalloc(array_size);\n \tmemset(array, 0, array_size);\n \tif (progress)\n-\t\tstart_progress(&progress_state, \"Deltifying %u objects...\", \"\", nr_result);\n+\t\tstart_progress(&progress_state, \"Deltifying %u objects...\", \"\", nr_deltas);\n \n \tdo {\n \t\tstruct object_entry *entry = list[--i];\n \t\tstruct unpacked *n = array + idx;\n-\t\tint j;\n-\n-\t\tif (!entry->preferred_base)\n-\t\t\tprocessed++;\n+\t\tint j, max_depth;\n \n-\t\tif (progress)\n-\t\t\tdisplay_progress(&progress_state, processed);\n-\n-\t\tif (entry->delta)\n-\t\t\t/* This happens if we decided to reuse existing\n-\t\t\t * delta from a pack. \"!no_reuse_delta &&\" is implied.\n-\t\t\t */\n-\t\t\tcontinue;\n-\n-\t\tif (entry->size < 50)\n-\t\t\tcontinue;\n-\n-\t\tif (entry->no_try_delta)\n-\t\t\tcontinue;\n-\n-\t\tfree_unpacked(n);\n+\t\tmem_usage -= free_unpacked(n);\n \t\tn->entry = entry;\n \n \t\twhile (window_memory_limit &&\n-\t\t window_memory_usage > window_memory_limit &&\n+\t\t mem_usage > window_memory_limit &&\n \t\t count > 1) {\n \t\t\tuint32_t tail = (idx + window - count) % window;\n-\t\t\tfree_unpacked(array + tail);\n+\t\t\tmem_usage -= free_unpacked(array + tail);\n \t\t\tcount--;\n \t\t}\n \n+\t\t/* We do not compute delta to *create* objects we are not\n+\t\t * going to pack.\n+\t\t */\n+\t\tif (entry->preferred_base)\n+\t\t\tgoto next;\n+\n+\t\tif (progress)\n+\t\t\tdisplay_progress(&progress_state, ++processed);\n+\n \t\t/*\n \t\t * If the current object is at pack edge, take the depth the\n \t\t * objects that depend on the current object into account\n@@ -1508,7 +1514,7 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n \t\t\tm = array + other_idx;\n \t\t\tif (!m->entry)\n \t\t\t\tbreak;\n-\t\t\tif (try_delta(n, m, max_depth) < 0)\n+\t\t\tif (try_delta(n, m, max_depth, &mem_usage) < 0)\n \t\t\t\tbreak;\n \t\t}\n \n@@ -1537,21 +1543,94 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n \tfree(array);\n }\n \n+#ifdef THREADED_DELTA_SEARCH\n+\n+struct thread_params {\n+\tpthread_t thread;\n+\tstruct object_entry **list;\n+\tunsigned list_size;\n+\tunsigned nr_deltas;\n+\tint window;\n+\tint depth;\n+};\n+\n+static void *threaded_find_deltas(void *arg)\n+{\n+\tstruct thread_params *p = arg;\n+\tif (p->list_size)\n+\t\tfind_deltas(p->list, p->list_size, p->nr_deltas,\n+\t\t\t p->window, p->depth);\n+\treturn NULL;\n+}\n+\n+static void ll_find_deltas(struct object_entry **list, unsigned list_size,\n+\t\t\t unsigned nr_deltas, int window, int depth)\n+{\n+\tstruct thread_params p[4];\n+\tint i, ret;\n+\n+\tfor (i = 0; i < 4; i++) {\n+\t\tunsigned sublist_size = list_size / (4 - i);\n+\t\tp[i].list = list;\n+\t\tp[i].list_size = sublist_size;\n+\t\tp[i].nr_deltas = nr_deltas;\n+\t\tp[i].window = window;\n+\t\tp[i].depth = depth;\n+\t\tret = pthread_create(&p[i].thread, NULL,\n+\t\t\t\t threaded_find_deltas, &p[i]);\n+\t\tif (ret)\n+\t\t\tdie(\"unable to create thread: %s\", strerror(ret));\n+\t\tlist += sublist_size;\n+\t\tlist_size -= sublist_size;\n+\t}\n+\n+\tfor (i = 0; i < 4; i++) {\n+\t\tpthread_join(p[i].thread, NULL);\n+\t}\n+}\n+\n+#else\n+#define ll_find_deltas find_deltas\n+#endif\n+\n static void prepare_pack(int window, int depth)\n {\n \tstruct object_entry **delta_list;\n-\tuint32_t i;\n+\tuint32_t i, n, nr_deltas;\n \n \tget_object_details();\n \n-\tif (!window || !depth)\n+\tif (!nr_objects || !window || !depth)\n \t\treturn;\n \n \tdelta_list = xmalloc(nr_objects * sizeof(*delta_list));\n-\tfor (i = 0; i < nr_objects; i++)\n-\t\tdelta_list[i] = objects + i;\n-\tqsort(delta_list, nr_objects, sizeof(*delta_list), type_size_sort);\n-\tfind_deltas(delta_list, window+1, depth);\n+\tnr_deltas = n = 0;\n+\n+\tfor (i = 0; i < nr_objects; i++) {\n+\t\tstruct object_entry *entry = objects + i;\n+\n+\t\tif (entry->delta)\n+\t\t\t/* This happens if we decided to reuse existing\n+\t\t\t * delta from a pack. \"!no_reuse_delta &&\" is implied.\n+\t\t\t */\n+\t\t\tcontinue;\n+\n+\t\tif (entry->size < 50)\n+\t\t\tcontinue;\n+\n+\t\tif (entry->no_try_delta)\n+\t\t\tcontinue;\n+\n+\t\tif (!entry->preferred_base)\n+\t\t\tnr_deltas++;\n+\n+\t\tdelta_list[n++] = entry;\n+\t}\n+\n+\tif (nr_deltas) {\n+\t\tqsort(delta_list, n, sizeof(*delta_list), type_size_sort);\n+\t\tll_find_deltas(delta_list, n, nr_deltas, window+1, depth);\n+\t}\n \tfree(delta_list);\n }\n \n"},{"id":"51921","messageId":"9e4733910708300917w46d25c61n387e89dc3b2985f9@mail.gmail.com","threadId":"9493","inReplyTo":"alpine.LFD.0.999.0708300033540.16727@xanadu.home","subject":"Re: performance on repack","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-08-30T16:17:26Z","receivedAt":"2007-08-30T16:17:26Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"Practicing on the kernel, without the patch:\nQ6600 with 4GB RAM\n\njonsmirl@terra:/home/linux$ time git repack -a -f --window=200 --depth=200\nGenerating pack...\nCounting objects: 518288\nDone counting 546466 objects.\nDeltifying 546466 objects...\n 100% (546466/546466) done\nWriting 546466 objects...\n 100% (546466/546466) done\nTotal 546466 (delta 452329), reused 0 (delta 0)\nPack pack-04c98effa112233951acbb2d8486eefac17a5a97 created.\n\nreal 16m27.752s\nuser 16m23.829s\nsys 0m2.192s\n\nWith the patch it didn't balance very well. First two threads finished\nin 2min, thrid in 5min, fourth in 10min.\n\nSo for fun I set it up to 16 threads, that kept all fours cores\nrunning until the end. It added 1:20 in overhead, but it finished in\n5m vs 16:30 unthreaded. Threading is an obvious win for this code.\n\njonsmirl@terra:/home/linux$ time git repack -a -f --window=200 --depth=200\nGenerating pack...\nCounting objects: 502267\nDone counting 546466 objects.\nDeltifying 545660 objects...\nDeltifying 545660 objects...\nDeltifying 545660 objects...\nDeltifying 545660 objects...\nDeltifying 545660 objects...\nDeltifying 545660 objects...\nDeltifying 545660 objects...\nDeltifying 545660 objects...\nDeltifying 545660 objects...\nDeltifying 545660 objects...\nDeltifying 545660 objects...\nDeltifying 545660 objects...\nDeltifying 545660 objects...\nDeltifying 545660 objects...\nDeltifying 545660 objects...\nDeltifying 545660 objects...\n 6% (34104/545660) done\n 6% (34099/545660) done\n 1% (6929/545660) donee\n 5% (30037/545660) done\n 6% (34101/545660) done\n 4% (25222/545660) done\n 6% (34102/545660) done\n 3% (19999/545660) done\n 6% (34102/545660) done\n 4% (27203/545660) done\n 6% (34102/545660) done\n 4% (23377/545660) done\n 6% (34042/545660) done\n 6% (34099/545660) done\n 6% (32740/545660) done\n\n\nreal 5m0.360s\nuser 17m41.822s\nsys 0m5.596s\njonsmirl@terra:/home/linux$\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"52153","messageId":"9e4733910709011454w630c53ecj67d7980838b729c@mail.gmail.com","threadId":"9493","inReplyTo":"alpine.LFD.0.999.0708300033540.16727@xanadu.home","subject":"Re: performance on repack","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-09-01T21:54:31Z","receivedAt":"2007-09-01T21:54:31Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/30/07, Nicolas Pitre wrote:\n> On Thu, 30 Aug 2007, Nicolas Pitre wrote:\n>\n> > Well, here is a quick implementation of this idea for those who would\n> > like to give it a try.\n> [...]\n\n\nAppears to be broken for a push.\n\njonsmirl@terra:~/mpc5200b$ git push dreamhost\nupdating 'refs/remotes/linus/master' using 'refs/heads/master'\n from d1caeb02b17c6bc215a9a40a98a1beb92dcbd310\n to 40ffbfad6bb79a99cc7627bdaca0ee22dec526f6\nGenerating pack...\nCounting objects: 1\nDone counting 3255 objects.\nResult has 1997 objects.\nDeltifying 398 objects...\nDeltifying 398 objects...\nDeltifying 398 objects...\nDeltifying 398 objects...\nDeltifying 398 objects...\nDeltifying 398 objects...\nDeltifying 398 objects...\nDeltifying 398 objects...\nDeltifying 398 objects...\nDeltifying 398 objects...\nDeltifying 398 objects...\nDeltifying 398 objects...\nDeltifying 398 objects...\nDeltifying 398 objects...\nDeltifying 398 objects...\nDeltifying 398 objects...\n 0% (2/398) donee\n 1% (4/398) donee\n 11% (47/398) done\n 3% (12/398) done\n 2% (8/398) donee\n\n 12% (49/398) done\n 17% (69/398) done\n 1% (4/398) donee\n 25% (100/398) done\n 19% (77/398) donee\n 23% (94/398) done\n 21% (84/398) done\n 25% (100/398) done\n 2% (10/398) done\n 1% (6/398) done\nerror: pack-objects died with strange error\nunpack eof before pack header was fully read\nng refs/remotes/linus/master n/a (unpacker error)\nerror: failed to push to 'ssh://jonsmirl1@git.digispeaker.com/~/mpc5200b.git'\njonsmirl@terra:~/mpc5200b$\n\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"}]}