{"thread":{"id":"27835","subject":"DAG scalability (was: Git commit generation numbers)","startedAt":"2011-07-17T22:18:19Z","lastAt":"2011-07-17T22:25:33Z","messageCount":2,"participants":["Shawn Pearce","Linus Torvalds"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"171523","messageId":"CAJo=hJvMrW4f-4Y1czR+Mx4kA=2Po+zQQXe2iOFnF7KJ=Ou3nA@mail.gmail.com","threadId":"27835","inReplyTo":null,"subject":"DAG scalability (was: Git commit generation numbers)","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2011-07-17T22:18:19Z","receivedAt":"2011-07-17T22:18:19Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Sun, Jul 17, 2011 at 12:30, Linus Torvalds\n<torvalds@linux-foundation.org> wrote:\n> The thing is, the very basic design of git is all about *incomplete*\n> DAG traversal. The DAG traversal part is pretty obvious and simple,\n> but the *partial* thing really is very very important. We absolutely\n> need it for reasonable scalability.\n...\n> That's a *really* fundamental design issue in git. Performance was\n> always a primary goal. And by primary, I really mean primary. As in\n> \"more important than just about anything else\".  There were other\n> primary goals, but really not very many.\n>\n> And there really aren't very good ways to limit DAG traversal.\n\nWhat about `git clone`?  We're always recomputing the entire DAG\nduring it. For a public repository like yours that only contains\npublic objects, its a horrible abuse of the servers that are serving\nthe repository...\n\nJust saying, not everything we do winds up being a partial or\nincomplete traversal in the name of performance. Sometimes we expend\n1.5 minutes of CPU time *per request* on a busy server because we\ndon't want a cache, but then we're off in this bike shed painting\ndiscussion about saving someone's desktop what 30 seconds of CPU time\nvia generation numbers in commits? Ugh. Cry me a river.\n\nMaybe I only complain about the server side utilization of clone\nbecause I run servers that have a lot of clone traffic.\n\n-- \nShawn.\n"},{"id":"171524","messageId":"CA+55aFxzY6YKAzYZFVzvsraSHnkXw47M9A4Kf1d8+d+YEZchzw@mail.gmail.com","threadId":"27835","inReplyTo":"CAJo=hJvMrW4f-4Y1czR+Mx4kA=2Po+zQQXe2iOFnF7KJ=Ou3nA@mail.gmail.com","subject":"Re: DAG scalability (was: Git commit generation numbers)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2011-07-17T22:25:33Z","receivedAt":"2011-07-17T22:25:33Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"On Sun, Jul 17, 2011 at 3:18 PM, Shawn Pearce <spearce@spearce.org> wrote:\n>\n> What about `git clone`?  We're always recomputing the entire DAG\n> during it. For a public repository like yours that only contains\n> public objects, its a horrible abuse of the servers that are serving\n> the repository...\n>\n> Just saying, not everything we do winds up being a partial or\n> incomplete traversal in the name of performance.\n\nI don't see your point.\n\nOF COURSE we sometimes traverse the whole tree - when we need all the\ndata. And it's expensive in those cases, but generally those cases are\nalso cases where the DAG traversal itself is just a tiny part of the\nbig picture. The commits tend to be almost irrelevant to \"git clone\",\nfor example: it tends to be tree and blob objects that are the biggest\ncost.\n\nBut there's a lot of common operations that would be much too\nexpensive unless we had the incomplete DAG traversal code. It's what\nmakes us able to do sub-second merges, it's what makes \"gitk @{6am}..\"\nbe fast, etc etc.\n\nMy point really was that the git DAG structure is really simple.\nPeople learn about DAG's in CS courses the first year.\n\nBut the kinds of things that git does, which is to try to partition\nthe DAG without having to walk it entirely - that's rare. I tried to\nfind papers about optimized DAG walking, and couldn't (but so many\nacademic papers are behind a pay-wall that I still don't know if there\nmight be some smart person who came up with a really good algorithm\nfor what the git-merge-base stuff does, for example)\n\n                    Linus\n"}]}