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.9 required=5.0 tests=BAYES_00,FROM_NUMERIC_TLD autolearn=no autolearn_force=no version=3.4.4 X-Google-Thread: 103376,587e0e0a16d65b10 X-Google-Attributes: gid103376,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news1.google.com!news3.google.com!proxad.net!feeder1-2.proxad.net!news.cs.univ-paris8.fr!gegeweb.org!de-l.enfer-du-nord.net!feeds.phibee-telecom.net!zen.net.uk!dedekind.zen.co.uk!news-peer-lilac.gradwell.net!not-for-mail From: "Stuart" Newsgroups: comp.lang.ada References: <49a6d506$0$32680$9b4e6d93@newsspool2.arcor-online.net> <4a18f335-30f6-4216-8376-0310eb560445@p11g2000yqe.googlegroups.com> <49a7ced2$0$31342$9b4e6d93@newsspool4.arcor-online.net> <49ae7bbf$1_1@glkas0286.greenlnk.net> Subject: Re: Invade wikipedia! Date: Wed, 4 Mar 2009 18:41:10 -0000 X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2900.3138 X-RFC2646: Format=Flowed; Original X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.3350 Message-ID: <49aec6cc_1@glkas0286.greenlnk.net> X-Original-NNTP-Posting-Host: glkas0286.greenlnk.net NNTP-Posting-Host: 20.133.0.1 X-Trace: 1236192072 news.gradwell.net 511 dnews/20.133.0.1:45584 X-Complaints-To: news-abuse@gradwell.net Xref: g2news1.google.com comp.lang.ada:3945 Date: 2009-03-04T18:41:10+00:00 List-Id: "Dmitry A. Kazakov" wrote in message news:srtflu8nsew.hkpkh8pk8o2f.dlg@40tude.net... > On Wed, 4 Mar 2009 13:20:54 -0000, Stuart wrote: > >> I looked at the following: >> >> package Sort is >> type Element is new integer; -- or whatever >> type Element_Number is range 1..10; -- or whatever >> type List is array(Element_Number) of Element; >> >> procedure Insertion_Sort(X : in out List); >> end Sort; >> >> package body Sort is >> procedure Insertion_Sort(X: in out List) is >> begin >> for I in X'First+1..X'Last loop >> declare >> Next_Value_to_Insert : constant Element := X(I); >> Insertion_Point : Element_Number := I; >> begin >> for J in reverse X'first .. I-1 loop >> exit when (Next_Value_to_Insert > X(J)); I think I should have made this: exit when (Next_Value_to_Insert >= X(J)); >> X(J+1) := X(J); -- Shift greater values up the sorted list >> Insertion_Point := Insertion_Point - 1; >> end loop; >> A(Insertion_Point) := Next_Value_to_Insert; I attempted to cancel this version and issue the corrected: X(Insertion_Point) := Next_Value_to_Insert; >> end; >> end loop; >> end Insertion_Sort; >> end Sort; >> >> Interestingly when the compiler I was using was set on a strong >> optimization >> mode it did a lot more loop unrolling in this case than for the other >> example. > > I think this is because the inner loop became a for-loop. I wonder if it > wouldn't be even more efficient (for integral element types) not to move > any elements while looking after the insertion point. And then move slices > when the insertion point is found: > > A (Insertion_Point + 1..I) := A (Insertion_Point..I - 1); > A (Insertion_Point) := Next_Value_to_Insert; I did play with this idea as well - it should offer benfit as the compiler could recognize a bulk memory copy and use the highly optimized system memcpy. I was not sure whether it fell outside the spirit of the original intention of the website that kicked this thread off, as it looks to be changing the algorithm to achieve performance tuning. Mind you I noticed that one of the C examples (for another problem) was significantly optimized for a multicore system - and this was presented as the 'C' performace figure. Are the current compilers good at mapping tasks to processor cores? Regards -- Stuart