On Sat, 9 Sep 2006, Jeff King wrote: > > The problem you describe seems to come from doing a depth-first display > of each branch No, not at all. We _don't_ do depth-first, or breadth-first. The thing is, neither would really work, since the "distance" between commits is very variable. Instead, the rule is always to try to traverse the tree in date order. That's most likely the closest order to what you want - it ends up being breadth-first if there is a lot of concurrent work, and if there is one old branch and one new branch, we'll look at the new one first, and approximate depth-first there. > Why not look at the tip of each "active" branch > simultaneously and pick the one with the most recent date? Which is _exactly_ what we do. However, it's just a heuristic. "Most recent date" is not well-defined in a distributed environment that doesn't have a global clock. If somebody does commits on a machine that has the clock just set wrong, "most recent" may well not be _really_ recent. So all the algorithms are actually very careful to just use the date as a heuristic. They have real guarantees, but they aren't about the ordering. The ordering is just used as a way to have _some_ non-random and likely good order to traverse the DAG in. Doing it depth-first would suck (you'd always reach the root before you reach a lot of much more interesting commits), and breadth-first is not well-defined either, since one "level" can be a year old for one parent, and a day old for another. So you could kind of think of the ordering as "breadth-first, modified by date" kind of thing. Linus - To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html