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

[Junio C Hamano <gitster@pobox.com>]

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

> 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.

>        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.

>      + 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.