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@xxxxxxxx>
---
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