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

Re: [PATCH v2 12/13] name-rev: eliminate recursion in name_rev()

From
SZEDER Gábor <szeder.dev@gmail.com>
Date
Dec 9, 2019, 12:22 UTC
Message-ID
<20191209122246.GB2746@szeder.dev>
In-Reply-To
<20191127175751.165445-1-jonathantanmy@google.com>
On Wed, Nov 27, 2019 at 09:57:51AM -0800, Jonathan Tan wrote:
Show 7 quoted lines
> > Note that this slightly changes the order of lines in the output of
> > 'git name-rev --all', usually swapping two lines every 35 lines in
> > git.git or every 150 lines in linux.git.  This shouldn't matter in
> > practice, because the output has always been unordered anyway.
> 
> I didn't verify that the changing of order is fine, but other than that,
> this patch looks great.

FWIW, the sorted output is the same (well, it would clearly be a bug if it wasn't):

  $ .../v2.24.0/bin/git name-rev --all |sort >orig.sorted
  $ git name-rev --all |sort >new.sorted
  $ diff -u orig.sorted new.sorted 
  $ echo $?
  0

I still don't understand where that slight change in the order of lines comes from, though I didn't really tried to understand it, to be honest...

> > This patch is best viewed with '--ignore-all-space'.
> 
> Thanks for the tip! I ended up unindenting the loop to see the changes
> better, but I should have done this instead.

At one point I was considering an additional noop preparatory commit that would have added one more indentation level to name_rev()'s for loop. That patch would have an empty diff with '--ignore-all-spaces', of course, and the diff of the patch eliminating the recursion would look sensible by default. Would that have been worth it? Dunno.

Show 8 quoted lines
> > -static void name_rev(struct commit *commit,
> > +static void name_rev(struct commit *start_commit,
> >  		const char *tip_name, timestamp_t taggerdate,
> >  		int from_tag)
> 
> There are many changes from tip_name to name->tip_name in this function
> that mean that tip_name is no longer used within this function. Should
> this cleanup have been done in one of the earlier patches?
I've added a new patch to do that.
> Apart from that, overall, this patch looks like a straightforward good
> change. When we have a parent, instead of immediately calling name_rev()
> recursively, we first add it to an array, and then (in reverse order)
> add it to a priority queue which is actually used as a LIFO stack.

Yeah, 'commit->parents' is a single linked list, so we can't iterate over it backwards, hence that interim array.

Previous: Jonathan TanNext: Johannes Schindelin
Message 79 of 98 in “name-rev: eliminate recursion”
  1. 00/15 name-rev: eliminate recursionSZEDER Gábor, Sep 19, 2019
  2. 01/15 t6120-describe: correct test repo history graph in commentSZEDER Gábor, Sep 19, 2019
  3. Junio C HamanoSep 20, 2019
  4. SZEDER GáborSep 20, 2019
  5. Junio C HamanoSep 28, 2019
  6. 02/15 t6120-describe: modernize the 'check_describe' helperSZEDER Gábor, Sep 19, 2019
  7. Junio C HamanoSep 20, 2019
  8. 03/15 name-rev: use strip_suffix() in get_rev_name()SZEDER Gábor, Sep 19, 2019
  9. René ScharfeSep 20, 2019
  10. SZEDER GáborSep 20, 2019
  11. 05/15 name-rev: use sizeof(*ptr) instead of sizeof(type) in allocationSZEDER Gábor, Sep 19, 2019
  12. Derrick StoleeSep 20, 2019
  13. SZEDER GáborSep 20, 2019
  14. René ScharfeSep 20, 2019
  15. 06/15 t6120: add a test to cover inner conditions in 'git name-rev's name_rev()SZEDER Gábor, Sep 19, 2019
  16. Derrick StoleeSep 20, 2019
  17. SZEDER GáborSep 20, 2019
  18. 04/15 name-rev: avoid unnecessary cast in name_ref()SZEDER Gábor, Sep 19, 2019
  19. René ScharfeSep 20, 2019
  20. 10/15 name-rev: restructure creating/updating 'struct rev_name' instancesSZEDER Gábor, Sep 19, 2019
  21. Derrick StoleeSep 20, 2019
  22. SZEDER GáborSep 20, 2019
  23. 08/15 name-rev: pull out deref handling from the recursionSZEDER Gábor, Sep 19, 2019
  24. Derrick StoleeSep 20, 2019
  25. SZEDER GáborSep 20, 2019
  26. René ScharfeSep 20, 2019
  27. SZEDER GáborSep 20, 2019
  28. SZEDER GáborSep 20, 2019
  29. SZEDER GáborSep 21, 2019
  30. René ScharfeSep 21, 2019
  31. SZEDER GáborSep 22, 2019
  32. René ScharfeSep 23, 2019
  33. SZEDER GáborSep 23, 2019
  34. René ScharfeSep 23, 2019
  35. SZEDER GáborSep 23, 2019
  36. René ScharfeSep 24, 2019
  37. SZEDER GáborSep 26, 2019
  38. René ScharfeSep 21, 2019
  39. SZEDER GáborSep 21, 2019
  40. René ScharfeSep 21, 2019
  41. 09/15 name-rev: restructure parsing commits and applying date cutoffSZEDER Gábor, Sep 19, 2019
  42. René ScharfeSep 21, 2019
  43. 07/15 name-rev: extract creating/updating a 'struct name_rev' into a helperSZEDER Gábor, Sep 19, 2019
  44. Derrick StoleeSep 20, 2019
  45. name-rev: rewrite create_or_update_name()Martin Ågren, Sep 22, 2019
  46. SZEDER GáborDec 9, 2019
  47. 11/15 name-rev: drop name_rev()'s 'generation' and 'distance' parametersSZEDER Gábor, Sep 19, 2019
  48. 13/15 name-rev: cleanup name_ref()SZEDER Gábor, Sep 19, 2019
  49. 12/15 name-rev: eliminate recursion in name_rev()SZEDER Gábor, Sep 19, 2019
  50. 14/15 name-rev: plug a memory leak in name_rev()SZEDER Gábor, Sep 19, 2019
  51. 15/15 name-rev: plug a memory leak in name_rev() in the deref caseSZEDER Gábor, Sep 19, 2019
  52. Derrick StoleeSep 20, 2019
  53. 14/15 name-rev: plug memory leak in name_rev() in the deref caseSZEDER Gábor, Sep 19, 2019
  54. SZEDER GáborSep 19, 2019
  55. 15/15 name-rev: plug memory leak in name_rev()SZEDER Gábor, Sep 19, 2019
  56. SZEDER GáborSep 19, 2019
  57. Derrick StoleeSep 20, 2019
  58. SZEDER GáborSep 20, 2019
  59. 00/13 name-rev: eliminate recursionSZEDER Gábor, Nov 12, 2019
  60. 01/13 t6120-describe: correct test repo history graph in commentSZEDER Gábor, Nov 12, 2019
  61. 03/13 name-rev: use strbuf_strip_suffix() in get_rev_name()SZEDER Gábor, Nov 12, 2019
  62. René ScharfeNov 12, 2019
  63. 02/13 t6120-describe: modernize the 'check_describe' helperSZEDER Gábor, Nov 12, 2019
  64. Jonathan TanNov 27, 2019
  65. 07/13 name-rev: extract creating/updating a 'struct name_rev' into a helperSZEDER Gábor, Nov 12, 2019
  66. 05/13 name-rev: use sizeof(*ptr) instead of sizeof(type) in allocationSZEDER Gábor, Nov 12, 2019
  67. 08/13 name-rev: pull out deref handling from the recursionSZEDER Gábor, Nov 12, 2019
  68. 06/13 t6120: add a test to cover inner conditions in 'git name-rev's name_rev()SZEDER Gábor, Nov 12, 2019
  69. 09/13 name-rev: restructure parsing commits and applying date cutoffSZEDER Gábor, Nov 12, 2019
  70. 04/13 name-rev: avoid unnecessary cast in name_ref()SZEDER Gábor, Nov 12, 2019
  71. 11/13 name-rev: drop name_rev()'s 'generation' and 'distance' parametersSZEDER Gábor, Nov 12, 2019
  72. Jonathan TanNov 27, 2019
  73. 13/13 name-rev: cleanup name_ref()SZEDER Gábor, Nov 12, 2019
  74. Jonathan TanNov 27, 2019
  75. SZEDER GáborDec 9, 2019
  76. 10/13 name-rev: restructure creating/updating 'struct rev_name' instancesSZEDER Gábor, Nov 12, 2019
  77. 12/13 name-rev: eliminate recursion in name_rev()SZEDER Gábor, Nov 12, 2019
  78. Jonathan TanNov 27, 2019
  79. SZEDER GáborDec 9, 2019
  80. Johannes SchindelinNov 12, 2019
  81. Sebastiaan DammannNov 13, 2019
  82. 00/14 name-rev: eliminate recursionSZEDER Gábor, Dec 9, 2019
  83. 01/14 t6120-describe: correct test repo history graph in commentSZEDER Gábor, Dec 9, 2019
  84. 02/14 t6120-describe: modernize the 'check_describe' helperSZEDER Gábor, Dec 9, 2019
  85. 03/14 name-rev: use strbuf_strip_suffix() in get_rev_name()SZEDER Gábor, Dec 9, 2019
  86. 04/14 name-rev: avoid unnecessary cast in name_ref()SZEDER Gábor, Dec 9, 2019
  87. 05/14 name-rev: use sizeof(*ptr) instead of sizeof(type) in allocationSZEDER Gábor, Dec 9, 2019
  88. 07/14 name-rev: extract creating/updating a 'struct name_rev' into a helperSZEDER Gábor, Dec 9, 2019
  89. 06/14 t6120: add a test to cover inner conditions in 'git name-rev's name_rev()SZEDER Gábor, Dec 9, 2019
  90. 08/14 name-rev: pull out deref handling from the recursionSZEDER Gábor, Dec 9, 2019
  91. 11/14 name-rev: drop name_rev()'s 'generation' and 'distance' parametersSZEDER Gábor, Dec 9, 2019
  92. 12/14 name-rev: use 'name->tip_name' instead of 'tip_name'SZEDER Gábor, Dec 9, 2019
  93. 10/14 name-rev: restructure creating/updating 'struct rev_name' instancesSZEDER Gábor, Dec 9, 2019
  94. 09/14 name-rev: restructure parsing commits and applying date cutoffSZEDER Gábor, Dec 9, 2019
  95. 14/14 name-rev: cleanup name_ref()SZEDER Gábor, Dec 9, 2019
  96. 13/14 name-rev: eliminate recursion in name_rev()SZEDER Gábor, Dec 9, 2019
  97. Derrick StoleeDec 9, 2019
  98. Junio C HamanoDec 11, 2019

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.