{"thread":{"id":"37237","subject":"[PATCH] use a hashmap to make remotes faster","startedAt":"2014-07-29T03:53:42Z","lastAt":"2014-07-29T08:09:49Z","messageCount":3,"participants":["patrick.reynolds@github.com","Matthieu Moy","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"246870","messageId":"305063.319715799-sendEmail@debian","threadId":"37237","inReplyTo":null,"subject":"[PATCH] use a hashmap to make remotes faster","fromName":"patrick.reynolds@github.com","fromEmail":"patrick.reynolds@github.com","sentAt":"2014-07-29T03:53:42Z","receivedAt":"2014-07-29T03:53:42Z","isPatch":true,"sender":{"key":"patrick.reynolds@github.com","avatar":"https://gravatar.com/avatar/883ab411a1f4a4d96fd05b139be699507f11dafe679b551194bd269370bffc61?d=mp&s=160"},"body":"Remotes are stored as an array, so looking one up or adding one without\nduplication is an O(n) operation.  Reading an entire config file full of\nremotes is O(n^2) in the number of remotes.  For a repository with tens of\nthousands of remotes, the running time can hit multiple minutes.\n\nHash tables are way faster.  So we add a hashmap from remote name to\nstruct remote and use it for all lookups.  The time to add a new remote to\na repo that already has 50,000 remotes drops from ~2 minutes to < 1\nsecond.\n\nWe retain the old array of remotes so iterators proceed in config-file\norder.\n---\n remote.c | 63 ++++++++++++++++++++++++++++++++++++++++++++++-----------------\n remote.h |  3 +++\n 2 files changed, 49 insertions(+), 17 deletions(-)\n\ndiff --git a/remote.c b/remote.c\nindex a0701f6..88499a4 100644\n--- a/remote.c\n+++ b/remote.c\n@@ -42,6 +42,7 @@ struct rewrites {\n static struct remote **remotes;\n static int remotes_alloc;\n static int remotes_nr;\n+static struct hashmap remotes_hash;\n \n static struct branch **branches;\n static int branches_alloc;\n@@ -136,26 +137,51 @@ static void add_url_alias(struct remote *remote, const char *url)\n \tadd_pushurl_alias(remote, url);\n }\n \n+struct remotes_hash_key {\n+\tconst char *str;\n+\tint len;\n+};\n+\n+static int remotes_hash_cmp(const struct remote *a, const struct remote *b, const struct remotes_hash_key *key)\n+{\n+\tif (key)\n+\t\treturn strncmp(a->name, key->str, key->len) || a->name[key->len];\n+\telse\n+\t\treturn strcmp(a->name, b->name);\n+}\n+\n+static inline void init_remotes_hash()\n+{\n+\tif (!remotes_hash.cmpfn)\n+\t\thashmap_init(&remotes_hash, (hashmap_cmp_fn)remotes_hash_cmp, 0);\n+}\n+\n static struct remote *make_remote(const char *name, int len)\n {\n-\tstruct remote *ret;\n-\tint i;\n+\tstruct remote *ret, *replaced;\n+\tstruct remotes_hash_key lookup;\n+\tstruct hashmap_entry lookup_entry;\n \n-\tfor (i = 0; i < remotes_nr; i++) {\n-\t\tif (len ? (!strncmp(name, remotes[i]->name, len) &&\n-\t\t\t   !remotes[i]->name[len]) :\n-\t\t    !strcmp(name, remotes[i]->name))\n-\t\t\treturn remotes[i];\n-\t}\n+\tif (!len)\n+\t\tlen = strlen(name);\n+\n+\tinit_remotes_hash();\n+\tlookup.str = name;\n+\tlookup.len = len;\n+\thashmap_entry_init(&lookup_entry, memhash(name, len));\n+\n+\tif ((ret = hashmap_get(&remotes_hash, &lookup_entry, &lookup)) != NULL)\n+\t\treturn ret;\n \n \tret = xcalloc(1, sizeof(struct remote));\n \tret->prune = -1;  /* unspecified */\n \tALLOC_GROW(remotes, remotes_nr + 1, remotes_alloc);\n \tremotes[remotes_nr++] = ret;\n-\tif (len)\n-\t\tret->name = xstrndup(name, len);\n-\telse\n-\t\tret->name = xstrdup(name);\n+\tret->name = xstrndup(name, len);\n+\n+\thashmap_entry_init(ret, lookup_entry.hash);\n+\treplaced = hashmap_put(&remotes_hash, ret);\n+\tassert(replaced == NULL);  /* no previous entry overwritten */\n \treturn ret;\n }\n \n@@ -722,13 +748,16 @@ struct remote *pushremote_get(const char *name)\n \n int remote_is_configured(const char *name)\n {\n-\tint i;\n+\tstruct remotes_hash_key lookup;\n+\tstruct hashmap_entry lookup_entry;\n \tread_config();\n \n-\tfor (i = 0; i < remotes_nr; i++)\n-\t\tif (!strcmp(name, remotes[i]->name))\n-\t\t\treturn 1;\n-\treturn 0;\n+\tinit_remotes_hash();\n+\tlookup.str = name;\n+\tlookup.len = strlen(name);\n+\thashmap_entry_init(&lookup_entry, memhash(name, lookup.len));\n+\n+\treturn hashmap_get(&remotes_hash, &lookup_entry, &lookup) != NULL;\n }\n \n int for_each_remote(each_remote_fn fn, void *priv)\ndiff --git a/remote.h b/remote.h\nindex 917d383..81cb5ff 100644\n--- a/remote.h\n+++ b/remote.h\n@@ -1,6 +1,7 @@\n #ifndef REMOTE_H\n #define REMOTE_H\n \n+#include \"hashmap.h\"\n #include \"parse-options.h\"\n \n enum {\n@@ -10,6 +11,8 @@ enum {\n };\n \n struct remote {\n+\tstruct hashmap_entry ent;  /* must be first */\n+\n \tconst char *name;\n \tint origin;\n \n-- \n2.0.0.rc4\n\n\n"},{"id":"246879","messageId":"vpqoaw8ha12.fsf@anie.imag.fr","threadId":"37237","inReplyTo":"305063.319715799-sendEmail@debian","subject":"Re: [PATCH] use a hashmap to make remotes faster","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@grenoble-inp.fr","sentAt":"2014-07-29T07:57:45Z","receivedAt":"2014-07-29T07:57:45Z","isPatch":true,"sender":{"key":"matthieu.moy@grenoble-inp.fr","avatar":"https://gravatar.com/avatar/72c8a2705971a25dfaff23cece15130d405685845d911aedd5667ace277f3fc5?d=mp&s=160"},"body":"\"patrick.reynolds@github.com\" <patrick.reynolds@github.com> writes:\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nIt seems you mixed your name and email address in your config file. I\nguess your name is \"Patrick Reynolds\", not\n\"patrick.reynolds@github.com\".\n\n> Remotes are stored as an array, so looking one up or adding one without\n> duplication is an O(n) operation.  Reading an entire config file full of\n> remotes is O(n^2) in the number of remotes.  For a repository with tens of\n> thousands of remotes, the running time can hit multiple minutes.\n\nJust being curious: in which senario do you have tens of thousands of\nremotes?\n\n(not an objection, it's a good thing anyway)\n\n> +static inline void init_remotes_hash()\n\nstatic inline void init_remotes_hash(void)\n\nNot a detailed review, but the patch sounds good other than that.\n\n-- \nMatthieu Moy\nhttp://www-verimag.imag.fr/~moy/\n"},{"id":"246882","messageId":"20140729080949.GC4114@peff.net","threadId":"37237","inReplyTo":"vpqoaw8ha12.fsf@anie.imag.fr","subject":"Re: [PATCH] use a hashmap to make remotes faster","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-07-29T08:09:49Z","receivedAt":"2014-07-29T08:09:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 29, 2014 at 09:57:45AM +0200, Matthieu Moy wrote:\n\n> \"patrick.reynolds@github.com\" <patrick.reynolds@github.com> writes:\n> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n> \n> It seems you mixed your name and email address in your config file. I\n> guess your name is \"Patrick Reynolds\", not\n> \"patrick.reynolds@github.com\".\n\nAlso, Patrick, please sign-off your patch (\"format-patch -s\").\n\n> > Remotes are stored as an array, so looking one up or adding one without\n> > duplication is an O(n) operation.  Reading an entire config file full of\n> > remotes is O(n^2) in the number of remotes.  For a repository with tens of\n> > thousands of remotes, the running time can hit multiple minutes.\n> \n> Just being curious: in which senario do you have tens of thousands of\n> remotes?\n> \n> (not an objection, it's a good thing anyway)\n\nWhenever you fork a repository at GitHub, we give you a leaf repository\nthat points its info/alternates to a master \"network.git\" repository for\nthe fork network.  The network.git repo contains all of the objects, and\nhas a remote configured for each of the child repositories. You would\nnever want to gc in that repository without doing a \"fetch --all\" first.\n\nMost networks have only a few dozen forks, but a few have a large number\n(torvalds/linux has ~5K, and homebrew is close to 10K).  And then\nsometimes a MOOC instructor tells an entire 50K-person class to fork a\nhello-world project all at once. :)\n\n-Peff\n"}]}