[PATCH] use a hashmap to make remotes faster

[PATCH] use a hashmap to make remotes faster

[patrick.reynolds]

[-- Attachment #1: Type: text/plain, Size: 3682 bytes --]

Remotes are stored as an array, so looking one up or adding one without
duplication is an O(n) operation.  Reading an entire config file full of
remotes is O(n^2) in the number of remotes.  For a repository with tens of
thousands of remotes, the running time can hit multiple minutes.

Hash tables are way faster.  So we add a hashmap from remote name to
struct remote and use it for all lookups.  The time to add a new remote to
a repo that already has 50,000 remotes drops from ~2 minutes to < 1
second.

We retain the old array of remotes so iterators proceed in config-file
order.
---
 remote.c | 63 ++++++++++++++++++++++++++++++++++++++++++++++-----------------
 remote.h |  3 +++
 2 files changed, 49 insertions(+), 17 deletions(-)

diff --git a/remote.c b/remote.c
index a0701f6..88499a4 100644
--- a/remote.c
+++ b/remote.c
@@ -42,6 +42,7 @@ struct rewrites {
 static struct remote **remotes;
 static int remotes_alloc;
 static int remotes_nr;
+static struct hashmap remotes_hash;
 
 static struct branch **branches;
 static int branches_alloc;
@@ -136,26 +137,51 @@ static void add_url_alias(struct remote *remote, const char *url)
 	add_pushurl_alias(remote, url);
 }
 
+struct remotes_hash_key {
+	const char *str;
+	int len;
+};
+
+static int remotes_hash_cmp(const struct remote *a, const struct remote *b, const struct remotes_hash_key *key)
+{
+	if (key)
+		return strncmp(a->name, key->str, key->len) || a->name[key->len];
+	else
+		return strcmp(a->name, b->name);
+}
+
+static inline void init_remotes_hash()
+{
+	if (!remotes_hash.cmpfn)
+		hashmap_init(&remotes_hash, (hashmap_cmp_fn)remotes_hash_cmp, 0);
+}
+
 static struct remote *make_remote(const char *name, int len)
 {
-	struct remote *ret;
-	int i;
+	struct remote *ret, *replaced;
+	struct remotes_hash_key lookup;
+	struct hashmap_entry lookup_entry;
 
-	for (i = 0; i < remotes_nr; i++) {
-		if (len ? (!strncmp(name, remotes[i]->name, len) &&
-			   !remotes[i]->name[len]) :
-		    !strcmp(name, remotes[i]->name))
-			return remotes[i];
-	}
+	if (!len)
+		len = strlen(name);
+
+	init_remotes_hash();
+	lookup.str = name;
+	lookup.len = len;
+	hashmap_entry_init(&lookup_entry, memhash(name, len));
+
+	if ((ret = hashmap_get(&remotes_hash, &lookup_entry, &lookup)) != NULL)
+		return ret;
 
 	ret = xcalloc(1, sizeof(struct remote));
 	ret->prune = -1;  /* unspecified */
 	ALLOC_GROW(remotes, remotes_nr + 1, remotes_alloc);
 	remotes[remotes_nr++] = ret;
-	if (len)
-		ret->name = xstrndup(name, len);
-	else
-		ret->name = xstrdup(name);
+	ret->name = xstrndup(name, len);
+
+	hashmap_entry_init(ret, lookup_entry.hash);
+	replaced = hashmap_put(&remotes_hash, ret);
+	assert(replaced == NULL);  /* no previous entry overwritten */
 	return ret;
 }
 
@@ -722,13 +748,16 @@ struct remote *pushremote_get(const char *name)
 
 int remote_is_configured(const char *name)
 {
-	int i;
+	struct remotes_hash_key lookup;
+	struct hashmap_entry lookup_entry;
 	read_config();
 
-	for (i = 0; i < remotes_nr; i++)
-		if (!strcmp(name, remotes[i]->name))
-			return 1;
-	return 0;
+	init_remotes_hash();
+	lookup.str = name;
+	lookup.len = strlen(name);
+	hashmap_entry_init(&lookup_entry, memhash(name, lookup.len));
+
+	return hashmap_get(&remotes_hash, &lookup_entry, &lookup) != NULL;
 }
 
 int for_each_remote(each_remote_fn fn, void *priv)
diff --git a/remote.h b/remote.h
index 917d383..81cb5ff 100644
--- a/remote.h
+++ b/remote.h
@@ -1,6 +1,7 @@
 #ifndef REMOTE_H
 #define REMOTE_H
 
+#include "hashmap.h"
 #include "parse-options.h"
 
 enum {
@@ -10,6 +11,8 @@ enum {
 };
 
 struct remote {
+	struct hashmap_entry ent;  /* must be first */
+
 	const char *name;
 	int origin;
 
-- 
2.0.0.rc4

Re: [PATCH] use a hashmap to make remotes faster

[Matthieu Moy]

"patrick.reynolds@github.com" <patrick.reynolds@github.com> writes:
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

It seems you mixed your name and email address in your config file. I
guess your name is "Patrick Reynolds", not
"patrick.reynolds@github.com".

> Remotes are stored as an array, so looking one up or adding one without
> duplication is an O(n) operation.  Reading an entire config file full of
> remotes is O(n^2) in the number of remotes.  For a repository with tens of
> thousands of remotes, the running time can hit multiple minutes.

Just being curious: in which senario do you have tens of thousands of
remotes?

(not an objection, it's a good thing anyway)

> +static inline void init_remotes_hash()

static inline void init_remotes_hash(void)

Not a detailed review, but the patch sounds good other than that.

-- 
Matthieu Moy
http://www-verimag.imag.fr/~moy/

Re: [PATCH] use a hashmap to make remotes faster

[Jeff King]

On Tue, Jul 29, 2014 at 09:57:45AM +0200, Matthieu Moy wrote:

> "patrick.reynolds@github.com" <patrick.reynolds@github.com> writes:
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> 
> It seems you mixed your name and email address in your config file. I
> guess your name is "Patrick Reynolds", not
> "patrick.reynolds@github.com".

Also, Patrick, please sign-off your patch ("format-patch -s").

> > Remotes are stored as an array, so looking one up or adding one without
> > duplication is an O(n) operation.  Reading an entire config file full of
> > remotes is O(n^2) in the number of remotes.  For a repository with tens of
> > thousands of remotes, the running time can hit multiple minutes.
> 
> Just being curious: in which senario do you have tens of thousands of
> remotes?
> 
> (not an objection, it's a good thing anyway)

Whenever you fork a repository at GitHub, we give you a leaf repository
that points its info/alternates to a master "network.git" repository for
the fork network.  The network.git repo contains all of the objects, and
has a remote configured for each of the child repositories. You would
never want to gc in that repository without doing a "fetch --all" first.

Most networks have only a few dozen forks, but a few have a large number
(torvalds/linux has ~5K, and homebrew is close to 10K).  And then
sometimes a MOOC instructor tells an entire 50K-person class to fork a
hello-world project all at once. :)

-Peff