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 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.216.241.9 with SMTP id f9mr540865wer.5.1343261731974; Wed, 25 Jul 2012 17:15:31 -0700 (PDT) MIME-Version: 1.0 Path: q11ni65577455wiw.1!nntp.google.com!goblin3!goblin1!goblin2!goblin.stu.neva.ru!weretis.net!feeder4.news.weretis.net!nuzba.szn.dk!news.jacob-sparre.dk!munin.jacob-sparre.dk!pnx.dk!.POSTED!not-for-mail From: "Randy Brukardt" Newsgroups: comp.lang.ada Subject: Re: Efficient Sequential Access to Arrays Date: Wed, 25 Jul 2012 19:15:25 -0500 Organization: Jacob Sparre Andersen Research & Innovation 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: static-69-95-181-76.mad.choiceone.net X-Trace: munin.nbi.dk 1343261730 12321 69.95.181.76 (26 Jul 2012 00:15:30 GMT) X-Complaints-To: news@jacob-sparre.dk NNTP-Posting-Date: Thu, 26 Jul 2012 00:15:30 +0000 (UTC) X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2900.5931 X-RFC2646: Format=Flowed; Original X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.6157 Date: 2012-07-25T19:15:25-05:00 List-Id: "Keean Schupke" wrote in message news:f2f61da1-3139-4dfc-b851-8398f27d558d@googlegroups.com... > 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. Enabling >> index checks in the Ada code would probably (in this case, where the >> algorithm has scatterered indexing of the array) slow it by an amount >> that swamps the effect of the multiplication optimization. > > On the specific point of array index checking, if you can statically prove > the algorithm > using the array will never use an out of range index, there is no need to > run-time index check. > > If we generate a random number between one and N, and then lookup the Nth > element, we do not > need to range check as the number is by definition in range. If the type > 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 needs to > be no > range checks on the array lookup. This isn't necessarily true. The following is *very* Ada language-lawyer, so skip if you don't want to know the details. (BTW, this is all Ada 95 thinking, refined somewhat since.) Ada scalar objects can be in a state known as "invalid" (see 13.9.1 in your Ada Reference Manual). For integer types, this corresponds to a value out of range. Ada compilers are always allowed to return invalid results from scalar operations, with a few exceptions. So in general, an Ada compiler does not actually need to make range checks on scalar objects. The only time that a check on a scalar object *has* to be performed is when using the value could lead to erroneous execution (such as in indexing out of range). So, formally, writing a scalar subtype does not ensure that a compiler can eliminate checks. Indeed, it doesn't necessarily mean anything at all, as scalar objects can be uninitialized and the compiler has to assume that they could be out of range unless it can prove that they are initialized on all paths. Of course, us compiler implementers *want* to eliminate checks based in subtypes. There are various strategies for doing so. The "usual" one is that the compiler defines some subtest of scalar objects as "known to be valid". Those are objects that the compiler can easily prove are initialized. (For Janus/Ada, we use a fairly conservative definition: stand-alone objects that are explicitly initialized, literals, loop parameters, and subprogram parameters. I don't remember if function results are included or not.). Checks have to be performed on assignments and other operations on "known to be valid" objects (array indexing is also treated this way) unless subtypes are the same or statically compatible AND all constituents of the source expression are "known to be valid". Our optimizer can remove a few checks that have been generated because of later flow analysis and the like, but what can be done then is quite limited. Generally, the compiler has to not generate the checks in the first place. I'm not sure precisely how GNAT handles this, but elimination of checks is *much* harder than it appears on the surface, mainly because Ada allows uninitialized objects (and still expects uses of them to be detected). > I don't know how good the compiler is at doing this? If the implementation model is "wrong", it might not do it at all. > There are times when the programmer can guarantee that the output of a > function will be > within range due to extensive unit testing and validation. But that doesn't guarantee that the compiler can remove the checks. > I wonder, is there a way to get the compiler (GNAT) to issue a warning > when it has to insert a range check? Can't say if there is a GNAT option, but it seems like a good idea. I added such an "information" (it's not a warning in the sense that normally it doesn't need to be corrected) to the (lengthy) to-do list for Janus/Ada. Randy.