From d0da003d5b1e65f6e52920e42582f43b357782ee Mon Sep 17 00:00:00 2001 From: Patrick Reynolds Date: Tue, 29 Jul 2014 14:43:39 +0000 Subject: use a hashmap to make remotes faster 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 Reviewed-by: Jeff King Signed-off-by: Junio C Hamano --- remote.h | 3 +++ 1 file changed, 3 insertions(+) (limited to 'remote.h') diff --git a/remote.h b/remote.h index 917d383a8..8b62efd2a 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; -- cgit v1.2.1