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.68.219.170 with SMTP id pp10mr563656pbc.1.1342728595954; Thu, 19 Jul 2012 13:09:55 -0700 (PDT) Path: p10ni8621817pbh.1!nntp.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!novia!news-peer1!btnet!zen.net.uk!hamilton.zen.co.uk!xlned.com!feeder5.xlned.com!feed.xsnews.nl!border-2.ams.xsnews.nl!plix.pl!newsfeed2.plix.pl!news.mi.ras.ru!goblin1!goblin.stu.neva.ru!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail From: Keean Schupke Newsgroups: comp.lang.ada Subject: Re: Efficient Sequential Access to Arrays Date: Mon, 16 Jul 2012 03:16:09 -0700 (PDT) Organization: http://groups.google.com Message-ID: References: <01983f1c-f842-4b1f-a180-bcef531dad4c@googlegroups.com> <44f2bfd0-75ed-4b9c-982e-61d5308f9c01@googlegroups.com> <1s8rnmtyqnrr$.1o78f1qaxeulh$.dlg@40tude.net> NNTP-Posting-Host: 82.44.19.199 Mime-Version: 1.0 X-Trace: posting.google.com 1342433769 10194 127.0.0.1 (16 Jul 2012 10:16:09 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Mon, 16 Jul 2012 10:16:09 +0000 (UTC) Cc: mailbox@dmitry-kazakov.de In-Reply-To: <1s8rnmtyqnrr$.1o78f1qaxeulh$.dlg@40tude.net> 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-16T03:16:09-07:00 List-Id: On Monday, 16 July 2012 08:47:01 UTC+1, Dmitry A. Kazakov wrote: > On Sun, 15 Jul 2012 13:03:12 -0700 (PDT), Keean Schupke wrote: >=20 > > 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: > >>=20 > >> &gt; However in order to achieve this performance I needed t= o rework the arrays > >> &gt; as the use of Indexes was too slow. > >>=20 > >> You have to measure it in order to know. Write two variants and = compare > >> their performance. > >=20 > > Have done, the difference is about 10k simulations per second. >=20 > Absolute figures tell little. How big is the relative difference? About 25% (30k with indexing, 40k with relative addressing) >=20 > 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 computation= s. > Wait 6 months, buy a new computer and you still will be ahead of the > schedule. The software needs to react faster than the competition at any given point = in time. That is all I can say really. >=20 > >> That depends on loop optimizations. I would expect GCC to optimi= ze access > >> to array elements per the loop&#39;s index. > >=20 > > It does not seem to, I'll see if I can post some assembly. >=20 > Loop optimization is a tricky issue. I suspect that tiny variations of co= de > may turn it on or off. You should read GCC documentation on that subject = to > see what is possible on which machines. It appears GCC is unable to optimise the indexing away when the index is dy= namic (relies on IO or PRNG for example). >=20 > >> &gt; So assuming we need this level of performance, what wou= ld be the best (and > >> &gt; most idiomatic Ada) > >>=20 > >> Indexing is unlikely to have a significant (&gt;5%) influenc= e on overall > >> performance. Usually it is other things. > >=20 > > It seems to have an significant influence in the benchmarks I have r= un and > > has a particular influence when sequentially accessing elements. >=20 > How much operations do you have per array element? If you do basically on= ly > 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. The algorithm is highly optimised, and has been developed over several year= s. The choice of data structures is pretty good, and the low operation coun= t indicates that the data structures are a good match for the topology of t= he problem. Most highly efficient algorithms do a lot of work with a few op= erations. I would recommend Tarjan for a view of the kind of algorithms we = are using: http://books.google.co.uk/books/about/Data_Structures_and_Network_Algorithm= s.html?id=3Dm1rAB3uWwBwC&redir_esc=3Dy >=20 > >> &gt; way to package this type of usage pattern as an > >> &gt; abstract datatype? > >>=20 > >> Array of aliased elements, to ensure elements independently addr= essable. > >=20 > > 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 expo= se an > > indexed-iterator that has '+' and '-' operations on = the iterator (not just > > a forward or bidirectional iterator). >=20 > Low-level optimization is not compatible with proper design. You have to > choose. If you do a controlled iterator type wrapping a pointer rather th= an > integer index, that most likely would be even slower. Highly optimised code can still have good structure, using inlining and gen= erics code can be elegant and fast. There is nothing wrong in design terms with a forward-iterator, in fact it = is better design from a generic point of view to expose the minimal set of = methods to efficiently implement the required algorithm. To see elegant and= efficient code constructed in this way see Stepanov's "Elements of Program= ming". http://www.elementsofprogramming.com/book.html Cheers, Keean.