Re: [RFC/PATCH 0/2] Speed up fetch with large number of tags

["Shawn O. Pearce" <spearce@spearce.org>]

Julian Phillips <julian@quantumfyre.co.uk> wrote:
> On Wed, 16 Sep 2009, Junio C Hamano wrote:
>> * It is tempting to use a hash table when you have to deal with an
>>   unordered collection, but in this case, wouldn't the refs obtained from
>>   the transport (it's essentially a ls-remote output, isn't it?) be
>>   sorted?  Can't you take advantage of that fact to optimize the loop,
>>   without adding a specialized hash table implementation?
>
> I wasn't sure if we could rely on the refs list being sorted.  But I've  
> got a new version that uses an extra string_list instead that is actually 
> slightly faster.  I'll post that shortly.

JGit depends on the fact that the refs list is sorted by the remote
peer, and that foo^{} immediately follows foo.  I don't think this
has ever been documented, but all sane implementations[1] follow
this convention and it may be something we could simply codify as
part of the protocol standard.

[1] Sane implementations are defined to be what I consider to be
    the two stable implementations in deployed use, git.git and JGit.

-- 
Shawn.