patch, 3 partscommit: convert pop_most_recent_commit() to prio_queue

> pop_most_recent_commit() calls commit_list_insert_by_date(), which and
> is itself called in a loop, which can lead to quadratic complexity.
> Replace the commit_list with a prio_queue to ensure logarithmic worst
> case complexity and convert all three users.
>
> Add a performance test that exercises one of them using a pathological
> history that consists of 50% merges and 50% root commits to demonstrate
> the speedup:
>
>    Test                          v2.50.1           HEAD
>    ----------------------------------------------------------------------
>    1501.2: rev-parse ':/65535'   2.48(2.47+0.00)   0.20(0.19+0.00) -91.9%
>
> Alas, sane histories don't benefit from the conversion much, and
> traversing Git's own history takes a 1% performance hit on my machine:

>    $ hyperfine -w3 -L git ./git_2.50.1,./git '{git} rev-parse :/^Initial.revision'
>    Benchmark 1: ./git_2.50.1 rev-parse :/^Initial.revision
>      Time (mean ± σ):      1.071 s ±  0.004 s    [User: 1.052 s, System: 0.017 s]
>      Range (min … max):    1.067 s …  1.078 s    10 runs
>
>    Benchmark 2: ./git rev-parse :/^Initial.revision
>      Time (mean ± σ):      1.079 s ±  0.003 s    [User: 1.060 s, System: 0.017 s]
>      Range (min … max):    1.074 s …  1.083 s    10 runs
>
>    Summary
>      ./git_2.50.1 rev-parse :/^Initial.revision ran
>        1.01 ± 0.00 times faster than ./git rev-parse :/^Initial.revision

> Add a performance test that exercises one of them using a pathological
> history that consists of 50% merges and 50% root commits to demonstrate
> the speedup:
> 
>    Test                          v2.50.1           HEAD
>    ----------------------------------------------------------------------
>    1501.2: rev-parse ':/65535'   2.48(2.47+0.00)   0.20(0.19+0.00) -91.9%
> 
> Alas, sane histories don't benefit from the conversion much, and
> traversing Git's own history takes a 1% performance hit on my machine:

>    $ hyperfine -w3 -L git ./git_2.50.1,./git '{git} rev-parse :/^Initial.revision'
>    Benchmark 1: ./git_2.50.1 rev-parse :/^Initial.revision
>      Time (mean ± σ):      1.071 s ±  0.004 s    [User: 1.052 s, System: 0.017 s]
>      Range (min … max):    1.067 s …  1.078 s    10 runs
> 
>    Benchmark 2: ./git rev-parse :/^Initial.revision
>      Time (mean ± σ):      1.079 s ±  0.003 s    [User: 1.060 s, System: 0.017 s]
>      Range (min … max):    1.074 s …  1.083 s    10 runs
> 
>    Summary
>      ./git_2.50.1 rev-parse :/^Initial.revision ran
>        1.01 ± 0.00 times faster than ./git rev-parse :/^Initial.revision
> 
> Signed-off-by: René Scharfe <l.s.r@web.de>
> ---
>  commit.c                          |  7 ++--
>  commit.h                          |  8 ++---
>  fetch-pack.c                      | 13 +++++---
>  object-name.c                     | 10 +++---
>  t/perf/p1501-rev-parse-oneline.sh | 55 +++++++++++++++++++++++++++++++
>  walker.c                          | 11 ++++---
>  6 files changed, 83 insertions(+), 21 deletions(-)
>  create mode 100755 t/perf/p1501-rev-parse-oneline.sh
> 
> diff --git a/commit.c b/commit.c
> index e915b2b9a1..0200759aaa 100644
> --- a/commit.c
> +++ b/commit.c
> @@ -31,6 +31,7 @@
>  #include "parse.h"
>  #include "object-file.h"
>  #include "object-file-convert.h"
> +#include "prio-queue.h"
>  
>  static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **);
>  
> @@ -738,17 +739,17 @@ void commit_list_sort_by_date(struct commit_list **list)
>  	commit_list_sort(list, commit_list_compare_by_date);
>  }
>  
> -struct commit *pop_most_recent_commit(struct commit_list **list,
> +struct commit *pop_most_recent_commit(struct prio_queue *queue,
>  				      unsigned int mark)
>  {
> -	struct commit *ret = pop_commit(list);
> +	struct commit *ret = prio_queue_get(queue);
>  	struct commit_list *parents = ret->parents;
>  
>  	while (parents) {
>  		struct commit *commit = parents->item;
>  		if (!repo_parse_commit(the_repository, commit) && !(commit->object.flags & mark)) {
>  			commit->object.flags |= mark;
> -			commit_list_insert_by_date(commit, list);
> +			prio_queue_put(queue, commit);
>  		}
>  		parents = parents->next;
>  	}
> diff --git a/commit.h b/commit.h
> index 70c870dae4..9630c076d6 100644
> --- a/commit.h
> +++ b/commit.h
> @@ -201,10 +201,10 @@ const char *repo_logmsg_reencode(struct repository *r,
>  
>  const char *skip_blank_lines(const char *msg);
>  
> -/** Removes the first commit from a list sorted by date, and adds all
> - * of its parents.
> - **/
> -struct commit *pop_most_recent_commit(struct commit_list **list,
> +struct prio_queue;
> +
> +/* Removes the first commit from a prio_queue and adds its parents. */
> +struct commit *pop_most_recent_commit(struct prio_queue *queue,
>  				      unsigned int mark);

> On 25/07/15 04:51PM, René Scharfe wrote:
>> pop_most_recent_commit() calls commit_list_insert_by_date(), which and
> 
> Did you mean?
> 
> s/which and/which/

>> is itself called in a loop, which can lead to quadratic complexity.
>> Replace the commit_list with a prio_queue to ensure logarithmic worst
>> case complexity and convert all three users.
> 
> If I understand correctly, `pop_most_recent_commit()` removes the most
> recent commit from a list of commits sorted by date and then inserts
> each of the removed commit's parents into the list while maintaining
> date order. Iterating through `struct commit_list` every time to find
> where to insert each parent parent leads to quadratic complexity. For
> repositories with many merge commits, this could scale poorly.

>> Add a performance test that exercises one of them using a pathological
>> history that consists of 50% merges and 50% root commits to demonstrate
>> the speedup:
>>
>>    Test                          v2.50.1           HEAD
>>    ----------------------------------------------------------------------
>>    1501.2: rev-parse ':/65535'   2.48(2.47+0.00)   0.20(0.19+0.00) -91.9%
>>
>> Alas, sane histories don't benefit from the conversion much, and
>> traversing Git's own history takes a 1% performance hit on my machine:
> 
> As "normal" repositories don't benefit here, it might be nice to more
> explicitly mention the the types of repositories that do benefit.

>> diff --git a/commit.h b/commit.h
>> index 70c870dae4..9630c076d6 100644
>> --- a/commit.h
>> +++ b/commit.h
>> @@ -201,10 +201,10 @@ const char *repo_logmsg_reencode(struct repository *r,
>>  
>>  const char *skip_blank_lines(const char *msg);
>>  
>> -/** Removes the first commit from a list sorted by date, and adds all
>> - * of its parents.
>> - **/
>> -struct commit *pop_most_recent_commit(struct commit_list **list,
>> +struct prio_queue;
>> +
>> +/* Removes the first commit from a prio_queue and adds its parents. */
>> +struct commit *pop_most_recent_commit(struct prio_queue *queue,
>>  				      unsigned int mark);
> 
> Previously, `pop_most_recent_commit()` would ensure commits inserted in
> the list were done it date order. Now this depends on how the caller has
> configured the `struct prio_queue`. This is fine though as previously
> the caller was required to ensure the list was sorted to begin with
> otherwise it wouldn't work properly.

> @@ -1461,7 +1462,7 @@ static int get_oid_oneline(struct repository *r,
>  			   const char *prefix, struct object_id *oid,
>  			   const struct commit_list *list)
>  {
> -	struct commit_list *copy = NULL, **copy_tail = ©
> +	struct prio_queue copy = { compare_commits_by_commit_date };
>  	const struct commit_list *l;
>  	int found = 0;
>  	int negative = 0;
> @@ -1483,9 +1484,9 @@ static int get_oid_oneline(struct repository *r,
>  
>  	for (l = list; l; l = l->next) {
>  		l->item->object.flags |= ONELINE_SEEN;
> -		copy_tail = &commit_list_insert(l->item, copy_tail)->next;
> +		prio_queue_put(&copy, l->item);
>  	}
> -	while (copy) {
> +	while (copy.nr) {
>  		const char *p, *buf;
>  		struct commit *commit;
>  		int matches;

> +build_history () {
> +	local max_level="$1" &&
> +	local level="${2:-1}" &&
> +	local mark="${3:-1}" &&
> +	if test $level -eq $max_level
> +	then
> +		echo "reset refs/heads/master" &&
> +		echo "from $ZERO_OID" &&
> +		echo "commit refs/heads/master" &&
> +		echo "mark :$mark" &&
> +		echo "committer C <c@example.com> 1234567890 +0000" &&
> +		echo "data <<EOF" &&
> +		echo "$mark" &&
> +		echo "EOF"
> +	else
> +		local level1=$((level+1)) &&
> +		local mark1=$((2*mark)) &&
> +		local mark2=$((2*mark+1)) &&
> +		build_history $max_level $level1 $mark1 &&
> +		build_history $max_level $level1 $mark2 &&
> +		echo "commit refs/heads/master" &&
> +		echo "mark :$mark" &&
> +		echo "committer C <c@example.com> 1234567890 +0000" &&
> +		echo "data <<EOF" &&
> +		echo "$mark" &&
> +		echo "EOF" &&
> +		echo "from :$mark1" &&
> +		echo "merge :$mark2"
> +	fi
> +}

> On Tue, Jul 15, 2025 at 04:51:07PM +0200, René Scharfe wrote:
> 
>> pop_most_recent_commit() calls commit_list_insert_by_date(), which and
>> is itself called in a loop, which can lead to quadratic complexity.
>> Replace the commit_list with a prio_queue to ensure logarithmic worst
>> case complexity and convert all three users.
> 
> I guess I'm cc'd because of my frequent complains about the quadratic
> nature of our commit lists? :)

> The patch itself looks reasonable. I think here:
> 
>> @@ -1461,7 +1462,7 @@ static int get_oid_oneline(struct repository *r,
>>  			   const char *prefix, struct object_id *oid,
>>  			   const struct commit_list *list)
>>  {
>> -	struct commit_list *copy = NULL, **copy_tail = ©
>> +	struct prio_queue copy = { compare_commits_by_commit_date };
>>  	const struct commit_list *l;
>>  	int found = 0;
>>  	int negative = 0;
>> @@ -1483,9 +1484,9 @@ static int get_oid_oneline(struct repository *r,
>>  
>>  	for (l = list; l; l = l->next) {
>>  		l->item->object.flags |= ONELINE_SEEN;
>> -		copy_tail = &commit_list_insert(l->item, copy_tail)->next;
>> +		prio_queue_put(&copy, l->item);
>>  	}
>> -	while (copy) {
>> +	while (copy.nr) {
>>  		const char *p, *buf;
>>  		struct commit *commit;
>>  		int matches;
> 
> our callers are always generating and passing in a list. So we could
> avoid the overhead of allocating the list in the first place by just
> taking a prio_queue. But maybe it gets weird with clearing the
> ONELINE_SEEN marks? We make a copy even in the current code so that we
> can call clear_commit_marks() on the complete set.
> 
> I guess we could add them to an array or something, but that probably
> ends up being roughly the same amount of work.

>> +build_history () {
>> +	local max_level="$1" &&
>> +	local level="${2:-1}" &&
>> +	local mark="${3:-1}" &&
>> +	if test $level -eq $max_level
>> +	then
>> +		echo "reset refs/heads/master" &&
>> +		echo "from $ZERO_OID" &&
>> +		echo "commit refs/heads/master" &&
>> +		echo "mark :$mark" &&
>> +		echo "committer C <c@example.com> 1234567890 +0000" &&
>> +		echo "data <<EOF" &&
>> +		echo "$mark" &&
>> +		echo "EOF"
>> +	else
>> +		local level1=$((level+1)) &&
>> +		local mark1=$((2*mark)) &&
>> +		local mark2=$((2*mark+1)) &&
>> +		build_history $max_level $level1 $mark1 &&
>> +		build_history $max_level $level1 $mark2 &&
>> +		echo "commit refs/heads/master" &&
>> +		echo "mark :$mark" &&
>> +		echo "committer C <c@example.com> 1234567890 +0000" &&
>> +		echo "data <<EOF" &&
>> +		echo "$mark" &&
>> +		echo "EOF" &&
>> +		echo "from :$mark1" &&
>> +		echo "merge :$mark2"
>> +	fi
>> +}
> 
> This took some brain cycles to decipher. It looks like we'll make
> 2^$level commits in a filled tree? It might be worth a brief comment
> describing the goal (and maybe even giving an example graph drawing for
> N=3 or something, though it gets out of hand quickly).

>> +test_perf "rev-parse ':/$(cat needle)'" "
>> +	git rev-parse ':/$(cat needle)' >actual
>> +"
> 
> Hmm, usually we frown on putting snippets inside double-quotes because
> it's so easy to accidentally interpolate outside of the test_eval. But
> maybe this is short enough to be OK. I guess you did it here especially
> so that the title is a nice ":/65535" and not the opaque "$(cat
> needle)".

> On 7/16/25 7:05 AM, Jeff King wrote:
> 
>> I actually have a series turning rev_info.commits into a prio_queue
>> which I need to polish up (mostly just writing commit messages; I've
>> been running with it for almost 2 years without trouble). Ironically it
>> does not touch this spot, as these commit lists are formed on their own.
> 
> That is not a coincidence.  I had a look at that series and tried to
> reach its goals while keeping rev_info.commits a commit_list.  Why?
> Mostly being vaguely uncomfortable with prio_queue' memory overhead,
> lack of type safety and dual use as a stack.  I still used it, but only
> as local variable, not in the central struct rev_info.
> 
> Anyway, I failed; revision.c::get_revision_1() took an 8% performance
> hit in my versions and none in yours, and I couldn't figure out why.
> Perhaps I should revisit it with the new prio_queue_replace() in hand,
> hmm..

> On 7/16/25 7:05 AM, Jeff King wrote:
> > On Tue, Jul 15, 2025 at 04:51:07PM +0200, René Scharfe wrote:
> > 
> >> pop_most_recent_commit() calls commit_list_insert_by_date(), which and
> >> is itself called in a loop, which can lead to quadratic complexity.
> >> Replace the commit_list with a prio_queue to ensure logarithmic worst
> >> case complexity and convert all three users.
> > 
> > I guess I'm cc'd because of my frequent complains about the quadratic
> > nature of our commit lists? :)
> 
> And because you introduced prio_queue.

> > Mostly I asked because I had to look at pop_most_recent_commit() to see
> > what operation would be made faster here. Looks like it's mostly ":/",
> > but maybe also fetch's mark_recent_complete_commits()? I guess we might
> > hit that if you have a huge number of refs?
> 
> The :/ handling was the easiest to test for me.  fetch_pack() and
> walker_fetch() require some server side to set up, which seems not worth
> it just to demonstrate quadratic behavior.  Having thousands of refs
> would make the list long enough to notice, as would having lots of
> merges.

> > I actually have a series turning rev_info.commits into a prio_queue
> > which I need to polish up (mostly just writing commit messages; I've
> > been running with it for almost 2 years without trouble). Ironically it
> > does not touch this spot, as these commit lists are formed on their own.
> 
> That is not a coincidence.  I had a look at that series and tried to
> reach its goals while keeping rev_info.commits a commit_list.  Why?
> Mostly being vaguely uncomfortable with prio_queue' memory overhead,
> lack of type safety and dual use as a stack.  I still used it, but only
> as local variable, not in the central struct rev_info.

> > That is not a coincidence.  I had a look at that series and tried to
> > reach its goals while keeping rev_info.commits a commit_list.  Why?
> > Mostly being vaguely uncomfortable with prio_queue' memory overhead,
> > lack of type safety and dual use as a stack.  I still used it, but only
> > as local variable, not in the central struct rev_info.
> 
> Hmm, I would have thought prio_queue had less memory overhead. You're
> spending one pointer per entry in a packed array, versus list nodes. But
> it's true that it doesn't shrink as items are removed (though that is
> something we _could_ implement).
> 
> The dual use as a stack actually came in handy for my series, IIRC.
> There are spots which use a commit_list but care about a specific order,
> and my list/prio_queue conversion helpers use that to create a non-heap
> prio_queue that just returns the items in the original order (it's
> actually FIFO, but we can get that by reversing).
> 
> I dunno. That's kind of horrible when I say it out loud, but it did make
> things work. I'm surprised that your attempt ended up with a performance
> hit when mine did not. Mine tried not to be clever, and even leaves in
> place a few spots where we convert between the two representations to
> satisfy various interfaces (with the goal that we'd probably eventually
> switch to prio_queue everywhere).

> On Wed, Jul 16, 2025 at 11:39:49AM +0200, René Scharfe wrote:
> 
>> On 7/16/25 7:05 AM, Jeff King wrote:
>>> On Tue, Jul 15, 2025 at 04:51:07PM +0200, René Scharfe wrote:
>>>
>>>> pop_most_recent_commit() calls commit_list_insert_by_date(), which and
>>>> is itself called in a loop, which can lead to quadratic complexity.
>>>> Replace the commit_list with a prio_queue to ensure logarithmic worst
>>>> case complexity and convert all three users.
>>>
>>> I guess I'm cc'd because of my frequent complains about the quadratic
>>> nature of our commit lists? :)
>>
>> And because you introduced prio_queue.
> 
> I think that was Junio, but I think I can be counted as a cheerleader
> for the topic. :)

>>> I actually have a series turning rev_info.commits into a prio_queue
>>> which I need to polish up (mostly just writing commit messages; I've
>>> been running with it for almost 2 years without trouble). Ironically it
>>> does not touch this spot, as these commit lists are formed on their own.
>>
>> That is not a coincidence.  I had a look at that series and tried to
>> reach its goals while keeping rev_info.commits a commit_list.  Why?
>> Mostly being vaguely uncomfortable with prio_queue' memory overhead,
>> lack of type safety and dual use as a stack.  I still used it, but only
>> as local variable, not in the central struct rev_info.
> 
> Hmm, I would have thought prio_queue had less memory overhead. You're
> spending one pointer per entry in a packed array, versus list nodes. But
> it's true that it doesn't shrink as items are removed (though that is
> something we _could_ implement).

> > Hmm, I would have thought prio_queue had less memory overhead. You're
> > spending one pointer per entry in a packed array, versus list nodes. But
> > it's true that it doesn't shrink as items are removed (though that is
> > something we _could_ implement).
> 
> If we just count the net data then a commit_list item has two pointers
> and a prio_queue_entry has a pointer and an ID for stability.  That's a
> tie.  ALLOC_GROW overallocates by ca. 50%, so that's 25% more on
> average for the prio_queue.  No idea what overhead malloc() needs per
> allocation, but I guess it's enough to tilt the scale back against
> commit_lists.

> On Sat, Jul 19, 2025 at 01:15:28PM +0200, René Scharfe wrote:
>
>> > Hmm, I would have thought prio_queue had less memory overhead. You're
>> > spending one pointer per entry in a packed array, versus list nodes. But
>> > it's true that it doesn't shrink as items are removed (though that is
>> > something we _could_ implement).
>> 
>> If we just count the net data then a commit_list item has two pointers
>> and a prio_queue_entry has a pointer and an ID for stability.  That's a
>> tie.  ALLOC_GROW overallocates by ca. 50%, so that's 25% more on
>> average for the prio_queue.  No idea what overhead malloc() needs per
>> allocation, but I guess it's enough to tilt the scale back against
>> commit_lists.
>
> Oh right, I totally forgot about the extra counter.

> René Scharfe <l.s.r@web.de> writes:
> 
>>  t/perf/p1501-rev-parse-oneline.sh | 55 +++++++++++++++++++++++++++++++
>>  create mode 100755 t/perf/p1501-rev-parse-oneline.sh
> 
> This unfortunately calls for something like.
> 
> Tonight's integration cycle I have this on top of your series
> in 'seen'.
> 
> Subject: [PATCH] fixup! commit: convert pop_most_recent_commit() to prio_queue
> 
>  t/meson.build | 1 +
>  1 file changed, 1 insertion(+)
> 
> diff --git a/t/meson.build b/t/meson.build
> index d052fc3e23..b39f6d008d 100644
> --- a/t/meson.build
> +++ b/t/meson.build
> @@ -1117,6 +1117,7 @@ benchmarks = [
>    'perf/p1450-fsck.sh',
>    'perf/p1451-fsck-skip-list.sh',
>    'perf/p1500-graph-walks.sh',
> +  'perf/p1501-rev-parse-oneline.sh',
>    'perf/p2000-sparse-operations.sh',
>    'perf/p3400-rebase.sh',
>    'perf/p3404-rebase-interactive.sh',

> Add a function to replace the top element of the queue that basically
> does the same as prio_queue_get() followed by prio_queue_put(), but
> without the work by prio_queue_get() to rebalance the heap.  It can be
> used to optimize loops that get one element and then immediately add
> another one.  That's common e.g., with commit history traversal, where
> we get out a commit and then put in its parents.

> On Tue, Jul 15, 2025 at 04:51:22PM +0200, René Scharfe wrote:
> 
>> Add a function to replace the top element of the queue that basically
>> does the same as prio_queue_get() followed by prio_queue_put(), but
>> without the work by prio_queue_get() to rebalance the heap.  It can be
>> used to optimize loops that get one element and then immediately add
>> another one.  That's common e.g., with commit history traversal, where
>> we get out a commit and then put in its parents.
> 
> Hmm. But surely we still need to rebalance the heap after adding an
> element? And indeed, we still call the new sift_down_root() function.

> On 7/16/25 7:09 AM, Jeff King wrote:
>> On Tue, Jul 15, 2025 at 04:51:22PM +0200, René Scharfe wrote:
>>
>>> Add a function to replace the top element of the queue that basically
>>> does the same as prio_queue_get() followed by prio_queue_put(), but
>>> without the work by prio_queue_get() to rebalance the heap.  It can be
>>> used to optimize loops that get one element and then immediately add
>>> another one.  That's common e.g., with commit history traversal, where
>>> we get out a commit and then put in its parents.
>>
>> Hmm. But surely we still need to rebalance the heap after adding an
>> element? And indeed, we still call the new sift_down_root() function.
> 
> Yes.
> 
>> But I guess we are getting away without the "bubble up" operation that
>> put would do? So we are doing half as much work (but still big-O the
>> same)?
> 
> Yes.
> 
> I thought about building this optimization into prio_queue_get(), but
> that would require prio_queue_peek() and prio_queue_put() to be adjusted
> as well and all prio_queue users would have to be either made aware of
> the not-fully-heapified state, or prevented from accessing prio_queue
> properties like .nr and .array.

> > I thought about building this optimization into prio_queue_get(), but
> > that would require prio_queue_peek() and prio_queue_put() to be adjusted
> > as well and all prio_queue users would have to be either made aware of
> > the not-fully-heapified state, or prevented from accessing prio_queue
> > properties like .nr and .array.
> 
> Here's what that would like like.  .nr and .array elements are kept
> consistent at all times, but the root item is not in heap order after a
> prio_queue_get().  That's good enough to enumerate all prio_queue items
> like commit-reach.c::queue_has_nonstale() or
> negotiator/skipping.c::push_parent() do.

> Optimize pop_most_recent_commit() by adding the first parent using the
> more efficient prio_queue_peek() and prio_queue_replace() instead of
> prio_queue_get() and prio_queue_put().
>
> On my machine this neutralizes the performance hit it took in Git's own
> repository when we converted it to prio_queue two patches ago (git_pq):

> diff --git a/commit.c b/commit.c
> index 0200759aaa..8244221b30 100644
> --- a/commit.c
> +++ b/commit.c
> @@ -742,17 +742,24 @@ void commit_list_sort_by_date(struct commit_list **list)
>  struct commit *pop_most_recent_commit(struct prio_queue *queue,
>  				      unsigned int mark)
>  {
> -	struct commit *ret = prio_queue_get(queue);
> +	struct commit *ret = prio_queue_peek(queue);
> +	int delete_pending = 1;

>  	struct commit_list *parents = ret->parents;
>  
>  	while (parents) {
>  		struct commit *commit = parents->item;
>  		if (!repo_parse_commit(the_repository, commit) && !(commit->object.flags & mark)) {
>  			commit->object.flags |= mark;
> -			prio_queue_put(queue, commit);
> +			if (delete_pending)
> +				prio_queue_replace(queue, commit);
> +			else
> +				prio_queue_put(queue, commit);
> +			delete_pending = 0;
>  		}
>  		parents = parents->next;
>  	}
> +	if (delete_pending)
> +		prio_queue_get(queue);
>  	return ret;
>  }

> René Scharfe <l.s.r@web.de> writes:
> 
>> diff --git a/commit.c b/commit.c
>> index 0200759aaa..8244221b30 100644
>> --- a/commit.c
>> +++ b/commit.c
>> @@ -742,17 +742,24 @@ void commit_list_sort_by_date(struct commit_list **list)
>>  struct commit *pop_most_recent_commit(struct prio_queue *queue,
>>  				      unsigned int mark)
>>  {
>> -	struct commit *ret = prio_queue_get(queue);
>> +	struct commit *ret = prio_queue_peek(queue);
>> +	int delete_pending = 1;
> 
> Briefly I was puzzled by the name (I would have called first-parent
> since the logic was "we treat first parent specially by using
> replace instead of get/put"), but the variable signals "instead of
> get to remove the item from the queue, we just peeked, so we need to
> remove it later" with its name, which is understandable.

> 
>>  	struct commit_list *parents = ret->parents;
>>  
>>  	while (parents) {
>>  		struct commit *commit = parents->item;
>>  		if (!repo_parse_commit(the_repository, commit) && !(commit->object.flags & mark)) {
>>  			commit->object.flags |= mark;
>> -			prio_queue_put(queue, commit);
>> +			if (delete_pending)
>> +				prio_queue_replace(queue, commit);
>> +			else
>> +				prio_queue_put(queue, commit);
>> +			delete_pending = 0;
>>  		}
>>  		parents = parents->next;
>>  	}
>> +	if (delete_pending)
>> +		prio_queue_get(queue);
>>  	return ret;
>>  }

> René Scharfe <l.s.r@web.de> writes:
> 
> > Use prio_queue to improve worst-case performance at the cost of slightly
> > worse best-case performance.  Then add and use prio_queue_replace() to
> > recover that loss.
> 
> Would change in the tiebreaking behaviour (aka sort stability) also
> a cost of this change, as this swaps use of sorted linearly linked
> list with priority queue?

> On Tue, Jul 15, 2025 at 05:07:38PM -0700, Junio C Hamano wrote:
> 
>> René Scharfe <l.s.r@web.de> writes:
>>
>>> Use prio_queue to improve worst-case performance at the cost of slightly
>>> worse best-case performance.  Then add and use prio_queue_replace() to
>>> recover that loss.
>>
>> Would change in the tiebreaking behaviour (aka sort stability) also
>> a cost of this change, as this swaps use of sorted linearly linked
>> list with priority queue?
> 
> The prio_queue uses insertion order as a tie-breaker for stability (with
> earlier entries coming first). For building the initial queue from the
> list, I think that is obviously fine (we feed them in sorted order,
> which the prio queue will retain). For inserting while we walk the list,
> we'll produce the same results as long as the original code always
> inserted new entries after existing ones (in the case of a tie on commit
> date, that is).
> 
> And I think that is the case, since commit_list_insert_by_date() does
> this:
> 
>           while ((p = *pp) != NULL) {
>                   if (p->item->date < item->date) {
>                           break;
>                   }
>                   pp = &p->next;
>           }
>           return commit_list_insert(item, pp);
> 
> So we only insert once we have found an item in the list _after_ us,
> retaining the same order.
> 
> But hopefully somebody can double check my logic, as it is quite
> possible I got something reversed above. ;)

> Yes, commit_list_insert_by_date() is stable, as it inserts commits after
> ones with the same date.  Items are popped from the top, so this ensures
> FIFO behavior for commits with the same date.
> 
> prio_queue ensures stability using an ID and favors lower ones, so it
> provides the same order.
> 
> We should add unit tests for that, no?

> On Tue, Jul 15, 2025 at 05:07:38PM -0700, Junio C Hamano wrote:
>
>> René Scharfe <l.s.r@web.de> writes:
>> 
>> > Use prio_queue to improve worst-case performance at the cost of slightly
>> > worse best-case performance.  Then add and use prio_queue_replace() to
>> > recover that loss.
>> 
>> Would change in the tiebreaking behaviour (aka sort stability) also
>> a cost of this change, as this swaps use of sorted linearly linked
>> list with priority queue?
>
> The prio_queue uses insertion order as a tie-breaker for stability (with
> earlier entries coming first). For building the initial queue from the
> list, I think that is obviously fine (we feed them in sorted order,
> which the prio queue will retain).

> 
> +#
> +# Creates lots of merges to make history traversal costly.  In
> +# particular it creates 2^($max_level-1)-1 2-way merges on top of
> +# 2^($max_level-1) root commits.  E.g., the commit history looks like
> +# this for a $max_level of 3:
> +#
> +#     _1_
> +#    /   \
> +#   2     3
> +#  / \   / \
> +# 4   5 6   7
> +#
> +# The numbers are the fast-import marks, which also are the commit
> +# messages.  1 is the HEAD commit and a merge, 2 and 3 are also merges,
> +# 4-7 are the root commits.
> +#

> René Scharfe <l.s.r@web.de> writes:
>>
>> +#
>> +# Creates lots of merges to make history traversal costly.  In
>> +# particular it creates 2^($max_level-1)-1 2-way merges on top of
>> +# 2^($max_level-1) root commits.  E.g., the commit history looks like
>> +# this for a $max_level of 3:
>> +#
>> +#     _1_
>> +#    /   \
>> +#   2     3
>> +#  / \   / \
>> +# 4   5 6   7
>> +#
>> +# The numbers are the fast-import marks, which also are the commit
>> +# messages.  1 is the HEAD commit and a merge, 2 and 3 are also merges,
>> +# 4-7 are the root commits.
>> +#
> 
> I feel that the reason there's no significant performance improvement is probably
> because mostly we are using the priority queue to sort O(siblings) nodes.
> For example, in this case, the most time-consuming operation is when the priority
> queue or commit list contains 4 and 5, and we then need to insert 6 and 7.
> 
> Assuming the maximum number of siblings is W and the number of nodes is N,
> the time complexity with a commit list is O(W² × N), while using a priority queue
> gives O(W log W × N). Perhaps in many projects, W isn't particularly large,
> which results in the performance improvement not being very significant.

> We add and retrieve each commit in the (relevant part of) history.  That
> takes O(N) and O(1) for the sorted list, and O(log N) and O(log N) for
> the prio_queue, where N is the length of the list.
>
> So the best-case history is a string of single-parent commits, keeping
> only a single item on the list/queue throughout.  That requires no
> sorting or heaping, making the additions and retrievals O(1).  The
> overall complexity is then O(N) for both variants, N being the number
> of commits in the history.
>
> Worst-case history might be a single merge of all commits -- a
> centipede or myriapod?  With all commits on the sorted list we get a
> complexity of O(N²) for the traversal, and O(N log N) with a prio_queue.

> René Scharfe <l.s.r@web.de> writes:
> 
>> We add and retrieve each commit in the (relevant part of) history.  That
>> takes O(N) and O(1) for the sorted list, and O(log N) and O(log N) for
>> the prio_queue, where N is the length of the list.
>>
>> So the best-case history is a string of single-parent commits, keeping
>> only a single item on the list/queue throughout.  That requires no
>> sorting or heaping, making the additions and retrievals O(1).  The
>> overall complexity is then O(N) for both variants, N being the number
>> of commits in the history.
>>
>> Worst-case history might be a single merge of all commits -- a
>> centipede or myriapod?  With all commits on the sorted list we get a
>> complexity of O(N²) for the traversal, and O(N log N) with a prio_queue.
> 
> In other words, for a typical two-parent merge, we peek the current
> one, "replace" it with its first parent and then do the usual "put
> and sift it down into place" for the second one.  
> 
> I am wondering if there is a more optimization opportunity if we
> allowed "put more than one, and then sift all of them down into
> place".  In other words, if I told the machinery:
> 
>     I am doing this put.  I promise I won't do get until I say "now
>     I'll start doing get's, so you are free to delay your internal
>     state maintenance and do so immediately before my next 'get'".
> 
> and did such put's a few times before I do a 'get', would there be a
> way to teach the machinery to take advantage of the promise?

> Optimize pop_most_recent_commit() by adding the first parent using the
> more efficient prio_queue_peek() and prio_queue_replace() instead of
> prio_queue_get() and prio_queue_put().
> 
> [... clipped ...]

> Hi René,
> 
> On Fri, 18 Jul 2025, René Scharfe wrote:
> 
>> Optimize pop_most_recent_commit() by adding the first parent using the
>> more efficient prio_queue_peek() and prio_queue_replace() instead of
>> prio_queue_get() and prio_queue_put().
>>
>> [... clipped ...]
> 
> I noticed that v2 of this patch not only made it into `next`, but it also
> introduced a commit subject suffix (likely unintended?):
> 
>   [PATCH v2 3/3] commit: use prio_queue_replace() in pop_most_recent_commit(),MIME-Version: 1.0
> 
> Maybe that is something you want to look into?

> Use prio_queue to improve worst-case performance at the cost of slightly
> worse best-case performance.  Then add and use prio_queue_replace() to
> recover that loss.
> 
> Changes since v2:
> [...]

> Use prio_queue to improve worst-case performance at the cost of slightly
> worse best-case performance.  Then add and use prio_queue_replace() to
> recover that loss.
> 
> Changes since v2:
> - Mention that a prio_queue improves performance for merge-heavy
>   histories in the commit message.
> - Add the new perf script to Meson build file.
> - Mention which kind of history we are aiming for and show its shape in
>   a comment in the perf script.
> - Remove unnecessary quotes and use single quotes for the perf test
>   code.
> - Rename the variable delete_pending to get_pending to align it with
>   the concrete function prio_queue_get() instead of referring to the
>   abstract concept of deletion, to improve readability.
> 
>   commit: convert pop_most_recent_commit() to prio_queue
>   prio-queue: add prio_queue_replace()
>   commit: use prio_queue_replace() in pop_most_recent_commit()