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

Re: [PATCH 2/6] commit: add generation number to struct commmit

From
Derrick Stolee <stolee@gmail.com>
Date
Apr 3, 2018, 18:31 UTC
Message-ID
<2b5a08da-6b15-194e-4336-ce7c84240a9b@gmail.com>
In-Reply-To
<20180403182800.GA8377@sigill.intra.peff.net>
On 4/3/2018 2:28 PM, Jeff King wrote:
Show 17 quoted lines
> On Tue, Apr 03, 2018 at 11:05:36AM -0700, Brandon Williams wrote:
>
>> On 04/03, Derrick Stolee wrote:
>>> The generation number of a commit is defined recursively as follows:
>>>
>>> * If a commit A has no parents, then the generation number of A is one.
>>> * If a commit A has parents, then the generation number of A is one
>>>    more than the maximum generation number among the parents of A.
>>>
>>> Add a uint32_t generation field to struct commit so we can pass this
>> Is there any reason to believe this would be too small of a value in the
>> future?  Or is a 32 bit unsigned good enough?
> The linux kernel took ~10 years to produce 500k commits. Even assuming
> those were all linear (and they're not), that gives us ~80,000 years of
> leeway. So even if the pace of development speeds up or we have a
> quicker project, it still seems we have a pretty reasonable safety
> margin.

That, and larger projects do not have linear histories. Despite having almost 2 million reachable commits, the Windows repository has maximum generation number ~100,000.

Thanks, -Stolee

Previous: Jeff KingNext: Brandon Williams
Message 16 of 162 in “Compute and consume generation numbers”
  1. 0/6 Compute and consume generation numbersDerrick Stolee, Apr 3, 2018
  2. 1/6 object.c: parse commit in graph firstDerrick Stolee, Apr 3, 2018
  3. Jonathan TanApr 3, 2018
  4. Jeff KingApr 3, 2018
  5. Derrick StoleeApr 3, 2018
  6. 6/6 commit-graph.txt: update future workDerrick Stolee, Apr 3, 2018
  7. Jonathan TanApr 3, 2018
  8. 5/6 commit.c: use generation to halt paint walkDerrick Stolee, Apr 3, 2018
  9. Jonathan TanApr 3, 2018
  10. 4/6 commit: use generations in paint_down_to_common()Derrick Stolee, Apr 3, 2018
  11. Stefan BellerApr 3, 2018
  12. Jonathan TanApr 3, 2018
  13. 2/6 commit: add generation number to struct commmitDerrick Stolee, Apr 3, 2018
  14. Brandon WilliamsApr 3, 2018
  15. Jeff KingApr 3, 2018
  16. Derrick StoleeApr 3, 2018
  17. Brandon WilliamsApr 3, 2018
  18. Stefan BellerApr 3, 2018
  19. Ramsay JonesApr 3, 2018
  20. Jeff KingApr 3, 2018
  21. Jonathan TanApr 3, 2018
  22. 3/6 commit-graph: compute generation numbersDerrick Stolee, Apr 3, 2018
  23. Jonathan TanApr 3, 2018
  24. Stefan BellerApr 3, 2018
  25. Derrick StoleeApr 3, 2018
  26. Brandon WilliamsApr 3, 2018
  27. Derrick StoleeApr 3, 2018
  28. Jeff KingApr 3, 2018
  29. Jeff KingApr 3, 2018
  30. 7/6 ref-filter: use generation number for --containsDerrick Stolee, Apr 4, 2018
  31. 8/6 commit: use generation numbers for in_merge_bases()Derrick Stolee, Apr 4, 2018
  32. Derrick StoleeApr 4, 2018
  33. Brandon WilliamsApr 4, 2018
  34. Jeff KingApr 4, 2018
  35. Derrick StoleeApr 4, 2018
  36. Jeff KingApr 4, 2018
  37. Jeff KingApr 4, 2018
  38. Derrick StoleeApr 4, 2018
  39. Jeff KingApr 4, 2018
  40. Derrick StoleeApr 4, 2018
  41. Jeff KingApr 4, 2018
  42. Derrick StoleeApr 4, 2018
  43. Jeff KingApr 4, 2018
  44. Jakub NarebskiApr 7, 2018
  45. Jakub NarebskiApr 7, 2018
  46. Derrick StoleeApr 8, 2018
  47. Jakub NarebskiApr 11, 2018
  48. Derrick StoleeApr 11, 2018
  49. Jakub NarebskiApr 14, 2018
  50. Jakub NarebskiApr 21, 2018
  51. Derrick StoleeApr 23, 2018
  52. 00/10 Compute and consume generation numbersDerrick Stolee, Apr 9, 2018
  53. 01/10 object.c: parse commit in graph firstDerrick Stolee, Apr 9, 2018
  54. 02/10 merge: check config before loading commitsDerrick Stolee, Apr 9, 2018
  55. Junio C HamanoApr 11, 2018
  56. Derrick StoleeApr 11, 2018
  57. 03/10 commit: add generation number to struct commmitDerrick Stolee, Apr 9, 2018
  58. Stefan BellerApr 9, 2018
  59. Junio C HamanoApr 11, 2018
  60. Derrick StoleeApr 11, 2018
  61. Junio C HamanoApr 11, 2018
  62. 04/10 commit-graph: compute generation numbersDerrick Stolee, Apr 9, 2018
  63. Junio C HamanoApr 11, 2018
  64. Derrick StoleeApr 11, 2018
  65. Eric SunshineApr 11, 2018
  66. Stefan BellerApr 11, 2018
  67. 05/10 commit: use generations in paint_down_to_common()Derrick Stolee, Apr 9, 2018
  68. 06/10 commit.c: use generation to halt paint walkDerrick Stolee, Apr 9, 2018
  69. Junio C HamanoApr 11, 2018
  70. Derrick StoleeApr 11, 2018
  71. 07/10 commit-graph.txt: update future workDerrick Stolee, Apr 9, 2018
  72. Junio C HamanoApr 12, 2018
  73. Derrick StoleeApr 12, 2018
  74. Jakub NarebskiApr 13, 2018
  75. 10/10 commit: add short-circuit to paint_down_to_common()Derrick Stolee, Apr 9, 2018
  76. 09/10 commit: use generation numbers for in_merge_bases()Derrick Stolee, Apr 9, 2018
  77. 08/10 ref-filter: use generation number for --containsDerrick Stolee, Apr 9, 2018
  78. 0/9 Compute and consume generation numbersDerrick Stolee, Apr 17, 2018
  79. 1/9 commit: add generation number to struct commmitDerrick Stolee, Apr 17, 2018
  80. 3/9 commit: use generations in paint_down_to_common()Derrick Stolee, Apr 17, 2018
  81. Jakub NarebskiApr 18, 2018
  82. Derrick StoleeApr 18, 2018
  83. 2/9 commit-graph: compute generation numbersDerrick Stolee, Apr 17, 2018
  84. 4/9 commit-graph.txt: update design documentDerrick Stolee, Apr 17, 2018
  85. Jakub NarebskiApr 18, 2018
  86. 6/9 commit: use generation numbers for in_merge_bases()Derrick Stolee, Apr 17, 2018
  87. Jakub NarebskiApr 18, 2018
  88. Derrick StoleeApr 23, 2018
  89. 7/9 commit: add short-circuit to paint_down_to_common()Derrick Stolee, Apr 17, 2018
  90. Jakub NarebskiApr 18, 2018
  91. Derrick StoleeApr 23, 2018
  92. Jakub NarebskiApr 23, 2018
  93. Derrick StoleeApr 24, 2018
  94. Jakub NarebskiApr 19, 2018
  95. 8/9 commit-graph: always load commit-graph informationDerrick Stolee, Apr 17, 2018
  96. Derrick StoleeApr 17, 2018
  97. Jakub NarebskiApr 19, 2018
  98. Derrick StoleeApr 23, 2018
  99. 9/9 merge: check config before loading commitsDerrick Stolee, Apr 17, 2018
  100. 5/9 ref-filter: use generation number for --containsDerrick Stolee, Apr 17, 2018
  101. Jakub NarebskiApr 18, 2018
  102. Derrick StoleeApr 23, 2018
  103. Jakub NarebskiApr 24, 2018
  104. Derrick StoleeApr 25, 2018
  105. Jakub NarebskiApr 19, 2018
  106. Derrick StoleeApr 23, 2018
  107. 00/10 Compute and consume generation numbersDerrick Stolee, Apr 25, 2018
  108. 01/10 ref-filter: fix outdated comment on in_commit_listDerrick Stolee, Apr 25, 2018
  109. Jakub NarebskiApr 28, 2018
  110. 02/10 commit: add generation number to struct commmitDerrick Stolee, Apr 25, 2018
  111. Jakub NarebskiApr 28, 2018
  112. Derrick StoleeApr 30, 2018
  113. 03/10 commit-graph: compute generation numbersDerrick Stolee, Apr 25, 2018
  114. Junio C HamanoApr 26, 2018
  115. Derrick StoleeApr 26, 2018
  116. Derrick StoleeApr 26, 2018
  117. Jakub NarebskiApr 29, 2018
  118. Derrick StoleeMay 1, 2018
  119. Jakub NarebskiMay 2, 2018
  120. 07/10 commit: use generation numbers for in_merge_bases()Derrick Stolee, Apr 25, 2018
  121. Jakub NarebskiApr 30, 2018
  122. 06/10 ref-filter: use generation number for --containsDerrick Stolee, Apr 25, 2018
  123. Jakub NarebskiApr 30, 2018
  124. 05/10 commit-graph: always load commit-graph informationDerrick Stolee, Apr 25, 2018
  125. Jakub NarebskiApr 29, 2018
  126. Derrick StoleeMay 1, 2018
  127. Jakub NarebskiApr 29, 2018
  128. 08/10 commit: add short-circuit to paint_down_to_common()Derrick Stolee, Apr 25, 2018
  129. Jakub NarebskiApr 30, 2018
  130. Derrick StoleeMay 1, 2018
  131. Jakub NarebskiMay 2, 2018
  132. Derrick StoleeMay 2, 2018
  133. 04/10 commit: use generations in paint_down_to_common()Derrick Stolee, Apr 25, 2018
  134. Junio C HamanoApr 26, 2018
  135. Jakub NarebskiApr 26, 2018
  136. Jakub NarebskiApr 28, 2018
  137. Jakub NarebskiApr 29, 2018
  138. 10/10 commit-graph.txt: update design documentDerrick Stolee, Apr 25, 2018
  139. Jakub NarebskiApr 30, 2018
  140. Derrick StoleeMay 1, 2018
  141. Jakub NarebskiMay 2, 2018
  142. 09/10 merge: check config before loading commitsDerrick Stolee, Apr 25, 2018
  143. Jakub NarebskiApr 30, 2018
  144. Derrick StoleeMay 1, 2018
  145. Jakub NarebskiMay 2, 2018
  146. Derrick StoleeApr 25, 2018
  147. Jakub NarebskiApr 28, 2018
  148. 00/11 Compute and consume generation numbersDerrick Stolee, May 1, 2018
  149. 01/11 ref-filter: fix outdated comment on in_commit_listDerrick Stolee, May 1, 2018
  150. 03/11 commit-graph: compute generation numbersDerrick Stolee, May 1, 2018
  151. 02/11 commit: add generation number to struct commmitDerrick Stolee, May 1, 2018
  152. 04/11 commit: use generations in paint_down_to_common()Derrick Stolee, May 1, 2018
  153. 05/11 commit-graph: always load commit-graph informationDerrick Stolee, May 1, 2018
  154. 07/11 commit: use generation numbers for in_merge_bases()Derrick Stolee, May 1, 2018
  155. 08/11 commit: add short-circuit to paint_down_to_common()Derrick Stolee, May 1, 2018
  156. 09/11 commit: use generation number in remove_redundant()Derrick Stolee, May 1, 2018
  157. Derrick StoleeMay 1, 2018
  158. Jakub NarebskiMay 3, 2018
  159. 10/11 merge: check config before loading commitsDerrick Stolee, May 1, 2018
  160. 11/11 commit-graph.txt: update design documentDerrick Stolee, May 1, 2018
  161. 06/11 ref-filter: use generation number for --containsDerrick Stolee, May 1, 2018
  162. Jakub NarebskiMay 3, 2018

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.