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

[Junio C Hamano <gitster@pobox.com>]

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.

>>  	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).

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