Tipy a triky

Na této stránce je pár různých programovacích triků určených hlavně pro zrychlení důležitých částí kódu. Veškerý kód je v Delphi, ovšem lze triviálně převést do jiných jazyků (např. do C, v Javě to zřejmě nemá příliš smysl, ale můžete to zkusit). Pokud váš programovací jazyk umožňuje vkládané (inline) funkce (což bohužel Delphi neumožňuje), můžete si dokonce z těchto triků udělat malou knihovnu. Pokud váš jazyk vkládané funkce neumí, tak příslušné triky musíte opakovat na každém místě použití – zabalit je do funkce je sice elegantní, ale režie volání funkce prakticky znehodnotí jakékoli dosažené časové úspory.

Všechny triky jsou založeny na tom, že pochopíte, o co v nich jde a příslušně to pak využijete. Pokud budete jenom slepě opisovat, může se vám stát, že trik aplikujete ve zcela nevhodné situaci! Většina triků se také snadno modifikuje pro různé příbuzné úlohy (např. trik výběr lze triviálně upravit pro nalezení minima či maxima dvou čísel), přičemž věřím, že podobné úpravy zvládnete sami.

Netvrdím, že uvedené triky jsou nejlepší možné (zvláště se to týká triků psaných v assembleru). Pokud přijdete na nějaké univerzálně platné vylepšení nějakého triku, dejte mi vědět!

Časové zhodnocení

U každého způsobu řešení (ať už klasického, nebo triku) je uveden odhad času, který tento úsek kódu potřebuje. U dnešních procesorů je velice obtížné přesně spočítat, jak dlouho bude nějaký úsek kódu trvat. Proto byl tento čas určen empiricky (měřením na AMD Athlon XP). Přesná doba trvání kódu je však velice závislá na umístění kódu, na tom, jaké další instrukce kódu předcházejí a kód následují, jak jsou naplněny cache paměti, atd. atd. Toto měření (stejně tak i případný teoretický výpočet) je také přímo závislé na architektuře procesoru a přesná čísla platí proto pouze pro příslušný typ.

Proto prosím berte časové hodnoty spíše jako hrubé odhady poměrů, spíše než přesné hodnocení času, který zabere provádění příslušného kódu.

Obsah

Triky jsou rozděleny do následujících kategorií:

Obecné
Floating point

Obecné triky

Complete boolean eval

Většina jazyků (Delphi nevýjimaje) používá (přinejmenším v implicitním nastavení) tzv. zkrácené vyhodnocování booleovských výrazů (short-circuit boolean evaluation), které způsobí, že v případě, že je o hodnotě booleovského výrazu rozhodnuto již před zpracováním všech operandů, je vyhodnocení okamžitě ukončeno a zbylé výrazy se již nevyhodnocují. V některých případech (zvláště pokud jsou v operandech volány funkce) se nám tato vlastnost hodí. Ovšem je třeba si uvědomit, že pokud jsou jako operandy použity rovnou proměnné, často se bez zkráceného vyhodnocování obejdeme, a tím kód i výrazně zrychlíme!

Zkrácené vyhodnocování můžeme vypnout buď pomocí nastavení překladače (což není příliš elegantní), nebo můžeme využít faktu, že běžné bitové operace and, or, xor (not obecně nikoliv, ten můžeme použít pouze s operátorem and!) fungují pro klasické proměnné typu Boolean (obsahující přímo hodnoty 0, 1) zcela stejně, ovšem u nich samozřejmě žádné zkrácené vyhodnocování neexistuje.

Klasické řešení Result := a and b and c; 13τ (hodně závislé na a,b,c)

Vypnutí direktivou překladače {$B+}Result := a and b and c;{$B-} 3τ

Bitové operátory Result := Byte(A) and Byte(B) and Byte(C) <> 0; 3τ

Výběr

Klasické řešení	if b then Result := x else Result := y;	13τ
Algebraické vyjádření	Result := Integer(b) * x + Integer(not b) * y;	8τ
Využití assembleru a CMOVcc	asm `CMP [b], 0 CMOVNZ EAX, DWORD PTR [x] CMOVZ EAX, DWORD PTR [y] MOV DWORD PTR [Result], EAX` end;	4τ

Floating point triky

V následující části je vždy proměnná x typu Single. Některé triky fungují i s většími proměnnými, jinde musíte něco upravit, jiné nefungují vůbec…

Porovnání vůči nule

Klasické řešení	Result := x > 0;	5τ
Přetypovat na celočíselný typ	Result := Integer((@x)^) > 0;	1τ

Obdobně i všechny ostatní testy proti nule. Tyto testy nejsou zcela přesné! Považují totiž zápornou nulu za záporné (nenulové) číslo a neřeší hodnoty NaN, považují je za běžná čísla (tzn. NaN může testu vyhovět). Problém se zápornou nulou můžeme vyřešit následující úpravou:

Klasické řešení Result := x <> 0; 5τ

Přetypování s ignorováním znaménka Result := Integer((@x)^) and $7FFFFFFF <> 0; 2τ

Klasické řešení Result := x < 0; 5τ

Přetypování Result := Cardinal((@x)^) > $80000000; 2τ

Když porovnáváme dvě floating-point čísla navzájem, můžeme tento test využít tak, že budeme vůči nule porovnávat rozdíl obou čísel.

Testy proti jiným číslům než je nula provádět můžeme, ovšem s tou nevýhodou, že si nejprve musíme zjistit binární reprezentaci daného floating-point čísla, kterou pak uvedeme jako celočíselnou konstantu (obvykle v hexadecimálním zápisu). Taková konstanta však v programu vypadá podivně.

Kladná část čísla

f(x) = max{x, 0}

Klasické řešení if x <= 0 then Result := 0 else Result := x; 19τ

Po využití předchozího triku if Integer((@x)^) <= 0 then Result := 0 else Result := x; 13τ

Elementární matematika Result := (x + Abs(x)) * 0.5; 2τ

Využití assembleru (použitelné i pro Integer) asm
MOV EAX, DWORD PTR [x] MOV EDX, EAX SAR EAX, 31 NOT EAX AND EAX, EDX MOV DWORD PTR [Result], EAX end; 2τ

Klasické řešení	Result := a and b and c;	13τ (hodně závislé na a,b,c)
Vypnutí direktivou překladače	`{$B+}`Result := a and b and c;`{$B-}`	3τ
Bitové operátory	Result := Byte(A) and Byte(B) and Byte(C) <> 0;	3τ

Klasické řešení	Result := x <> 0;	5τ
Přetypování s ignorováním znaménka	Result := Integer((@x)^) and $7FFFFFFF <> 0;	2τ
Klasické řešení	Result := x < 0;	5τ
Přetypování	Result := Cardinal((@x)^) > $80000000;	2τ

Klasické řešení	if x <= 0 then Result := 0 else Result := x;	19τ
Po využití předchozího triku	if Integer((@x)^) <= 0 then Result := 0 else Result := x;	13τ
Elementární matematika	Result := (x + Abs(x)) * 0.5;	2τ
Využití assembleru (použitelné i pro Integer)	asm `MOV EAX, DWORD PTR [x] MOV EDX, EAX SAR EAX, 31 NOT EAX AND EAX, EDX MOV DWORD PTR [Result], EAX` end;	2τ