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
MFMartin Fick <mfick@codeaurora.org>
Date
May 23, 2012, 00:46 UTC
Message-ID
<201205221846.38230.mfick@codeaurora.org>
In-Reply-To
<7v8vgj3imy.fsf@alter.siamese.dyndns.org>
On Tuesday, May 22, 2012 05:23:17 pm Junio C Hamano wrote:
Show 6 quoted lines
> Martin Fick <mfick@codeaurora.org> writes:
>
> I think we can ignore that 400 part from the above for
> now.  As they are independent "projects", it is
> unreasonable to expect that any solution would add costs
> less than linearly when you add more projects.

As far as git is concerned, sure they are independent, but the projects aren't really independent. Separate repos were likely selected for scalibility reasons in the first place, but this ends up being a "scale fail" pattern. I don't expect git to fix this * 400 issue, but I want to highlight, how difficult it is to make things scale in these cases and that this problems is a natural multiplier when you split something into separate git repos because your tags tend to now be multiplied. So while 10K tags sound like a lot but manageable for 1 repo, it ends up actually being 4M tags if you split your repos.

...
Show 7 quoted lines
> I think the assumption in your build-bot scenario needs
> to be a bit more clarified to give context.  I am
> assuming, when you say "see if projects are up to date",
> you mean your build-bot is interested in a single branch
> in each repository, possibly together with new tags that
> have become reachable from the updated tip of the branch
> (if the branch tip moved). 
Just the branch generally.
> I also assume that the
> build-bot polls very often and that is why 200MB (or
> divided by 400 it would be 0.5MB, which still is a lot
> when you talk about a single repository) hurts a lot.

To clarify for others (since you likely know), we serialize our submits, so the "poll" is before every build to ensure that we are up to date with what just got merged. In our case we use Gerrit with slaves (read only Gerrit copies), so we offload the "update" to the slave, which incurs the same hit, all though it is not quite a No Op but close (there will have been a batch of commits added to a few projects). But then since the slave may be slightly behind the master (replication from the master to the slave takes time, partially because of the same ref advertisement problem), so we want to verify the slave update by polling the master, which if replication was fast enough would be a No Op. So, our attempts to scale by using slaves does not help very much since the real update and the No Op are almost identical in their impacts... There are workarounds, but mostly hacks.

...
Show 5 quoted lines
> Unlike the capability exchange that happens after the
> initial connection, there is no gap in the protocol for
> the side that initiates the connection to tell the
> serving side to skip/delay the initial ref
> advertisement.

Crazy stupid suggestion: could the URI somehow be exploited to signal the option to disable advertisements? What if the path part of the URI started with something like several slashes? Older servers just strip the extra slashes right? Newer servers could disable advertisements if they see the slashes. Of course, this gets ugly if scripts add slashes and expect them to be stripped (old clients talking to new servers would probably then fail),

-Martin
-- 
Employee of Qualcomm Innovation Center, Inc. which is a 
member of Code Aurora Forum
Previous: Junio C Hamano
Message 46 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.