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

[Stephan Beyer]

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

Signed-off-by: Stephan Beyer <s-be...@gmx.net>
---
 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 majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html