From: Shawn O. Pearce Date: Wed, 16 Sep 2009 22:42:53 GMT Subject: Re: [RFC/PATCH 0/2] Speed up fetch with large number of tags Message-ID: <20090916224253.GB14660@spearce.org> In-Reply-To: Julian Phillips 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.