Re: Computer architects leaving Intel...

Terje Mathisen <terje.mathisen@tmsw.no> writes:

[how to detect interval overlap]

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.

[...]

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);
}

Note that there are two distinct problems that are relevant to
the discussion:  is there any overlap, and is there overlap of
the wrong kind.  The question of Is there any overlap can be
done with a simple comparison if there is a non-branching abs()
function available (assuming a flat linear address space):

   if( abs( source - destination ) < n ) ...

The question of Is there overlap of wrong kind, which is like
what memmove would want to ask, can be done with a single
comparison if the bad direction is known in advanced, and fixed.
An example is given by Anton, and a revision of that in my
recent response to his posting.