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

[Linus Torvalds <torvalds@linux-foundation.org>]

On Thu, 31 Jul 2008, Junio C Hamano wrote:
> 
> 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:

> $ 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