summaryrefslogtreecommitdiff
path: root/fetch-pack.c
diff options
context:
space:
mode:
authorJonathan Tan <jonathantanmy@google.com>2019-03-27 21:11:10 (GMT)
committerJunio C Hamano <gitster@pobox.com>2019-04-01 06:51:05 (GMT)
commitb7643009123216792aa158d3b2ca64a79adc01e2 (patch)
tree05a197eaf32b132f94c6ed1089c7c53c758ca265 /fetch-pack.c
parentaeb582a98374c094361cba1bd756dc6307432c42 (diff)
downloadgit-b7643009123216792aa158d3b2ca64a79adc01e2.zip
git-b7643009123216792aa158d3b2ca64a79adc01e2.tar.gz
git-b7643009123216792aa158d3b2ca64a79adc01e2.tar.bz2
fetch-pack: binary search when storing wanted-refs
In do_fetch_pack_v2(), the "sought" array is sorted by name, and it is not subsequently reordered (within the function). Therefore, receive_wanted_refs() can assume that "sought" is sorted, and can thus use a binary search when storing wanted-refs retrieved from the server. Replace the existing linear search with a binary search. This improves performance significantly when mirror cloning a repository with more than 1 million refs. Signed-off-by: Jonathan Tan <jonathantanmy@google.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'fetch-pack.c')
-rw-r--r--fetch-pack.c19
1 files changed, 10 insertions, 9 deletions
diff --git a/fetch-pack.c b/fetch-pack.c
index 812be15..e018b1c 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -1295,6 +1295,11 @@ static void receive_shallow_info(struct fetch_pack_args *args,
}
}
+static int cmp_name_ref(const void *name, const void *ref)
+{
+ return strcmp(name, (*(struct ref **)ref)->name);
+}
+
static void receive_wanted_refs(struct packet_reader *reader,
struct ref **sought, int nr_sought)
{
@@ -1302,20 +1307,16 @@ static void receive_wanted_refs(struct packet_reader *reader,
while (packet_reader_read(reader) == PACKET_READ_NORMAL) {
struct object_id oid;
const char *end;
- int i;
+ struct ref **found;
if (parse_oid_hex(reader->line, &oid, &end) || *end++ != ' ')
die(_("expected wanted-ref, got '%s'"), reader->line);
- for (i = 0; i < nr_sought; i++) {
- if (!strcmp(end, sought[i]->name)) {
- oidcpy(&sought[i]->old_oid, &oid);
- break;
- }
- }
-
- if (i == nr_sought)
+ found = bsearch(end, sought, nr_sought, sizeof(*sought),
+ cmp_name_ref);
+ if (!found)
die(_("unexpected wanted-ref: '%s'"), reader->line);
+ oidcpy(&(*found)->old_oid, &oid);
}
if (reader->status != PACKET_READ_DELIM)