Re: [PATCH 1/3] commit-reach: use one walk in remove_redundant()

From: Derrick Stolee <stolee@gmail.com>
Date: Jan 31, 2021, 03:59 UTC
Message-ID: <e5863616-ff74-88f2-3d6a-c8dbe03477fe@gmail.com>
In-Reply-To: <xmqqtur0vl7i.fsf@gitster.c.googlers.com>

On 1/28/2021 3:51 PM, Junio C Hamano wrote:

Show 16 quoted lines

> "Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:
>> +		parents = c->parents;
>> +		while (parents) {
>> +			if (!(parents->item->object.flags & STALE)) {
>> +				parents->item->object.flags |= STALE;
>> +				prio_queue_put(&queue, parents->item);
>> +			}
>> +			parents = parents->next;
>> +		}
>> +	}
> 
> So, the inner loop makes sure we won't revisit STALE parent, but
> keep digging parents we haven't seen, and stop when the generation
> is old enough.  What happens when there is no generation number
> computed yet, I wonder...  We'll keep getting infinity and dig all
> the way down to root?

If we are on commits that have no generation number yet, then we will walk until reaching commits in the commit-graph file that have a computed generation (or in the heuristic case, when we have reached all but one of the commits).

In the case of the commit-graph, all commits will have generation number "infinity". In such a case, perhaps the old algorithm _is_ the best we can do, at least for now.

The trade-off is that we might walk more commits in unusual cases with few input commits. That quadratic behavior will take over as the input size grows, no matter if there is a commit-graph or not.

I can do a big more digging into these unusual cases, especially when we cannot rely on commit-graphs being present.

One way to ensure we do not regress from the current behavior would be to condition the new algorithm with

	if (generation_numbers_enabled(the_repository))
		new_algorithm();
	else
		old_algorithm();

much like in repo_is_descendant_of().

Is that a good plan?

Thanks, -Stolee