git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Shawn O. Pearce <spearce@spearce.org>
Date
Sep 16, 2009, 22:42 UTC
Message-ID
<20090916224253.GB14660@spearce.org>
In-Reply-To
<alpine.LNX.2.00.0909162141140.13697@reaper.quantumfyre.co.uk>
Julian Phillips <julian@quantumfyre.co.uk> wrote:
Show 10 quoted lines
> 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.
Previous: Julian PhillipsNext: Junio C Hamano
Message 6 of 17 in “Speed up fetch with large number of tags”
  1. 0/2 Speed up fetch with large number of tagsJulian Phillips, Sep 16, 2009
  2. 1/2 ref-dict: Add a set of functions for working with a ref dictionaryJulian Phillips, Sep 16, 2009
  3. 2/2 fetch: Speed up fetch by using ref dictionaryJulian Phillips, Sep 16, 2009
  4. Junio C HamanoSep 16, 2009
  5. Julian PhillipsSep 16, 2009
  6. Shawn O. PearceSep 16, 2009
  7. Junio C HamanoSep 16, 2009
  8. Shawn O. PearceSep 16, 2009
  9. Junio C HamanoSep 16, 2009
  10. fetch: Speed up fetch by rewriting find_non_local_tagsJulian Phillips, Sep 16, 2009
  11. Junio C HamanoSep 16, 2009
  12. Julian PhillipsSep 16, 2009
  13. Julian PhillipsSep 17, 2009
  14. Johan HerlandSep 17, 2009
  15. fetch: Speed up fetch by rewriting find_non_local_tagsJulian Phillips, Sep 17, 2009
  16. Shawn O. PearceSep 16, 2009
  17. Junio C HamanoSep 22, 2009

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.