{"thread":{"id":"37393","subject":"[PATCH] sha1_name: avoid quadratic list insertion in handle_one_ref","startedAt":"2014-08-21T18:30:29Z","lastAt":"2014-08-22T04:04:46Z","messageCount":2,"participants":["René Scharfe","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"248072","messageId":"53F63AC5.80901@web.de","threadId":"37393","inReplyTo":null,"subject":"[PATCH] sha1_name: avoid quadratic list insertion in handle_one_ref","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2014-08-21T18:30:29Z","receivedAt":"2014-08-21T18:30:29Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Similar to 16445242 (fetch-pack: avoid quadratic list insertion in\nmark_complete), sort only after all refs are collected instead of while\ninserting.  The result is the same, but it's more efficient that way.\nThe difference will only be measurable in repositories with a large\nnumber of refs.\n\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\n sha1_name.c | 3 ++-\n 1 file changed, 2 insertions(+), 1 deletion(-)\n\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 63ee66f..7098b10 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -839,7 +839,7 @@ static int handle_one_ref(const char *path,\n \t}\n \tif (object->type != OBJ_COMMIT)\n \t\treturn 0;\n-\tcommit_list_insert_by_date((struct commit *)object, list);\n+\tcommit_list_insert((struct commit *)object, list);\n \treturn 0;\n }\n \n@@ -1366,6 +1366,7 @@ static int get_sha1_with_context_1(const char *name,\n \t\tif (!only_to_die && namelen > 2 && name[1] == '/') {\n \t\t\tstruct commit_list *list = NULL;\n \t\t\tfor_each_ref(handle_one_ref, &list);\n+\t\t\tcommit_list_sort_by_date(&list);\n \t\t\treturn get_sha1_oneline(name + 2, sha1, list);\n \t\t}\n \t\tif (namelen < 3 ||\n-- \n2.1.0\n"},{"id":"248097","messageId":"20140822040446.GB27992@peff.net","threadId":"37393","inReplyTo":"53F63AC5.80901@web.de","subject":"Re: [PATCH] sha1_name: avoid quadratic list insertion in handle_one_ref","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-22T04:04:46Z","receivedAt":"2014-08-22T04:04:46Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 21, 2014 at 08:30:29PM +0200, René Scharfe wrote:\n\n> Similar to 16445242 (fetch-pack: avoid quadratic list insertion in\n> mark_complete), sort only after all refs are collected instead of while\n> inserting.  The result is the same, but it's more efficient that way.\n> The difference will only be measurable in repositories with a large\n> number of refs.\n\nLooks good, thanks.\n\nI was hoping one of these would be fixing the quadratic http-push\nbehavior I mentioned yesterday, but alas. We seem to have a lot of\nquadratic spots to fix. :)\n\n-Peff\n"}]}