Re: [PATCH v3-wip] revision traversal: show full history with merge simplification

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Jul 31, 2008, 22:26 UTC
Message-ID: <alpine.LFD.1.10.0807311513020.3277@nehalem.linux-foundation.org>
In-Reply-To: <7vabfxyacx.fsf_-_@gitster.siamese.dyndns.org>

On Thu, 31 Jul 2008, Junio C Hamano wrote:

Show 5 quoted lines

> 
> The same query with 's/| head -n 1/>/dev/null' is more expensive.  In fact
> it is much more expensive than the non-incremental one (v2), and about
> three times more expensive than non-limiting --full-history for explaining
> the history of kernel/printk.c.

Hmm? Why is that, exactly? Does it walk over the same commit over and over and over again or something?

Can you combine --simplify-merges and --topo-order to get a fast version again (since --topo-order will force a non-incrmental walk)?

I have this suspicion (gut feel only, not anything else to back it up) that for any complex global history, you'll always end up having a lot of merges "live" and have a hard time getting a lot of early output.

That may be why you get a fairly big delay before even the first commit:

Show 8 quoted lines

> $ time sh -c 'git log --pretty=oneline --abbrev-commit \
>        --simplify-merges --parents \
>        -- kernel/printk.c | head -n 1'
> 5dfb66b... 1d9b9f6... c9272c4... Merge branch 'for-linus' of git://git.o-hand.com/linux-mfd
>
> real    0m0.344s
> user    0m0.324s
> sys     0m0.020s

>From your previous email:

   $ git rev-list --parents --full-history --topo-order HEAD -- kernel/printk.c
   3.75user 0.47system 0:04.22elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k

so that's less than 10% of the whole time, but it's still a _lot_ slower than the

   $ git rev-list --parents --full-history HEAD -- kernel/printk.c | head -n 200
   0.16user 0.02system 0:00.18elapsed 103%CPU (0avgtext+0avgdata 0maxresident)k

and that was the first 200 commits, not just the first one. I bet you got the first one in about a tenth of that time - so I'm guessing 0.016s (also based on my own testing - it's below 0.01s here, but I'm willing to bet my machine is faster than yours is).

So getting the first one with "--simplify-merges" was really a _lot_ slower.

That said, I'm a huge beliver in the incremental approach - it just looks like this is potentially "just barely incremental" in practice.

Of course, with a more linear history than the kernel, your approach probably works better.

			Linus