paco@letaba.rice.edu (Paul Havlak) (11/29/90)
In article <BURLEY.90Nov28084920@pogo.ai.mit.edu>, burley@pogo.ai.mit.edu (Craig Burley) writes: |> In article <1990Nov28.065242.10154@murdoch.acc.Virginia.EDU> gl8f@astsun.astro.Virginia.EDU (Greg Lindahl) writes: |> |> In article <17680:Nov2806:04:1090@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: |> |> >Huh? A double-pointer array, as we were discussing, is a |> >single-dimensional array of pointers to single-dimensional arrays. To |> >access a random element of the array takes two additions and two memory |> >references. In contrast, to access a random element of a flat array |> >takes two additions, a multiplication, and a memory reference. On most |> >widely used machines, a multiplication is quite a bit slower than a |> >memory reference, particularly a cached memory reference. That's why |> >double-pointer arrays are better than flat arrays for so many |> >applications. |> |> Except that inside loops, the multiplication is strength-reduced to an |> addition. That's why flat arrays are faster than double-pointer arrays |> for so many applications. ... |> Hmm, could you explain to me how to strength-reduce multiplication to addition |> for random references to array elements within loops, as in |> |> SUBROUTINE FOO(A) |> REAL A(37,103) |> INTEGER I,J |> DO I,1=100 |> DO J,1=100 |> A(SOMEFUNC(I),OTHERFUNC(J)) = 0. |> END DO |> END DO |> END |> |> where SOMEFUNC and OTHERFUNC may be external functions or statement functions |> with expressions sufficient to ensure that there is no linearity between their |> inputs (I and J) and their outputs (used as array indices)? ... Sure, no compiler can strength-reduce subscripts containing complicated functions. But then the addressing arithmetic is already expensive, and the marginal cost of the multiplication is pretty low. Where flat arrays win is in the vast majority of array subscripts, 80 percent (static, probably a higher dynamic percentage) of which are linear functions of the loop induction variables. Such references to flat arrays can often be moved into registers using transformations based on dependence analysis. (Callahan, Carr & Kennedy, "Improving Register Allocation for Subscripted Variables", SIGPLAN PLDI '90, White Plains, June 1990; SIGPLAN Notices 25:6, June 1990) Dependence analysis (unfortunately) still has significant problems with double- pointer arrays. Use flat arrays with explicit subscripts and modern, commercially-available compilers will optimize your memory references and addressing arithmetic. Use pointers and you may have to optimize them yourself. Hand-optimization is still a valid choice for those machine/language combinations where optimizing compilers don't exist or aren't good enough. But advanced architectures such as the i860 and the RS/6000 will make it increasingly hard to get portable efficiency without leaving optimization to the compiler. --Paul