{"thread":{"id":"44281","subject":"[PATCH] upload-pack: use priority queue in reachable() check","startedAt":"2016-10-11T21:21:23Z","lastAt":"2016-10-11T21:27:01Z","messageCount":2,"participants":["Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"303929","messageId":"20161011212016.hnw4dl473puhyax7@sigill.intra.peff.net","threadId":"44281","inReplyTo":null,"subject":"[PATCH] upload-pack: use priority queue in reachable() check","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-10-11T21:20:16Z","receivedAt":"2016-10-11T21:21:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Like a lot of old commit-traversal code, this keeps a\ncommit_list in commit-date order, and and inserts parents\ninto the list. This means each insertion is potentially\nlinear, and the whole thing is quadratic (though the exact\nruntime depends on the relationship between the commit dates\nand the parent topology).\n\nThese days we have a priority queue, which can do the same\nthing with a much better worst-case time.\n\nSigned-off-by: Jeff King \n---\nThis was inspired by a real-world case where several instances of\nupload-pack were chewing minutes of CPU, and backtraces in each instance\npointed to this function. Unfortunately, I only saw the server side of\nthese requests. I pulled the contents of have_obj and want_obj out of\nthe process via gdb, but I wasn't able to reproduce the slow fetch.\n\nSo I'm not 100% sure that this fixes it, but the problem hasn't happened\nagain. And it certainly seems like it couldn't _hurt_ to optimize this.\n\n upload-pack.c | 13 +++++++------\n 1 file changed, 7 insertions(+), 6 deletions(-)\n\ndiff --git a/upload-pack.c b/upload-pack.c\nindex 5ec21e6..d9e381f 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -16,6 +16,7 @@\n #include \"string-list.h\"\n #include \"parse-options.h\"\n #include \"argv-array.h\"\n+#include \"prio-queue.h\"\n \n static const char * const upload_pack_usage[] = {\n \tN_(\"git upload-pack [] \"),\n@@ -319,12 +320,12 @@ static int got_sha1(const char *hex, unsigned char *sha1)\n \n static int reachable(struct commit *want)\n {\n-\tstruct commit_list *work = NULL;\n+\tstruct prio_queue work = { compare_commits_by_commit_date };\n \n-\tcommit_list_insert_by_date(want, &work);\n-\twhile (work) {\n+\tprio_queue_put(&work, want);\n+\twhile (work.nr) {\n \t\tstruct commit_list *list;\n-\t\tstruct commit *commit = pop_commit(&work);\n+\t\tstruct commit *commit = prio_queue_get(&work);\n \n \t\tif (commit->object.flags & THEY_HAVE) {\n \t\t\twant->object.flags |= COMMON_KNOWN;\n@@ -340,12 +341,12 @@ static int reachable(struct commit *want)\n \t\tfor (list = commit->parents; list; list = list->next) {\n \t\t\tstruct commit *parent = list->item;\n \t\t\tif (!(parent->object.flags & REACHABLE))\n-\t\t\t\tcommit_list_insert_by_date(parent, &work);\n+\t\t\t\tprio_queue_put(&work, parent);\n \t\t}\n \t}\n \twant->object.flags |= REACHABLE;\n \tclear_commit_marks(want, REACHABLE);\n-\tfree_commit_list(work);\n+\tclear_prio_queue(&work);\n \treturn (want->object.flags & COMMON_KNOWN);\n }\n \n-- \n2.10.1.572.g142464c\n"},{"id":"303932","messageId":"xmqqshs27f21.fsf@gitster.mtv.corp.google.com","threadId":"44281","inReplyTo":"20161011212016.hnw4dl473puhyax7@sigill.intra.peff.net","subject":"Re: [PATCH] upload-pack: use priority queue in reachable() check","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-10-11T21:26:30Z","receivedAt":"2016-10-11T21:27:01Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Like a lot of old commit-traversal code, this keeps a\n> commit_list in commit-date order, and and inserts parents\n> into the list. This means each insertion is potentially\n> linear, and the whole thing is quadratic (though the exact\n> runtime depends on the relationship between the commit dates\n> and the parent topology).\n>\n> These days we have a priority queue, which can do the same\n> thing with a much better worst-case time.\n>\n> Signed-off-by: Jeff King \n> ---\n> This was inspired by a real-world case where several instances of\n> upload-pack were chewing minutes of CPU, and backtraces in each instance\n> pointed to this function. Unfortunately, I only saw the server side of\n> these requests. I pulled the contents of have_obj and want_obj out of\n> the process via gdb, but I wasn't able to reproduce the slow fetch.\n>\n> So I'm not 100% sure that this fixes it, but the problem hasn't happened\n> again. And it certainly seems like it couldn't _hurt_ to optimize this.\n\nThis does look good and looks like a quite straight-forward change.\n\nWill queue; thanks.\n"}]}