Re: [PATCH 09/10] Introduce get_octopus_merge_bases() in commit.c

From: Junio C Hamano <gitster@pobox.com>
Date: Jun 6, 2008, 15:36 UTC
Message-ID: <7vy75ivamo.fsf@gitster.siamese.dyndns.org>
In-Reply-To: <alpine.DEB.1.00.0806061316350.1783@racer>

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

> Clever, but for performance reasons I think it might be better to use a 
> commit list here.

Why? We do not iterate this that many times, and you do not gain much from extra allocations of commit_list structure you would need to do.

Show 11 quoted lines

>>  	one->object.flags |= PARENT1;
>> -	two->object.flags |= PARENT2;
>>  	insert_by_date(one, &list);
>> -	insert_by_date(two, &list);
>> +	for (i = 0; i < n; i++) {
>> +		twos[i]->object.flags |= PARENT2;
>> +		insert_by_date(twos[i], &list);
>> +	}
>
> Ah, now that is clever: I thought we would get into a lot of problems 
> because we would need a bit for every initial commit.

That's not coming from being _clever_, but from solving a different problem than what you thought we are solving. This is _not_ computing the "base of all of them" as "git-show-branch --merge-base" computes.

Instead, this is "compute '2' given C and A+B", without actually having to have a commit T(A,B), for a merge to create T(A,B,C).

Show 5 quoted lines

>           o---o---A
>          /         .
>     ----1---2---B...T(A,B)
>              \       .
>               o---C...T(A,B,C)

Instead of fabricating a commit T(A,B) and drop it as "two", you drop "A" and "B" both marked as PARENT2 into the list and have the logic traverse as before.

The purpose of this exercise is not doing the merge base computation for an octopus in one round. In fact, you do _not_ want to compute it upfront. Re-read the original message the above picture comes from to remind you of why (and the loop with a big comment at the bottom of git-merge-octopus). This is for a better computation of $MRC in each round there. .