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.3 required=5.0 tests=BAYES_00, REPLYTO_WITHOUT_TO_CC 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.68.223.40 with SMTP id qr8mr280365pbc.0.1342690275741; Thu, 19 Jul 2012 02:31:15 -0700 (PDT) Path: b9ni4982320pbl.0!nntp.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!nx02.iad01.newshosting.com!newshosting.com!194.74.65.76.MISMATCH!news-peer0!news-peer1!btnet!zen.net.uk!hamilton.zen.co.uk!xlned.com!feeder5.xlned.com!feed.xsnews.nl!border-3.ams.xsnews.nl!plix.pl!newsfeed2.plix.pl!news.mi.ras.ru!goblin-spool!goblin1!goblin.stu.neva.ru!feeds.phibee-telecom.net!de-l.enfer-du-nord.net!feeder1.enfer-du-nord.net!gegeweb.org!aioe.org!.POSTED!not-for-mail From: "Dmitry A. Kazakov" Newsgroups: comp.lang.ada Subject: Re: Efficient Sequential Access to Arrays Date: Mon, 16 Jul 2012 09:47:01 +0200 Organization: cbb software GmbH Message-ID: <1s8rnmtyqnrr$.1o78f1qaxeulh$.dlg@40tude.net> References: <01983f1c-f842-4b1f-a180-bcef531dad4c@googlegroups.com> <44f2bfd0-75ed-4b9c-982e-61d5308f9c01@googlegroups.com> Reply-To: mailbox@dmitry-kazakov.de NNTP-Posting-Host: 9A8bJrx4NhDLcSmbrb6AdA.user.speranza.aioe.org Mime-Version: 1.0 X-Complaints-To: abuse@aioe.org User-Agent: 40tude_Dialog/2.0.15.1 X-Notice: Filtered by postfilter v. 0.8.2 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Date: 2012-07-16T09:47:01+02:00 List-Id: On Sun, 15 Jul 2012 13:03:12 -0700 (PDT), 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. Absolute figures tell little. How big is the relative difference? It does not worth efforts if the gain or loss is under 10%. Let your simulation take 10 long years. 10% would mean 1 extra year of computations. Wait 6 months, buy a new computer and you still will be ahead of the schedule. >> That depends on loop optimizations. I would expect GCC to optimize access >> to array elements per the loop's index. > > It does not seem to, I'll see if I can post some assembly. Loop optimization is a tricky issue. I suspect that tiny variations of code may turn it on or off. You should read GCC documentation on that subject to see what is possible on which machines. >> > So assuming we need this level of performance, what would be the best (and >> > most idiomatic Ada) >> >> Indexing is unlikely to have a significant (>5%) influence on overall >> performance. Usually it is other things. > > It seems to have an significant influence in the benchmarks I have run and > has a particular influence when sequentially accessing elements. How much operations do you have per array element? If you do basically only indexing then there must be something wrong with the algorithm. Otherwise, say one multiplication per 100 instructions, is nothing, especially when memory access (a very slow thing) is involved. >> > way to package this type of usage pattern as an >> > abstract datatype? >> >> Array of aliased elements, to ensure elements independently addressable. > > Yes, the type itself will need to have aliased elements, but I was > assuming this would be hidden in a package as an ADT, and would expose an > indexed-iterator that has '+' and '-' operations on the iterator (not just > a forward or bidirectional iterator). Low-level optimization is not compatible with proper design. You have to choose. If you do a controlled iterator type wrapping a pointer rather than integer index, that most likely would be even slower. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de