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

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

From
Junio C Hamano <gitster@pobox.com>
Date
Jun 8, 2026, 13:36 UTC
Message-ID
<xmqq5x3tyx0e.fsf@gitster.g>
In-Reply-To
<pull.2140.v3.git.1780832592.gitgitgadget@gmail.com>

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

Show 5 quoted lines
> Changes in v3:
>
>  * Adopted Rene's suggestion to move the flush logic below the LIFO
>    early-return (LIFO mode never sets get_pending, so flushing there is a
>    no-op).
Sensible.
>  * Went a step further and inlined the flush logic directly into get() and
>    peek(), eliminating the flush_get() helper and its forward declaration of
>    sift_down_root().

Hmph, unless there is a reason to allow the copies in get() and peek() to deviate from each other, e.g., what flush_get() had to do inside get() and peek() were slightly different, I am not sure if this is a good move. I do not know if the slight difference of the "inlined" logic we have in the patch between the one in get() and the other one in peek() has merit, either. It certainly lets you avoid an unnecessary clearing of the get_pending bit (when a get was pending but the queue has more items to yield) immediately followed by turning it back on again (which happens always unless the function makes an early return for an empty queue) in get(), which will never happen in flush() that will always clear the bit before it returns, but is such an avoidance of an assignment really worth it? I suspect that with the static inline version of flush_get(), compilers are smart enough to optimize it away, but I dunno.

Show 16 quoted lines
>        void *prio_queue_get(struct prio_queue *queue)
>        {
>        	if (!queue->nr)
>        		return NULL;
>        	if (!queue->compare)
>      ++		return queue->array[--queue->nr].data;
>      ++
>      ++	if (queue->get_pending) {
>      ++		if (!--queue->nr) {
>      ++			queue->get_pending = 0;
>      ++			return NULL;
>      ++		}
>      ++		queue->array[0] = queue->array[queue->nr];
>      ++		sift_down_root(queue);
>      ++	}
>      + 

The above is from [1/2] (this is a minor point, but flipping the order of two patches to make the "nr_internal clean-up" as a preliminary step might have made commenting on this part easier to read). I wondered if it is easier to understand if the first early return is guarded by a conditional that takes get_pending into account.

	if (queue->nr_internal <= queue->get_pending)
		return NULL;

As I said, since the above hunk is immediately followed by an unconditional assignment of "queue->get_pending = 1", clearing get_pending = 0 only when we leave inside the if() block works as an optimization that is not available on the peek() side. But with the "ah the queue is empty already, the queue->ne == 1 is due to the lazy get that did not rebalance" tweak, it would become unneeded, I think.

Show 16 quoted lines
>      + void *prio_queue_peek(struct prio_queue *queue)
>      + {
>       +	if (!queue->nr_internal)
>        		return NULL;
>        	if (!queue->compare)
>       +		return queue->array[queue->nr_internal - 1].data;
>      + 
>      + 	if (queue->get_pending) {
>      + 		queue->get_pending = 0;
>      +-		if (!--queue->nr)
>      ++		if (!--queue->nr_internal)
>      + 			return NULL;
>      +-		queue->array[0] = queue->array[queue->nr];
>      ++		queue->array[0] = queue->array[queue->nr_internal];
>      + 		sift_down_root(queue);
>      + 	}
This is from [2/2]; the same 
	if (queue->nr_internal <= queue->get_pending)
		return NULL;
applies here, I think.
Previous: Kristofer Karlsson via GitGitGadgetNext: Kristofer Karlsson via GitGitGadget
Message 13 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.