git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Junio C Hamano <gitster@pobox.com>
Date
Jun 30, 2026, 20:59 UTC
Message-ID
<xmqqh5mjrbgq.fsf@gitster.g>
In-Reply-To
<pull.2140.v4.git.1780945851.gitgitgadget@gmail.com>

"Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com> writes:

Show 33 quoted lines
> 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.
Previous: Kristofer Karlsson via GitGitGadgetNext: Kristofer Karlsson
Message 17 of 18 in “prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion”
  1. prio-queue: fold lazy_queue into prio_queue for automatic get+put fusionKristofer Karlsson via GitGitGadget, Jun 6, 2026
  2. Junio C HamanoJun 6, 2026
  3. Kristofer KarlssonJun 6, 2026
  4. Junio C HamanoJun 8, 2026
  5. 0/2 prio-queue: fold lazy_queue into prio_queue for automatic get+put fusionKristofer Karlsson via GitGitGadget, Jun 6, 2026
  6. 1/2 prio-queue: fold lazy_queue into prio_queue for automatic get+put fusionKristofer Karlsson via GitGitGadget, Jun 6, 2026
  7. 2/2 prio-queue: rename .nr to .nr_internal to prevent direct accessKristofer Karlsson via GitGitGadget, Jun 6, 2026
  8. René ScharfeJun 7, 2026
  9. Kristofer KarlssonJun 7, 2026
  10. 0/2 prio-queue: fold lazy_queue into prio_queue for automatic get+put fusionKristofer Karlsson via GitGitGadget, Jun 7, 2026
  11. 1/2 prio-queue: fold lazy_queue into prio_queue for automatic get+put fusionKristofer Karlsson via GitGitGadget, Jun 7, 2026
  12. 2/2 prio-queue: rename .nr to .nr_internal to prevent direct accessKristofer Karlsson via GitGitGadget, Jun 7, 2026
  13. Junio C HamanoJun 8, 2026
  14. 0/2 prio-queue: fold lazy_queue into prio_queue for automatic get+put fusionKristofer Karlsson via GitGitGadget, Jun 8, 2026
  15. 1/2 prio-queue: rename .nr to .nr_ and add accessor helpersKristofer Karlsson via GitGitGadget, Jun 8, 2026
  16. 2/2 prio-queue: fold lazy_queue into prio_queue for automatic get+put fusionKristofer Karlsson via GitGitGadget, Jun 8, 2026
  17. Junio C HamanoJun 30, 2026
  18. Kristofer KarlssonJun 30, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.