use a hashmap to make remotes fasterpr/remotes-in-hashmap

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.

Signed-off-by: Patrick Reynolds <patrick.reynolds@github.com>
Reviewed-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

1 files changed, 3 insertions, 0 deletions

diff --git a/remote.h b/remote.h
index 917d383a80..8b62efd2ad 100644
--- a/remote.h
+++ b/remote.h
@@ -2,6 +2,7 @@
 #define REMOTE_H
 
 #include "parse-options.h"
+#include "hashmap.h"
 
 enum {
 	REMOTE_CONFIG,
@@ -10,6 +11,8 @@ enum {
 };
 
 struct remote {
+	struct hashmap_entry ent;  /* must be first */
+
 	const char *name;
 	int origin;