Re: Computer architects leaving Intel...

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"