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
MFMartin Fick <mfick@codeaurora.org>
Date
Sep 30, 2011, 01:13 UTC
Message-ID
<201109291913.34196.mfick@codeaurora.org>
In-Reply-To
<20110929221143.23806.25666.julian@quantumfyre.co.uk>

On Thursday, September 29, 2011 04:11:42 pm Julian Phillips wrote:

Show 12 quoted lines
> Currently we linearly search through lists of refs when
> we need to find a specific ref.  This can be very slow
> if we need to lookup a large number of refs.  By
> changing to a binary search we can make this faster.
> 
> In order to be able to use a binary search we need to
> change from using linked lists to arrays, which we can
> manage using ALLOC_GROW.
> 
> We can now also use the standard library qsort function
> to sort the refs arrays.
>

This works for me, however unfortunately, I cannot find any scenarios where it improves anything over the previous fix by René. :(

I tested many things, clones, fetches, fetch noops, checkouts, garbage collection. I am a bit surprised, because I thought that my hack of a hash map did improve still on checkouts on packed refs, but it could just be that my hack was buggy and did not actually do a full orphan check.

Thanks,
-Martin
Previous: Junio C HamanoNext: Junio C Hamano
Message 62 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.