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

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

From
Kristofer Karlsson <krka@spotify.com>
Date
Jun 7, 2026, 09:30 UTC
Message-ID
<CAL71e4NDJtMN+i6E+BwQ=rvM4o8gwuDRUAn5fuQhYnQH_CzCxA@mail.gmail.com>
In-Reply-To
<fe20bde6-9e86-4162-9bbd-af4d058e499e@web.de>
On Sun, 7 Jun 2026 at 09:30, René Scharfe <l.s.r@web.de> wrote:
>
> Calling flush_get() later, when we know that we have items and a
> compare function, is cleaner, as we never need it in LIFO mode, and
> is also slightly faster (patch below).

Thanks for the benchmark and the suggestion to move flush_get() below the LIFO check - that's cleaner since LIFO never sets get_pending.

One edge case to note: without a second !nr_internal check after flush_get(), two consecutive get() calls on a single-element queue will return stale data instead of NULL. I went a step further and inlined the flush logic directly into get()/peek(), which also removes the forward declaration.

> Still there's this 1% performance gap to the current code that I
> don't understand.  Do you see it as well?

Yes, I saw a similar trend on my laptop (Core Ultra 7 155U), but with very high variance - the results were too noisy to be conclusive even with 20+ runs. On an idle server (Xeon @ 2.20GHz) with much lower variance, all three variants (v2 as posted, your patch, and the inlined version) came out ~1.3% faster than the baseline across 30 interleaved runs (p < 0.01). So it seems CPU-dependent - possibly branch prediction or code alignment differences between microarchitectures.

Results from the idle server (30 interleaved runs, paired t-test):
  Variant               Avg       SE  vs baseline           95% CI          p
  -------------- ---------- -------- ------------ ---------------- ----------
  baseline          2002.5ms     9.2ms   (baseline)
  v2-posted         1976.6ms     3.2ms      -1.29%    -41 to -11ms     0.0019
  v2-rene           1977.7ms     3.1ms      -1.24%    -42 to  -8ms     0.0071
  v2-latest         1975.3ms     1.8ms      -1.36%    -46 to  -9ms     0.0069
  baseline:  9ac3f193c0 (The 11th batch)
  v2-posted: v2 as sent to the list
  v2-rene:   v2 + your flush_get patch
  v2-latest: v2 + inlined flush (for v3)
Will send a v3 with the inlined flush shortly.
- Kristofer
Previous: René ScharfeNext: Kristofer Karlsson via GitGitGadget
Message 9 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.