[PATCH v2 0/3] commit: convert pop_most_recent_commit() to prio_queue

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()

 commit.c                          | 14 ++++--
 commit.h                          |  8 ++--
 fetch-pack.c                      | 13 +++---
 object-name.c                     | 10 ++---
 prio-queue.c                      | 45 ++++++++++++++------
 prio-queue.h                      |  8 ++++
 t/meson.build                     |  1 +
 t/perf/p1501-rev-parse-oneline.sh | 71 +++++++++++++++++++++++++++++++
 t/unit-tests/u-prio-queue.c       | 23 ++++++++++
 walker.c                          | 11 +++--
 10 files changed, 170 insertions(+), 34 deletions(-)
 create mode 100755 t/perf/p1501-rev-parse-oneline.sh

Range-diff against v1:
1:  d9c0d13801 ! 1:  5bff885d0f commit: convert pop_most_recent_commit() to prio_queue
    @@ Metadata
      ## Commit message ##
         commit: 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.
    +    pop_most_recent_commit() calls commit_list_insert_by_date() for parent
    +    commits, which is itself called in a loop.  This can lead to quadratic
    +    complexity if there are many merges.  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
    @@ object-name.c: static enum get_oid_result get_oid_with_context_1(struct reposito
      
      			free_commit_list(list);
     
    + ## t/meson.build ##
    +@@ t/meson.build: 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',
    +
      ## t/perf/p1501-rev-parse-oneline.sh (new) ##
     @@
     +#!/bin/sh
    @@ t/perf/p1501-rev-parse-oneline.sh (new)
     +
     +test_perf_fresh_repo
     +
    ++#
    ++# 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.
    ++#
     +build_history () {
     +	local max_level="$1" &&
     +	local level="${2:-1}" &&
    @@ t/perf/p1501-rev-parse-oneline.sh (new)
     +	sed -n -e "s/^.* //p" -e "q" <commits >needle
     +'
     +
    -+test_perf "rev-parse ':/$(cat needle)'" "
    -+	git rev-parse ':/$(cat needle)' >actual
    -+"
    ++test_perf "rev-parse :/$(cat needle)" '
    ++	git rev-parse :/$(cat needle) >actual
    ++'
     +
     +test_expect_success 'verify result' '
     +	test_cmp expect actual
2:  a4011d850c = 2:  a2e57ca443 prio-queue: add prio_queue_replace()
3:  dc535e8b64 ! 3:  1cbea38524 commit: use prio_queue_replace() in pop_most_recent_commit()
    @@ commit.c: void commit_list_sort_by_date(struct commit_list **list)
      {
     -	struct commit *ret = prio_queue_get(queue);
     +	struct commit *ret = prio_queue_peek(queue);
    -+	int delete_pending = 1;
    ++	int get_pending = 1;
      	struct commit_list *parents = ret->parents;
      
      	while (parents) {
    @@ commit.c: void commit_list_sort_by_date(struct commit_list **list)
      		if (!repo_parse_commit(the_repository, commit) && !(commit->object.flags & mark)) {
      			commit->object.flags |= mark;
     -			prio_queue_put(queue, commit);
    -+			if (delete_pending)
    ++			if (get_pending)
     +				prio_queue_replace(queue, commit);
     +			else
     +				prio_queue_put(queue, commit);
    -+			delete_pending = 0;
    ++			get_pending = 0;
      		}
      		parents = parents->next;
      	}
    -+	if (delete_pending)
    ++	if (get_pending)
     +		prio_queue_get(queue);
      	return ret;
      }