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: 103376,56525db28240414a X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit Received: by 10.68.228.227 with SMTP id sl3mr7769146pbc.5.1342383387772; Sun, 15 Jul 2012 13:16:27 -0700 (PDT) Path: l9ni11880pbj.0!nntp.google.com!news2.google.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, 15 Jul 2012 13:16:27 -0700 (PDT) Organization: http://groups.google.com Message-ID: References: <01983f1c-f842-4b1f-a180-bcef531dad4c@googlegroups.com> <646635a0-ca6e-4f90-bfd7-90e9fd41f989@googlegroups.com> NNTP-Posting-Host: 82.44.19.199 Mime-Version: 1.0 X-Trace: posting.google.com 1342383387 18146 127.0.0.1 (15 Jul 2012 20:16:27 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Sun, 15 Jul 2012 20:16:27 +0000 (UTC) In-Reply-To: <646635a0-ca6e-4f90-bfd7-90e9fd41f989@googlegroups.com> 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 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Date: 2012-07-15T13:16:27-07:00 List-Id: On Sunday, 15 July 2012 20:52:42 UTC+1, Shark8 wrote: > On Sunday, July 15, 2012 12:40:08 PM UTC-6, Keean Schupke wrote: > > The Monte-Carlo simulator I am working on is now performing better i= n Ada than in C++ using profile-guided compilation (57k simulations per sec= ond for Ada &#39;vs&#39; 56k simulations per second for C++). > >=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 > >=20 > > Contrast this with C++ where we can return a pointer to the array el= ement, and we just need to add the record_size to step to the next element. > >=20 > > So assuming we need this level of performance, what would be the bes= t (and most idiomatic Ada) way to package this type of usage pattern as an = abstract datatype? > >=20 > >=20 > > Cheers, > > Keean. >=20 > Hm; the problem is that such optimizations are highly dependent on assump= tions that might not be true in the future. Consider, for example, compilin= g targeting the JVM: the arrays are not guaranteed to be continuous with co= ntiguous components and therefore such a method would invite incorrect resu= lt/behavior to the program. >=20 > That said, if I needed to resort to such micro-optimizations I'd thro= w them all into a generic-package [if possible] and comment the heck out of= the subprogram bodies. {Or if you're using a common pattern you might = be able to explain the pattern in the package-body and then do the implemen= tations -- You might be able to get away with a generic-iterator inside the= package body.} There are type-theoretic ways to deal with this in functional programming t= hat do not rely on the underlying machine architecture at all. For example = see: The Derivative of a Regular Type is its Type of One-Hole Contexts [Conor Mc= Bride] http://strictlypositive.org/diff.pdf Conor discusses trees, but the same is true for arrays, the type system can= maintain the context, allowing a single pointer into the array to represen= t the 'current' element, the 'left context' and the 'right context'. I am not sure such a rigorous analysis is necessary though, consider the fo= llowing: the language semantics could be changed to allow this by for examp= le having a primitive iterator type on arrays that supported operations lik= e: declare J : Array_Iterator :=3D Array(5); begin J :=3D J + 1; J.Property =3D Value; end This would not expose the underlying machine architecture and would allow t= he kind of optimisations needed. J could have a range derived from the arra= y bounds to bounds check the access. It seems obvious enough that I am wondering if there is a way to do this th= at I missed? Cheers, Keean.