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=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM autolearn=ham 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.74.41 with SMTP id q9mr1665195pav.41.1343314453423; Thu, 26 Jul 2012 07:54:13 -0700 (PDT) Path: b9ni64917635pbl.0!nntp.google.com!border1.nntp.dca.giganews.com!border4.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!novia!volia.net!news2.volia.net!feed-A.news.volia.net!border1.nntp.ams2.giganews.com!border3.nntp.ams.giganews.com!border1.nntp.ams.giganews.com!nntp.giganews.com!newsfeed.straub-nv.de!news.swapon.de!news.glorb.com!npeer02.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail From: Keean Schupke Newsgroups: comp.lang.ada Subject: Re: Efficient Sequential Access to Arrays Date: Sun, 22 Jul 2012 09:02:38 -0700 (PDT) Organization: http://groups.google.com Message-ID: <74ebccf9-ca67-4eeb-a900-2d53777c655b@googlegroups.com> References: <01983f1c-f842-4b1f-a180-bcef531dad4c@googlegroups.com> NNTP-Posting-Host: 82.44.19.199 Mime-Version: 1.0 X-Trace: posting.google.com 1342973061 4186 127.0.0.1 (22 Jul 2012 16:04:21 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Sun, 22 Jul 2012 16:04:21 +0000 (UTC) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=82.44.19.199; posting-account=T5Z2vAoAAAB8ExE3yV3f56dVATtEMNcM User-Agent: G2/1.0 X-Received-Bytes: 3484 X-Original-Bytes: 3689 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Date: 2012-07-22T09:02:38-07:00 List-Id: On Sunday, 22 July 2012 11:09:44 UTC+1, (unknown) wrote: > On Monday, 16 July 2012 04:40:08 UTC+10, Keean Schupke wrote: >=20 > > However in order to achieve this performance I needed to rework the = arrays as the use of Indexes was too slow. An example of this is lets say w= e are accessing element 5 from array A &quot;A(5)&quot; this requir= es a multiplication to access (base_address + index * record_size). To acce= ss the neighbour A(6) also requires a multiplication. Accessing the array s= equentially requires a multiplication per step. >=20 > Have you tried turning on high optimisation? Yes this is compiled with test: test.adb rm -f *.gcda gnatmake -march=3Dnative -O3 -fprofile-generate -ftest-coverage -gnatp -gn= atn test -bargs -shared -cargs -fdata-sections -ffunction-sections -largs -= Wl,--gc-sections ./test touch test.adb gnatmake -march=3Dnative -O3 -fprofile-use -gnatp -gnatn test -bargs -shar= ed -cargs -fdata-sections -ffunction-sections -largs -Wl,--gc-sections >=20 > If you are accessing elements sequentially, > the optimiser will probably not do multiplications, > but instead access successive elements by means of additions. It is difficult to say if lack of this optimisation is the cause of the slo= wness. What does seem to be the case is that storing the index of the next element= of a linked list is slower than storing the address. >=20 > Other factors may be relevant: > 1. For example, if the size of a > record is small-ish, the compiler may use shifts and/or > adds/subtracts instead of multiplications. >=20 > 2. The hardware multiplier may be one of the fast kind, > in which case the time is negligible. The target (achieved by the relative addressing code) is 57,000 simulations= per second. Currently the fastest version using array indexing is 42,000 s= imulations per second. 36% is too big a difference to ignore, and this is a= real world problem not a benchmark. So I am looking for ideas to improve t= he array indexing version.=20 I am not sure what is the cause of the speed difference, it may not be the = actual array index lookup time, but a consequence of using array lookup whe= re the other version uses direct addressing (pointer dereference with no of= fset). Cheers, Keean.