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

Re: [PATCH v3] refs: Use binary search to lookup refs faster

From
Michael Haggerty <mhagger@alum.mit.edu>
Date
Oct 2, 2011, 05:15 UTC
Message-ID
<4E87F383.1050403@alum.mit.edu>
In-Reply-To
<7vk48qouht.fsf@alter.siamese.dyndns.org>
On 09/30/2011 06:38 PM, Junio C Hamano wrote:
Show 13 quoted lines
> Michael Haggerty <mhagger@alum.mit.edu> writes:
> 
>> On 09/30/2011 01:48 AM, Junio C Hamano wrote:
>>> This version looks sane, although I have a suspicion that it may have
>>> some interaction with what Michael may be working on.
>>
>> Indeed, I have almost equivalent changes in the giant patch series that
>> I am working on [1].
> 
> Good; that was the primary thing I wanted to know.  I want to take
> Julian's patch early but if the approach and data structures were
> drastically different from what you are cooking, that would force
> unnecessary reroll on your part, which I wanted to avoid.

Um, well, my patch series includes the same changes that Julian's wants to introduce, but following lots of other changes, cleanups, documentation improvements, etc. Moreover, my patch series builds on mh/iterate-refs, with which Julian's patch conflicts. In other words, it would be a real mess to reroll my series on top of Julian's patch. (That is of course not to imply that I hold a mutex on refs.c.) Because it changes a data structure that is used throughout refs.c, changes a lot of lines of code.

I think that the switch from linked list + linear sort to array plus binary sort is a pretty obvious win in terms of code complexity and *potential* performance improvement, but empirically I haven't seen any claims that it brings performance improvements beyond "René's patch". (Though, honestly, I've lost track of which "René's patch" is being discussed and I don't see anything relevant in Junio's tree.)

Intuitively, given that populating the reference cache involves O(N)
I/O, speeding up lookups can only help if there are very many ref
lookups within a single git invocation.  I think we will get a better
improvement by avoiding the reading of unneeded loose refs by reading
them one subdirectory at a time instead of always reading them en masse.
 I wanted to reach that milestone before submitting my changes.
My preference would be:
1. Merge jp/get-ref-dir-unsorted, perhaps even into maint.  It is a
simple, noninvasive, and obvious improvement and helps performance a lot
in an important use case.
2. Hold off on merging jp/get-ref-dir-unsorted for a while to give me a
chance to avoid conflict hell.
3. Evaluate René's patch on its own merits; if it makes sense regardless
of the binary search speedups, then it can be accepted independently to
give most of the performance benefit already.
Are there any other patches in this area that I've forgotten?
Michael
-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/
Previous: Julian PhillipsNext: Junio C Hamano
Message 59 of 126 in “Git is not scalable with too many refs/*”
  1. NAKAMURA TakumiJun 9, 2011
  2. Sverre RabbelierJun 9, 2011
  3. Shawn PearceJun 9, 2011
  4. A Large Angry SCMJun 9, 2011
  5. Shawn PearceJun 9, 2011
  6. Jeff KingJun 9, 2011
  7. NAKAMURA TakumiJun 10, 2011
  8. Jeff KingJun 13, 2011
  9. Andreas EricssonJun 14, 2011
  10. Jeff KingJun 14, 2011
  11. Junio C HamanoJun 14, 2011
  12. Sverre RabbelierJun 14, 2011
  13. Johan HerlandJun 14, 2011
  14. Sverre RabbelierJun 14, 2011
  15. Jeff KingJun 14, 2011
  16. Shawn PearceJun 14, 2011
  17. Jeff KingJun 14, 2011
  18. Shawn PearceJun 14, 2011
  19. Martin FickSep 8, 2011
  20. Martin FickSep 9, 2011
  21. Thomas RastSep 9, 2011
  22. Thomas RastSep 9, 2011
  23. Jens LehmannSep 9, 2011
  24. Martin FickSep 25, 2011
  25. Christian CouderSep 26, 2011
  26. Martin FickSep 26, 2011
  27. Christian CouderSep 26, 2011
  28. Martin FickSep 30, 2011
  29. Martin FickSep 30, 2011
  30. Martin FickSep 30, 2011
  31. Martin FickSep 30, 2011
  32. Junio C HamanoOct 1, 2011
  33. Michael HaggertyOct 2, 2011
  34. Martin FickOct 3, 2011
  35. Michael HaggertyOct 4, 2011
  36. Martin FickOct 3, 2011
  37. Junio C HamanoOct 3, 2011
  38. Michael HaggertyOct 4, 2011
  39. Martin FickOct 8, 2011
  40. Michael HaggertyOct 9, 2011
  41. Martin FickSep 28, 2011
  42. Martin FickSep 28, 2011
  43. Julian PhillipsSep 29, 2011
  44. Martin FickSep 29, 2011
  45. Julian PhillipsSep 29, 2011
  46. Martin FickSep 29, 2011
  47. Julian PhillipsSep 29, 2011
  48. René ScharfeSep 29, 2011
  49. Junio C HamanoSep 29, 2011
  50. refs: Use binary search to lookup refs fasterJulian Phillips, Sep 29, 2011
  51. Junio C HamanoSep 29, 2011
  52. refs: Use binary search to lookup refs fasterJulian Phillips, Sep 29, 2011
  53. Junio C HamanoSep 29, 2011
  54. refs: Use binary search to lookup refs fasterJulian Phillips, Sep 29, 2011
  55. Junio C HamanoSep 29, 2011
  56. Michael HaggertySep 30, 2011
  57. Junio C HamanoSep 30, 2011
  58. refs: Remove duplicates after sorting with qsortJulian Phillips, Sep 30, 2011
  59. Michael HaggertyOct 2, 2011
  60. Junio C HamanoOct 2, 2011
  61. Junio C HamanoOct 4, 2011
  62. Martin FickSep 30, 2011
  63. Junio C HamanoSep 30, 2011
  64. Julian PhillipsSep 30, 2011
  65. Martin FickSep 30, 2011
  66. Martin FickSep 29, 2011
  67. Julian PhillipsSep 29, 2011
  68. Martin FickSep 29, 2011
  69. René ScharfeSep 30, 2011
  70. Martin FickSep 30, 2011
  71. Junio C HamanoSep 30, 2011
  72. René ScharfeSep 30, 2011
  73. René ScharfeOct 1, 2011
  74. 1/8 checkout: check for "Previous HEAD" notice in t2020René Scharfe, Oct 1, 2011
  75. Sverre RabbelierOct 1, 2011
  76. 2/8 revision: factor out add_pending_sha1René Scharfe, Oct 1, 2011
  77. 3/8 checkout: use add_pending_{object,sha1} in orphan checkRené Scharfe, Oct 1, 2011
  78. 4/8 revision: add leak_pending flagRené Scharfe, Oct 1, 2011
  79. 5/8 bisect: use leak_pending flagRené Scharfe, Oct 1, 2011
  80. 6/8 bundle: use leak_pending flagRené Scharfe, Oct 1, 2011
  81. 7/8 checkout: use leak_pending flagRené Scharfe, Oct 1, 2011
  82. 8/8 commit: factor out clear_commit_marks_for_object_arrayRené Scharfe, Oct 1, 2011
  83. Martin FickSep 26, 2011
  84. Sverre RabbelierSep 26, 2011
  85. Martin FickSep 26, 2011
  86. Sverre RabbelierSep 26, 2011
  87. Martin FickSep 26, 2011
  88. Julian PhillipsSep 26, 2011
  89. Martin FickSep 26, 2011
  90. Julian PhillipsSep 26, 2011
  91. Martin FickSep 26, 2011
  92. Junio C HamanoSep 26, 2011
  93. Julian PhillipsSep 26, 2011
  94. Martin FickSep 26, 2011
  95. Martin FickSep 26, 2011
  96. Julian PhillipsSep 26, 2011
  97. David Michael BarrSep 26, 2011
  98. refs.c: Fix slowness with numerous loose refsDavid Barr, Sep 27, 2011
  99. David Michael BarrSep 27, 2011
  100. Junio C HamanoSep 26, 2011
  101. Don't sort ref_list too earlyJulian Phillips, Sep 27, 2011
  102. Michael HaggertyOct 2, 2011
  103. Martin FickSep 27, 2011
  104. Julian PhillipsSep 27, 2011
  105. Martin FickSep 27, 2011
  106. Julian PhillipsSep 27, 2011
  107. Sverre RabbelierSep 27, 2011
  108. Julian PhillipsSep 27, 2011
  109. Sverre RabbelierSep 27, 2011
  110. Nguyen Thai Ngoc DuySep 27, 2011
  111. Michael HaggertySep 27, 2011
  112. Julian PhillipsSep 27, 2011
  113. Julian PhillipsSep 26, 2011
  114. Michael HaggertySep 26, 2011
  115. Martin FickSep 26, 2011
  116. Thomas RastSep 26, 2011
  117. Michael HaggertySep 9, 2011
  118. Michael HaggertySep 9, 2011
  119. Jens LehmannSep 9, 2011
  120. Andreas EricssonJun 10, 2011
  121. Shawn PearceJun 10, 2011
  122. Jakub NarebskiJun 10, 2011
  123. Jeff KingJun 10, 2011
  124. Andreas EricssonJun 13, 2011
  125. Jakub NarebskiJun 9, 2011
  126. Stephen BashJun 9, 2011

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.