Re: [PATCH] Introduce filter_independent() in commit.c

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

Miklos Vajna <vmiklos@frugalware.org> writes:

> +struct commit_list *filter_independent(unsigned char *head,
> +	struct commit_list *heads)
> +{
> +	struct commit_list *b, *i, *j, *k, *bases = NULL, *ret = NULL;
> +	struct commit_list **pptr = &ret;
> +
> +	commit_list_insert(lookup_commit(head), &heads);

Isn't the special casing of head making this function less easier to reuse
in other contexts?  "show-branch --independent" is about getting N commits
and removing commits from that set that can be reachable from another
commit, so there is no need nor reason to treat one "head" in any special
way.

> +	for (i = heads; i; i = i->next) {
> +		for (j = heads; j; j = j->next) {
> +			if (i == j)
> +				continue;
> +			b = get_merge_bases(i->item, j->item, 1);
> +			for (k = b; k; k = k->next)
> +				commit_list_insert(k->item, &bases);
> +		}
> +	}

You run (N-1)*N merge-base computation to get all pairwise merge-bases
here.  As merge-base(A,B) == merge-base(B,A), this is computing the same
thing twice.

Isn't your "b" leaking?

> +	for (i = heads; i; i = i->next) {
> +		int found = 0;
> +		for (b = bases; b; b = b->next) {
> +			if (!hashcmp(i->item->object.sha1, b->item->object.sha1)) {
> +				found = 1;

Then you see if the given heads exactly match one of the merge bases you
found earlier.  But does this have to be in a separate pass?

Isn't your "bases" list leaking?

Even though you may be able to reduce more than 25 heads, you run N^2
merge base traversals, which means 625 merge base traversals for 25 heads;
show-branch engine can do the same thing with a single traversal.

Can't we do better than O(N^2)?

Let's step back a bit and think.  You have N commits (stop thinking about
"my head and N other heads" like your function signature suggests).  For
each one, you would want to see if it is reachable from any of the other
(N-1) commits, and if so, you would exclude it from the resulting set.
And you do that for all N commits and you are done.  You can relatively
easily do this with an O(N) traversals.

Now, if you have one commit and other (N-1) commits, is there a way to
efficiently figure out if that one commit is reachable from any of the
other (N-1) commits?

If there were a merge of these other (N-1) commits, and if you compute a
merge base between that merge commit and the one commit you are looking
at, what would you get?  Yes, you will get your commit back if and only if
it is reachable from some of these (N-1) commits.

If you recall the merge-base-many patch we discussed earlier, that is
exactly what it computes, isn't it?