Re: Invade wikipedia!

["Stuart" <stuart@0.0>]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> 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