Re: [PATCH 3/3] Make clear_commit_marks() clean harder

On Mon, 3 Jul 2006, Johannes Schindelin wrote:

No, that's not the problem.

The problem is that if we unconditionally traverse parents - whether parsed or not - any merge will basically result in a 2* expansion of the working set: we'll traverse all children twice (whether they meet again or not).

So the cost of doign unconditional traversals of parents basically approaches 2^n, where 'n' is the number of merges.

Now, the fact that we only traverse parents without adding new ones (and the decision on whether it is parsed or not is irrelevant - the only relevant part being that we don't parse any _new_ ones) means that each commit itself is very cheap to traverse, but O(2^n) ends up meaning that even a small constant will eventually be pretty big.

The proper fix is _not_ to add the "object->parsed" check (which is silly, wrong, and doesn't fix anything at all), but to add a check for whether the object has been seen or not.

In the case of clearing flags, you have two choices:

 - _set_ a new flag ("already cleared"). This would work - once - but is 
   obviously pretty bad.

   This is what we do in all the other cases. We usually call the flag 
   SEEN or similar.

 - depend on the flags being "dense", and saying that we depend on the 
   fact that in order for any of the flags to have been set in the first 
   place, at least _one_ of them needs to be set in the path leading up to 
   that commit.

Now, for the specific case of get_merge_bases(), the flags _are_ dense. Individual flags may not be (eg the "UNINTERESTING" flag, whatever it's called, will not be dense), but the question of "is _any_ of the flags we care about set" _will_ be dense.

As such, adding a

	/* Have we already cleared this? */
	if (!(mask & object->flags))
		return;
	object->flags &= ~mask;

to the traversal function will fix the O(m+2^n) behaviour, and turn the traversal into O(m+n) (where "n" is the number of merges, and "m" is the total number of commits).

		Linus