patch, 4 partsline-log: optimize merge commit processing

The first patch is an optimization of the line-level log machinery. The rest are cleanups in the area that I subjectively consider slight improvements.

SZEDER Gábor (4):
  line-log: avoid unnecessary tree diffs when processing merge commits
  line-log: get rid of the parents array in
    process_ranges_merge_commit()
  line-log: initialize diff queue in process_ranges_ordinary_commit()
  line-log: simplify condition checking for merge commits

 line-log.c | 50 ++++++++++++++++++++------------------------------
 1 file changed, 20 insertions(+), 30 deletions(-)

In process_ranges_merge_commit(), the line-level log first creates an array of diff queues by iterating over all parents of a merge commit and computing a tree diff for each. Then in a second loop it iterates over those diff queues, and if it finds that none of the interesting paths were modified in one of them, then it will return early. This means that when none of the interesting paths were modified between a merge and its first parent, then the tree diff between the merge and its second (Nth...) parent was computed in vain.

Unify these two loops, so when it iterates over all parents of a merge commit, then it first computes the tree diff between the merge and that particular parent and then processes the resulting diff queue right away. This way we can spare some tree diff computing, thereby speeding up line-level log in repositories with mergy history:

  # git.git, 25.8% of commits are merges:
  Benchmark 1: ./git_v2.51.0 -C ~/src/git log -L:'lookup_commit(':commit.c v2.51.0
    Time (mean ± σ):      1.001 s ±  0.009 s    [User: 0.906 s, System: 0.095 s]
    Range (min … max):    0.991 s …  1.023 s    10 runs

  Benchmark 2: ./git -C ~/src/git log -L:'lookup_commit(':commit.c v2.51.0
    Time (mean ± σ):     445.5 ms ±   3.4 ms    [User: 358.8 ms, System: 84.3 ms]
    Range (min … max):   440.1 ms … 450.3 ms    10 runs

  Summary
    './git -C ~/src/git log -L:'lookup_commit(':commit.c v2.51.0' ran
      2.25 ± 0.03 times faster than './git_v2.51.0 -C ~/src/git log -L:'lookup_commit(':commit.c v2.51.0'

  # linux.git, 7.5% of commits are merges:
  Benchmark 1: ./git_v2.51.0 -C ~/src/linux.git log -L:build_restore_work_registers:arch/mips/mm/tlbex.c v6.16
    Time (mean ± σ):      3.246 s ±  0.007 s    [User: 2.835 s, System: 0.409 s]
    Range (min … max):    3.232 s …  3.255 s    10 runs

  Benchmark 2: ./git -C ~/src/linux.git log -L:build_restore_work_registers:arch/mips/mm/tlbex.c v6.16
    Time (mean ± σ):      2.467 s ±  0.014 s    [User: 2.113 s, System: 0.353 s]
    Range (min … max):    2.455 s …  2.505 s    10 runs

  Summary
    './git -C ~/src/linux.git log -L:build_restore_work_registers:arch/mips/mm/tlbex.c v6.16' ran
      1.32 ± 0.01 times faster than './git_v2.51.0 -C ~/src/linux.git log -L:build_restore_work_registers:arch/mips/mm/tlbex.c v6.16'

And since now each iteration computes a tree diff and processes its result, there is no reason to store the diff queues for each merge parent anymore, so replace that diff queue array with a loop-local diff queue variable. With this change the static free_diffqueues() helper function in 'line-log.c' has no more callers left, remove it.

Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
---
 line-log.c | 20 +++++---------------
 1 file changed, 5 insertions(+), 15 deletions(-)

On 8/24/2025 3:06 PM, SZEDER Gábor wrote:

Great find! This goes all the way back to the original implementation in 12da1d1f6f (Implement line-history search (git log -L), 2013-03-28) where this detail could easily be missed in the rest of the scaffolding to implement the feature.

This is an understandable mistake to make as it can take some time to understand Git's simplified history computation and how it short- circuits these merge diffs in most cases.

Great stats!

This diff is a lot cleaner than I expected it to be. Excellent!

I applied this patch locally and tested it on a few repos I have to give extra confidence to your patch.

For an internal monorepo, I was able to measure these results:

Benchmark 1: old
  Time (mean ± σ):     19.709 s ±  0.014 s    [User: 18.846 s, System: 0.862 s]
  Range (min … max):   19.681 s … 19.725 s    10 runs
 
Benchmark 2: new
  Time (mean ± σ):      9.061 s ±  0.015 s    [User: 8.487 s, System: 0.574 s]
  Range (min … max):    9.042 s …  9.089 s    10 runs
 
Summary
  'new' ran
    2.18 ± 0.00 times faster than 'old'

I did also want to check to see the impact of f32dde8c12 (line-log: integrate with changed-path Bloom filters, 2020-05-11), and having computed filters diminished the size of your impact somewhat:

Your Git example:

Benchmark 1: old
  Time (mean ± σ):     279.2 ms ±   2.2 ms    [User: 231.0 ms, System: 47.9 ms]
  Range (min … max):   275.5 ms … 282.6 ms    10 runs
 
Benchmark 2: new 
  Time (mean ± σ):     242.4 ms ±   3.6 ms    [User: 191.8 ms, System: 50.4 ms]
  Range (min … max):   237.3 ms … 249.9 ms    12 runs
 
Summary
  'new ' ran
    1.15 ± 0.02 times faster than 'old'

Your Linux example:

Benchmark 1: old
  Time (mean ± σ):      1.694 s ±  0.008 s    [User: 1.524 s, System: 0.169 s]
  Range (min … max):    1.688 s …  1.714 s    10 runs
 
Benchmark 2: new 
  Time (mean ± σ):      1.644 s ±  0.008 s    [User: 1.482 s, System: 0.161 s]
  Range (min … max):    1.636 s …  1.663 s    10 runs
 
Summary
  'new ' ran
    1.03 ± 0.01 times faster than 'old'

My internal monorepo example:

Benchmark 1: old
  Time (mean ± σ):      3.749 s ±  0.007 s    [User: 3.188 s, System: 0.559 s]
  Range (min … max):    3.736 s …  3.759 s    10 runs
 
Benchmark 2: new
  Time (mean ± σ):      2.713 s ±  0.005 s    [User: 2.318 s, System: 0.394 s]
  Range (min … max):    2.706 s …  2.723 s    10 runs
 
Summary
  'new' ran
    1.38 ± 0.00 times faster than 'old'

Rerunning with "-c commitGraph.readChangedPaths=false" resulted in numbers closer to your examples (940ms->420ms for Git and 2.6->2.1s for Linux). I expect most users to be in the situation where there are no changed-path Bloom filters, so this is very good to deliver that value.

At first, I found this to be concerning: we only store filters for the diff between a commit and its first parent, so this cost of visiting the later parents should be _much worse_ in those cases. However, it turns out that the way that the filters are handled in line_log_process_ranges_arbitrary_commit() avoids a call to process_ranges_merge_commit() if the filter says that the first parent is TREESAME on the given path.

This means that a good chunk of the performance benefits in f32dde8c12 (line-log: integrate with changed-path Bloom filters, 2020-05-11) are _actually_ due to avoiding this extra work for multiple parents. Thanks for digging in and bringing this benefit to all users!

Thanks, -Stolee

SZEDER Gábor <szeder.dev@gmail.com> writes:

This is surprisingly small change that eliminates quite a lot of waste. Nicely done.

On Mon, Aug 25, 2025 at 08:35:53AM -0700, Junio C Hamano wrote:

It's funny you say that...

This patch series just turned 6 years old this weekend, and up until Sunday morning this first patch was actually two, because the optimization and the removal of the now unnecessary diffqueues array were two separate patches that I finally decided to squash together.

Here is the diff of that optimization-only patch :)

  ---- >8 ----

 line-log.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)

We can easily iterate through the parents of a merge commit without turning the list of parents into a dynamically allocated array of parents, so let's do so. This way we can avoid a memory allocation for each processed merge commit, though its effect on runtime seems to be unmeasurable.

Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
---
 line-log.c | 24 ++++++++++++------------
 1 file changed, 12 insertions(+), 12 deletions(-)

process_ranges_ordinary_commit() uses a local diff queue variable, which it leaves uninitialized before passing its address to queue_diffs(). This is not an issue, because at the end of that function the contents of an other diff queue is moved into it by simply overwriting whatever is in there, i.e. without reading any uninitialized memory.

Still, seeing the uninitialized diff queue being passed around scared me more than once, so out of caution let's make sure that it's initialized.

Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
---
 line-log.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

In process_ranges_arbitrary_commit() the condition deciding whether the given commit is not a merge, i.e. that it doesn't have more than one parent, is head-scratchingly backwards, flip it.

Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
---
 line-log.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

SZEDER Gábor <szeder.dev@gmail.com> writes:

Hmph, the condition is about "is it a root commit? or is it a single-parent commit?", which does not sound overly complicated to me.

On 8/25/2025 4:57 PM, Junio C Hamano wrote:

It is something that one can interpret carefully by thinking about it, but the negation and OR condition made me need to pause and think about it, while the positive of "does it have a parent and a second parent?" was something that flowed naturally when I read it.

Definitely a taste thing, so I could see you wanting to skip this one on a pure "don't touch what's not broken" policy.

Thanks, -Stolee

Derrick Stolee <stolee@gmail.com> writes:

Yeah, that I 100% agree with.  If it were

	if (!(c->parent && c->parent->next))
		handle_ordinary_commit();
	else
		handle_merge_commit();

that would have been very easy to grok. I do not have a strong preference between that and

	if (c->parent && c->parent->next)
		handle_merge_commit();
	else
		handle_ordinary_commit();

myself, but I always felt that handling ordinary commits was the primary thing in this code path, which made me react to the swapping of orders of these two calls.

True, too, but the code that fails to be in a readable shape too falls into the "broken" category, so in that sense I do not mind queuing the patch, either (and indeed tonight's 'seen' will include this step in the topic).

Thanks.

On 8/24/2025 3:06 PM, SZEDER Gábor wrote:

I gave a detailed double-check of your perf numbers in a direct reply to that patch.

These cleanups are very welcome. The whole series is excellent.

Thanks, -Stolee