{"thread":{"id":"37394","subject":"[PATCH] walker: avoid quadratic list insertion in mark_complete","startedAt":"2014-08-21T18:30:24Z","lastAt":"2014-08-22T04:01:31Z","messageCount":2,"participants":["René Scharfe","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"248073","messageId":"53F63AC0.1090605@web.de","threadId":"37394","inReplyTo":null,"subject":"[PATCH] walker: avoid quadratic list insertion in mark_complete","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2014-08-21T18:30:24Z","receivedAt":"2014-08-21T18:30:24Z","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 walker.c | 6 ++++--\n 1 file changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/walker.c b/walker.c\nindex 0148264..0596e99 100644\n--- a/walker.c\n+++ b/walker.c\n@@ -205,7 +205,7 @@ static int mark_complete(const char *path, const unsigned char *sha1, int flag,\n \tstruct commit *commit = lookup_commit_reference_gently(sha1, 1);\n \tif (commit) {\n \t\tcommit->object.flags |= COMPLETE;\n-\t\tcommit_list_insert_by_date(commit, &complete);\n+\t\tcommit_list_insert(commit, &complete);\n \t}\n \treturn 0;\n }\n@@ -271,8 +271,10 @@ int walker_fetch(struct walker *walker, int targets, char **target,\n \t\t}\n \t}\n \n-\tif (!walker->get_recover)\n+\tif (!walker->get_recover) {\n \t\tfor_each_ref(mark_complete, NULL);\n+\t\tcommit_list_sort_by_date(&complete);\n+\t}\n \n \tfor (i = 0; i < targets; i++) {\n \t\tif (interpret_target(walker, target[i], &sha1[20 * i])) {\n-- \n2.1.0\n"},{"id":"248096","messageId":"20140822040131.GA27992@peff.net","threadId":"37394","inReplyTo":"53F63AC0.1090605@web.de","subject":"Re: [PATCH] walker: avoid quadratic list insertion in mark_complete","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-22T04:01:31Z","receivedAt":"2014-08-22T04:01:31Z","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:24PM +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\nThanks, this looks obviously correct.\n\nI wonder if we should do this on top:\n\ndiff --git a/walker.c b/walker.c\nindex 0148264..70088b8 100644\n--- a/walker.c\n+++ b/walker.c\n@@ -203,7 +203,7 @@ static int interpret_target(struct walker *walker, char *target, unsigned char *\n static int mark_complete(const char *path, const unsigned char *sha1, int flag, void *cb_data)\n {\n \tstruct commit *commit = lookup_commit_reference_gently(sha1, 1);\n-\tif (commit) {\n+\tif (commit && !(commit->object.flags & COMPLETE)) {\n \t\tcommit->object.flags |= COMPLETE;\n \t\tcommit_list_insert_by_date(commit, &complete);\n \t}\n\nIt's not as big a deal with your patch since you've made it O(n log n),\nbut reducing n further does not hurt.\n\n-Peff\n"}]}