Path: utzoo!utgpu!watserv1!watmath!att!att!pacbell.com!ucsd!sdd.hp.com!zaphod.mps.ohio-state.edu!usc!snorkelwacker.mit.edu!ai-lab!life!burley
From: burley@pogo.ai.mit.edu (Craig Burley)
Newsgroups: comp.lang.fortran
Subject: Re: strength reduction of array address calculations
Message-ID: <BURLEY.90Nov28205003@pogo.ai.mit.edu>
Date: 29 Nov 90 01:50:03 GMT
References: <17680:Nov2806:04:1090@kramden.acf.nyu.edu>
	<1990Nov28.065242.10154@murdoch.acc.Virginia.EDU>
	<BURLEY.90Nov28084920@pogo.ai.mit.edu>
	<1990Nov28.213735.25563@murdoch.acc.Virginia.EDU>
Sender: news@ai.mit.edu
Organization: /home/fsf/burley/.organization
Lines: 85
In-reply-to: gl8f@astsun7.astro.Virginia.EDU's message of 28 Nov 90 21:37:35 GMT

In article <1990Nov28.213735.25563@murdoch.acc.Virginia.EDU> gl8f@astsun7.astro.Virginia.EDU (Greg Lindahl) writes:

   In article <BURLEY.90Nov28084920@pogo.ai.mit.edu> burley@pogo.ai.mit.edu (Craig Burley) writes:

   >Hmm, could you explain to me how to strength-reduce multiplication to addition
   >for random references to array elements within loops, as in

   You can't. But many references are regular. So in this loop:

      do j = 1, 100
	 do i = 1, 100
	    bleah = a( i, j )
	 enddo         ^^^^ - all loop vars
      enddo

C'mon guys, enough is enough: I said "for RANDOM REFERENCES to array
elements within loops" clearly enough!  We've beaten the non-random reference
issue to death.  I was responding (somewhat tongue in cheek, though hoping I'd
actually get an incredibly insightful answer) to someone who had said one can
strength-reduce the multiplies away in loops in response to yet another person
who clearly had been talking about, yes, RANDOM references.

So, yes, I know (or am pretty sure) you can't.  But I asked the question anyway,
because I wanted to know the poster's answer, or at least suggest without being
overly and publically rude that perhaps he shouldn't have responded to a post
about random references to arrays saying they can be strength-reduced.

A common example of random accesses are scatter/gather operations.  The array
element access computation in the following function in C:

    void foo(a,b,c)
    float a[100][100];
    int b[100];
    int c[100];
    {
    int i, j;

    for (i = 0; i < 100; ++i)
      for (j = 0; j < 100; ++j)
        a[b[i]][c[j]] = 3.1415*(i+j);
    }

can and must be implemented using pointer indirection, not multiplication.  The
same computation in this similar function in Fortran:

    SUBROUTINE FOO(A,B,C)
    REAL A(100,100)
    INTEGER B(100),C(100),I,J
C
    DO I=1,100
       DO J=1,100
          A(C(J),B(I)) = 3.1415*(I+J)
       END DO
    END DO
C
    END

can and must be implemented using multiplication, not pointer indirection.

For many applications, the choice is Fortran, not due to optimization but to
the requirement that the caller of FOO be able to pass any shape arrays to FOO,
as in:

    REAL ARRAY(10,10,10,10),INDX1(10,10),INDX2(5,2,5,2)
    CALL FOO(ARRAY,INDX1,INDX2)

The corresponding call in C:

    float array[10][10][10][10];
    float indx1[10][10];
    float indx2[5][2][5][2];
    foo(array,indx1,indx2);

would not work.

Further, with regards to optimization, it is likely true that on many computers
(especially older ones) references to memory (and lets assume we do cache misses)
are faster than integer multiplies.  However, it's my guess that on many machines
where people are actually coding fast numerical/scientific computing problems,
integer (and even floating-point) multiplies are as fast or faster, or are done
in a parallel fashion and end up being preferrable in cases where memory is
a bottleneck but the multiplier is available.
--

James Craig Burley, Software Craftsperson    burley@ai.mit.edu