Optimalizace v Lispu
Mezi programátory je široce rozšířena pověra, že programy v Lispu jsou
vždy pomalé. Skutečnost je ovšem jiná, Lisp kombinuje některé dobré vlastnosti
jazyků se statickým i dynamickým typováním a kromě toho nabízí
v oblasti optimalizace i některé vskutku nevšední možnosti,
v řadě jiných programovacích jazycích neznámé. Podívejme se, jak široké
optimalizační možnosti Lispu jsou a co konkrétně Lisp v tomto směru nabízí.
Pojem optimalizace
Optimalizaci lze chápat velmi široce. Optimalizovat lze algoritmy, kód, práci
programátora. Programový kód lze optimalizovat na rychlost, paměť, bezpečnost.
V tomto článku se zaměříme na optimalizace obsažené přímo v ANSI
standardu jazyka Common Lisp, umožňující efektivní spolupráci programátora
s lispovými překladači. Máme tím na mysli optimalizace zdrojového
i strojového kódu a optimalizaci práce programátora. Co se týče jiných
dialektů Lispu, ty mají zpravidla odlišné optimalizační prostředky a mnohdy se
optimalizacemi vůbec nezabývají.
Stabilita kódu
Common Lisp vznikl z potřeby sjednotit mnoho lispových dialektů do
jediného, společného jazyka. Přibližně před patnácti lety došlo
k jeho stabilizaci, která byla završena roku 1994 schválením ANSI
standardu jazyka. Standard dostál svému cíli definovat stabilní jazyk, platí
bez jediné změny dodnes a ani v budoucích letech v něm nelze očekávat
žádné změny, možná jsou pouze budoucí rozšíření.
Díky stabilitě standardu jsou standardu odpovídající programy v Common
Lispu i po mnoha letech použitelné, na rozdíl od některých jiných
populárních programovacích jazyků, kde je definice jazyka stále ještě ve vývoji
a neustále se mění. Z toho vyplývají první dvě důležité optimalizace.
Optimalizace: Co jednou v Common Lispu napíšete
v souladu se standardem jazyka, nemusíte znovu přepisovat.
Optimalizace: Kód odpovídající standardu jazyka můžete
zkompilovat libovolným překladačem standard splňujícím. Můžete si tedy ke
svému kódu vybrat překladač dle aktuální potřeby.
Interpretovaný nebo kompilovaný?
Jednou z častých pověr týkajících se Lispu je, že se jedná
o "interpretovaný" a tudíž pomalý jazyk. Skutečnost je taková, že pojem
"interpretovaný" je jednak poněkud nejasný (je tím myšlena interpretace
zdrojového textu nebo interpretace byte kódu?) a jednak, že u málokterého
jazyka je v jeho definici stanoveno, co se má interpretovat a co se
interpretovat nesmí. V případě Common Lispu, stejně jako třeba
u jazyka C, nic takového obecně stanoveno není. Některé lispové
překladače překládají kód do strojových instrukcí, některé do byte kódu a
u některých si můžete způsob překladu vybrat. Interpret zdrojového kódu
mi není znám.
Optimalizace: Potřebujete-li, aby výsledný kód běžel co
nejrychleji, necháte jej přeložit do strojového kódu. Potřebujete-li, aby kód
byl co nejmenší, necháte jej přeložit do byte kódu.
Někteří programátoři se domnívají, že kvůli dynamickému charakteru lispových
definic, umožňujících předefinování funkcí za běhu, je nutné, aby Lisp byl
pomalý. Skutečnost je v případě Common Lispu taková, že:
-
Naprostá většina posixových programů využívá knihovnu libc, která
u svých exportovaných funkcí umožňuje, prostřednictvím obalovacích
knihoven, přesně totéž. V souvislosti s tímto faktem jsem
stížnosti na pomalost libc dosud neslyšel.
-
Standardní funkce jazyka (kterých je několik set) předefinovány být nesmí.
Takové funkce tedy může překladač zpracovávat zcela libovolným způsobem,
dokonce nemusí docházet na příslušným místě ke skutečnému volání funkce, což
umožňuje vyšší míru manipulace s kódem a tím pádem i potenciálně
kvalitnější optimalizace.
-
Ne vždy se předefinování funkce v Common Lispu projeví, neprojeví se
u inlinovaných funkcí.
Každopádně možnost dynamického předefinování funkcí je velmi důležitá
optimalizace práce programátora. Nemusíte kvůli změně jednoho volání
v programu překládat celý programový celek znovu, stačí v editoru
zavolat příkaz předání nové definice změněné funkce překladači.
Optimalizace: Překlad do strojového kódu obvykle nic nemění na
interaktivitě prostředí. I překladače, které generují pouze strojový kód,
fungují za normálních okolností plně dynamicky a interaktivně.
Typování
Common Lisp je obecně jazykem s dynamickým typováním, tj. každá proměnná
může obecně nabývat hodnoty libovolného typu a informace o typu je
součástí hodnoty proměnné. Ve skutečnosti tomu ovšem takto vždy být nemusí,
a to ze dvou důvodů:
-
Typ proměnné nebo funkce je deklarován programátorem ve zdrojovém kódu.
-
Typ lokální proměnné je možné určit z kontextu.
Občasné deklarace typů ve spolupráci s automatickým odvozováním typů
lokálních proměnných překladačem je velmi mocný optimalizační prostředek.
Rychlost kódu je typicky ovlivněna cykly, tj. lokálními částmi kódu. Lze-li
v takových místech odvodit typy proměnných automaticky nebo
s částečnou asistencí programátora, dochází ke skloubení výhod dynamicky a
staticky typovaných jazyků.
Optimalizace: Programátor uvádí typy proměnných jen
v místech, kde je potřeba překladači napovědět nebo kde mu záleží na
kontrole dat (assertions). Kde je to možné, tam si překladač může odvodit typ
sám a tudíž automaticky generovat efektivní kód. Kvalitně optimalizující
překladač přitom dokáže upozornit na místa, kde mu informace o typu chybí.
Tím se ušetří práce programátora oproti jazykům s povinným typováním (jako
je C, C++ nebo Java, kde je zbytečně nutné uvádět informaci o typu skoro
všude) a přitom lze generovat efektivnější kód než v případě jazyků
s výhradně dynamickým typováním (jako je Perl nebo Python).
Schopností automatického typování ovšem nedisponuje každý překladač. Překladač
dokonce smí veškeré typové deklarace, stejně jako většinu ostatních
deklarací, kompletně ignorovat. Cílem standardu je definovat
přenositelný jazyk, avšak bez kladení zbytečných nároků na své implementace.
Nejen proto je třeba Common Lisp nezaměňovat se silně typovanými jazyky,
a to i přesto, že občas poskytuje lepší typovou kontrolu než jazyky,
u nichž je silné typování zdůrazňováno. Kladete-li důraz na bezpečnost
typování, musíte použít některý ze skutečných silně typovaných jazyků, jako je
například Ada nebo Mercury.
Garbage collection
Garbage collection je přímo legendárním pojmem v debatách o rychlosti
běhu kódu. Ještě před nedávnem bylo její používání častým námětem připomínek
na adresu "pomalosti kódu", povětšinou nepodložených ničím jiným než naprostou
neznalostí problematiky.
Předně je potřeba si uvědomit, že nikomu nic nebrání programovat v Common
Lispu stejným způsobem jako v jazyce C. Tj. alokovat si jeden velký úsek
paměti a "ručně" provádět jeho správu. Pak je práce garbage collectoru nulová
a žádné zpomalení tudíž nemůže působit. Využití garbage collection je tedy
volitelné.
Pro použití garbage collection existují v zásadě dva důvody:
-
Chcete si ušetřit spoustu programátorské práce související s ruční
správou paměti.
-
Dobrý garbage collector může fungovat efektivněji než ruční správa paměti
napsaná programátorem, který problematice správy paměti dostatečně dobře a do
hloubky nerozumí. Uvolňování bloků paměti při garbage collection může být
například prováděno v jednom větším kroku místo několika malých a může
mít lepší lokalitu.
Využití garbage collectoru obvykle vede jednak k velké úspoře
programátorské práce už při psaní samotného kódu, a jednak
k zefektivnění výsledného kódu. Postupy provádění
garbage collection jsou dnes mnohem rafinovanější než byly v začátcích
používání této techniky a až na výjimečné situace je časová režie garbage
collectoru víceméně zanedbatelná. Hůře je na tom garbage collection
s pamětí, protože na rozdíl od okamžité dealokace dat se v paměti
skoro vždy nachází nějaké to smetí, až do chvíle příštího sběru. To je však
vyváženo tím, že v případě systémů s rozumným garbage collectorem je
pojem "memory leak" záležitostí známou jen z doslechu od cizinců. Stejně
tak se vám nemůže stát, že se něco bude v automaticky spravované oblasti
paměti odkazovat na již uvolněná data, s dobře známými následky. Pokud by
pak kvůli garbage collection mělo dojít ke skutečným výkonnostním problémům,
což se teoreticky může stát, pracuje-li program s velkým množstvím
datových objektů silně dynamického charakteru, je možno zabránit přítomnosti
přílišného množství smetí umístěním kritické části dat do ručně spravovaného
pole.
Optimalizace: Garbage collection ušetří spoustu programátorské
práce. Ušetřené prostředky lze mimo jiné využít na optimalizaci použitých
algoritmů a technik, povětšinou vedoucích k optimalizacím programu
účinnějších než veškeré optimalizační metody běžných překladačů.
Optimalizace: V mnoha programech garbage collection omezí
spotřebu paměti programu na konkrétní limit, na rozdíl od programátorských
prostředí umožňujících úniky paměti (pamatujete si ještě na starší verze
Netscape?).
Samozřejmě je nutné mít na paměti, že nic není odolné proti dostatečně hloupým
postupům a chybám. Ani garbage collection nezamezí ničím neomezenému
růstu zásobníku, do kterého se jen přidává a nic se z něj neodebírá.
Nastavení preferencí optimalizace
Některé optimalizace jdou proti sobě. Často máte například na výběr mezi
zvýšením rychlosti prováděného kódu a zmenšením jeho velikosti, nemůžete mít
obojí, typicky při expanzi cyklů (loop unrolling). Zatímco u mnoha
překladačů máte na výběr mezi prostým "optimalizovat" nebo "neoptimalizovat" či
mezi několika sekvenčně vzrůstajícími stupni optimalizace, Common Lisp umožňuje
volný výběr z několika parametrů. Deklarace optimalizace jsou přitom opět
součástí standardu jazyka, nikoliv jen stanoveny nějakým konkrétním
překladačem.
Standard Common Lispu definuje pět parametrů ovlivňujících výslednou
optimalizaci kódu: speed, space, safety,
debug, compilation-speed. Každému z těchto
parametrů lze přiřadit jeden ze čtyř stupňů důležitosti, přičemž standard
nestanovuje jejich přesnou interpretaci, ta závisí čistě na konkrétním
překladači (může je i zcela ignorovat).
Parametry speed a space umožňují preferovat rychlost
a velikost výsledného kódu. Například při nízké hodnotě speed a
vysoké hodnotě space může překladač generovat byte kód, zatímco
v opačném případě strojový kód. Nebo může vzájemná hodnota těchto
parametrů určovat, do jaké míry se má provádět expanze cyklů.
Parametr safety říká, nakolik má být generovaný kód zabezpečený
proti běžným programátorským chybám, jako je například překročení hranic pole
nebo přiřazení hodnoty do proměnné s odlišným deklarovaným typem.
U většiny překladačů jiných programovacích jazyků nemáte na výběr a musíte
se smířit buď se vždy přítomnou (kód zpomalující a zvětšující) kontrolou, nebo
naopak s tím, že není prováděna žádná kontrola, nebo s kontrolou přítomnou
v případě použití externích nástrojů. V Common Lispu si stačí jen
nastavit příslušnou optimalizaci.
Konečně parametr debug definuje, jaké mají být v kódu
ponechány ladící informace, a parametr compilation-speed
určuje, jak moc vám záleží na rychlosti kompilace.
Optimalizace: Optimalizaci lze optimalizovat s ohledem na
konkrétní potřeby programu.
Velmi zajímavou vlastností těchto parametrů, jinde málokdy viděnou, je možnost
definovat je nejen na úrovni celého překladu nebo celého zdrojového souboru,
nýbrž i na úrovni jednotlivé funkce nebo bloku funkce. Máte-li tedy
v programu jediné místo kritické z hlediska rychlosti, nastavíte mu
po odladění parametr speed na nejvyšší hodnotu a ostatní parametry
na hodnoty nejnižší, aniž by to ovlivnilo optimalizace kteréhokoliv
jiného kódu.
Optimalizace: Optimalizaci lze optimalizovat přesně
v místech, kde je to žádoucí.
Common lispový program také jen málokdy specifikuje úroveň optimalizace pro
program jako celek přímo. To je ponecháno na uživateli, který si může veškeré
výše uvedené optimalizační parametry před překladem nastavit dle svého gusta.
Nemusí kvůli tomu editovat žádné zdrojové texty ani žádné makefile.
Optimalizace: Optimalizaci si uživatel může optimalizovat
s ohledem na své potřeby.
Pro úplnost dodejme, že mezi optimalizační parametry podobného druhu patří
ještě možnost zažádat si o inlinování konkrétní funkce, což je technika
dobře známá například v případě C++. Již méně obvyklou je možnost zažádat
si naopak o neinlinování konkrétní funkce.
Překlad kódu
U staticky překládaných jazyků lze kód překládat jen v podobě
zdrojového souboru a k překladu musí dojít za normálních okolností ještě
před spuštěním výsledného programu. Dynamické jazyky k tomu přidávají
konstrukce load a eval, umožňující
vyhodnocení kódu programovacího jazyka za běhu. Common Lisp
kromě toho nabízí ještě dva další důležité mechanismy: Překladová makra a
kompilaci za běhu.
Překladová makra (compiler macros) jsou makra expandovaná jen v době
překladu. Jedná se o rozšíření mechanismu maker, spočívající
v zastínění jména funkce nebo makra v určité fázi překladu. Tento
prostředek umožňuje provádět nad kódem "vnější" transformace, bez zásahu do
samotného kódu. Využití se nabízí například pro optimalizaci některých
aritmetických konstrukcí v programech provádějících numerické výpočty.
Optimalizace: V některých situacích lze pomocí
překladových maker automaticky optimalizovat konstrukce, které překladač neumí
optimalizovat sám.
Kompilace za běhu spočívá v možnosti zkompilovat během provádění programu
libovolnou, třeba až v daném okamžiku dynamicky zkonstruovanou funkci.
Programátor tak získává možnost ve svém programu dynamicky generovat kód ve
stejné kvalitě jako statický kód, a to bez nutnosti používání dočasných
souborů (jako je tomu v případě postupu
define--save--compile-file--load).
Jako typické smysluplné využití této možnosti se nabízí zpracování uživatelem
zadávaných regulárních výrazů -- pro každý regulární výraz můžete vytvořit plně
optimalizovaný program provádějící jeho porovnávání, místo obvyklé interpretace
byte kódu zpracovaného regulárního výrazu.
Optimalizace: Překlad kódu dynamicky vytvořeného za běhu
programu je stejně kvalitní jako překlad statického kódu.
Jsou programy v Common Lispu rychlé nebo pomalé?
Common Lisp disponuje celou řadou optimalizačních prostředků. V článku
bylo uvedeno několik optimalizací, které v jiných prostředích běžně
nenalezneme. Po stránce vlastností jazyka má Common Lisp díky vyšší abstrakci
jazyka a uvedeným rysům předpoklady generovat efektivnější kód než jazyky nižší
úrovně, jako je například C.
Praktická zkušenost se svobodnými common lispovými překladači ukazuje, že
rychlost provádění programů zkompilovaných do strojového kódu je o něco
nižší, než provádění analogického kódu zkompilovaného gcc (které asi lze
považovat za jeden z nejlépe optimalizujících svobodných překladačů). Důvodem
je to, že v případě gcc je low-level optimalizacím výsledného kódu
věnováno mnohonásobně větší než v případě svobodných common lispových
překladačů. Rozdíl však není příliš dramatický a praktickou roli hraje
především ve výpočetně náročných aplikacích. Záleží také hlavně na
aplikaci, aplikace využívající multimediálních instrukcí intelovských procesorů
budou určitě rychlejší, bude-li je překládat gcc, aplikace dynamického
charakteru s vysokou úrovní abstrakce kódu zase mohou běžet rychleji při
použití Common Lispu.
V případě dynamických jazyků, jako je třeba Python nebo Perl, se často
argumentuje, že na rychlosti kódu nezáleží, protože časově kritické části,
kterých v kódu nebývá mnoho, lze napsat jako moduly v jazyce C
(stejný přístup používá populární common lispový překladač Clisp). Tento
argument je v zásadě správný, naráží však na určitý praktický problém, že
se u komplikovanějších systémů stává programování v C nezbytností, se
všemi důsledky z toho plynoucími. Těmi jsou zejména složitý kód,
nedostupnost některých rysů jazyka pro takový kód, jeho nestabilita
(segmentation fault v Pythonu může programátora přivádět do stavu blízkého
zoufalství) a nemožnost ladění s pomocí mocných nástrojů pro daný jazyk
dostupných. Proto bývá občas výhodnější místo investice do přepisování kódu do
C raději investovat do silnějšího hardwaru. V případě kvalitního
překladu, který je podmíněn dostatečnými optimalizačními rysy jazyka,
nemusíte investovat ani do dodatečné programátorské práce ani do hardwaru,
výsledný kód je sám o sobě dostatečně dobrý. I v Common Lispu
se občas využívají knihovny v C, nikoliv ovšem z důvodu potřeby vyšší
rychlosti běhu kódu, nýbrž prostě z důvodu využití stávajícího knihovny
bez nutnosti psaní její lispové varianty, smíří-li se programátor s výše
uvedenými nedostatky implikovanými takovým postupem.
Odkazy
| 
Reklama
Anketa
