Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Terje Mathisen <terje.mathisen@tmsw.no>
Newsgroups: comp.arch
Subject: Re: Computer architects leaving Intel...
Date: Wed, 11 Sep 2024 13:07:33 +0200
Organization: A noiseless patient Spider
Lines: 86
Message-ID: <vbrtll$3ip2f$1@dont-email.me>
References: <vaqgtl$3526$1@dont-email.me>
 <memo.20240830090549.19028u@jgd.cix.co.uk>
 <2024Aug30.161204@mips.complang.tuwien.ac.at> <86r09ulqyp.fsf@linuxsc.com>
 <2024Sep8.173639@mips.complang.tuwien.ac.at>
 <20240910114903.00003fff@yahoo.com> <861q1ring8.fsf@linuxsc.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 11 Sep 2024 13:07:34 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="a3d4cfd2b6e2f0f800404264c5cd202c";
	logging-data="3761231"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+vr3HG/ZfFMTv3stOk6u9WJt0qAhd72oMW5mv1Bduwzw=="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.18.2
Cancel-Lock: sha1:qeAoDIGuvlKz/JUnz3SHRigCAyU=
In-Reply-To: <861q1ring8.fsf@linuxsc.com>
Bytes: 4688

Tim Rentsch wrote:
> Michael S <already5chosen@yahoo.com> writes:
> 
>> On Sun, 08 Sep 2024 15:36:39 GMT
>> anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:
>>
>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>>
>>>> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>>>
>>>>> There was still no easy way to determine whether your software
>>>>> that calls memcpy() actually works as expected on all hardware,
>>>>
>>>> There may not be a way to tell if memcpy()-calling code will work
>>>> on platforms one doesn't have, but there is a relatively simple
>>>> and portable way to tell if some memcpy() call crosses over into
>>>> the realm of undefined behavior.
>>>
>>> 1) At first I thought that yes, one could just check whether there is
>>> an overlap of the memory areas.  But then I remembered that you cannot
>>> write such a check in standard C without (in the general case)
>>> exercising undefined behaviour;  and then the compiler could eliminate
>>> the check or do something else that's unexpected.  Do you have such a
>>> check in mind that does not exercise undefined behaviour in the
>>> general case?
>>
>> The check that reliably catches all overlaps seems easy.
>> E.g. (src <= dst) == (src+len > dst)

Does that work for dst < src? What if dst+len < src?

I.e. no overlap?

The first test will be false while the second test will always be true 
when src >= dst, so I think it will have false positives?

What about:

   max(src,dst) < (min(src,dst)+len)

If you have a min/max circuit, i.e a two-element sorter, then it could 
be quite efficient, otherwise run the min first, then the max and the 
add during the second cycle, before the less than test in the third cycle.


>> In theory, on unusual hardware platform it can give false positives.
>> May be, for task in hand that's o.k.
> 
> The challenge is to find portable C that doesn't enter the arena
> of undefined behavior (and also detects exactly those cases where
> overlap occurs), and that is quite a stringent criterion.
> 
> The comparison shown works if src and dst both point to elements
> of the same array.  But if they don't, comparing pointers to see
> if one is less than another (or any of <, <=, >, >=) is undefined
> behavior.  At the bit level it wouldn't surprise me to learn that
> the test shown always returns accurate information.  However the
> C standard doesn't promise that a bit-level comparison will be
> done, and implementations are allowed to do anything at all for
> this test in cases where src and dst point to (somewhere within)
> different top-level objects.  What the hardware does doesn't
> matter - what needs to be satisfied are the rules of the C
> standard, and they are less forgiving.
> 
> I should add that I appreciate your proposed solution;  it's
> better than what I think I would have come up with under a
> similar set of assumptions.
> 

I do believe though that in reality it could be faster to use the 
branchy version, and let the branch predictors do their job instead of 
having to wait to evaluate all three terms:

bool is_overlap(char *src, char *dst, size_t len)
{
   if (src < dst) {
     return (src+len > dst);
   }
   return (dst+len > src);
}

Terje

-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"