[PATCH] Modify git-rev-list ... [ resend to fix whitespace mangle ]

[Jon Seymour <jon.seymour@gmail.com>]

On 6/4/05, Junio C Hamano <junkio@cox.net> wrote:
> I only fast-forwarded over maths on your website about the epoch
> ordering, but what the patch tries to do sounds right to me.
>
> One nitpick request I have is to name its test t6000 series, to
> match the naming convention Pasky came up with?
>
>         First digit tells the family:
>
>                 0 - the absolute basics and global stuff
>                 1 - the basic commands concerning database
>                 2 - the basic commands concerning the working tree
>                 3 - the other basic commands (e.g. ls-files)
>                 4 - the diff commands
>                 5 - the pull and exporting commands
>                 6 - the revision tree commands (even e.g. merge-base)
>

Sure. I'll modify the patch and repost.

> Also I wonder what the performance implication of this patch is.
>

It actually works quite well. I took some care to make sure the
algorithm didn't have to scan the entire tree if you only want part of
it and is roughly linear in the number of edges it actually processes.
It does this by borrowing the original heuristic of a latest date
first scan, and also by accumulating "work" to do prior to propagating
it through the network. This means that most nodes are only visited (a
small-multiple of) once.

One thing to be aware of is that it does have to scan to epoch
boundaries which, in the Linux kernel, are spaced an average of 100
commits apart. The first time you run it on a cold-cache, the output
pauses for a while after the first few commits. But run it again when
the cache is warm and the performance is, IMO, quite ok.

Here are the cold-cache stats on the Linux-2.6 tree which has 1300
commits and quite a lot of merges and forks

$ time git-rev-list --merge-order --show-breaks HEAD > out 2>err

real    0m32.283s
user    0m0.135s
sys     0m0.141s

And the warm cache stats:

$ time git-rev-list --merge-order --show-breaks HEAD > out 2>err

real    0m0.181s
user    0m0.119s
sys     0m0.040s

Compared with the standard algorithm:

$ time git-rev-list HEAD > out 2>err

real    0m0.112s
user    0m0.065s
sys     0m0.032s

So, it is perhaps 50-100% slower on a warm-cache than the standard algorithm.

jon.
--
homepage: http://www.zeta.org.au/~jon/
blog: http://orwelliantremors.blogspot.com/