diff options
| author | Jonathan Tan <jonathantanmy@google.com> | 2019-03-27 14:11:10 -0700 |
|---|---|---|
| committer | Junio C Hamano <gitster@pobox.com> | 2019-04-01 15:51:05 +0900 |
| commit | b7643009123216792aa158d3b2ca64a79adc01e2 (patch) | |
| tree | 05a197eaf32b132f94c6ed1089c7c53c758ca265 /fetch-pack.c | |
| parent | aeb582a98374c094361cba1bd756dc6307432c42 (diff) | |
| download | git-b7643009123216792aa158d3b2ca64a79adc01e2.tar.gz | |
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.c | 19 |
1 files changed, 10 insertions, 9 deletions
diff --git a/fetch-pack.c b/fetch-pack.c index 812be15d7e..e018b1c0a4 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) |