When it is amoral... (Re: When is a cast not a cast?)

[Tim McDaniel]

Suppose that pointer addition means that "&A[i] + &A[j] == &A[i+j]".
(Is this what you had in mind, Peter?)

In a previous article, I showed that "&A[i] + &A[j] == &A[i+j]"
requires (in general) that pointers be represented internally as pairs
"(location,base_of_array)".  To briefly recap, if we want
        Total = A + B;
we can't just add the addresses as integers.  For example, suppose
that A and B point into an array Array that starts at address 100, and
that A is 102 and B is 104.  A+B must then be 106.  Adding A+B as
integers would yield 102+104 == 206, which is incorrect.  We must use
pairs as above and compute Total by
        Total.base = A.base;            /* or B.base */
        Total.loc = (A.loc - A.base) + B.loc;
(so Total.loc = (102-100)+104 == 106, as required).


In article <127 at quad.uucp>, dts at quad.uucp (David T. Sandberg) writes:
> More to the point, what's the difference between the 7 clubs and the
> 8 clubs?
I think he meant "midpoint", not "difference".

In article <4097 at ficc.uu.net> peter at ficc.uu.net (Peter da Silva) writes:
>You have to align the result before using it, of course.

I agree that these results would have to be aligned.  But how?

For
            some_type * M, * A, * B;
let's compare
  a:        M = (A + B) / 2;
versus
  b:        M = A + (B - A) / 2;

a: Mid, A, and B take 6 addresses to represent: (M.loc,M.base),
(A.loc,A.base), (B.loc,B.base).  Assume that A and B point into the
same array, so A.base==B.base.  The best implementation I can think of
is
        t = (A.loc + B.loc) / 2                   /* average */
                - A.base;                         /* begin aligning */
        M.loc = (t - t % sizeof *A) + A.base;     /* rest of aligning */
        M.base = A.base;
You see, it's not guaranteed that "(A.loc+B.loc)/2" is aligned for
A.base.  We have to see how far it is from A.base (the first
subtraction), align that to "sizeof (some_type)" (second subtraction
and the modulo), and add A.base back in to get the address.
Total operation count: 1 divide (or right shift), 1 modulo (or
bitwise-AND if "sizeof *A" is a power of 2), 4 adds/subtracts.  Note
that a modulo is usually as expensive as a divide.

We can do better if A.base is known to be aligned on a "sizeof (*A)"
boundary.  However, many systems can't guarantee this for arbitrarily-
large types.  For example, if A.base was malloced, it may only be at
an 8-byte boundary (for a VAX).  Even if we know that A.base is so
aligned (for example, if some_type is long, and all longs are so
aligned), we can only improve it to
        t = (A.loc + B.loc) / 2;
        M.loc = t - t % sizeof *A;
        M.base = A.base;
Operations: 1 divide (or right shift), 1 modulo (or bitwise-AND if
"sizeof *A" is a power of two), 2 adds/subtracts.  Even this solution
ignores overflow for the first add.

b: If no single data object takes more than half of memory, overflow
is impossible.  Representing the 3 pointers uses only 3 addresses:
Mloc, Aloc, Bloc. 
        Mloc = Aloc + (Bloc - Aloc) / sizeof *A / 2;
Operations: 1 divide (or right shift if "sizeof *A" is a power of 2),
2 adds/subtracts.


So pointer addition doubles the size of pointers, runs slower, and is
susceptible to overflow.  As far as I can tell, the only thing it
gains us is the ability to write
        midpoint = (start + end) / 2;
instead of
        /* midpoint is the midpoint of start and end, because
         * A + (B-A)/2 == A + B/2 - A/2 == A/2 + B/2 == (A+B)/2. */
        midpoint = start + (end - start) / 2;


Peter, you can't just say "let there be pointer addition", and
                         FIAT LUX!
there is pointer addition, and it is good.  You have to propose an
actual implementation.  Furthermore, if this implementation is more
costly than the current situation, you have to show that the gains
outweigh the costs.  You have done neither.

--

             Tim, the Bizarre and Oddly-Dressed Enchanter

Center for      |||  Internet, BITNET:  mcdaniel at uicsrd.csrd.uiuc.edu
Supercomputing  |||  UUCP:     {uunet,convex,pur-ee}!uiucuxc!uicsrd!mcdaniel
Research and    |||  ARPANET:  mcdaniel%uicsrd at uxc.cso.uiuc.edu
Development,    |||  CSNET:    mcdaniel%uicsrd at uiuc.csnet
U of Illinois   |||  DECnet:   GARCON::"mcdaniel at uicsrd.csrd.uiuc.edu"