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

[Jeff King <peff@peff.net>]

On Tue, Jul 29, 2014 at 02:43:39PM +0000, Patrick Reynolds wrote:

> 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>

As observers might have guessed, I already reviewed this off-list, but
to make it clear:

  Reviewed-by: Jeff King <peff@peff.net>

-Peff