From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=0.4 required=5.0 tests=BAYES_00,DATE_IN_PAST_24_48, FORGED_GMAIL_RCVD,FREEMAIL_FROM autolearn=no autolearn_force=no version=3.4.4 X-Google-Thread: a07f3367d7,56525db28240414a X-Google-Attributes: gida07f3367d7,public,usenet X-Google-NewGroupId: yes X-Google-Language: ENGLISH,ASCII-7-bit Received: by 10.66.78.106 with SMTP id a10mr1540580pax.14.1343315754184; Thu, 26 Jul 2012 08:15:54 -0700 (PDT) Path: b9ni65040893pbl.0!nntp.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!border6.newsrouter.astraweb.com!news.astraweb.com!border6.a.newsrouter.astraweb.com!feed.xsnews.nl!border-1.ams.xsnews.nl!newsfeed.straub-nv.de!news.swapon.de!news.glorb.com!news-out.readnews.com!transit3.readnews.com!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail From: robin.vowels@gmail.com Newsgroups: comp.lang.ada Subject: Re: Efficient Sequential Access to Arrays Date: Tue, 24 Jul 2012 09:00:24 -0700 (PDT) Organization: http://groups.google.com Message-ID: <4ce44d2d-d789-42a0-a6ed-035f7f8d58be@googlegroups.com> References: <01983f1c-f842-4b1f-a180-bcef531dad4c@googlegroups.com> <87ipdf4vh6.fsf@mid.deneb.enyo.de> NNTP-Posting-Host: 123.2.70.40 Mime-Version: 1.0 X-Trace: posting.google.com 1343146057 12729 127.0.0.1 (24 Jul 2012 16:07:37 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Tue, 24 Jul 2012 16:07:37 +0000 (UTC) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=123.2.70.40; posting-account=S_MdrwoAAAD7T2pxG2e393dk6y0tc0Le User-Agent: G2/1.0 Content-Type: text/plain; charset=ISO-8859-1 Date: 2012-07-24T09:00:24-07:00 List-Id: On Monday, 23 July 2012 03:34:26 UTC+10, Niklas Holsti wrote: > On 12-07-22 19:21 , Florian Weimer wrote: > > * Keean Schupke: > > > >> So assuming we need this level of performance, what would be the > >> best (and most idiomatic Ada) way to package this type of usage > >> pattern as an abstract datatype? > > > > You should look at compiler dumps to figure out why the strength > > reduction optimization does not kick in. > > > > As I understand it, the program is accessing A(I,J), where A is a 2D > array, and also accessing A(I+1,J), A(I,J+1), and the other neighbours > of A(I,J), eight in all. > > I,J are indices that are *not* traversed in sequential order, but in > some scattered order. > > Computing the address of A(I,J) involves multiplications of J and I with > the size of an array element and the size of an array row, respectively. > The problem seems to be that the results of these multiplications are > not reused in computing the address of A(I+1,J) etc. > > If the index constraints (or at least the row length) of A are static > (compile-time) constants, and the address of A(I,J) has been computed, > and c1 and c2 are some other compile-time constants (-1, 0, +1 in this > program), then the address of A(I+c1,J+c2) can be computed by adding a > static offset to the address of A(I,J). This is what happens when A(I,J) > and the neighbours are accessed through a C pointer, or when Keean uses > address arithmetic explicitly in the Ada program. The question is why > the Ada compiler is not doing this optimization. > > As I understand it, "strength reduction" is a loop optimization where an > expression of the form C*i, with "i" the loop index, is replaced by a > new variable that is incremented by C on each loop iteration. But in > Keean's program the indices I,J are not loop indices, nor linearly > related to loop indices. > > The optimization that would be required here is to replace (X+C)*F by > X*F+C*F, when C and F are static constants and X*F has already been > computed and is available. This would replace the multiplication by an > addition of a static constant. I've never seen this special kind of > optimization proposed or described. I think that it's a standard optimisation. For the PL/I optimising compiler for the CDC Cyber (c. 1980), multiplication was eliminated for matrix elements by using a table of offsets into each row. Thus, double subscripting reduced to simple addition. > (We are of course (I believe) assuming that index range checks are > turned off.) Index range checks should be left on.