walker: avoid quadratic list insertion in mark_complete

Similar to 16445242 (fetch-pack: avoid quadratic list insertion in
mark_complete), sort only after all refs are collected instead of while
inserting.  The result is the same, but it's more efficient that way.
The difference will only be measurable in repositories with a large
number of refs.

Signed-off-by: Rene Scharfe <l.s.r@web.de>
Acked-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/walker.c b/walker.c
index 633596e06fcaa1154980f95c858c61379c968d49..0b5ee3c92e5ebc2a04215b4181d04123091e02f3 100644 (file)
--- a/walker.c
+++ b/walker.c
@@ -204,7 +204,7 @@ static int mark_complete(const char *path, const unsigned char *sha1, int flag,
        struct commit *commit = lookup_commit_reference_gently(sha1, 1);
        if (commit) {
                commit->object.flags |= COMPLETE;
-               commit_list_insert_by_date(commit, &complete);
+               commit_list_insert(commit, &complete);
        }
        return 0;
 }
@@ -269,8 +269,10 @@ int walker_fetch(struct walker *walker, int targets, char **target,
                }
        }
 
-       if (!walker->get_recover)
+       if (!walker->get_recover) {
                for_each_ref(mark_complete, NULL);
+               commit_list_sort_by_date(&complete);
+       }
 
        for (i = 0; i < targets; i++) {
                if (interpret_target(walker, target[i], &sha1[20 * i])) {