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.