Jako 15:lla - FASTDIV yli 5 kertaa nopeampi kuin DIV !

Delphi_Coder kirjoitti:

Eräässä ohjelmassa oli tarve jakaa useita lukuja 15:lla, tarpeen SEKÄ tulos ETTÄ jakojäännös.

Normaalisti näin:

A := X DIV 15;
B := X MOD 15;

Mutta tässä oleva esimerkki näyttää yli 5 kertaa nopeamman tavan laskea samat tulokset.

Tässä voitte testata samaa eri CPU:lla varustetulla tietokoneella.

Ajat on laskettu suoraan Windows -API:sta löytyvän GetTickCount -funktion avulla.

Olisi tietysti kiva, jos x86 -prosessoreissa olisi suoraan tällaiset käskyt:

FASTDIV
PREPAREFASTDIV

Mutta eipä ole valmiina.
Tässäkin on vain 15:lla jakamista varten tuo FASTDIV, mutta siis jokaista eri jakajaa varten tarvitaan erilainen proseduuri -jollei sitten vakioida esim. jotacin record -tyyppiä siten, että ko. recordissa olisi valmiiksi laskettuna yleisen fastdiv -algoritmin tarvitsemat tiedot määrättyä jakajaa varten.

JOS riittää pelkkä jakolaskun tulos, on tämä FASTDIV vieläkin nopeampi.
Tässä kuitenkin siis lasketaan sekä X DIV 15, että myös X MOD 15.

Itse laskutoimitukset siis suoraan assemblerilla, mutta kuten allaolevasta huomaa, Delphi on mainio ympäristö myös tähän:

Allaolevassa koodissa on luettavuuden parantamiseksi koko koodi ajettu AddDots() -proseduurin läpi.

JOS haluat kopioida koodin, aja ko. lähdekoodille procedure RemoveDots(SL:TStrings);

Se löytyy täältä:

http://keskustelu.suomi24.fi/node/12135877

Ja sitten FASTDIV15 -lähdekoodiin:

---------------------------------------------------------

.
.
. procedure RunOriginalDivPrim;
. asm
. push EBX
. mov EBX, 125000000
.
. @@L1:
. mov EAX, EBX
. add EAX, 4169967295
.
. // Calc EAX DIV 15:
. mov ECX, 15
. XOR EDX, EDX
. DIV ECX
. // Calculated
.
. dec EBX
. jnz @@L1
.
. pop EBX
. end;
.
. procedure RunFastDiv15Prim;
. asm
. push EBX
. mov EBX, 125000000
.
. @@L1:
. mov EAX, EBX
. add EAX, 4169967295
.
. // Calc EAX DIV 15:
. push EAX // push Dividend from EAX.
. mov EDX, $88888889
. MUL EDX
. mov EAX, EDX // = SHR 32
. SHR EAX, 3 // = SHR 3 = total SHR 35
. mov ECX, EAX // copy the real result into ECX.
. mov EDX, 15
. MUL EDX
. pop EDX // pop Dividend into EDX.
. sub EDX, EAX
. mov EAX, ECX
. // Calculated
.
. dec EBX
. jnz @@L1
.
. pop EBX
. end;
.
. var
. T1, T2, T3, T4 : Longword;
.
. procedure RunOriginalDiv;
. begin
. T1 := GetTickCount;
. RunOriginalDivPrim;
. T2 := GetTickCount;
. end;
.
. procedure RunFastDiv15;
. begin
. T3 := GetTickCount;
. RunFastDiv15Prim;
. T4 := GetTickCount;
. end;
.
. procedure Compare_Division_Speed(SL:TStrings);
. var
. QSt, S : String;
.
. begin
. // 1. Original DIV:
.
. RunOriginalDiv;
.
. Str((T2-T1)* 0.001:6:3, QSt);
. S := 'Original DIV run time is ' QSt ' seconds';
. SL.Add(S);
.
. // 2. Fast DIV:
.
. RunFastDiv15;
.
. Str((T4-T3)* 0.001:6:3, QSt);
. S := 'Fast DIV run time is ' QSt ' seconds';
. SL.Add(S);
. end;
.
. // Napin klikkauksen käsittelijä:
.
. procedure TfrmEngAlpha.bnSpeedClick(Sender: TObject);
. begin
. Compare_Division_Speed(memPrimeInfo.Lines);
. end;
.
. (*
. Orig DIV: 2.469 seconds
. Fast DIV: 0.422 seconds
.
. per 125 million loops.
. *)
.

kirjoitti:

Anonyymi

Kirjoita kommentti

5000

Lähetä