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,CP1252 Received: by 10.66.85.226 with SMTP id k2mr69877paz.34.1342756024589; Thu, 19 Jul 2012 20:47:04 -0700 (PDT) Path: b9ni11283778pbl.0!nntp.google.com!border1.nntp.dca.giganews.com!border4.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!nntp.giganews.com!novia!news-hub.siol.net!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 12:12:48 -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> <1lgvwexsx8ovd.xdbvohz8eowp.dlg@40tude.net> <4c86d54d-dfeb-44f1-9638-3c416ea51d74@googlegroups.com> NNTP-Posting-Host: 82.44.19.199 Mime-Version: 1.0 X-Trace: posting.google.com 1342465968 27230 127.0.0.1 (16 Jul 2012 19:12:48 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Mon, 16 Jul 2012 19:12:48 +0000 (UTC) Cc: mailbox@dmitry-kazakov.de 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 Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: quoted-printable Date: 2012-07-16T12:12:48-07:00 List-Id: On Monday, 16 July 2012 19:48:22 UTC+1, Dmitry A. Kazakov wrote: > On Mon, 16 Jul 2012 09:39:45 -0700 (PDT), Keean Schupke wrote: >=20 > > On Monday, 16 July 2012 15:57:04 UTC+1, Dmitry A. Kazakov wrote: >=20 > >> Which itself looks like a problem. It takes no less than 25% of = overall > >> performance for mere shuffling data in a task unrelated to stuff= like > >> recoding etc. This looks wrong to me. I would look for a better > >> algorithm/structure. > >=20 > > I find this comment puzzling and does not match my experience. >=20 > It is just an observation that more than 25% of CPU load is spent to heat > the atmosphere rather than doing something useful. >=20 > > What algorithm for disjoint-set do you suggest I use? >=20 > I would try to avoid using such things if the problem is large. Perhaps you would like to outline your methodology for algorithm developmen= t? How would you go about designing an efficient algorithm to solve these k= ind of problems: =95 Network connectivity. =95 Percolation. =95 Image processing. (okay this ones a bit vague, but this list is copied = from the paper) =95 Least common ancestor. =95 Equivalence of finite state automata. =95 Hinley-Milner polymorphic type inference. =95 Kruskal's minimum spanning tree algorithm.=20 =95 Games (Go, Hex) =95 Compiling equivalence statements in Fortran. Can you can suggest a more efficient algorithm for any of these than WQUPC? >=20 > > Until you have read it I don't > > think you can comment on the quality of algorithm I am using. >=20 > Quality is an objective measure which does not depend on whether anybody > reads anything. You can only comment on the quality of the algorithm if you understand the = problem. What does a good quality algorithm to solve the percolation proble= m look like? (You can find a definition of the percolation problem in the W= QUPC paper I posted a link to). If you can come up with a better algorithm = it would be worthy of publication. > =20 > >> It appears GCC is unable to optimise the indexing away when the = index is > >> dynamic (relies on IO or PRNG for example). > >>=20 > >> You should read its documentation in order to be able to say. Co= nsequent > >> indexing could be optimized as addition to the register-stored b= ase. > >=20 > > It may be able to optimize the access in loops, but this is for more= complex. >=20 > Either the problem is that the GCC's is unable to optimize something = or it > is not. >=20 > > The node in the array contains pointers to other nodes. When we foll= ow the > > pointers we want to be able to access the neighbours consider: > > > > type Node_Type is record=20 > > Next : access all Node_Type; > > Other : access all Node_Type; > > Data : Data_Type; > > end record; > > > > type A is array (Index_Type) of aliased Node_Type; > > > > X : A; > > > > So we can access the next record like this: > > > > D :=3D X(Y).Next.Data; > > > > but how do we access the neighbouring nodes? We cannot do: > > > > D :=3D (X(Y).Next + 1).Data; >=20 > X(Y+1).Next.Data; > X(Y).Next.Next.Data; >=20 > No idea what you are trying to do. But indexing *must* be faster than > indirection. You should make your data structures straight. Straight data structures require copying data. If we were to use an array i= nstead of a linked list then every state change would require copying stuff= . Also each node would require enough space to store every other node (pote= ntially) which would overflow the cache and seriously slow down the code. O= ther people have tried this approach and their code is slower. >=20 > >> &gt; Highly optimised code can still have good structure, us= ing inlining and > >> &gt; generics code can be elegant and fast. > >>=20 > >> Code using generics/templates is never elegant nor fast, but tha= t is an > >> off-topic. > >>=20 > >> &gt; There is nothing wrong in design terms with a forward-i= terator, in fact it > >> &gt; is better design from a generic point of view to expose= the minimal set of > >> &gt; methods to efficiently implement the required algorithm= . > >>=20 > >> This is only necessary when the class of the container type is w= ider than > >> just arrays, e.g. includes other structures like lists. > >=20 > > This ignores the fact that the interface for an ADT should be indepe= ndent > > of its implementation. >=20 > That is impossible for built-in types like arrays, which (unfortunately) > lack inheritable interfaces in Ada. I agree with you here - its a shame. I wonder if there is some kind of desi= gn principle in Ada that makes this undesirable, or if this is just an over= sight. >=20 > >> If you have performance problems with arrays, which are built-in= and > >> subject of tailored optimization, you cannot expect situation im= proved by > >> puzzling the compiler with more abstract types. That could only = disable > >> optimization. > >=20 > > Maybe you are thinking of something more complex than I am. An ADT i= s just > > a private type with associated functions in a package. >=20 > It is difficult for the compiler to optimize wrappers of array operations > like indexing. You said you failed to make GCC to optimize raw array > access. Why wrapping that into functions should do any better? It doesn't do any worse... the functions are mostly single line and get inl= ined before the optimisation pass. It has the benefit of better code struct= ure, improved modularity and better readability. On the whole many positives, and no negatives (because its just as fast in = my tests). >=20 > > Element's is different from the STL. It includes native 'con= cepts' that > > define axiomatic constraints on software modules. >=20 > I have no idea what "axiomatic constraints on software modules"= could mean. See: http://akrzemi1.wordpress.com/2012/01/11/concept-axioms-what-for/ Cheers, Keean.