http-walker: reduce O(n) ops with doubly-linked list

Using the a Linux-kernel-derived doubly-linked list
implementation from the Userspace RCU library allows us to
enqueue and delete items from the object request queue in
constant time.

This change reduces enqueue times in the prefetch() function
where object request queue could grow to several thousand
objects.

I left out the list_for_each_entry* family macros from list.h
which relied on the __typeof__ operator as we support platforms
without it.  Thus, list_entry (aka "container_of") needs to be
called explicitly inside macro-wrapped for loops.

The downside is this costs us an additional pointer per object
request, but this is offset by reduced overhead on queue
operations leading to improved performance and shorter queue
depths.

Signed-off-by: Eric Wong <e@80x24.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

1 files changed, 15 insertions, 27 deletions

diff --git a/http-walker.c b/http-walker.c
index 48f2df4d31..0b2425531a 100644
--- a/http-walker.c
+++ b/http-walker.c
@@ -2,6 +2,7 @@
 #include "commit.h"
 #include "walker.h"
 #include "http.h"
+#include "list.h"
 
 struct alt_base {
 	char *base;
@@ -23,7 +24,7 @@ struct object_request {
 	struct alt_base *repo;
 	enum object_request_state state;
 	struct http_object_request *req;
-	struct object_request *next;
+	struct list_head node;
 };
 
 struct alternates_request {
@@ -41,7 +42,7 @@ struct walker_data {
 	struct alt_base *alt;
 };
 
-static struct object_request *object_queue_head;
+static LIST_HEAD(object_queue_head);
 
 static void fetch_alternates(struct walker *walker, const char *base);
 
@@ -110,19 +111,10 @@ static void process_object_response(void *callback_data)
 
 static void release_object_request(struct object_request *obj_req)
 {
-	struct object_request *entry = object_queue_head;
-
 	if (obj_req->req !=NULL && obj_req->req->localfile != -1)
 		error("fd leakage in release: %d", obj_req->req->localfile);
-	if (obj_req == object_queue_head) {
-		object_queue_head = obj_req->next;
-	} else {
-		while (entry->next != NULL && entry->next != obj_req)
-			entry = entry->next;
-		if (entry->next == obj_req)
-			entry->next = entry->next->next;
-	}
 
+	list_del(&obj_req->node);
 	free(obj_req);
 }
 
@@ -130,8 +122,10 @@ static void release_object_request(struct object_request *obj_req)
 static int fill_active_slot(struct walker *walker)
 {
 	struct object_request *obj_req;
+	struct list_head *pos, *tmp, *head = &object_queue_head;
 
-	for (obj_req = object_queue_head; obj_req; obj_req = obj_req->next) {
+	list_for_each_safe(pos, tmp, head) {
+		obj_req = list_entry(pos, struct object_request, node);
 		if (obj_req->state == WAITING) {
 			if (has_sha1_file(obj_req->sha1))
 				obj_req->state = COMPLETE;
@@ -148,7 +142,6 @@ static int fill_active_slot(struct walker *walker)
 static void prefetch(struct walker *walker, unsigned char *sha1)
 {
 	struct object_request *newreq;
-	struct object_request *tail;
 	struct walker_data *data = walker->data;
 
 	newreq = xmalloc(sizeof(*newreq));
@@ -157,18 +150,9 @@ static void prefetch(struct walker *walker, unsigned char *sha1)
 	newreq->repo = data->alt;
 	newreq->state = WAITING;
 	newreq->req = NULL;
-	newreq->next = NULL;
 
 	http_is_verbose = walker->get_verbosely;
-
-	if (object_queue_head == NULL) {
-		object_queue_head = newreq;
-	} else {
-		tail = object_queue_head;
-		while (tail->next != NULL)
-			tail = tail->next;
-		tail->next = newreq;
-	}
+	list_add_tail(&newreq->node, &object_queue_head);
 
 #ifdef USE_CURL_MULTI
 	fill_active_slots();
@@ -451,11 +435,15 @@ static int fetch_object(struct walker *walker, unsigned char *sha1)
 {
 	char *hex = sha1_to_hex(sha1);
 	int ret = 0;
-	struct object_request *obj_req = object_queue_head;
+	struct object_request *obj_req = NULL;
 	struct http_object_request *req;
+	struct list_head *pos, *head = &object_queue_head;
 
-	while (obj_req != NULL && hashcmp(obj_req->sha1, sha1))
-		obj_req = obj_req->next;
+	list_for_each(pos, head) {
+		obj_req = list_entry(pos, struct object_request, node);
+		if (!hashcmp(obj_req->sha1, sha1))
+			break;
+	}
 	if (obj_req == NULL)
 		return error("Couldn't find request for %s in the queue", hex);