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 25, 2012, 00:39 UTC
Message-ID
<20120525003920.GB11300@sigill.intra.peff.net>
In-Reply-To
<201205241817.46034.mfick@codeaurora.org>
On Thu, May 24, 2012 at 06:17:45PM -0600, Martin Fick wrote:
Show 14 quoted lines
> On Monday, May 21, 2012 04:14:17 pm Jeff King wrote:
> > On Mon, May 21, 2012 at 01:45:25PM -0400, Jeff King wrote:
> > Martin, let me know if this improves things for your
> > many-ref cases (and if you are still seeing slowness in
> > your repos with many refs, let me know which operations
> > cause it).
> 
> I have not been ignoring you, I am sorry that I have not 
> replied yet.  Unfortunately, I am having a very hard time 
> getting conclusive tests with my large repo.  I making
> plenty of mistakes in what I think I am testing I believe,
> but also I am having a hard time getting reproducible 
> results so far.  And some tests take quite a while, so it is 
> not always obvious what I might be doing wrong.

No worries. I am pretty confident that the patches I supplied so far are a good thing whether they help your case or not. So if you come back in a month and show that they solved all your problems, then great. And if they don't, then it will just show us what new problems we have to work on. :)

> Were your tests mostly warm cache tests?

Yes, exclusively warm. And all of the refs were packed, which makes the warm/cold difference less interesting (it's one 30MB or so file). I don't think there's much point in thinking about the performance of 400K loose refs (which would be absolutely horrific cold-cache on most traditional filesystems). If you have that many, you would want to keep the bulk of them packed.

-Peff
Previous: Martin FickNext: Martin Fick
Message 25 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.