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
Michael Haggerty <mhagger@alum.mit.edu>
Date
May 22, 2012, 03:59 UTC
Message-ID
<4FBB0F21.5080608@alum.mit.edu>
In-Reply-To
<20120521235219.GA5589@sigill.intra.peff.net>
On 05/22/2012 01:52 AM, Jeff King wrote:
Show 22 quoted lines
> On Mon, May 21, 2012 at 06:14:17PM -0400, Jeff King wrote:
>
>> The rails and git cases run in ~28s and ~37s, respectively, again mostly
>> going to the actual object transfer. So I think this series removes all
>> of the asymptotically bad behavior from this code path.
>>
>> One thing to note about all of these repos is that they tend to have
>> several refs pointing to a single commit. None of the speedups in this
>> series depends on that fact, but it may be that on a repo with more
>> independent refs, we may uncover other code paths (e.g., I know that my
>> fix for mark_complete in ea5f220 improves the case with duplicate refs,
>> but would not help if you really have 400K refs pointing to unique
>> commits[1]).
>
> Hmm. So I started to do some experimentation with this and noticed
> something odd.
>
> Try doing "git fetch . refs/*:refs/*" in a repository with a large
> number of refs (e.g., 400K). With git v1.7.10, this takes about 9.5s on
> my machine. But using the version of git in "next" takes about 16.5s.
> Bisection points to your 432ad41 (refs: store references hierarchically,
> 2012-04-10). Perf shows sort_ref_dir and msort_with_tmp as hot spots.
I'm looking into this.

For your test, were the 400k references all in one "directory", or were they sharded somehow?

A large number of packed references in a single namespace is the worst-case scenario for the hierarchical refs change. Since the refs in a namespace are all stored in a single array, there is no benefit from the hierarchical storage whereas there is some extra cost from traversing the namespace tree for each lookup. But the performance hit shouldn't be this large.

Michael
-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/
Previous: Jeff KingNext: Jeff King
Message 17 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.