summaryrefslogtreecommitdiff
path: root/http-walker.c
diff options
context:
space:
mode:
authorEric Wong <e@80x24.org>2016-07-11 20:51:31 (GMT)
committerJunio C Hamano <gitster@pobox.com>2016-07-12 22:17:42 (GMT)
commit94e99012fc7a02c5504214294279fa49b4cc8ce3 (patch)
tree6d60fd9cd99b5ea19a3fc9a32e48bcd74342fc42 /http-walker.c
parent17966c0a63d25b1cc2dd1e98d30873e643bd581f (diff)
downloadgit-94e99012fc7a02c5504214294279fa49b4cc8ce3.zip
git-94e99012fc7a02c5504214294279fa49b4cc8ce3.tar.gz
git-94e99012fc7a02c5504214294279fa49b4cc8ce3.tar.bz2
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>
Diffstat (limited to 'http-walker.c')
-rw-r--r--http-walker.c42
1 files changed, 15 insertions, 27 deletions
diff --git a/http-walker.c b/http-walker.c
index 48f2df4..0b24255 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);