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,BIG5 Received: by 10.180.106.3 with SMTP id gq3mr1160177wib.1.1343175494423; Tue, 24 Jul 2012 17:18:14 -0700 (PDT) Received: by 10.66.72.73 with SMTP id b9mr689733pav.9.1343175493791; Tue, 24 Jul 2012 17:18:13 -0700 (PDT) Path: ge7ni57615390wib.0!nntp.google.com!feed-C.news.volia.net!volia.net!news2.volia.net!feed-A.news.volia.net!4no1884433pbo.1!news-out.google.com!b9ni51550107pbl.0!nntp.google.com!border1.nntp.dca.giganews.com!border4.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!nntp.giganews.com!ctu-peer!news.nctu.edu.tw!netnews.chu.edu.tw!News.leobbs.net!goblin2!goblin.stu.neva.ru!aioe.org!.POSTED!not-for-mail From: "Dmitry A. Kazakov" Newsgroups: comp.lang.ada Subject: Re: Efficient Sequential Access to Arrays Date: Tue, 17 Jul 2012 08:31:11 +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="big5" Content-Transfer-Encoding: 8bit Date: 2012-07-17T08:31:11+02:00 List-Id: On Mon, 16 Jul 2012 12:12:48 -0700 (PDT), Keean Schupke wrote: > 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: >> >> > 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. > > Perhaps you would like to outline your methodology for algorithm > development? I don't develop algorithms I apply them. 25% overhead on indexing is too much. > How would you go about designing an efficient algorithm to > solve these kind of problems: > > �E Network connectivity. 1. Open amazon site 2. Search "netwok adapter" 3. Choose 5 different with minimal price 4. Among them select one with maximal positive customer reports 5. Buy it (Network connectivity is not an algorithmic problem) >> 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 > instead of a linked list then every state change would require copying > stuff. In Ada you rename array elements. This lets the compiler to choose between copying and handling it in-place. BTW copying might turn more effective depending on the architecture. >> >> 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? > > It doesn't do any worse... the functions are mostly single line and get > inlined before the optimisation pass. Did you verify that? > On the whole many positives, and no negatives (because its just as fast in my tests). But you said you failed to optimize multiplication away. >> > 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. > > See: > > http://akrzemi1.wordpress.com/2012/01/11/concept-axioms-what-for/ Ah, you meant invariants, propositions regarding program semantics maintained true during code transformations, e.g. for optimization. In more complex cases user could help the compiler giving some advices. But for low-level optimizations like ones of indexing this stuff is buried in the compiler guts. However, yes, Ada should have interfaces of integer types, interfaces of index types, interfaces of array types etc, annotated by pre-/post-conditions and invariants. Unfortunately, presently interfaces are tied with by-reference types. It is unclear when Ada will provide interfaces for all types. Otherwise, regarding program correctness stuff there is SPARK and some in Ada 2012. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de