Re: [PATCH v2 19/21] bisect: use a bottom-up traversal to find relevant weights

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

Stephan Beyer <s-beyer@gmx.net> writes:

>  struct commit_list *find_bisection(struct commit_list *list,
> @@ -470,8 +541,11 @@ struct commit_list *find_bisection(struct commit_list *list,
>  		compute_all_weights(list, weights);
>  		best = best_bisection_sorted(list);
>  	} else {
> +		int i;
>  		compute_relevant_weights(list, weights);
>  		best = best_bisection(list);
> +		for (i = 0; i < on_list; i++) /* cleanup */
> +			free_commit_list(weights[i].children);
>  	}
>  	assert(best);
>  	*reaches = node_data(best->item)->weight;

One thing I forgot to mention is that we now may want to reconsider
what the first loop in this function does.  It used to be that the
purpose of the loop is to "count the number of total and
tree-changing items on the list while reversing the list" as the
comment says.  While it is still necessary to count the items (by
the way, with 16/21 you made these two numbers identical, i.e. there
no longer is a separate 'total' but your 'total' now actually means
the number of tree-changing items), I do not know if the "reverse"
would still be a good fit for the performance characteristic of the
new algorithm.

The list-reversal there was done as an optimization to make sure
that older ones are processed early to avoid looping too much just
to follow the list to find a single-parent commit whose parent's
weight is already known, as the only meaningful optimization in the
original algorithm was the "we can increment one without doing the
costly graph re-traversal for single-strand-of-pearls".  That
optimization may no longer relevant (or it could even be harmful)
as you traverse the graph in reverse.