Re: three-way diff performance problem

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Jul 21, 2009, 19:31 UTC
Message-ID: <alpine.LFD.2.01.0907211225220.19335@localhost.localdomain>
In-Reply-To: <7v7hy1g7vg.fsf@alter.siamese.dyndns.org>

On Tue, 21 Jul 2009, Junio C Hamano wrote:

> 
> What's that cmovne?

It's "conditional move if not equal".

So the source code is

                /* We cannot squash it with earlier one */
                for (lline = sline->lost_head;
                     lline;
                     lline = lline->next)
                        if (lline->parent_map & this_mask)
                                last_one = lline;

adn the compiler has generated this:

	loop:
		test   %r14,0x10(%rdx)
		cmovne %rdx,%rcx
		mov    (%rdx),%rdx
		test   %rdx,%rdx
		jne loop

from it. In the above, '%r14' contains this_mask, and '%rcx' contains 'last_line' and '%rdx' contains 'lline'.

So:

 - test   %r14,0x10(%rdx)

   test "this_mask & lline->parent_map"

 - cmovne %rdx,%rcx

   "if the test above was non-zero, then last_one = lline"

 - mov    (%rdx),%rdx

   "lline = lline->next"

 - test   %rdx,%rdx

   "is lline NULL"

 - jne loop

   no, continue.

Show 12 quoted lines

> The function append_lost() is the meat of combining.  When you have seen
> a hunk like this:
> 
>     @@ -l,k +m,n @@
>     -lost line
>     -another lost line
>      common line
>     +added line
> 
> We queue the lost lines in front of a surviving line (that is sline that
> points at "common line").  "lost line" and "another lost line" are stored
> in lline (lost line) and they are queued to sline->lost_head.

Right. And "sline->lost_head" is going to have over a _million_ entries.

So each time you add one, we'll traverse that loop a million times. For each new entry. End result: that loop gets executed on the order of a million million times. It doesn't help that the compiler made it be very efficient code ;(

			Linus