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.66.84.8 with SMTP id u8mr1479803pay.45.1343000086160; Sun, 22 Jul 2012 16:34:46 -0700 (PDT) Path: b9ni34698554pbl.0!nntp.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!ctu-peer!news.nctu.edu.tw!goblin1!goblin.stu.neva.ru!news.mixmin.net!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 20:48:22 +0200 Organization: cbb software GmbH 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> 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-16T20:48:22+02:00 List-Id: On Mon, 16 Jul 2012 09:39:45 -0700 (PDT), Keean Schupke wrote: > On Monday, 16 July 2012 15:57:04 UTC+1, Dmitry A. Kazakov wrote: >> 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. > > I find this comment puzzling and does not match my experience. It is just an observation that more than 25% of CPU load is spent to heat the atmosphere rather than doing something useful. > What algorithm for disjoint-set do you suggest I use? I would try to avoid using such things if the problem is large. > Until you have read it I don't > think you can comment on the quality of algorithm I am using. Quality is an objective measure which does not depend on whether anybody reads anything. >> It appears GCC is unable to optimise the indexing away when the index is >> dynamic (relies on IO or PRNG for example). >> >> You should read its documentation in order to be able to say. Consequent >> indexing could be optimized as addition to the register-stored base. > > It may be able to optimize the access in loops, but this is for more complex. Either the problem is that the GCC's is unable to optimize something or it is not. > The node in the array contains pointers to other nodes. When we follow the > pointers we want to be able to access the neighbours consider: > > type Node_Type is record > 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 := X(Y).Next.Data; > > but how do we access the neighbouring nodes? We cannot do: > > D := (X(Y).Next + 1).Data; X(Y+1).Next.Data; X(Y).Next.Next.Data; No idea what you are trying to do. But indexing *must* be faster than indirection. You should make your data structures straight. >> > Highly optimised code can still have good structure, using inlining and >> > generics code can be elegant and fast. >> >> Code using generics/templates is never elegant nor fast, but that is an >> off-topic. >> >> > 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. >> >> This is only necessary when the class of the container type is wider than >> just arrays, e.g. includes other structures like lists. > > This ignores the fact that the interface for an ADT should be independent > of its implementation. That is impossible for built-in types like arrays, which (unfortunately) lack inheritable interfaces in Ada. >> If you have performance problems with arrays, which are built-in and >> subject of tailored optimization, you cannot expect situation improved by >> puzzling the compiler with more abstract types. That could only disable >> optimization. > > Maybe you are thinking of something more complex than I am. An ADT is just > a private type with associated functions in a package. 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? > Element's is different from the STL. It includes native 'concepts' that > define axiomatic constraints on software modules. I have no idea what "axiomatic constraints on software modules" could mean. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de