[PATCH v2 0/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion

["Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com>]

Rene's lazy_queue wrapper in describe.c was a clever optimization -- by
deferring the get, a following put becomes a simple replace, avoiding a full
remove-rebalance-insert cycle.

It turns out this pattern is so common in git's traversal code that it makes
sense to fold it into prio_queue itself. Gets and puts are interleaved in
virtually every commit walk, so the fusion is essentially always a win.

This is mostly a code simplification -- three callers had independently
reimplemented the same optimization, and they all collapse to plain get+put
now. The 3-6% speedup on traversal-heavy workloads is a nice bonus.

More details and benchmark numbers in the commit message. Benchmarks were
run on next which includes kk/commit-reach-optim -- those results represent
the more realistic end state.

Related to but independent of the cascade sift-down work in
kk/prio-queue-cascade-sift -- the two can land in either order.

Changes since v1:

 * Added a second commit that renames .nr to .nr_internal so that direct
   access from outside prio-queue.c is a compile error. Verified that after
   the rename, only prio-queue.c references nr_internal.

 * Added prio_queue_for_each() macro for callers that need to walk all
   elements (describe.c, show-branch.c, commit-reach.c, revision.c,
   negotiator/skipping.c).

 * Converted remaining .nr loop conditions to use
   prio_queue_get()/prio_queue_peek() as the loop condition, or
   prio_queue_size() where get/peek isn't suitable.

 * Fixed several callers missed in v1 (object-name.c, fetch-pack.c,
   path-walk.c, pack-bitmap-write.c, negotiator/default.c,
   negotiator/skipping.c, revision.c, builtin/last-modified.c).

Kristofer Karlsson (2):
  prio-queue: fold lazy_queue into prio_queue for automatic get+put
    fusion
  prio-queue: rename .nr to .nr_internal to prevent direct access

 builtin/describe.c          | 70 ++++++++-------------------------
 builtin/last-modified.c     |  7 ++--
 builtin/show-branch.c       | 24 +++++-------
 commit-reach.c              | 24 ++++++------
 commit.c                    | 11 +-----
 fetch-pack.c                |  4 +-
 negotiator/default.c        |  4 +-
 negotiator/skipping.c       | 12 +++---
 object-name.c               |  2 +-
 pack-bitmap-write.c         | 10 ++---
 path-walk.c                 |  8 ++--
 prio-queue.c                | 77 ++++++++++++++++++++-----------------
 prio-queue.h                | 19 +++++----
 revision.c                  | 16 ++++----
 t/unit-tests/u-prio-queue.c |  6 +--
 walker.c                    |  4 +-
 16 files changed, 129 insertions(+), 169 deletions(-)


base-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2140%2Fspkrka%2Flazy-prio-queue-pr-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2140/spkrka/lazy-prio-queue-pr-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/2140

Range-diff vs v1:

 1:  29af24445e = 1:  29af24445e prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion
 -:  ---------- > 2:  bb8b0f78f1 prio-queue: rename .nr to .nr_internal to prevent direct access

-- 
gitgitgadget