On Mon, Apr 24, 2017 at 07:29:28AM -0400, Jeff King wrote:
> A related question is whether the caller should ever be asking to swap
> something with itself. This particular case[1] comes from
> prio_queue_reverse(). I suspect its "<=" could become a "<", but I
> haven't thought it through carefully.
OK, I actually looked closer and we definitely should drop the "<=". I
was thrown off by the assignment of "j" inside the loop condition. IMHO
it might be more obvious to write as:
for (i = 0, j = queue->nr - 1; i < j; i++, j--)
swap(queue, i, j);
but I left it as-is.
So I think this patch is an obvious improvement whatever we do with
SWAP(). There's still an open question of whether SWAP() should be more
careful about its inputs (normally I'd say yes, but I know this is a
potentially performance critical call).
-- >8 --
Subject: [PATCH] prio_queue_reverse: don't swap elements with themselves
Our array-reverse algorithm does the usual "walk from both
ends, swapping elements". We can quit when the two indices
are equal, since:
1. Swapping an element with itself is a noop.
2. If i and j are equal, then in the next iteration i is
guaranteed to be bigge than j, and we will exit the
loop.
So exiting the loop on equality is slightly more efficient.
And more importantly, the new SWAP() macro does not expect
to handle noop swaps; it will call memcpy() with the same src
and dst pointers in this case. It's unclear whether that
causes a problem on any platforms by violating the
"overlapping memory" constraint of memcpy, but it does cause
valgrind to complain.
Signed-off-by: Jeff King <peff@xxxxxxxx>
---
prio-queue.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/prio-queue.c b/prio-queue.c
index 17252d231..fc3860fdc 100644
--- a/prio-queue.c
+++ b/prio-queue.c
@@ -21,7 +21,7 @@ void prio_queue_reverse(struct prio_queue *queue)
if (queue->compare != NULL)
die("BUG: prio_queue_reverse() on non-LIFO queue");
- for (i = 0; i <= (j = (queue->nr - 1) - i); i++)
+ for (i = 0; i < (j = (queue->nr - 1) - i); i++)
swap(queue, i, j);
}
--
2.13.0.rc0.459.g06dc2b676