Large repositories with a huge amount of merge commits in the
bisection process could lead to stack overflows in git bisect.
In order to prevent this, this commit uses an *iterative* version
for counting the number of ancestors of a commit.
Signed-off-by: Stephan Beyer <s-be...@gmx.net>
---
In the cover letter I promised that bisect will be faster.
It's not rocket science to know that replacing a simple recursion
by an iterative version involving a list (with alloc'ing and stuff)
makes the code slower.
For my git master branch test, this changed the running time
from ~50 to ~60 seconds. However, for a smaller stack size,
this changes the running time from <crash> to ~60 seconds.
That's a win ;-)
bisect.c | 55 ++++++++++++++++++++++---------------------------------
1 file changed, 22 insertions(+), 33 deletions(-)
diff --git a/bisect.c b/bisect.c
index 412e2c0..03e7660 100644
--- a/bisect.c
+++ b/bisect.c
@@ -26,33 +26,23 @@ static const char *term_good;
/* Remember to update object flag allocation in object.h */
#define COUNTED (1u<<16)
-/*
- * This is a truly stupid algorithm, but it's only
- * used for bisection, and we just don't care enough.
- *
- * We care just barely enough to avoid recursing for
- * non-merge entries.
- */
static int count_distance(struct commit_list *entry)
{
int nr = 0;
+ struct commit_list *todo = NULL;
+ commit_list_append(entry->item, &todo);
- while (entry) {
- struct commit *commit = entry->item;
- struct commit_list *p;
+ while (todo) {
+ struct commit *commit = pop_commit(&todo);
- if (commit->object.flags & (UNINTERESTING | COUNTED))
- break;
- if (!(commit->object.flags & TREESAME))
- nr++;
- commit->object.flags |= COUNTED;
- p = commit->parents;
- entry = p;
- if (p) {
- p = p->next;
- while (p) {
- nr += count_distance(p);
- p = p->next;
+ if (!(commit->object.flags & (UNINTERESTING | COUNTED))) {
+ struct commit_list *p;
+ if (!(commit->object.flags & TREESAME))
+ nr++;
+ commit->object.flags |= COUNTED;
+
+ for (p = commit->parents; p; p = p->next) {
+ commit_list_insert(p->item, &todo);
}
}
}
@@ -287,7 +277,7 @@ static struct commit_list *do_find_bisection(struct
commit_list *list,
* can reach. So we do not have to run the expensive
* count_distance() for single strand of pearls.
*
- * However, if you have more than one parents, you cannot
+ * However, if you have more than one parent, you cannot
* just add their distance and one for yourself, since
* they usually reach the same ancestor and you would
* end up counting them twice that way.
@@ -296,17 +286,16 @@ static struct commit_list *do_find_bisection(struct
commit_list *list,
* way, and then fill the blanks using cheaper algorithm.
*/
for (p = list; p; p = p->next) {
- if (p->item->object.flags & UNINTERESTING)
- continue;
- if (weight(p) != -2)
- continue;
- weight_set(p, count_distance(p));
- clear_distance(list);
+ if (!(p->item->object.flags & UNINTERESTING)
+ && (weight(p) == -2)) {
+ weight_set(p, count_distance(p));
+ clear_distance(list);
- /* Does it happen to be at exactly half-way? */
- if (!find_all && halfway(p, nr))
- return p;
- counted++;
+ /* Does it happen to be at exactly half-way? */
+ if (!find_all && halfway(p, nr))
+ return p;
+ counted++;
+ }
}
show_list("bisection 2 count_distance", counted, nr, list);
--
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
