threads / discuss / 27835

DAG scalability (was: Git commit generation numbers)

Subject: DAG scalability (was: Git commit generation numbers)

## tl;dr

2 messages between Jul 17, 2011 and Jul 17, 2011.

replies: 1people: 2as markdown or json

Shawn Pearce· Jul 17, 2011, 22:18 UTC · lore

On Sun, Jul 17, 2011 at 12:30, Linus Torvalds <torvalds@linux-foundation.org> wrote:

> The thing is, the very basic design of git is all about *incomplete*
> DAG traversal. The DAG traversal part is pretty obvious and simple,
> but the *partial* thing really is very very important. We absolutely
> need it for reasonable scalability.

...

Show 6 quoted lines

> That's a *really* fundamental design issue in git. Performance was
> always a primary goal. And by primary, I really mean primary. As in
> "more important than just about anything else".  There were other
> primary goals, but really not very many.
>
> And there really aren't very good ways to limit DAG traversal.

What about `git clone`? We're always recomputing the entire DAG during it. For a public repository like yours that only contains public objects, its a horrible abuse of the servers that are serving the repository...

Just saying, not everything we do winds up being a partial or incomplete traversal in the name of performance. Sometimes we expend 1.5 minutes of CPU time *per request* on a busy server because we don't want a cache, but then we're off in this bike shed painting discussion about saving someone's desktop what 30 seconds of CPU time via generation numbers in commits? Ugh. Cry me a river.

Maybe I only complain about the server side utilization of clone because I run servers that have a lot of clone traffic.

-- 
Shawn.

Linus Torvalds· Jul 17, 2011, 22:25 UTC · re: Shawn Pearce · lore

Re: DAG scalability (was: Git commit generation numbers)

On Sun, Jul 17, 2011 at 3:18 PM, Shawn Pearce <spearce@spearce.org> wrote:

Show 8 quoted lines

>
> What about `git clone`?  We're always recomputing the entire DAG
> during it. For a public repository like yours that only contains
> public objects, its a horrible abuse of the servers that are serving
> the repository...
>
> Just saying, not everything we do winds up being a partial or
> incomplete traversal in the name of performance.

I don't see your point.

OF COURSE we sometimes traverse the whole tree - when we need all the data. And it's expensive in those cases, but generally those cases are also cases where the DAG traversal itself is just a tiny part of the big picture. The commits tend to be almost irrelevant to "git clone", for example: it tends to be tree and blob objects that are the biggest cost.

But there's a lot of common operations that would be much too expensive unless we had the incomplete DAG traversal code. It's what makes us able to do sub-second merges, it's what makes "gitk @{6am}.." be fast, etc etc.

My point really was that the git DAG structure is really simple. People learn about DAG's in CS courses the first year.

But the kinds of things that git does, which is to try to partition the DAG without having to walk it entirely - that's rare. I tried to find papers about optimized DAG walking, and couldn't (but so many academic papers are behind a pay-wall that I still don't know if there might be some smart person who came up with a really good algorithm for what the git-merge-base stuff does, for example)

                    Linus