Re: I need the fastest routine

"Sasa Zeman" <sasaz72@xxxxxxx> wrote in message
news:48830b7f@xxxxxxxxxxxxxxxxxxxxxxxxx
0,217537s 960051513 0 Using pointers (8/loop) !!! BUG !!!

BUG !! - we can't have that.

I have changed it to 1 offset instead of 0 offset.

Furthermore i changed the initial min/max to the first element.
By doing that, i can use if then else instead of two if's.

I now have 3 versions, 8/loop with double if's, same with if then else, and
a 16/loop if then else.
I ran test wth ascending array (0..999999) and a Random test.

The result (Ascending):
-------------------------------------
Using pointers (8/loop)
2,847194 s - 0/999999

Using pointers (8/loop - a)
2,368591 s - 0/999999

Using pointers (16/loop - b)
2,460686 s - 0/999999

That's pretty interesting, unrolling 16 instead of 8 is actually slower.

The result (Random):
-------------------------------------
Using pointers (8/loop)
2,464990 s - 6/9999999

Using pointers (8/loop - a)
2,480348 s - 6/9999999

Using pointers (16/loop - b)
2,378352 s - 6/9999999

Now here the if then else is slower than double if's - kind of interesting.

But anyway, here is the latest 16/loop code, the others is just to
delete/reduce to 8 or 4.

......................................................................
procedure MinMaxArray0_1b(const aArray: array of Integer;
out aMax, aMin: Integer);
TYPE
tIa = PACKED ARRAY [1..16] OF INTEGER ;
tpIa = ^tIa ;
var
I: Integer;
pIa : tPIa ;
iMin,iMax : INTEGER ;
rm : Integer ;
begin
pIa :=@aArray[0];
iMax := PIa^[1];
iMin := PIa^[1];
rm := Length (aArray) MOD 16 ;
for I := 1 to Length(aArray) DIV 16 do
begin
if ( PIa^[1] > iMax ) OR ( PIa^[2] > iMax ) OR ( PIa^[3] > iMax ) OR (
PIa^[4] > iMax ) OR ( PIa^[5] > iMax ) OR ( PIa^[6] > iMax ) OR ( PIa^[7] >
iMax ) OR ( PIa^[8] > iMax ) OR
( PIa^[9] > iMax ) OR ( PIa^[10] > iMax ) OR ( PIa^[11] > iMax ) OR
( PIa^[12] > iMax ) OR ( PIa^[13] > iMax ) OR ( PIa^[14] > iMax ) OR (
PIa^[15] > iMax ) OR ( PIa^[16] > iMax ) then BEGIN
IF PIa^[1] > iMax THEN
iMax := PIa^[1];
IF PIa^[2] > iMax THEN
iMax := PIa^[2];
IF PIa^[3] > iMax THEN
iMax := PIa^[3];
IF PIa^[4] > iMax THEN
iMax := PIa^[4];
IF PIa^[5] > iMax THEN
iMax := PIa^[5];
IF PIa^[6] > iMax THEN
iMax := PIa^[6];
IF PIa^[7] > iMax THEN
iMax := PIa^[7];
IF PIa^[8] > iMax THEN
iMax := PIa^[8];
IF PIa^[9] > iMax THEN
iMax := PIa^[9];
IF PIa^[10] > iMax THEN
iMax := PIa^[10];
IF PIa^[11] > iMax THEN
iMax := PIa^[11];
IF PIa^[12] > iMax THEN
iMax := PIa^[12];
IF PIa^[13] > iMax THEN
iMax := PIa^[13];
IF PIa^[14] > iMax THEN
iMax := PIa^[14];
IF PIa^[15] > iMax THEN
iMax := PIa^[15];
IF PIa^[16] > iMax THEN
iMax := PIa^[16];
END ELSE // <==== this is instead of END;
if ( PIa^[1] < iMin ) OR ( PIa^[2] < iMin ) OR ( PIa^[3] < iMin ) OR (
PIa^[4] < iMin ) OR ( PIa^[5] < iMin ) OR ( PIa^[6] < iMin ) OR ( PIa^[7] <
iMin ) OR ( PIa^[8] < iMin )OR
( PIa^[9] < iMin ) OR ( PIa^[10] < iMin ) OR ( PIa^[11] < iMin ) OR
( PIa^[12] < iMin ) OR ( PIa^[13] < iMin ) OR ( PIa^[14] < iMin ) OR (
PIa^[15] < iMin ) OR ( PIa^[16] < iMin ) then BEGIN
IF PIa^[1] < iMin THEN
iMin := PIa^[1];
IF PIa^[2] < iMin THEN
iMin := PIa^[2];
IF PIa^[3] < iMin THEN
iMin := PIa^[3];
IF PIa^[4] < iMin THEN
iMin := PIa^[4];
IF PIa^[5] < iMin THEN
iMin := PIa^[5];
IF PIa^[6] < iMin THEN
iMin := PIa^[6];
IF PIa^[7] < iMin THEN
iMin := PIa^[7];
IF PIa^[8] < iMin THEN
iMin := PIa^[8];
IF PIa^[9] < iMin THEN
iMin := PIa^[9];
IF PIa^[10] < iMin THEN
iMin := PIa^[10];
IF PIa^[11] < iMin THEN
iMin := PIa^[11];
IF PIa^[12] < iMin THEN
iMin := PIa^[12];
IF PIa^[13] < iMin THEN
iMin := PIa^[13];
IF PIa^[14] < iMin THEN
iMin := PIa^[14];
IF PIa^[15] < iMin THEN
iMin := PIa^[15];
IF PIa^[16] < iMin THEN
iMin := PIa^[16];
END ;
Inc(PIa);
end;
for I := 1 to rm do
begin
IF PIa^[I] < iMin THEN
iMin := PIa^[I];
IF PIa^[I] > iMax THEN
iMax := PIa^[I];
end;
aMax := iMin;
aMin := iMax;
end;
...............................


--
Med venlig hilsen/Best regards
Stig Johansen



.

Relevant Pages

  • Re: I need the fastest routine
    ... I really can't thank you enough for helping me with this one. ... I just can't imagine the performance boost if I replace the minmax routine with the one you provided. ... I am working with local variables iMin and iMax instead of aMin and aMax. ...
    (borland.public.delphi.language.basm)
  • Re: I need the fastest routine
    ... but current processors minimize the jump in the loop so much ... PIa^> iMax) then BEGIN ... PIa^< iMin) then BEGIN ... Then i tried 'unrolling' with an array of 8, ...
    (borland.public.delphi.language.basm)
  • Re: Generalized range
    ... I think just increasing a "counter" from iMin to iMax should be fine, achieving more precision by making computations fuzzy -- i don't know, perhaps it's very good. ... elsewhere) is the addition/subtraction of a fixed epsilon to ensure ...
    (comp.lang.python)
  • Generalized range
    ... return range(iMin, iMax, iStep) ... elsewhere) is the addition/subtraction of a fixed epsilon to ensure ... particular values of iMax, iMin and iStep. ...
    (comp.lang.python)
  • Re: I need the fastest routine
    ... aMin:= iMax; ... (you can find the result for this code at "Using pointers (16/loop)") ... 2,818878s 0 0 Reading array value once ... 1,115688s 0 0 Hubert Seidel ASM ...
    (borland.public.delphi.language.basm)