Re: [PATCH 1/5] add SWAP macro

From: René Scharfe <l.s.r@web.de>
Date: Apr 29, 2017, 18:16 UTC
Message-ID: <11699799-6bdf-484d-5a1c-8e8fa7981594@web.de>
In-Reply-To: <20170428214934.tuqihgch6qeen3ni@sigill.intra.peff.net>

Am 28.04.2017 um 23:49 schrieb Jeff King:

Show 27 quoted lines

> On Fri, Apr 28, 2017 at 07:04:51PM +0200, René Scharfe wrote:
> 
>>> What should:
>>>
>>>     SWAP(foo[i], foo[j]);
>>>
>>> do when i == j? With this code, it ends up calling
>>>
>>>     memcpy(&foo[i], &foo[j], ...);
>>>
>>> which can cause valgrind to complain about overlapping memory. I suspect
>>> in practice that noop copies are better off than partial overlaps, but I
>>> think it does still violate the standard.
>>>
>>> Is it worth comparing the pointers and bailing early?
>>
>> Hmm, so swapping a value with itself can be a useful thing to do?
>> Otherwise an assert would be more appropriate.
> 
> No, I doubt that it's useful, and it's probably a sign of a bug
> elsewhere. But it's likely a _harmless_ bug, so it may be irritating to
> die when we hit it rather than continuing.
> 
> I dunno. I could go either way. Or we could leave it as-is, and let
> valgrind find the problem. That has zero run-time cost, but of course
> nobody bothers to run valgrind outside of the test suite, so the inputs
> are not usually very exotic.

It would be problematic on platforms where memcpy has to erase the destination before writing new values (I don't know any example).

We could use two temporary buffers. The object code is the same with GCC around 5 and Clang 3.2 or higher -- at least for prio-queue.c.

With GCC 4.9.2 (that's what Debian stable currently has) the result is actually slightly better with two buffers because a 128-bit move starts to get used (https://godbolt.org/g/18HQDQ).

Show 8 quoted lines

>> Swapping with *partial* overlap sounds tricky, or even evil.  If
>> we want to support that for some reason we'd have to use memmove
>> in the middle.  But that would still corrupt at least one of the
>> objects, wouldn't it?
> 
> Yes, the overlap case is probably an actual bug. Detecting it is a bit
> harder, but definitely possible. I hate to pay the run-time cost for it,
> but I wonder if a compiler could optimize it out.

How is it possible to arrive at such a situation? We'd need two objects of the same size (we check that in SWAP) and one of them would start inside of the other one, i.e. the pointer difference between them would be a fraction of 1. So the type system would have to be tricked into it, right?

How *would* we detect overlaps? The obvious checks (a+len<=b||b+len<=a) are undefined if applied to objects that don't belong to the same array. And members of the same array would not overlap to begin with..

It may be my laziness speaking, but do we really need such a check? If someone constructs interleaving objects then they'd need to implement the necessary checks themselves IMHO.

Show 11 quoted lines

>> The line in question is this one:
>>
>> 	for (i = 0; i <= (j = (queue->nr - 1) - i); i++)
>>
>> Assignment in the middle?  Hmm.  Why not do it like this?
>>
>> 	for (i = 0, j = queue->nr - 1; i < j; i++, j--)
>>
>> Looks less complicated to me.
> 
> Yes, see my other reply. :)

Ah, so that's where I stole it from. ;) Perhaps my source amnesia was in part caused by confusion about your reasoning there: The code does A, B would be better, so let's do C. Wait, what? :)

René