Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!uakari.primate.wisc.edu!uflorida!gatech!mcnc!uvaarpa!murdoch!astsun.astro.Virginia.EDU!gl8f From: gl8f@astsun.astro.Virginia.EDU (Greg Lindahl) Newsgroups: comp.lang.fortran Subject: Re: strength reduction of array address calculations Message-ID: <1990Nov29.041958.2254@murdoch.acc.Virginia.EDU> Date: 29 Nov 90 04:19:58 GMT References: <1990Nov28.213735.25563@murdoch.acc.Virginia.EDU> Sender: news@murdoch.acc.Virginia.EDU Organization: Department of Astronomy, University of Virginia Lines: 79 In article burley@pogo.ai.mit.edu (Craig Burley) writes: > 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. I was not claiming that I could strength-reduce random references. I was claiming that most references were in fact not random. >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. Well, I think you've managed to be publically rude ;-) I responded because the original poster, Dan, made a statement comparing flat arrays and double-pointer arrays that I found untrue. Whether or not he's talking about random references, I find that strength reduction can reduce the cost of flat arrays IN MY CODE to be less than double-pointer arrays. Why? Because my array accesses are regular. And that's what my posting was about. If you want to talk about random arrays, well, it's a fascinating subject, but that doesn't preclude discussion of flat arrays. >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); > } This can be strength-reduced, although I would be hard pressed to see how the compiler could do it automagaically. If, in Fortran, you do the gather with each column getting one outer loop iteration, strength reduction is possible. It'd look something like this: DO I = 1, NUMCOLS ICOL = B(I) DO J = 1, NUMROWS(I) A( C(I,J), ICOL ) = 3.1415*(whatever) ENDDO ENDDO Since ICOL is constant across the inner loop, it can be strength reduced. I hope I haven't switched rows and columns, I can never remember which one's which by name although I know which index varies fastest :-) The major problem with implementing this is that you have a different number of row elements to be gathered in each column, so using a flat array C() wastes space if you don't have a good idea of the upper bound. In cases where you are merely permuting things, this isn't a problem. In other cases, it might be a big problem. If you are using rectangular arrays, a smart FORTRAN compiler could get the best of both worlds by using flat arrays and making a work array of pointers to rows, which it could use for any address calculation which couldn't be strength-reduced. >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) But you can use flat arrays in C. All it takes is a define... and then your C compiler can often strength-reduce regular acceses.