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

Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)

From
Jeff King <peff@peff.net>
Date
May 22, 2012, 17:46 UTC
Message-ID
<20120522174648.GE11600@sigill.intra.peff.net>
In-Reply-To
<7vaa105dah.fsf@alter.siamese.dyndns.org>
On Tue, May 22, 2012 at 10:35:50AM -0700, Junio C Hamano wrote:
Show 21 quoted lines
> > In this case, the packed-refs file is 30MB. Even just gzipping it takes
> > it down to 2MB. As far as I know, we don't ever do random access on the
> > file, but instead just stream it into memory.
> 
> True.
> 
> The current code reads the whole thing in upon first use of _any_ element
> in the file, just like the index codepath does for the index file.
> 
> But the calling pattern to the refs machinery is fairly well isolated and
> all happens in refs.c file.  Especially thanks to the recent work by
> Michael Haggerty, for "I am about to create a new branch 'frotz'; do I
> have 'refs/heads/frotz' or anything that begins with 'refs/heads/frotz/'?"
> kind of callers, it is reasonably easy to design a better structured
> packed-refs file format to allow us to read only a subtree portion of
> refs/ hierarchy, and plug that logic into the lazy ref population code.
> Such a "design a better packed-refs format for scalability to 400k refs"
> is a very well isolated project that has high chance of succeeding without
> breaking things.  No code outside refs.c assumes that there is a flat
> array of refs that records what was read from the packed-refs file and can
> walk linearly over it, unlike the in-core index.

Yeah. As gross as I find a 30MB packed-refs file, I don't actually think that is the bottle-neck at all. Sure, it wastes some disk cache, but in the grand scheme of things, anybody with 400K refs probably has a much, much bigger object database.

So there probably isn't much point in clever tricks to make it smaller on disk, especially if they will make further partial-read optimizations harder to do. But...

> If you do "for_each_ref()" for everything (e.g. sending 'have' during the
> object transfer, or repacking the whole repository), you would end up
> needing to read the whole thing for obvious reasons.

I think Michael's work is really great for the loose refs, where hitting each directory is very expensive. But for a repo with packed refs that is just going to call for_each_ref, I'm worried that breaking apart the ref list is going to cause noticeable overhead. But still, the regression I'm seeing seems way too big for that overhead, so I think something else is going on. We just need to find it.

-Peff
Previous: Junio C HamanoNext: Michael Haggerty
Message 34 of 46 in “remove_duplicates() in builtin/fetch-pack.c is O(N^2)”
  1. Michael HaggertyMay 21, 2012
  2. Junio C HamanoMay 21, 2012
  3. demerphqMay 21, 2012
  4. Jeff KingMay 21, 2012
  5. Jeff KingMay 21, 2012
  6. 1/5 fetch-pack: sort incoming headsJeff King, May 21, 2012
  7. Junio C HamanoMay 22, 2012
  8. Jeff KingMay 22, 2012
  9. Jeff KingMay 24, 2012
  10. 2/5 fetch-pack: avoid quadratic behavior in remove_duplicatesJeff King, May 21, 2012
  11. 3/5 add sorting infrastructure for list refsJeff King, May 21, 2012
  12. 4/5 fetch-pack: sort the list of incoming refsJeff King, May 21, 2012
  13. 5/5 fetch-pack: avoid quadratic loop in filter_refsJeff King, May 21, 2012
  14. Junio C HamanoMay 22, 2012
  15. Jeff KingMay 21, 2012
  16. Jeff KingMay 22, 2012
  17. Michael HaggertyMay 22, 2012
  18. Jeff KingMay 22, 2012
  19. Michael HaggertyMay 22, 2012
  20. Jeff KingMay 22, 2012
  21. Michael HaggertyMay 22, 2012
  22. Jeff KingMay 22, 2012
  23. Michael HaggertyMay 24, 2012
  24. Martin FickMay 25, 2012
  25. Jeff KingMay 25, 2012
  26. Martin FickMay 25, 2012
  27. Jeff KingMay 25, 2012
  28. Martin FickMay 25, 2012
  29. Jeff KingMay 25, 2012
  30. Nguyen Thai Ngoc DuyMay 22, 2012
  31. Michael HaggertyMay 22, 2012
  32. Jeff KingMay 22, 2012
  33. Junio C HamanoMay 22, 2012
  34. Jeff KingMay 22, 2012
  35. Michael HaggertyMay 24, 2012
  36. Nguyen Thai Ngoc DuyMay 23, 2012
  37. Junio C HamanoMay 22, 2012
  38. Martin FickMay 21, 2012
  39. Jeff KingMay 21, 2012
  40. Junio C HamanoMay 21, 2012
  41. Jeff KingMay 21, 2012
  42. Martin FickMay 22, 2012
  43. Jeff KingMay 22, 2012
  44. Martin FickMay 22, 2012
  45. Junio C HamanoMay 22, 2012
  46. Martin FickMay 23, 2012

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.