From: Junio C Hamano <gitster@pobox.com>
Date: Tue, 28 Aug 2012 23:39:11 GMT
Subject: Re: [PATCH 5/5] (BROKEN) get_merge_bases_many(): walk from many tips in parallel
Message-ID: <7vvcg2y4bk.fsf@alter.siamese.dyndns.org>
In-Reply-To: <7v8vcyzomw.fsf@alter.siamese.dyndns.org>

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

> Junio C Hamano <gitster@pobox.com> writes:
>
>> Junio C Hamano <gitster@pobox.com> writes:
>>
>>>  	for (i = 0; i < cnt; i++) {
>>> -		if (rslt[i])
>>> +		/*
>>> +		 * Is rslt[i] an ancestor of any of the others?
>>> +		 * then it is not interesting to us.
>>> +		 */
>>> +		for (j = 0; j < i; j++)
>>> +			others[j] = rslt[j];
>>> +		for (j = 1 + 1; j < cnt; j++)
>>
>> s/1 + 1/i + 1/;
>>
>> With that, all tests seem to pass ;-)
>
> "git merge-base" itself seems to have more room for improvement.
> Trying to recompute bases for recent 200 merges in the kernel
> history with the attached script does not show any improvement with
> or without the series on top of recent "master".  Correctnesswise it
> seems to be OK, though---I get byte-for-byte identical output.
>
> -- >8 --
> #!/bin/sh
>
> git rev-list --committer=torvalds@linux-foundation.org \
>     --max-parents=2 --min-parents=2 --parents v3.5..v3.6-rc2 >RL
>
> cmd='
> 	while read result parent1 parent2
> 	do
> 		$GIT merge-base $parent1 $parent2
> 	done <RL
> '
>
> GIT="rungit master" time sh -c "$cmd" >:stock
> GIT=../git.git/git time sh -c "$cmd" >:optim
> cmp :stock :optim
> -- 8< --

I have this suspicion that it is spending most of its time in
insert-by-date.  Luckily, merge_bases_many() is totally outside of
the usual revision traversal and its use of the commit list is
pretty well isolated.

Peff, can I interest you into resurrecting your $gmane/174007 and
$gmane/174008 (we do not need pop_commit_from_queue() in the latter;
everything can stay as static to commit.c for now) to see how well
priority queue based approach would perform?