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 22, 2012, 22:19 UTC
Message-ID
<201205221619.31738.mfick@codeaurora.org>
In-Reply-To
<20120522182157.GB20305@sigill.intra.peff.net>
On Tuesday, May 22, 2012 12:21:57 pm Jeff King wrote:
> On Mon, May 21, 2012 at 11:51:16PM -0600, Martin Fick 
wrote:
> AFAIK, ref advertisement scales linearly. Which is
> probably not acceptable over a slow link, and we could
> do better.

Right, although it is not just a slow link issue. Linear or not, this problem does not scale, it needs to be based on N, the number of refs which need updating, not N the number of refs in the repo.

I gave the following numbers to Junio and Shawn recently and I figure it is probably worth mentioning them here to perhaps give others some insights into just how bad this problem can be...

Android consists of approximately 400 projects, and if anyone tags their builds regularly, that means that they will be tagging 400 projects per build. We have something like 10K tags on average across 400 projects, so when we do a simple No Op sync just to see if all 400 projects are up to date, this yields about 200MB of data over the wire (4M refs)!!!

That 200MB is using a -j4 on repo sync and it chews up about 1.5 cores on a high end server to serve that 200MB for over 1min. Now imagine a build bot needing to build about 25 images in parallel all just doing a No Op sync to see if they are up to date! That's 25 * 200MB = 5GB data and 25 * 1.5 cores ~= 36 cores. That means our high end 24 core server falls over all for a No Op.

As you can imagine, we really would like to see this eliminated from our workflows. If we want to check 400 projects to see if they are up to date, it should be 400 refs, not 400 * 10K,

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