{"thread":{"id":"19390","subject":"On data structures and parallelism","startedAt":"2009-05-17T15:23:35Z","lastAt":"2009-05-17T20:35:44Z","messageCount":5,"participants":["Heikki Orsila","Linus Torvalds","david@lang.hm"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"114135","messageId":"20090517152335.GC11543@zakalwe.fi","threadId":"19390","inReplyTo":null,"subject":"On data structures and parallelism","fromName":"Heikki Orsila","fromEmail":"shdl@zakalwe.fi","sentAt":"2009-05-17T15:23:35Z","receivedAt":"2009-05-17T15:23:35Z","isPatch":false,"sender":{"key":"shdl@zakalwe.fi","avatar":null},"body":"There was an interesting discussion at\n\nhttp://realworldtech.com/forums/index.cfm?action=detail&id=98909&threadid=98430&roomid=2\n\nthat involves DAGs and decompression in Git. The problem is achieving \nparallelism. The following comment was made:\n\n\"And is it possible to store the block pointers from one object to \nanother in uncompressed form?\"\n\nIs there a case in Git where an \"object\" could store SHA1 in \nuncompressed format, allowing prefetching the next object in chain \nbefore uncompressing the current object? Prefetching could increase \nparallelism (and speedup) in some cases.\n\nA quick glance at Git's source code showed that commit objects are \ncompressed. Having even a single parent SHA1 in uncompressed format \nwould allow some prefetching. All but perhaps a few objects contain at \nleast one parent SHA1 :-)\n\n-- \nHeikki Orsila\nheikki.orsila@iki.fi\nhttp://www.iki.fi/shd\n"},{"id":"114139","messageId":"alpine.LFD.2.01.0905170950230.3301@localhost.localdomain","threadId":"19390","inReplyTo":"20090517152335.GC11543@zakalwe.fi","subject":"Re: On data structures and parallelism","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-05-17T17:06:26Z","receivedAt":"2009-05-17T17:06:26Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 17 May 2009, Heikki Orsila wrote:\n>\n> There was an interesting discussion at\n> \n> http://realworldtech.com/forums/index.cfm?action=detail&id=98909&threadid=98430&roomid=2\n> \n> that involves DAGs and decompression in Git. The problem is achieving \n> parallelism. The following comment was made:\n> \n> \"And is it possible to store the block pointers from one object to \n> another in uncompressed form?\"\n\nFor the biggest form of this, we actually already do.\n\nThe single biggest win of compression is the delta-compression: the \nregular zlib compression is generally about a factor-of-two for unpacked \nand \"base\" delta entries, but much less for already delta-compressed \nentries. In comparison, the delta-compression is likely about a factor of \n10 or more.\n\nAnd the delta compression already has the SHA1 pointer to the delta base \nentry uncompressed, but the compression is serialized by the fact that we \nneed to uncompress the base entry in order to then apply a delta on top of \nit.\n\nNow, there's no question that we could have higher levels of parallelism \nby walking multiple such chains in parallel (we don't always have more \nthan one chain to walk, but sometimes we do). But as I point out in that \nthread, we currently don't have any locking for the core object \ndatastructures, and adding that locking would likely slow down things more \nthan it speeds things up for the normal case.\n\nFor 'git fsck', we could speed things up a lot by doing parallel work - \nand we wouldn't need to have anything else uncompressed, we could just \ntake advantage of the fact that we could try to uncompress the different \ndelta chains in parallel. And yes, fsck is really slow, but on the other \nhand, it's something that most people never do, and I do about once a \nmonth. The fact that it takes four minutes rather than one is not a big \ndeal.\n\nThere are other forms of compression where the SHA1 pointers are inside \nthe compressed data (the \"regular\" commit->{commit,tree} relationships and \ntree->{anything} cases).\n\nAnd yes, we could probably get rid of at least the zlib compression in \nsome of that. Much of that data doesn't even compress very well (SHA1's \nare basically uncompressible), and the compression is done largely because \nwe have one unified interface for everything (so the basic object code \ndoesn't need to care about different object types or different formats: \nit's all just binary data with a magic header to it).\n\nBut in that case, we'd probably not want to keep a separate uncompressed \ntree, we'd just decide that \"compression is too expensive to be worth it\".\n\nThat said, on my laptops, CPU time really _never_ is the issue. Every \nsingle time something is slow, the issue is a slow 4200rpm disk that may \nget 25MB/s off it for linear things in the best case, but seeks take \nmilliseconds and any kind of random access will just kill performance.\n\nSo in the big picture, I suspect even the wasted CPU-time is worth it. It \nmakes some operations slower, but anything that makes the on-disk data \ndenser is good. Because the case I end up caring most about is always the \nuncached case.\n\n\t\t\tLinus\n"},{"id":"114140","messageId":"alpine.LFD.2.01.0905171038320.3301@localhost.localdomain","threadId":"19390","inReplyTo":"alpine.LFD.2.01.0905170950230.3301@localhost.localdomain","subject":"Re: On data structures and parallelism","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-05-17T17:46:29Z","receivedAt":"2009-05-17T17:46:29Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 17 May 2009, Linus Torvalds wrote:\n> \n> That said, on my laptops, CPU time really _never_ is the issue. Every \n> single time something is slow, the issue is a slow 4200rpm disk that may \n> get 25MB/s off it for linear things in the best case, but seeks take \n> milliseconds and any kind of random access will just kill performance.\n\nSide note - I've several times desperately tried to see if IO parallelism \nhelps. It doesn't. Some drives do better if they get many independent \nreads and can just do them concurrently. Sadly, that's pretty rare for \nreads on rotational media, and impossible with legacy IDE drives (that \ndon't have the ability to do tagged queueing). \n\nSo when I try to do IO in parallel (which git does support for many \noperations), that just makes the whole system come to a screeching halt \nbecause it now seeks around the disk a lot more. A similar issue that \noften kill parallelism on CPU's (bad cache behavior, and lots of \noutstanding memory requests) kills parallelism on disks too - disk \nperformance simply is much _better_ if you do serial things than if you \ntry to parallelize the same work.\n\nIt would be different if I had a fancy high-end RAID system with tagged \nqueueing and lots of spare bandwidth that could be used in parallel. But \nthat's not what the git usage scenario often is. All the people pushing \nmulti-core seem to always ignore the big issues, and always working on \nnice trivial problems with a small and well-behaved \"kernel\" that has no \nIO and preferably didn't cache well even when single-threaded (ie \n\"streaming\" data).\n\n\t\t\tLinus\n"},{"id":"114143","messageId":"alpine.DEB.1.10.0905171230070.26653@asgard","threadId":"19390","inReplyTo":"alpine.LFD.2.01.0905171038320.3301@localhost.localdomain","subject":"Re: On data structures and parallelism","fromName":"","fromEmail":"david@lang.hm","sentAt":"2009-05-17T19:31:35Z","receivedAt":"2009-05-17T19:31:35Z","isPatch":false,"sender":{"key":"david@lang.hm","avatar":null},"body":"On Sun, 17 May 2009, Linus Torvalds wrote:\n\n> On Sun, 17 May 2009, Linus Torvalds wrote:\n>>\n>> That said, on my laptops, CPU time really _never_ is the issue. Every\n>> single time something is slow, the issue is a slow 4200rpm disk that may\n>> get 25MB/s off it for linear things in the best case, but seeks take\n>> milliseconds and any kind of random access will just kill performance.\n>\n> Side note - I've several times desperately tried to see if IO parallelism\n> helps. It doesn't. Some drives do better if they get many independent\n> reads and can just do them concurrently. Sadly, that's pretty rare for\n> reads on rotational media, and impossible with legacy IDE drives (that\n> don't have the ability to do tagged queueing).\n>\n> So when I try to do IO in parallel (which git does support for many\n> operations), that just makes the whole system come to a screeching halt\n> because it now seeks around the disk a lot more. A similar issue that\n> often kill parallelism on CPU's (bad cache behavior, and lots of\n> outstanding memory requests) kills parallelism on disks too - disk\n> performance simply is much _better_ if you do serial things than if you\n> try to parallelize the same work.\n>\n> It would be different if I had a fancy high-end RAID system with tagged\n> queueing and lots of spare bandwidth that could be used in parallel. But\n> that's not what the git usage scenario often is. All the people pushing\n> multi-core seem to always ignore the big issues, and always working on\n> nice trivial problems with a small and well-behaved \"kernel\" that has no\n> IO and preferably didn't cache well even when single-threaded (ie\n> \"streaming\" data).\n\ndo things change with SSDs? I've heard that even (especially??) with the \nIntel SSDs you want to have several operations going in paralllel to get \nthe best out of them.\n\nDavid Lang\n"},{"id":"114145","messageId":"alpine.LFD.2.01.0905171308010.3301@localhost.localdomain","threadId":"19390","inReplyTo":"alpine.DEB.1.10.0905171230070.26653@asgard","subject":"Re: On data structures and parallelism","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-05-17T20:35:44Z","receivedAt":"2009-05-17T20:35:44Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 17 May 2009, david@lang.hm wrote:\n> \n> do things change with SSDs? I've heard that even (especially??) with the Intel\n> SSDs you want to have several operations going in paralllel to get the best\n> out of them.\n\nThere's a slight, but noticeable, improvement.\n\nThis is: \"echo 3 > /proc/sys/vm/drop_caches; time git diff\" run in a loop. \n\nWith 'core.preloadindex = true':\n\n\treal\t0m1.138s\n\treal\t0m1.116s\n\treal\t0m1.132s\n\treal\t0m1.120s\n\treal\t0m1.106s\n\treal\t0m1.132s\n\nand with it set to 'false':\n\n\treal\t0m1.256s\n\treal\t0m1.258s\n\treal\t0m1.242s\n\treal\t0m1.240s\n\treal\t0m1.244s\n\treal\t0m1.242s\n\nso it's about a 10% improvement. Which is pretty good, considering \nthat\n\n (a) those disks are fast enough that even for that totally cache-cold \n     case, I get about 35% CPU utilization for the single-threaded case.\n\n     And that's despite this being a 3.2GHz Nehalem box, so 35% CPU is \n     really quite remarkably good. Om my (much slower) laptop with a \n     1.2GHz Core 2, I get 2-3% CPU-time (and the whole operation takes 20 \n     seconds).\n\n (b) Not all the IO ends up being parallelized, since there is a \n     per-directory mutex that means that even though we start 20 threads, \n     it probably gets a much smaller amount of real parallelism due to \n     locking.\n\nin general, the IO parallelization obviously helps most when the IO is \nslow _and_ overlaps perfectly. Perfect overlap doesn't end up happening \ndue to the per-directory lookup semaphore (think of it like a bank \nconflict in trying to parallelize memory accesses), but with a slow NFS \nconnection you should get reasonably close to that optimal situation.\n\nBut with a single spindle, and rotating media, there really is sadly very \nlittle room for optimization. I suspect a SATA with TCQ disk might be able \nto do _somewhat_ better than my old PATA-only laptop (discounting the fact \nthat my PATA laptop harddisk is extra slow due to being just 4200rpm: any \ndesktop disk will be much faster), but I doubt the index preloading is \nreally all that noticeable.\n\nIn fact, I just tested on another machine, and saw no difference \nwhat-so-ever. If anything, it was slightly slower. I suspect TCQ is a \nbigger win with writes.\n\n\t\t\tLinus\n"}]}