Re: [PATCH 7/8] combine-diff: Fast changed-to-all-parents paths scanning

From: Junio C Hamano <gitster@pobox.com>
Date: Feb 3, 2014, 23:39 UTC
Message-ID: <xmqqeh3jbwbt.fsf@gitster.dls.corp.google.com>
In-Reply-To: <xmqqk3dbbwwf.fsf@gitster.dls.corp.google.com>

Junio C Hamano <gitster@pobox.com> writes:

Show 25 quoted lines

> Kirill Smelkov <kirr@mns.spb.ru> writes:
>
>> As was recently shown (c839f1bd "combine-diff: optimize
>> combine_diff_path sets intersection"), combine-diff runs very slowly. In
>> that commit we optimized paths sets intersection, but that accounted
>> only for ~ 25% of the slowness, and as my tracing showed, for linux.git
>> v3.10..v3.11, for merges a lot of time is spent computing
>> diff(commit,commit^2) just to only then intersect that huge diff to
>> almost small set of files from diff(commit,commit^1).
>>
>> That's because at present, to compute combine-diff, for first finding
>> paths, that "every parent touches", we use the following combine-diff
>> property/definition:
>>
>>     D(A,P1...Pn) = D(A,P1) ^ ... ^ D(A,Pn)      (w.r.t. paths)
>>
>> where
>>
>>     D(A,P1...Pn) is combined diff between commit A, and parents Pi
>>
>> and
>>
>>     D(A,Pi) is usual two-tree diff Pi..A
>
> and A ^ B means what???

Silly me; obviously it is the "set intersection" operator.

We probably could instead use the "current" set of paths as literal pathspec to compute subsequent paths, i.e.

	D(A,Pi,PS) is two tree diff P1..A limited to paths PS

	D(A,P1...Pn) = D(A,P1,[]) ^
        	       D(A,P2,D(A,P1,[])) ^
                       ...
        	       D(A,Pn,D(A,P1...Pn-1))

if we did not want to reinvent the whole tree walking thing, which would add risks for new bugs and burden to maintain this and the usual two-tree diff tree walking in sync.