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

From: Martin Fick <[email-masked]>
Date: Fri, 30 Sep 2011 09:45:34 -0600

On Thursday, September 29, 2011 09:44:40 pm Junio C Hamano 
wrote:
> Martin Fick <[email-masked]> writes:
> > This works for me, however unfortunately, I cannot find
> > any scenarios where it improves anything over the
> > previous fix by René.  :(
> 
> Nevertheless, I would appreciate it if you can try this
> _without_ René's patch. This attempts to make
> resolve_ref() cheap for _any_ caller. René's patch
> avoids calling it in one specific callchain.
> 
> They address different issues. René's patch is probably
> an independently good change (I haven't thought about
> the interactions with the topics in flight and its
> implications on the future direction), but would not
> help other/new callers that make many calls to
> resolve_ref().

Agreed.  Here is what I am seeing without René's patch.

Checkout in NON packed ref repo takes about 20s, with patch 
v3 of binary search, it takes about 11s (1s slower than 
René's patch).

Checkout in packed ref repo takes about 5:30min, with patch 
v3 of binary search, it takes about 10s (also 1s slower than 
René's patch).

I'd say that's not bad, it seems like the 1s difference is 
doing the search 60K+times (my tests don't quite scan the 
full list), so the search seems to scale well with patch v3.

-Martin

-- 
Employee of Qualcomm Innovation Center, Inc. which is a 
member of Code Aurora Forum