jlg@lanl.gov (Jim Giles) (10/20/90)
> You refuse to acknowledge that sometimes pointers can be used without > adding an index first, I do not! I refuse to acknowledge that this optimization is the exclusive province of pointers! If you can precompute the index, the compiler can apply the data flow graph to find the _use_ of the index and _always_ add the array base address - at _exactly_ the same point that _you_ would manually precompute the pointer (or anywhere in between - where ever is most efficient). I personally find that the compiler's ability to do this saves me a lot of drudgery. > [...] that some of us don't mind using the most > appropriate available tool for the job, I have always spoken _in_favor_ of this concept. Pointers are (maybe) the most appropriate tool for memory manager internals and memory mapped device drivers - little else. So, the issue is to attack the "available" component of your criterion. In C, pointers are practically the _only_ tools available. In future languages, I hope that pointers (if present at all) are little used curiosities (as they deserve to be). > [...] and that packed array tries > cannot be expressed as recursive data structures. First: I don't believe in the "cannot be expressed" part of your statement. Second: packed array tries _are_ implemented as arrays - so the issue is irrelevant to this discussion anyway (which is _still_ mostly about whether pointers are really _needed_ or not). Or, maybe it _IS_ relevant, since it is an application that you seem to consider important which DOES NOT use explicit pointers. End of chapter 6 J. Giles
mjs@hpfcso.HP.COM (Marc Sabatella) (10/30/90)
>I do not! I refuse to acknowledge that this optimization is the >exclusive province of pointers! If you can precompute the index, the >compiler can apply the data flow graph to find the _use_ of the index >and _always_ add the array base address - at _exactly_ the same point >that _you_ would manually precompute the pointer (or anywhere in >between - where ever is most efficient). I personally find that the >compiler's ability to do this saves me a lot of drudgery. int array[100]; int *p; extern int *bar(); foo () { p = bar(); *p = 42; } versus int array[100]; int i; extern int bar(); foo () { i = bar(); array[i] = 42; } Tough to get code for foo() in the second case to be as good as code in the first case without more interprocedural data flow analysis than most compilers are capable of. Especially if we extend the problem and let "p" optionally point into either of two arrays, where "bar" reads from stdin to determine which array to point into. Bad code design? Possibly. But don't make the claim that indices can always be as efficient as pointers.
jlg@lanl.gov (Jim Giles) (10/31/90)
From article <8960019@hpfcso.HP.COM>, by mjs@hpfcso.HP.COM (Marc Sabatella): > [...] > int array[100]; int array[100]; > int *p; int i; > extern int *bar(); extern int bar(); > > foo () foo () > { { > p = bar(); i = bar(); > *p = 42; array[i] = 42; > } } > [...] > Tough to get code for foo() in the second case to be as good as code in the > first case without more interprocedural data flow analysis than most compilers > are capable of. [...] Yes, but the problem is not whether foo() in isolation is more efficient but whether the _program_ as a whole is more efficient. In this case, in order for these two programs to have the same semantics, the base of array[] must be added into p. Whether this add is done in foo() or in bar(), it still takes the same time to do. Further, if the assignment to array[] involved an expression more complicated than '42' (like, having references to other arrays for example), then the pointer version would not be able to optimize as well since it can't know from pointers whether they are within the same or different arrays. So, in general the "pointer-free" version will be faster. At worst, it will be the same. > [...] Especially if we extend the problem and let "p" optionally > point into either of two arrays, where "bar" reads from stdin to determine > which array to point into. [...] In this case, bar() could be given array[] as an argument which has the "aliased" attribute turned on. Then, bar() could use the "shallow copy" assignment to select which of the two arrays that array[] really represented. As you mentioned, this is bad coding practice (usually), but if you need it, you can do it. Note: as I've repeatedly pointed out, "aliased" variables are _identical_ in semantics to Pascal style pointers (with the exception that the set of things they can be aliased to is easily determined by the compiler). J. Giles