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

Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()

From
MFMartin Fick <mfick@codeaurora.org>
Date
Apr 2, 2012, 16:24 UTC
Message-ID
<201204021024.49706.mfick@codeaurora.org>
In-Reply-To
<4F7780F5.3060306@lsrfire.ath.cx>
On Saturday, March 31, 2012 04:11:01 pm René Scharfe wrote:
Show 5 quoted lines
> Speed up prepare_revision_walk() by adding commits
> without sorting to the commit_list and at the end sort
> the list in one go.  Thanks to mergesort() working
> behind the scenes, this is a lot faster for large
> numbers of commits than the current insert sort.

This speeds up my git push test on my repo with ~100K refs case from out ~43s to about ~10s. Not bad, thanks!

The rest of the 10s do not seem to be spent with high CPU on either the pushing or the receiving side (only a very small 100% burst on both sides near the end of the operation). I also ran iotop on the receiving side and could not find any activity (of course, the repo is likely cached). iftop does show a decent amount of traffic during this time, so perhaps we are finally approaching the protocol limit?

But, I have my doubts on that to be honest. The reason is because I am able to hack Gerrit to receive this push much faster (around 3.5s) by reusing a cached RevWalk. Without the cached RevWalk, Gerrit (using jgit) is about the same as your new patch ~10s. I am not saying that git is spending its time in the same place (but it may be) as jgit, but with jgit, the time I was able to save with the cached RevWalk was the time spent loading and parsing the RevCommits. This could be the same thing that git is doing? And while it may not be I/O (disk) bound so to speak since the packs are likely cached, it may still be memory bound on that I/O? If it is memory bound, and not I/O(disk) or CPU bound, I guess it makes sense that git and jgit would perform about the same (10s)?

Thanks again for your patch,
-Martin
-- 
Employee of Qualcomm Innovation Center, Inc. which is a 
member of Code Aurora Forum
Previous: Junio C HamanoNext: Shawn Pearce
Message 17 of 37 in “Git push performance problems with ~100K refs”
  1. Martin FickMar 30, 2012
  2. Junio C HamanoMar 30, 2012
  3. Martin FickMar 30, 2012
  4. Jeff KingMar 30, 2012
  5. Jeff KingMar 30, 2012
  6. Martin FickMar 30, 2012
  7. 1/3 add mergesort() for linked listsRené Scharfe, Mar 31, 2012
  8. Junio C HamanoApr 5, 2012
  9. René ScharfeApr 8, 2012
  10. Junio C HamanoApr 9, 2012
  11. Stephen BoydApr 11, 2012
  12. Junio C HamanoApr 11, 2012
  13. 2/3 commit: use mergesort() in commit_list_sort_by_date()René Scharfe, Mar 31, 2012
  14. 3/3 revision: insert unsorted, then sort in prepare_revision_walk()René Scharfe, Mar 31, 2012
  15. Martin FickMar 31, 2012
  16. Junio C HamanoMar 31, 2012
  17. Martin FickApr 2, 2012
  18. Shawn PearceApr 2, 2012
  19. Martin FickApr 2, 2012
  20. Shawn PearceApr 2, 2012
  21. Jeff KingApr 2, 2012
  22. Jeff KingApr 2, 2012
  23. Martin FickApr 2, 2012
  24. Nguyen Thai Ngoc DuyApr 3, 2012
  25. Martin FickApr 3, 2012
  26. 0/3 Commit cacheNguyễn Thái Ngọc Duy, Apr 3, 2012
  27. 1/3 parse_commit_buffer: rename a confusing variable nameNguyễn Thái Ngọc Duy, Apr 3, 2012
  28. 2/3 Add commit cache to help speed up commit traversalNguyễn Thái Ngọc Duy, Apr 3, 2012
  29. 3/3 Add parse_commit_for_rev() to take advantage of sha1-cacheNguyễn Thái Ngọc Duy, Apr 3, 2012
  30. Nguyen Thai Ngoc DuyApr 5, 2012
  31. Shawn PearceApr 6, 2012
  32. Nguyen Thai Ngoc DuyApr 7, 2012
  33. Nguyen Thai Ngoc DuyApr 3, 2012
  34. Jeff KingApr 2, 2012
  35. René ScharfeApr 2, 2012
  36. Jeff KingApr 3, 2012
  37. Jeff KingApr 3, 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.