[PATCH] upload-pack: use priority queue in reachable() check

[PATCH] upload-pack: use priority queue in reachable() check

[Jeff King]

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

Re: [PATCH] upload-pack: use priority queue in reachable() check

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

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

This does look good and looks like a quite straight-forward change.

Will queue; thanks.