Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ncar!tank!uxc!garcon!uicsrd.csrd.uiuc.edu!mcdaniel From: mcdaniel@uicsrd.csrd.uiuc.edu (Tim McDaniel) Newsgroups: comp.lang.c Subject: Re: When it is amoral... (Re: When is a cast not a cast?) Message-ID: <925@garcon.cso.uiuc.edu> Date: 7 May 89 07:58:09 GMT References: <2765@buengc.BU.EDU> <563@lzaz.ATT.COM> <4093@ficc.uu.net> <127@quad.uucp> <4097@ficc.uu.net> Sender: news@garcon.cso.uiuc.edu Reply-To: mcdaniel@uicsrd.csrd.uiuc.edu (Tim McDaniel) Organization: Center for Supercomputing R&D (Cedar), U. of Ill. Lines: 97 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@quad.uucp>, dts@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@ficc.uu.net> peter@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@uicsrd.csrd.uiuc.edu Supercomputing ||| UUCP: {uunet,convex,pur-ee}!uiucuxc!uicsrd!mcdaniel Research and ||| ARPANET: mcdaniel%uicsrd@uxc.cso.uiuc.edu Development, ||| CSNET: mcdaniel%uicsrd@uiuc.csnet U of Illinois ||| DECnet: GARCON::"mcdaniel@uicsrd.csrd.uiuc.edu"