[PATCH 05/16] bisect: get rid of recursion in count_distance()
- From
Stephan Beyer <s-beyer@gmx.net>
- Date
- Feb 26, 2016, 02:04 UTC
- Message-ID
- <1456452282-10325-6-git-send-email-s-beyer@gmx.net>
- In-Reply-To
- <1456452282-10325-1-git-send-email-s-beyer@gmx.net>
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-beyer@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