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

From: Junio C Hamano <gitster@pobox.com>
Date: Jun 21, 2008, 09:45 UTC
Message-ID: <7vr6arazp9.fsf@gitster.siamese.dyndns.org>
In-Reply-To: <1214007784-4801-1-git-send-email-vmiklos@frugalware.org>

Miklos Vajna <vmiklos@frugalware.org> writes:

Show 7 quoted lines

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

Show 9 quoted lines

> +	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?

Show 5 quoted lines

> +	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?