[PATCH 15/16] bisect: compute best bisection in compute_relevant_weights()

[Stephan Beyer <s-beyer@xxxxxxx>]

This commit gets rid of the O(#commits) extra overhead of
the best_bisection() function.

Signed-off-by: Stephan Beyer <s-beyer@xxxxxxx>
---
 bisect.c | 43 ++++++++++++++++++-------------------------
 1 file changed, 18 insertions(+), 25 deletions(-)

diff --git a/bisect.c b/bisect.c
index 827a82a..185a3cf 100644
--- a/bisect.c
+++ b/bisect.c
@@ -27,6 +27,8 @@ static int total;
 
 static unsigned marker;
 
+static struct commit_list best_bisection;
+
 struct node_data {
 	int weight;
 	unsigned marked;
@@ -73,6 +75,14 @@ static inline int distance_direction(struct commit *commit)
 	return 0;
 }
 
+static inline void update_best_bisection(struct commit *commit)
+{
+	if (distance_direction(commit) >= 0
+	 && node_data(commit)->weight > node_data(best_bisection.item)->weight) {
+		best_bisection.item = commit;
+	}
+}
+
 static int compute_weight(struct commit *entry)
 {
 	int nr = 0;
@@ -153,29 +163,6 @@ static void show_list(const char *debug, int counted,
 }
 #endif /* DEBUG_BISECT */
 
-static struct commit_list *best_bisection(struct commit_list *list)
-{
-	struct commit_list *p, *best;
-	int best_distance = -1;
-
-	best = list;
-	for (p = list; p; p = p->next) {
-		int distance;
-		unsigned flags = p->item->object.flags;
-
-		if (flags & TREESAME)
-			continue;
-		distance = get_distance(p->item);
-		if (distance > best_distance) {
-			best = p;
-			best_distance = distance;
-		}
-	}
-
-	best->next = NULL;
-	return best;
-}
-
 struct commit_dist {
 	struct commit *commit;
 	int distance;
@@ -403,6 +390,7 @@ static void bfs_up_to_merges(struct commit_list *queue,
 			}
 		}
 
+		update_best_bisection(top);
 		pop_commit(&queue);
 	}
 }
@@ -459,8 +447,10 @@ static int find_new_queue_from_merges(struct commit_list **queue,
 static void compute_merge_weights(struct commit_list *merges)
 {
 	struct commit_list *p;
-	for (p = merges; p; p = p->next)
+	for (p = merges; p; p = p->next) {
 		compute_weight(p->item);
+		update_best_bisection(p->item);
+	}
 }
 
 static void modified_bfs(struct commit_list *queue)
@@ -489,6 +479,9 @@ static void compute_relevant_weights(struct commit_list *list,
 	struct commit_list *p;
 	struct commit_list *sources = build_reversed_dag(list, weights);
 
+	best_bisection.item = sources->item;
+	best_bisection.next = NULL;
+
 	for (p = sources; p; p = p->next)
 		node_data(p->item)->weight = 1;
 	modified_bfs(sources);
@@ -541,7 +534,7 @@ struct commit_list *find_bisection(struct commit_list *list,
 		best = best_bisection_sorted(list);
 	} else {
 		compute_relevant_weights(list, weights);
-		best = best_bisection(list);
+		best = &best_bisection;
 	}
 	assert(best);
 	*reaches = node_data(best->item)->weight;
-- 
2.7.1.354.gd492730.dirty

--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html