Re: gitk-1.0 released

On Fri, 20 May 2005, Kari Hameenaho wrote:

But that _does_ actually go back all the way in time.

It does so inside of "git-rev-tree", and that's why git-rev-tree is slow.

What you can do, is to special-case certain things that git-rev-tree does, and try to do them more efficiently.

For example, git-rev-list is much nicer to use, exactly because it does only one very particular special case of what git-rev-tree does, ie "list all revisions". Because it's a special case, you can do it incrementally.

Similarly, you _can_ actually do "git-rev-tree HEAD ^OLD_HEAD" as a special case too, and do it "as incrementally as possible". It's more complicated than the (trivial) git-rev-list, so I've not actually done it, but it's clearly important enough that I _should_ do it.

The way to do it "as incrementally as possible" is to start with the 
HEAD, and walk down and print out everything until you hit OLD_HEAD or a 
merge. Then:
 - If you hit OLD_HEAD, you're done.
 - If you hit a merge, you know the merge itself wasn't in OLD_HEAD, but 
   now one of the sides might contain OLD_HEAD which might have a merge
   pointing to the other side, so you don't know if you should show any of 
   the commits below it. What you do is:
    - walk down both paths in date order - like rev-list does - until you 
      _do_ hit OLD_HEAD. Here "date order" ends up being an approximation 
      for "how do I avoid going down a long chain that ends up already 
      being pointed to by OLD_HEAD"
    - mark everything reachable from OLD_HEAD as being uninteresting (aka 
      "seen"), and everything that reaches OLD_HEAD as being interesting
      and print it out.
    - as long as there are commits that aren't marked either uninteresting 
      _or_ interesting (they are unknown) continue to walk the commit 
      chain in date order, where the parent(s) of an uninteresting commit 
      is always uninteresting.
    - eventually, you'll have no unknowns left, and you can stop.

In the worst case, you'll end up walking back to the root (somebody did development against the root, and then merged that development up after OLD_HEAD), but that ends up being increasingly unlikely as the project grows, so in practice this kind of algorithm will always end up doign work that is comparable to the amount of development between OLD_HEAD and HEAD, and independent of the total history size.

I might have missed some detail in the above, but it should be _fairly_ straightforward to start with rev-list.c and make it generate the lists of "interesting", "uninteresting" and "unknown" commits and do the above.

Is anybody up for coding up this small exercise in graph traversal?

		Linus