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.224.180.205 with SMTP id bv13mr741631qab.8.1343292429253; Thu, 26 Jul 2012 01:47:09 -0700 (PDT) Received: by 10.66.78.106 with SMTP id a10mr1392130pax.14.1343292327352; Thu, 26 Jul 2012 01:45:27 -0700 (PDT) Path: a15ni101900513qag.0!nntp.google.com!q21no11553278qas.0!news-out.google.com!b9ni61666166pbl.0!nntp.google.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: Thu, 26 Jul 2012 01:38:41 -0700 (PDT) Organization: http://groups.google.com Message-ID: References: <01983f1c-f842-4b1f-a180-bcef531dad4c@googlegroups.com> <87ipdf4vh6.fsf@mid.deneb.enyo.de> <4ce44d2d-d789-42a0-a6ed-035f7f8d58be@googlegroups.com> NNTP-Posting-Host: 82.44.19.199 Mime-Version: 1.0 X-Trace: posting.google.com 1343292327 23807 127.0.0.1 (26 Jul 2012 08:45:27 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Thu, 26 Jul 2012 08:45:27 +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: 8115 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Date: 2012-07-26T01:38:41-07:00 List-Id: On Thursday, 26 July 2012 01:15:25 UTC+1, Randy Brukardt wrote: > "Keean Schupke" wrote in message=20 > > On Wednesday, 25 July 2012 08:09:09 UTC+1, Niklas Holsti wrote: > ... > >> Sure, in general. But here the OP (Keean) is trying to beat the > >> performance of C++ that uses pointers without index checks. Enab= ling > >> index checks in the Ada code would probably (in this case, where= the > >> algorithm has scatterered indexing of the array) slow it by an a= mount > >> that swamps the effect of the multiplication optimization. > > > > On the specific point of array index checking, if you can statically= prove=20 > > the algorithm > > using the array will never use an out of range index, there is no ne= ed to=20 > > run-time index check. > > > > If we generate a random number between one and N, and then lookup th= e Nth=20 > > element, we do not > > need to range check as the number is by definition in range. If the = type=20 > > system can carry such proofs > > (for example using range types in Ada) so you have: > > > > subtype Idx is Integer range 1 .. 10; > > type Arr is array (Idx) of Integer; > > function Random returns Idx; > > A : Arr; > > A(Random); -- as the random number is already in the range there nee= ds to=20 > > be no > > range checks on the array lookup. >=20 > This isn't necessarily true. The following is *very* Ada language-law= yer, so=20 > skip if you don't want to know the details. (BTW, this is all Ada 95= =20 > thinking, refined somewhat since.) >=20 > Ada scalar objects can be in a state known as "invalid" (see 13= .9.1 in your=20 > Ada Reference Manual). For integer types, this corresponds to a value out= of=20 > range. Ada compilers are always allowed to return invalid results from=20 > scalar operations, with a few exceptions. So in general, an Ada compiler= =20 > does not actually need to make range checks on scalar objects. The only t= ime=20 > that a check on a scalar object *has* to be performed is when using the= =20 > value could lead to erroneous execution (such as in indexing out of range= ). This is an equivalent concept to nullable, so two questions: What is the literal for 'invalid', IE: X : Index :=3D #INVALID -- we should be able to initialise to invalid. if X =3D #INVALID -- I want to be able to test for invalid. >=20 > So, formally, writing a scalar subtype does not ensure that a compiler ca= n=20 > eliminate checks. Indeed, it doesn't necessarily mean anything at all= , as=20 > scalar objects can be uninitialized and the compiler has to assume that t= hey=20 > could be out of range unless it can prove that they are initialized on al= l=20 > paths. Like not null we therefore need: type X_Type is new Integer not invalid range 0 .. 10; X : X_Type; -- error X : X_Type :=3D 0; -- OK >=20 > Of course, us compiler implementers *want* to eliminate checks based in= =20 > subtypes. There are various strategies for doing so. The "usual"= ; one is that=20 > the compiler defines some subtest of scalar objects as "known to be = valid".=20 > Those are objects that the compiler can easily prove are initialized. (Fo= r=20 > Janus/Ada, we use a fairly conservative definition: stand-alone objects t= hat=20 > are explicitly initialized, literals, loop parameters, and subprogram=20 > parameters. I don't remember if function results are included or not.= ).=20 > Checks have to be performed on assignments and other operations on "= known to=20 > be valid" objects (array indexing is also treated this way) unless s= ubtypes=20 > are the same or statically compatible AND all constituents of the source= =20 > expression are "known to be valid". The above helps the compiler eliminate range checks, the other is type prom= otion: for example: X : not invalid Integer :=3D 99; Y : array (10 .. 1000) of Integer; if X <=3D 1000 then -- type of X is now : not invalid Integer range Integer'First .. 1000; if X >=3D 10 then -- type of X is now : not invalid Integer range 10 .. 1000; Y(X) -- No need for any range checks. end if; end if; >=20 > Our optimizer can remove a few checks that have been generated because of= =20 > later flow analysis and the like, but what can be done then is quite=20 > limited. Generally, the compiler has to not generate the checks in the fi= rst=20 > place. See above for language changes to facilitate better range check removal. >=20 > I'm not sure precisely how GNAT handles this, but elimination of chec= ks is=20 > *much* harder than it appears on the surface, mainly because Ada allows= =20 > uninitialized objects (and still expects uses of them to be detected). This is something I have looked at in a couple of different contexts, and u= sing dependent types (a simple example of which is above) there are known t= echniques for removing all implicit range checks. Personally I dont like im= plicit stuff, so for me personally I would like the compiler to never inser= t implicit checks but instead issue a compile error if it ever had to inser= t an implicit range check. As above you may have to insert explicit range c= hecks to satisfy the compiler, or you may used an unchecked conversion to t= ell the compiler, trust me, i know what I am doing and I have verified the = code will not generate out of bounds values due to unit testing and formal = verification methods. >=20 > > I don't know how good the compiler is at doing this? >=20 > If the implementation model is "wrong", it might not do it at a= ll. >=20 > > There are times when the programmer can guarantee that the output of= a=20 > > function will be > > within range due to extensive unit testing and validation. >=20 > But that doesn't guarantee that the compiler can remove the checks. The compiler should remove the range checks if the programmer is telling it= that the value is definitely within range. With a 'not invalid' type modif= ier, this can be done with some kind of unchecked conversion. >=20 > > I wonder, is there a way to get the compiler (GNAT) to issue a warni= ng=20 > > when it has to insert a range check? >=20 > Can't say if there is a GNAT option, but it seems like a good idea. I= added=20 > such an "information" (it's not a warning in the sense that= normally it=20 > doesn't need to be corrected) to the (lengthy) to-do list for Janus/A= da. >=20 > Randy. Cheers, Keean.