Subject: Re: [PATCH v3] refs: Use binary search to lookup refs faster

From: Martin Fick <[email-masked]>
Date: Thu, 29 Sep 2011 19:13:08 -0600

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