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

Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min

From
Kristofer Karlsson <krka@spotify.com>
Date
Jul 6, 2026, 21:52 UTC
Message-ID
<CAL71e4NZYdpw5cvi6ARn1req8xaRGGg9X4xhZKp6S9Dz4K23aQ@mail.gmail.com>
In-Reply-To
<1aa5b755-0f74-46d5-bd6e-a9cb7f3fbb12@web.de>
On Sun, 7 Jun 2026 at 09:30, René Scharfe <l.s.r@web.de> wrote:
>
> So I guess we keep the full sift-down for prio_queue_replace(), knowing
> that sometimes we have a lot of items that end up at or close to the
> root of the heap.

The lazy-fold series (kk/prio-queue-get-put-fusion) is in next now. I rebased this cascade patch on top of it to check if it's still useful.

With lazy-fold in place the regression scenario you identified is resolved. The only remaining change is in flush_get(), where unfused gets now cascade instead of sifting down:

  -    queue->array[0] = queue->array[--queue->nr_];
  -    sift_down_root(queue);
  +    --queue->nr_;
  +    sift_up_rebalance(queue);
plus the ~20-line sift_up_rebalance() implementation.

I benchmarked this on the linux kernel repo and on a large merge-heavy repo.

The results are consistent: a real but small 1-2% end-to-end improvement across commands. A prio-queue microbenchmark would likely show a larger difference, but the queue is only a fraction of the total work in any real git operation.

The lazy-fold optimization cannibalized some of the value here, so cascade only helps the remaining unfused gets. As you observed, cascade is better there, but there are fewer of them now that there is more fusing happening.

I am on the fence about whether 1-2% end-to-end justifies adding another sift function. If you (René and Junio) think the benefit is too small for the code cost, I am happy to drop this patch. Otherwise I can submit a small reroll on top of kk/prio-queue-get-put-fusion (or rather next, in practice).

Thanks, Kristofer

Previous: Junio C HamanoNext: René Scharfe
Message 13 of 24 in “prio-queue: use cascade-down sift for faster extract-min”
  1. prio-queue: use cascade-down sift for faster extract-minKristofer Karlsson via GitGitGadget, May 31, 2026
  2. Junio C HamanoJun 1, 2026
  3. Junio C HamanoJun 1, 2026
  4. Kristofer KarlssonJun 1, 2026
  5. prio-queue: use cascade-down for faster extract-minKristofer Karlsson via GitGitGadget, Jun 1, 2026
  6. René ScharfeJun 2, 2026
  7. Kristofer KarlssonJun 2, 2026
  8. Kristofer KarlssonJun 5, 2026
  9. René ScharfeJun 7, 2026
  10. Kristofer KarlssonJun 7, 2026
  11. Junio C HamanoJun 29, 2026
  12. Junio C HamanoJun 8, 2026
  13. Kristofer KarlssonJul 6, 2026
  14. René ScharfeJul 8, 2026
  15. Kristofer KarlssonJul 8, 2026
  16. René ScharfeJul 8, 2026
  17. Kristofer KarlssonJul 8, 2026
  18. 0/2 prio-queue: use bottom-up sift for extract-minKristofer Karlsson via GitGitGadget, Jul 8, 2026
  19. 1/2 prio-queue: extract sift_up() from prio_queue_put()Kristofer Karlsson via GitGitGadget, Jul 8, 2026
  20. 2/2 prio-queue: use cascade for unfused getsKristofer Karlsson via GitGitGadget, Jul 8, 2026
  21. René ScharfeJul 10, 2026
  22. Kristofer KarlssonJul 10, 2026
  23. René ScharfeJul 10, 2026
  24. Kristofer KarlssonJul 10, 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.