Re: [PATCH v2 19/21] bisect: use a bottom-up traversal to find relevant weights
- From
Junio C Hamano <gitster@pobox.com>
- Date
- Apr 26, 2016, 18:27 UTC
- Message-ID
- <xmqqh9eogr90.fsf@gitster.mtv.corp.google.com>
- In-Reply-To
- <1460294354-7031-20-git-send-email-s-beyer@gmx.net>
Stephan Beyer <s-beyer@gmx.net> writes:
Show 13 quoted lines
> 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.