From: Jeff King <peff@peff.net>
Date: Tue, 29 Jul 2014 17:46:42 GMT
Subject: Re: [PATCH v2] use a hashmap to make remotes faster
Message-ID: <20140729174642.GB20042@peff.net>
In-Reply-To: <25222.0938886865-sendEmail@debian>

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