From: Junio C Hamano Date: Tue, 30 Jun 2026 20:59:33 GMT Subject: Re: [PATCH v4 0/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion Message-ID: In-Reply-To: "Kristofer Karlsson via GitGitGadget" writes: > 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 1.7-2.7% speedup on traversal-heavy workloads is a nice bonus. > > More details and benchmark numbers in the commit message. > > Related to but independent of the cascade sift-down work in > kk/prio-queue-cascade-sift -- the two can land in either order. > > Changes in v4: > > * Thanks Junio for review, applied all suggestions. > > * Renamed .nr_internal to .nr_ > > * Restored flush_get() as a static inline helper instead of inlining the > flush logic into get() and peek(). > > * Guard empty-queue check with nr_ <= get_pending. > > * Flipped commit order: the rename/accessor commit is now first, and the > behavioral fusion change is second. This was partly messy -- the first > rename commit introduces some ugly intermediate code (e.g. describe.c's > prio_queue_for_each with a skip variable) that gets cleaned up in commit > 2 when the lazy get makes it unnecessary. So, this is the "other" topic that we would want to merge first before the kk/prio-queue-cascade-sift topic. This round looks good to me. Thanks.