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,FORGED_MUA_MOZILLA 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.180.24.202 with SMTP id w10mr2642624wif.0.1343032501048; Mon, 23 Jul 2012 01:35:01 -0700 (PDT) Path: ge7ni48470337wib.0!nntp.google.com!feed-C.news.volia.net!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!border4.nntp.ams.giganews.com!border2.nntp.ams.giganews.com!ramfeed-2.ams.xsnews.nl!feed.xsnews.nl!border-2.ams.xsnews.nl!feeder1.cambriumusenet.nl!feeder2.cambriumusenet.nl!feed.tweaknews.nl!216.40.29.245.MISMATCH!novia!border4.nntp.dca.giganews.com!border3.nntp.dca.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!ctu-peer!news.nctu.edu.tw!goblin1!goblin.stu.neva.ru!eweka.nl!hq-usenetpeers.eweka.nl!xlned.com!feeder1.xlned.com!npeer.de.kpn-eurorings.net!npeer-ng0.de.kpn-eurorings.net!newsfeed.arcor.de!newsspool2.arcor-online.net!news.arcor.de.POSTED!not-for-mail Date: Sun, 15 Jul 2012 23:44:48 +0200 From: Georg Bauhaus User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.7; rv:13.0) Gecko/20120614 Thunderbird/13.0.1 MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: Efficient Sequential Access to Arrays References: <01983f1c-f842-4b1f-a180-bcef531dad4c@googlegroups.com> <44f2bfd0-75ed-4b9c-982e-61d5308f9c01@googlegroups.com> In-Reply-To: <44f2bfd0-75ed-4b9c-982e-61d5308f9c01@googlegroups.com> Message-ID: <500339d0$0$6564$9b4e6d93@newsspool4.arcor-online.net> Organization: Arcor NNTP-Posting-Date: 15 Jul 2012 23:44:48 CEST NNTP-Posting-Host: 011a5c7f.newsspool4.arcor-online.net X-Trace: DXC==G6LGIBWJf;i6K;>iZ]7634IUK]GbD7b?PCY\c7>ejV8a\BgjeC>?:7BCg5TBBJ><8 X-Complaints-To: usenet-abuse@arcor.de X-Original-Bytes: 5564 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Date: 2012-07-15T23:44:48+02:00 List-Id: On 15.07.12 22:03, Keean Schupke wrote: > On Sunday, 15 July 2012 20:48:35 UTC+1, Dmitry A. Kazakov wrote: >> On Sun, 15 Jul 2012 11:40:08 -0700 (PDT), Keean Schupke wrote: >> >> > However in order to achieve this performance I needed to rework the arrays >> > as the use of Indexes was too slow. >> >> You have to measure it in order to know. Write two variants and compare >> their performance. > > Have done, the difference is about 10k simulations per second. > >> >> > An example of this is lets say we are >> > accessing element 5 from array A "A(5)" this requires a multiplication to >> > access (base_address + index * record_size). >> >> It does not, because 5 is constant. > > Obviously the index is not actually a constant but the result of selecting a random element in the list. The multiplication is necessary for finding this first element, but the operations on relative elements (+/-1, +/-2 etc) can use addition with a pointer, not so with an index. There is address arithmetic in System.*. For the simple case of constant distances, something like the following might have some hints. Or it might if redone after thinking. procedure Grab has the multiplication for offsets of components of a record type object in an array. The point is that one may express offsets by referring to type attributes that follow from representation clauses and then convert between addresses and pointers. with Ada.Numerics.Float_Random; use Ada.Numerics.Float_Random; with System.Address_To_Access_Conversions, System.Storage_Elements; procedure Iter_Arrays (Size : Natural) is Storage_Elements : constant := 1; type Index is mod 2**32; type Data is digits 6; for Data'Size use 32; G : Generator; type Things is record One: Data := Data (Random (G)); Two: Data := Data (Random (G)); end record; for Things use record One at 0 * Storage_Elements range 0 .. Data'Size - 1; Two at 4 * Storage_Elements range 0 .. Data'Size - 1; end record; pragma Assert (Things'Size = 64); type List is array (Index range <>) of Things; for List'Alignment use 4 * Storage_Elements; for List'Component_Size use 64; -- using array indexing procedure Bumble (A : in out List; Step : Index) is begin for K in A'First + Step .. A'Last - Step loop declare Diff_Backward : constant Data := A (K).One - A (K - Step).Two; Diff_Forward : constant Data := A (K).Two - A (K + Step).One; begin if (abs Diff_Backward) < (abs Diff_Forward) then A (K).One := A (K - Step).One; else A (K).Two := A (K + Step).Two; end if; end; end loop; end Bumble; -- using relative addresses package Indirection is new System.Address_To_Access_Conversions (Object => Data); subtype Data_Pointer is Indirection.Object_Pointer; procedure Grab (A : in out List; Step : Index) is -- [A] = [one][two][one][two]...[one][two] use System.Storage_Elements, Indirection; Offset_Backward : constant Storage_Offset := Storage_Offset (0 + Step * 8 + 4); Offset_Forward : constant Storage_Offset := Storage_Offset (0 - Step * 8 + 0); begin for K in A'First + Step .. A'Last - Step loop declare Back : constant Data_Pointer := To_Pointer (A (K).One'Address + Offset_Backward); Ahead : constant Data_Pointer := To_Pointer (A (K).Two'Address + Offset_Backward); Diff_Backward : constant Data := A (K).One - Back.all; Diff_Forward : constant Data := A (K).One - Ahead.all; begin if (abs Diff_Backward) < (abs Diff_Forward) then A (K).One := A (K - Step).One; else A (K).Two := A (K + Step).Two; end if; end; end loop; end Grab; Test_Data : List (0 .. Index(Size)); begin Bumble (Test_Data, 2); Grab (Test_Data, 3); end Iter_Arrays;