{"thread":{"id":"50830","subject":"[PATCH] fetch-pack: binary search when storing wanted-refs","startedAt":"2019-03-27T21:11:16Z","lastAt":"2019-03-28T03:13:19Z","messageCount":2,"participants":["Jonathan Tan","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"372588","messageId":"20190327211110.46327-1-jonathantanmy@google.com","threadId":"50830","inReplyTo":null,"subject":"[PATCH] fetch-pack: binary search when storing wanted-refs","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-03-27T21:11:10Z","receivedAt":"2019-03-27T21:11:16Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"In do_fetch_pack_v2(), the \"sought\" array is sorted by name, and it is\nnot subsequently reordered (within the function). Therefore,\nreceive_wanted_refs() can assume that \"sought\" is sorted, and can thus\nuse a binary search when storing wanted-refs retrieved from the server.\n\nReplace the existing linear search with a binary search. This improves\nperformance significantly when mirror cloning a repository with more\nthan 1 million refs.\n\nSigned-off-by: Jonathan Tan <jonathantanmy@google.com>\n---\n fetch-pack.c | 19 ++++++++++---------\n 1 file changed, 10 insertions(+), 9 deletions(-)\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex e69993b2eb..e8266bd45a 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -1298,6 +1298,11 @@ static void receive_shallow_info(struct fetch_pack_args *args,\n \t}\n }\n \n+static int cmp_name_ref(const void *name, const void *ref)\n+{\n+\treturn strcmp(name, (*(struct ref **)ref)->name);\n+}\n+\n static void receive_wanted_refs(struct packet_reader *reader,\n \t\t\t\tstruct ref **sought, int nr_sought)\n {\n@@ -1305,20 +1310,16 @@ static void receive_wanted_refs(struct packet_reader *reader,\n \twhile (packet_reader_read(reader) == PACKET_READ_NORMAL) {\n \t\tstruct object_id oid;\n \t\tconst char *end;\n-\t\tint i;\n+\t\tstruct ref **found;\n \n \t\tif (parse_oid_hex(reader->line, &oid, &end) || *end++ != ' ')\n \t\t\tdie(_(\"expected wanted-ref, got '%s'\"), reader->line);\n \n-\t\tfor (i = 0; i < nr_sought; i++) {\n-\t\t\tif (!strcmp(end, sought[i]->name)) {\n-\t\t\t\toidcpy(&sought[i]->old_oid, &oid);\n-\t\t\t\tbreak;\n-\t\t\t}\n-\t\t}\n-\n-\t\tif (i == nr_sought)\n+\t\tfound = bsearch(end, sought, nr_sought, sizeof(*sought),\n+\t\t\t\tcmp_name_ref);\n+\t\tif (!found)\n \t\t\tdie(_(\"unexpected wanted-ref: '%s'\"), reader->line);\n+\t\toidcpy(&(*found)->old_oid, &oid);\n \t}\n \n \tif (reader->status != PACKET_READ_DELIM)\n-- \n2.21.0.197.gd478713db0\n\n"},{"id":"372604","messageId":"20190328031314.GB10032@sigill.intra.peff.net","threadId":"50830","inReplyTo":"20190327211110.46327-1-jonathantanmy@google.com","subject":"Re: [PATCH] fetch-pack: binary search when storing wanted-refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-03-28T03:13:14Z","receivedAt":"2019-03-28T03:13:19Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Mar 27, 2019 at 02:11:10PM -0700, Jonathan Tan wrote:\n\n> In do_fetch_pack_v2(), the \"sought\" array is sorted by name, and it is\n> not subsequently reordered (within the function). Therefore,\n> receive_wanted_refs() can assume that \"sought\" is sorted, and can thus\n> use a binary search when storing wanted-refs retrieved from the server.\n> \n> Replace the existing linear search with a binary search. This improves\n> performance significantly when mirror cloning a repository with more\n> than 1 million refs.\n\nThis looks good.\n\nThe flow in do_fetch_pack_v2() is a little funny. I wanted to\ndouble-check that we always sorted the sought list, because it only\nhappens in the CHECK_LOCAL state of the state machine.\n\nBut as far as I can tell we always begin the function in CHECK_LOCAL, it\nalways transitions out to another state, and we never go back to it. So\nall of that part of the state-machine switch could really just be done\nonce before entering the state-machine's while loop.\n\nNot really relevant to your patch, but maybe worth tweaking separately\n(or maybe not, if people find the all-in-a-state-machine style more\nreadable; I found it more confusing to reason about).\n\n> +static int cmp_name_ref(const void *name, const void *ref)\n> +{\n> +\treturn strcmp(name, (*(struct ref **)ref)->name);\n> +}\n\nAfter some errors with qsort comparison functions a while back[1], I\ndouble-checked that this has the right number of asterisks. I believe it\ndoes. :)\n\n-Peff\n\n[1] https://public-inbox.org/git/d1b58614-989f-5998-6c53-c19eee409a2f@web.de/\n    and the child thread it spawned are interesting reading, though I\n    don't think we ever followed up on it.\n"}]}