{"thread":{"id":"37242","subject":"[PATCH v2] use a hashmap to make remotes faster","startedAt":"2014-07-29T14:43:39Z","lastAt":"2014-09-05T15:16:26Z","messageCount":5,"participants":["Patrick Reynolds","Jeff King","Junio C Hamano","Stefan Beller"],"isPatch":true,"patchVersion":2,"patchTotal":null},"messages":[{"id":"246920","messageId":"25222.0938886865-sendEmail@debian","threadId":"37242","inReplyTo":null,"subject":"[PATCH v2] use a hashmap to make remotes faster","fromName":"Patrick Reynolds","fromEmail":"patrick.reynolds@github.com","sentAt":"2014-07-29T14:43:39Z","receivedAt":"2014-07-29T14:43:39Z","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\nSigned-off-by: Patrick Reynolds <patrick.reynolds@github.com>\n---\nmark function with no arguments as taking void\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..52533e4 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(void)\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":"246925","messageId":"20140729174642.GB20042@peff.net","threadId":"37242","inReplyTo":"25222.0938886865-sendEmail@debian","subject":"Re: [PATCH v2] use a hashmap to make remotes faster","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-07-29T17:46:42Z","receivedAt":"2014-07-29T17:46:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 29, 2014 at 02:43:39PM +0000, Patrick Reynolds wrote:\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> Hash tables are way faster.  So we add a hashmap from remote name to\n> struct remote and use it for all lookups.  The time to add a new remote to\n> a repo that already has 50,000 remotes drops from ~2 minutes to < 1\n> second.\n> \n> We retain the old array of remotes so iterators proceed in config-file\n> order.\n> \n> Signed-off-by: Patrick Reynolds <patrick.reynolds@github.com>\n\nAs observers might have guessed, I already reviewed this off-list, but\nto make it clear:\n\n  Reviewed-by: Jeff King <peff@peff.net>\n\n-Peff\n"},{"id":"246982","messageId":"xmqqd2cmzorv.fsf@gitster.dls.corp.google.com","threadId":"37242","inReplyTo":"25222.0938886865-sendEmail@debian","subject":"Re: [PATCH v2] use a hashmap to make remotes faster","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-07-30T18:26:28Z","receivedAt":"2014-07-30T18:26:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Please don't do this:\n\n    Content-Type: multipart/related; boundary=\"----MIME delimiter for sendEmail-128858.688128279\"\n"},{"id":"248892","messageId":"5409887A.1000602@gmail.com","threadId":"37242","inReplyTo":"25222.0938886865-sendEmail@debian","subject":"Re: [PATCH v2] use a hashmap to make remotes faster","fromName":"Stefan Beller","fromEmail":"stefanbeller@gmail.com","sentAt":"2014-09-05T09:55:06Z","receivedAt":"2014-09-05T09:55:06Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On 29.07.2014 16:43, Patrick Reynolds wrote:\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> Hash tables are way faster.  So we add a hashmap from remote name to\n> struct remote and use it for all lookups.  The time to add a new remote to\n> a repo that already has 50,000 remotes drops from ~2 minutes to < 1\n> second.\n> \n> We retain the old array of remotes so iterators proceed in config-file\n> order.\n> \n> Signed-off-by: Patrick Reynolds <patrick.reynolds@github.com>\n> ---\n> mark function with no arguments as taking void\n> \n>  remote.c | 63 ++++++++++++++++++++++++++++++++++++++++++++++-----------------\n>  remote.h |  3 +++\n>  2 files changed, 49 insertions(+), 17 deletions(-)\n> \n> diff --git a/remote.c b/remote.c\n> index a0701f6..52533e4 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(void)\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)\n> diff --git a/remote.h b/remote.h\n> index 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\nI stumbled about this comment  \"/* must be first */\"\nwhen reading the changelog.\n\nWhy does it need to be first?\nIs it a common reason I'm just not aware of,\nor would it make sense to put the reason into the comment as well?\n\nThanks,\nStefan\n\n>  \tconst char *name;\n>  \tint origin;\n>  \n> \n"},{"id":"248900","messageId":"20140905151626.GA1846@peff.net","threadId":"37242","inReplyTo":"5409887A.1000602@gmail.com","subject":"Re: [PATCH v2] use a hashmap to make remotes faster","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-09-05T15:16:26Z","receivedAt":"2014-09-05T15:16:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Sep 05, 2014 at 11:55:06AM +0200, Stefan Beller wrote:\n\n> >  struct remote {\n> > +\tstruct hashmap_entry ent;  /* must be first */\n> > +\n> \n> I stumbled about this comment  \"/* must be first */\"\n> when reading the changelog.\n> \n> Why does it need to be first?\n> Is it a common reason I'm just not aware of,\n> or would it make sense to put the reason into the comment as well?\n\nYes, it's a requirement of the hashmap code. It stores arbitrary\nstructs, but uses the front of the type for its bookkeeping data (the\nhash and a linked list pointer to the next item in the bucket). This is\ndocumented in Documentation/technical/api-hashmap.txt.\n\n-Peff\n"}]}