[PATCH] upload-pack: use priority queue in reachable() check
- From
Jeff King <peff@peff.net>
- Date
- Oct 11, 2016, 21:20 UTC
- Message-ID
- <20161011212016.hnw4dl473puhyax7@sigill.intra.peff.net>
Like a lot of old commit-traversal code, this keeps a commit_list in commit-date order, and and inserts parents into the list. This means each insertion is potentially linear, and the whole thing is quadratic (though the exact runtime depends on the relationship between the commit dates and the parent topology).
These days we have a priority queue, which can do the same thing with a much better worst-case time.
Signed-off-by: Jeff King <peff@peff.net> --- This was inspired by a real-world case where several instances of upload-pack were chewing minutes of CPU, and backtraces in each instance pointed to this function. Unfortunately, I only saw the server side of these requests. I pulled the contents of have_obj and want_obj out of the process via gdb, but I wasn't able to reproduce the slow fetch.
So I'm not 100% sure that this fixes it, but the problem hasn't happened again. And it certainly seems like it couldn't _hurt_ to optimize this.
upload-pack.c | 13 +++++++------ 1 file changed, 7 insertions(+), 6 deletions(-)
diff --git a/upload-pack.c b/upload-pack.c index 5ec21e6..d9e381f 100644 --- a/upload-pack.c +++ b/upload-pack.c @@ -16,6 +16,7 @@ #include "string-list.h" #include "parse-options.h" #include "argv-array.h" +#include "prio-queue.h" static const char * const upload_pack_usage[] = { N_("git upload-pack [<options>] <dir>"), @@ -319,12 +320,12 @@ static int got_sha1(const char *hex, unsigned char *sha1) static int reachable(struct commit *want) { - struct commit_list *work = NULL; + struct prio_queue work = { compare_commits_by_commit_date }; - commit_list_insert_by_date(want, &work); - while (work) { + prio_queue_put(&work, want); + while (work.nr) { struct commit_list *list; - struct commit *commit = pop_commit(&work); + struct commit *commit = prio_queue_get(&work); if (commit->object.flags & THEY_HAVE) { want->object.flags |= COMMON_KNOWN; @@ -340,12 +341,12 @@ static int reachable(struct commit *want) for (list = commit->parents; list; list = list->next) { struct commit *parent = list->item; if (!(parent->object.flags & REACHABLE)) - commit_list_insert_by_date(parent, &work); + prio_queue_put(&work, parent); } } want->object.flags |= REACHABLE; clear_commit_marks(want, REACHABLE); - free_commit_list(work); + clear_prio_queue(&work); return (want->object.flags & COMMON_KNOWN); }
-- 2.10.1.572.g142464c