[PATCH] sha1_name: avoid quadratic list insertion in handle_one_ref

René Scharfe· Aug 21, 2014, 18:30 UTC · lore

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>
---
 sha1_name.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

Show changes to sha1_name.c +2 −1

diff --git a/sha1_name.c b/sha1_name.c
index 63ee66f..7098b10 100644
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -839,7 +839,7 @@ static int handle_one_ref(const char *path,
 	}
 	if (object->type != OBJ_COMMIT)
 		return 0;
-	commit_list_insert_by_date((struct commit *)object, list);
+	commit_list_insert((struct commit *)object, list);
 	return 0;
 }
 
@@ -1366,6 +1366,7 @@ static int get_sha1_with_context_1(const char *name,
 		if (!only_to_die && namelen > 2 && name[1] == '/') {
 			struct commit_list *list = NULL;
 			for_each_ref(handle_one_ref, &list);
+			commit_list_sort_by_date(&list);
 			return get_sha1_oneline(name + 2, sha1, list);
 		}
 		if (namelen < 3 ||

-- 
2.1.0

Jeff King· Aug 22, 2014, 04:04 UTC · re: René Scharfe · lore

Re: [PATCH] sha1_name: avoid quadratic list insertion in handle_one_ref

On Thu, Aug 21, 2014 at 08:30:29PM +0200, René Scharfe wrote:

Show 5 quoted lines

> 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.

Looks good, thanks.

I was hoping one of these would be fixing the quadratic http-push behavior I mentioned yesterday, but alas. We seem to have a lot of quadratic spots to fix. :)

-Peff

patchsha1_name: avoid quadratic list insertion in handle_one_ref