From 6d6d06c9012e96d74e9ea7aeeb6ce6dcd1a11b0f Mon Sep 17 00:00:00 2001 From: Michael Haggerty Date: Tue, 25 Nov 2014 09:02:31 +0100 Subject: [PATCH] prune_remote(): sort delete_refs_list references en masse Inserting items into a list in sorted order is O(N^2) whereas appending them unsorted and then sorting the list all at once is O(N lg N). string_list_insert() also removes duplicates, and this change loses that functionality. But the strings in this list, which ultimately come from a for_each_ref() iteration, cannot contain duplicates. Signed-off-by: Michael Haggerty Reviewed-by: Jonathan Nieder Signed-off-by: Junio C Hamano --- builtin/remote.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/builtin/remote.c b/builtin/remote.c index d5a5a1663b..7d5c8d2074 100644 --- a/builtin/remote.c +++ b/builtin/remote.c @@ -1341,8 +1341,9 @@ static int prune_remote(const char *remote, int dry_run) const char *refname = states.stale.items[i].util; delete_refs[i] = refname; - string_list_insert(&delete_refs_list, refname); + string_list_append(&delete_refs_list, refname); } + sort_string_list(&delete_refs_list); if (!dry_run) { struct strbuf err = STRBUF_INIT; -- 2.11.4.GIT