Re: [PATCH 1/5] add SWAP macro

On Mon, Apr 24, 2017 at 07:29:28AM -0400, Jeff King wrote:

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@peff.net>
---
 prio-queue.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)