From: Martin Fick <mfick@codeaurora.org>
Date: Fri, 30 Sep 2011 01:13:08 GMT
Subject: Re: [PATCH v3] refs: Use binary search to lookup refs faster
Message-ID: <201109291913.34196.mfick@codeaurora.org>
In-Reply-To: <20110929221143.23806.25666.julian@quantumfyre.co.uk>

On Thursday, September 29, 2011 04:11:42 pm Julian Phillips 
wrote:
> Currently we linearly search through lists of refs when
> we need to find a specific ref.  This can be very slow
> if we need to lookup a large number of refs.  By
> changing to a binary search we can make this faster.
> 
> In order to be able to use a binary search we need to
> change from using linked lists to arrays, which we can
> manage using ALLOC_GROW.
> 
> We can now also use the standard library qsort function
> to sort the refs arrays.
> 

This works for me, however unfortunately, I cannot find any 
scenarios where it improves anything over the previous fix 
by René.  :(

I tested many things, clones, fetches, fetch noops, 
checkouts, garbage collection.  I am a bit surprised, 
because I thought that my hack of a hash map did improve 
still on checkouts on packed refs, but it could just be that 
my hack was buggy and did not actually do a full orphan 
check.

Thanks,

-Martin