Programovací jazyk Clojure 18: základní techniky optimalizace aplikací

Obsah

1. Programovací jazyk Clojure 18: základní techniky optimalizace aplikací

2. Referenčně transparentní funkce a jejich význam při optimalizaci aplikací

3. Využití funkce memoize pro úschovu a další použití již vypočtených návratových hodnot funkcí

4. Praktický příklad použití funkce memoize

5. Volba vhodných kolekcí při implementaci složitějších datových typů

6. Seznamy vs. vektory

7. Implementace seznamů v programovacím jazyku Clojure

8. Implementace vektorů v programovacím jazyku Clojure

9. Odkazy na Internetu

1. Programovací jazyk Clojure 18: základní techniky optimalizace aplikací

„First make it right. Then make it fast“

V předchozích částech seriálu o Javě i o virtuálním stroji Javy (JVM) jsme se při popisu programovacího jazyka Clojure zabývali především tím, jak se v tomto jazyku používají jednotlivé technologie, které Clojure vývojářům nabízí. Popsali jsme si především způsob práce se symboly a hodnotami navázanými na tyto symboly, vytváření nových funkcí včetně funkcí anonymních, použití neměnných (immutable) kolekcí, použití sekvencí a samozřejmě taktéž lazy sekvencí, způsoby spouštění funkcí v samostatných vláknech, použití transakcí ve vícevláknových programech, navázání symbolů na takzvané validátory, kooperaci mezi programovacími jazyky Clojure a Java a v neposlední řadě jsme se taktéž zabývali makrosystémem programovacího jazyka Clojure. Ovšem prozatím jsme si řekli jen velmi málo informací o tom, jak je možné aplikace vytvářené v Clojure optimalizovat, a to jak s ohledem na rychlost výsledných aplikací (popř.&nbsb;na dobu odezvy) i s ohledem na paměťovou náročnost.

To, že se touto poměrně důležitou záležitostí zabýváme až v osmnácté části našeho povídání o programovacím jazyce Clojure je ve skutečnosti záměr, protože některé optimalizace je (především u velkých aplikací) možné a vhodné provádět až ve chvíli, kdy je aplikace z velké části funkční a kdy se na reálných datech ukáže, kde jsou ve skutečnosti největší problémy způsobující například pomalý běh aplikace, její pomalé odezvy či její velkou paměťovou náročnost. Čistě teoreticky by mělo být možné tato místa objevit již v době analýzy, ovšem poměrně velká část aplikací prochází redesignem až v době vývoje (zákazník například potřebuje do aplikace přidat další funkce, které změní strukturu databáze, což se v lepším případě projeví jen ve změně hierarchie tříd/funkcí, v horším případě pak v nutnosti vertikálně či horizontálně rozdělit databázi atd. atd.). Pokud se však větší část aplikace vytváří v programovacím jazyku Clojure, je možné se zpočátku soustředit na implementaci vlastních algoritmů, zaměřit se na správné použití funkcionálních technik (tím si programátor otevírá cestu k možnosti relativně snadno zvýšit výkonnost aplikace) a teprve posléze se zabývat optimalizací na nižších úrovních.

2. Referenčně transparentní funkce a jejich význam při optimalizaci aplikací

Již v úvodních článcích o programovacím jazyce Clojure jsme si řekli, že tento jazyk patří, společně s klasickým LISPem, Scheme, Haskellem či Erlangem do skupiny (ne vždy nutně čistě) funkcionálních jazyků, tj. programovacích jazyků vycházejících z teorie takzvaného λ-kalkulu, jehož autorem je Alonzo Church (na první návrhy LISPu se dokonce můžeme dívat jako na jeden z formalizovaných způsobů zápisu λ-kalkulu, pro nějž jen tak mimochodem existuje mechanismus vyhodnocování jednotlivých λ výrazů; taktéž se tím vysvětluje přítomnost znaku lambda v logu jazyka Clojure). Ve skutečnosti sice Clojure není čistě funkcionálním jazykem, ovšem v případě, že vývojář bude při tvorbě svých aplikací dodržovat zásady funkcionálního programování, bude pro něj mnohem snadnější vytvářet skutečně výkonné aplikace; ať se to již týká snadnější tvorby bezpečných vícevláknových aplikací či možnosti použití funkce memoize popsané v následující kapitole.

Připomeňme si, že v programovacím jazyce Clojure jsou funkce považovány za plnohodnotné datové typy, což znamená, že funkce lze navázat na libovolný symbol (a tím vlastně původně anonymní funkci pojmenovat), funkce lze předávat jako parametry do jiných funkcí a funkce mohou být taktéž návratovou hodnotou jiných funkcí – funkce tedy může vytvořit a vrátit jinou funkci. Clojure taktéž podporuje práci s uzávěry (closure(s)), tj. funkcí svázaných s nějakým symbolem vytvořeným vně funkce. Podpora uzávěrů umožňuje například tvorbu funkcí sdílejících společný kontext (GUI) atd. Ovšem vzhledem k tomu, že – jak již víme – Clojure není čistě funkcionálním jazykem, je možné při vytváření uživatelských funkcí přímo z dané funkce přistupovat k nějakému globálnímu symbolu, přesněji řečeno k symbolu „globálnímu“ v rámci nějakého jmenného prostoru. Taktéž lze vytvářet funkce s vedlejším efektem, které například zapisují data do souborů, mění hodnotu navázanou na globální symboly atd.

Vývojáři by však neměli tyto možnosti nabízené programovacím jazykem Clojure zneužívat, protože tím znemožňují využití některých optimalizačních technik a v neposlední řadě si taktéž komplikují možnost testování takto vytvořených funkcí. Namísto toho se ukazuje být velmi výhodné vytvářet takzvané referenčně transparentní funkce, což jsou funkce, které nepřistupují k žádným globálním symbolům, nemají žádný vedlejší efekt ani si nepamatují žádný vnitřní stav (příkladem „funkce“ s vnitřním stavem je například Math/random). Referenčně transparentní funkci jsou při jejím volání předány parametry a funkce pouze na základě hodnot předaných parametrů vrátí nějaký výsledek. Tato (pochopitelná) vlastnost má jeden důležitý důsledek – chování referenčně transparentní funkce je nezávislé na stavu aplikace a je taktéž zcela nezávislé na tom, kdy je funkce zavolána.

3. Využití funkce memoize pro úschovu a další použití již vypočtených návratových hodnot funkcí

Chování referenčně transparentní funkce je v čase neměnné a navíc platí, že pokud se funkce volá se stejnými parametry, vždy pro tyto parametry vrátí stejnou návratovou hodnotu. Díky tomu, že chování funkce je izolované od zbytku aplikace, nemusí se při jejím volání používat žádná synchronizace s ostatními vlákny (není ostatně bez zajímavosti, že výše zmíněná „funkce“ Math/random interně používá synchronizaci – zámky). V předchozí kapitole jsme si řekli, že návratová hodnota referenčně transparentní funkce je závislá pouze na hodnotě parametrů předaných této funkci, což mj. znamená, že je možné volání funkce nahradit konstantou, která byla někdy v minulosti volanou funkcí vrácena pro zadané parametry. Teoreticky je tedy možné vytvořit tabulku (či spíše mapu), která pro zadané parametry vrátí stejnou hodnotu, jaká by se vrátila při volání zvolené funkce. Jak je však možné tuto teoretickou vlastnost použít v praxi? Ve skutečnosti to není nijak obtížné, protože můžeme využít funkci memoize, která je součástí standardní knihovny programovacího jazyka Clojure.

Zajímavé je, že funkce memoize je implementována velmi jednoduše, což jen ukazuje, jak flexibilní programovací jazyk Clojure může být:

(defn memoize
    "Returns a memoized version of a referentially transparent function. The
    memoized version of the function keeps a cache of the mapping from arguments
    to results and, when calls with the same arguments are repeated often, has
    higher performance at the expense of higher memory use."
    {:added "1.0"
     :static true}
    [f]
    (let [mem (atom {})]
        (fn [& args]
            (if-let [e (find @mem args)]
                (val e)
                (let [ret (apply f args)]
                    (swap! mem assoc args ret)
                    ret)))))

Ve funkci memoize, které se v parametru f předává libovolná referenčně transparentní funkce (ve skutečnosti zcela libovolná funkce – žádná kontrola se neprovádí!), je interně použita mapa navázaná na symbol mem, do níž se jako klíče ukládají parametry volané funkce a jako příslušné hodnoty pak návratové hodnoty zavolané funkce. Dvojice klíč-hodnota mapy mem se postupně rozšiřují a vytváří se tak cache pro danou funkci. V případě, že se při „volání“ funkce f v mapě nalezne klíč odpovídající předávaným parametrům, vrátí se přímo hodnota uložená v mapě pomocí (val e), v opačném případě se funkce zavolá (forma apply f args) a její návratová hodnota se uloží do mapy mem (swap! …). Použití memoize má pouze tři nedostatky: interní mapu mem není možné při běhu aplikace smazat, neprovádí se žádné kontroly na to, zda je předávaná funkce skutečně referenčně transparentní a mapa s uloženými výsledky není automaticky serializována/deserializována při restartu aplikace – proto se při restartu začne vytvářet znovu (serializovanou mapu by navíc bylo možné použít v testech).

Povšimněte si, co je výsledkem volání funkce memoize – je jím anonymní funkce (přesněji řečeno uzávěr), kterou lze přiřadit k symbolu pomocí def/defn.

4. Praktický příklad použití funkce memoize

Ukažme si nyní, jak je možné v praxi využít funkci memoize popsanou v předchozí kapitole. V jedné z předcházejících částí tohoto seriálu byla jako demonstrační příklad použita rychlá varianta funkce pro výpočet faktoriálu. O rychlou variantu se jednalo z toho důvodu, že v ní nebyla použita rekurze (přesněji řečeno tail rekurze), ale namísto toho se jednoduše aplikovala funkce * (násobení) na sekvenci hodnot 1..n. Mírně upravená rychlá podoba funkce fact je vypsána pod tímto odstavcem. Úprava oproti tvaru funkce použité v předchozích článcích spočívá v použití konstanty 1M při volání funkce range, čímž docílíme toho, že se při vlastním výpočtu namísto hodnot typu long (rozsah 64 bitů) budou používat instance třídy java.math.BigDecimal, čímž se rozšíří rozsah výsledných hodnot:

; rychlý výpočet faktoriálu
(defn fact
    [n]
    (apply *
        (range 1M (inc n))))

Výpočet faktoriálu je sice skutečně relativně rychlý, ovšem v případě, že budeme tuto funkci volat stále se stejným parametrem, bude se výpočet neustále opakovat. To se již může negativně projevit na výsledném výkonu aplikace, zejména tehdy, pokud se bude počítat faktoriál velkého čísla n, což v dané implementaci vyžaduje n násobení, které není v případě java.math.BigDecimal rychlou operací. Ostatně se o tom můžeme jednoduše přesvědčit sami:

user=> (dotimes [i 10] (time (fact 10000)))
"Elapsed time: 1351.005784 msecs"
"Elapsed time: 1308.91524 msecs"
"Elapsed time: 1307.073668 msecs"
"Elapsed time: 1367.755396 msecs"
"Elapsed time: 1516.798644 msecs"
"Elapsed time: 1357.112148 msecs"
"Elapsed time: 1343.379676 msecs"
"Elapsed time: 1397.393524 msecs"
"Elapsed time: 1319.43194 msecs"
"Elapsed time: 1311.928468 msecs"
nil
 
user=>

Každý výpočet trval přibližně 1,3 sekundy, nezávisle na tom, že jsme volali referenčně transparentní funkci se stále stejným parametrem. Pokud však využijeme funkci memoize, bude vše vypadat zcela jinak:

; rychlý výpočet faktoriálu se zapamatováním výsledku výpočtu
(def fact2
    (memoize (
        fn [n]
        (apply *
            (range 1M (inc n))))))

Předchozí zápis znamená vytvoření nového symbolu se jménem fact2 navázaného na výsledek funkce memoize, které se předala anonymní funkce pro výpočet faktoriálu (vlastní zápis výpočtu se vůbec nezměnil). Při každém volání fact2 se zkontroluje, zda již pro předávaný parametr neexistuje výsledek a ten se případně použije. Časy běhu funkce fact2 pro stejný parametr pak budou diametrálně odlišné:

user=> (dotimes [i 10] (time (fact2 10000)))
"Elapsed time: 1320.770096 msecs"
"Elapsed time: 0.022908 msecs"
"Elapsed time: 0.013688 msecs"
"Elapsed time: 0.013692 msecs"
"Elapsed time: 0.013688 msecs"
"Elapsed time: 0.013408 msecs"
"Elapsed time: 0.013412 msecs"
"Elapsed time: 0.013412 msecs"
"Elapsed time: 0.013132 msecs"
"Elapsed time: 0.013968 msecs"
nil
 
user=>

Vidíme, že výpočet proběhl pouze jednou a posléze se již prakticky ihned vracel výsledek uložený ve vyrovnávací paměti (mapě)! Jedná se tedy o klasický typ optimalizace, v níž se programátor rozhoduje mezi dobou běhu a nároky na operační paměť.

5. Volba vhodných kolekcí při implementaci složitějších datových typů

Kromě snahy o použití referenčně transparentních funkcí může programátor dosti podstatným způsobem ovlivnit výkonnost aplikace taktéž volbou vhodných typů kolekcí, s jejichž využitím se vytváří složitější datové struktury – stromy, grafy atd. Připomeňme si, že programovací jazyk Clojure podporuje čtyři typy kolekcí. Ve všech případech se jedná o neměnitelné (immutable) kolekce, jejichž obsah není možné měnit – nelze do nich tedy přidávat další prvky, ubírat prvky ani měnit hodnotu prvků. Ve standardní knihovně ovšem existuje velké množství funkcí, které vezmou kolekci jako svůj vstupní parametr a vrátí kolekci jinou, například původní kolekci s přidaným novým prvkem atd. (původní kolekce však zůstane nezměněna). Všechny čtyři typy kolekcí jsou i se svými konstruktory vypsány v následující tabulce:

Při volbě vhodné kolekce, která má tvořit základ datové struktury, se vývojář může orientovat i podle toho, jaké rozhraní (ve smyslu programovacího jazyka Java) jednotlivé kolekce implementují. Tím jsou určeny základní vlastnosti každé kolekce:

Programátoři většinou nemívají problém s rozhodnutím, zda se má použít seznam/vektor na jedné straně či mapa na straně druhé – pokud se má při přístupu k prvkům použít neceločíselný klíč, je většinou na místě použít mapu. Ovšem poněkud horší situaci má vývojář při rozhodování, pro které datové struktury má využít seznam (list) a kde naopak vektor (vector). To je i téma následující kapitoly.

Odkazy na související články:

1. Clojure Data Structures
   http://clojure.org/data_structures
2. The Structure and Interpretation of Computer Programs: 2.2.1 Representing Sequences
   http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html#%_sec₂.2.1
3. The Structure and Interpretation of Computer Programs: 3.3.1 Mutable List Structure
   http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-22.html#%_sec₃.3.1

6. Seznamy vs. vektory

Programovací jazyk LISP, z něhož je Clojure ve velké míře odvozen, byl původně založen prakticky pouze na použití seznamů, které se využívaly jak pro ukládání dat, tak i pro reprezentaci vlastního programu, protože program (jeho funkce) lze reprezentovat jako seznam seznamů. Nejinak je tomu i v programovacím jazyce Clojure, jenž však kromě seznamů poměrně intenzivně používá i vektory (například parametry funkce se zapisují do vektorů atd.), což musí mít svoje opodstatnění. Seznamy a vektory se totiž od sebe odlišují především svojí vnitřní strukturou, z níž přímo vyplývají i operace, které lze s těmito kolekcemi provádět a v neposlední řadě i složitost jednotlivých operací, která nás dnes taktéž zajímá.

Jeden z rozdílů mezi oběma kolekcemi spočívá v tom, že prvky vektorů je možné číst jako přímou sekvenci i jako sekvenci otočenou (od posledního prvku k prvku prvnímu). Nad vektorem lze tedy zavolat funkci seq i rseq, zatímco u seznamů pouze funkci seq – prvky lze číst pouze od začátku seznamu do konce. Další rozdíl mezi seznamy a vektory spočívá v odlišném chování funkce conj, kterou lze použít k vytvoření kopie původní kolekce doplněné o nové prvky. U seznamů se prvky přidávají na jeho začátek, zatímco u vektorů je tomu přesně naopak – vrácen je nový vektor s prvky přidanými na jeho konci. Podobně se liší chování funkcí pop a peek. Shrňme si nyní jednotlivé funkční rozdíly mezi seznamy a vektory přehledně do tabulky:

Důležité je při optimalizaci aplikací i porovnání výpočetní složitosti některých funkcí z předchozí tabulky, protože právě odlišná složitost může výrazným způsobem ovlivnit výkonnost celé aplikace, zejména tehdy, pokud se budou používat kolekce s velkým množstvím prvků. Zajímavé je, že funkce count má v obou případech konstantní složitost: O(1). To znamená, že v Clojure nemá smysl počítat počet prvků seznamu s využitím rekurzivní funkce, což je jeden z oblíbených školních příkladů používaných při výuce LISPu :-) Naproti tomu funkce nth se sice u obou typů kolekcí chová stejně, má však výrazně odlišnou složitost: O(n) v případě seznamů (lineární složitost) a O(log₃₂N) v případě vektorů (logaritmická složitost). U krátkých vektorů (do 32 prvků) je složitost konstantní a i u delších vektorů je počet kroků nutných pro získání n-tého prvku velmi malý (například dva kroky pro vektory o délce přibližně 1000 prvků atd.). Složitost funkce peek je v případě vektoru taktéž rovna O(log₃₂N), na rozdíl od funkce last se složitostí O(N) – v případě vektorů tedy vždy používejte peek!

Povšimněte si, že vektory ve skutečnosti neodpovídají složitostí některých funkcí běžně chápaným vektorům-jednorozměrným polím. Je tomu tak z toho důvodu, že v Clojure jsou vektory implementovány odlišným způsobem a to zejména proto, aby bylo možné jednoduše implementovat funkci conj, tj. aby se již vytvořená datová struktura mohla sdílet mezi větším množstvím vektorů (to je možné i díky jejich neměnnosti), Proč se od sebe seznamy a vektory tak diametrálně odlišují, si řekneme v následujících dvou kapitolách.

7. Implementace seznamů v programovacím jazyku Clojure

Programovací jazyk LISP, který je ideovým předchůdcem jazyka Clojure, byl původně založen prakticky pouze na použití seznamů, které byly považovány za zcela univerzální datovou strukturu. V tradičních LISPech jsou seznamy implementované pomocí takzvaných tečka-dvojic (dot-pair), což jsou dvojice prvků, přičemž každý prvek buď může obsahovat nějakou hodnotu nebo obsahuje odkaz na další tečka-dvojici. Běžný seznam pak byl vytvořen jako jednosměrně vázaný lineární seznam složený z tečka-dvojic, kde první prvek ve dvojici obsahoval nějakou hodnotu a druhý prvek pak odkaz na prvek následující. U některých variant programovacího jazyka LISP se navíc obsah každého prvku v tečka dvojici rozděloval na takzvaný tag (řekněme zjednodušeně popis datového typu) a vlastní hodnotu, což bylo z hlediska obsazení operační paměti poměrně efektivní řešení. Pro přístup k prvkům seznamů se používaly dvě funkce pojmenované z historických důvodů car a cdr. Funkce car vracela první prvek seznamu a funkce cdr zbytek seznamu, tj. všechny prvky následující.

Vzhledem k tomu, že seznam byl implementován formou na sebe navazujících tečka dvojic, byla implementace obou funkcí car/cdr triviální a tyto funkce měly konstantní složitost. Naproti tomu funkce nth (přístup k n-tému prvku seznamu) měla složitost lineární: O(n). Podobně funkce zjišťující počet prvků seznamu count měla lineární složitost. V případě programovacího jazyka Clojure je situace poněkud odlišná od většiny dalších implementací LISPu. První odlišnost spočívá v tom, že prvky seznamu jsou typu java.lang.Object a jedná se tedy vždy o reference a nikoli přímo o hodnoty. Na celý seznam se tedy můžeme dívat jako na posloupnost referencí, interně je ovšem celý seznam tvořen rekurzivní strukturou složenou z prvního prvku a zbytku seznamu (jde tedy o obdobu tečka-dvojic) – právě tato vlastnost vede k tomu, že přidání dalších prvků na začátek seznamu pomocí funkce conj je výpočetně nenáročnou operací. Vlastní hodnoty jsou pak uloženy někde na haldě (heapu). Druhá odlišnost spočívá v tom, že každý seznam si pamatuje svoji délku, takže složitost funkce count je v jazyce Clojure konstantní.

Jen pro zajímavost se podívejme na část kódu s implementací seznamu:

public class PersistentList extends ASeq implements IPersistentList, IReduce, List, Counted {
 
    // první prvek seznamu
    private final Object _first;
    // další prvky seznamu
    private final IPersistentList _rest;
    // délka seznamu
    private final int _count;
 
// složitost O(1)
public Object first(){
    return _first;
}
 
// složitost O(1)
public ISeq next(){
    if(_count == 1)
        return null;
    return (ISeq) _rest;
}
// složitost O(n)
public Object get(int index){
    return RT.nth(this, index);
}

Volání funkce nth interně vede k volání následující metody:

static Object nthFrom(Object coll, int n){
    else if(coll instanceof Sequential) {
        ISeq seq = RT.seq(coll);
        coll = null;
        for(int i = 0; i <= n && seq != null; ++i, seq = seq.next()) {
            if(i == n)
                return seq.first();
        }
        throw new IndexOutOfBoundsException();

8. Implementace vektorů v programovacím jazyku Clojure

V programovacím jazyku Clojure se na mnoha místech seznamy nahrazují za vektory, protože práce s vektory může být více efektivní. Vektor můžeme považovat za jednorozměrné pole hodnot libovolných typů, takže by se mohlo zdát, že složitost přístupu k jeho prvkům bude konstantní O(N). Ve skutečnosti jsou však vektory interně implementovány poněkud složitějším (a velmi zajímavým) způsobem a to především z toho důvodu, aby bylo snadné k vektorům připojovat další prvky – tak vznikne nový vektor, ovšem původní vektor musí samozřejmě zůstat zachovaný. Proto se v Clojure (a v některých dalších moderních programovacích jazycích) používají pro implementaci vektorů takzvané RRB-Stromy (RRB-Trees, Relaxed Radix Balanced Trees). V Clojure jsou použity (vyvážené) RRB-stromy, které mají v každém listu uloženo jednorozměrné pole o délce 32 prvků. Pokud se pracuje s kratším vektorem, je pro jeho uložení použit strom pouze s jedním listem a tudíž je vektor skutečně reprezentován jednorozměrným polem (ve skutečnosti se vedle vlastního stromu používá ještě pomocné pole tail, pro jednoduchost však jeho roli v tomto textu poněkud zanedbáme).

U delších vektorů se v 32prvkovém poli uloženém v kořenu stromu nenachází přímo prvky vektoru, ale reference na další listy, z nichž každý opět obsahuje 32prvkové pole. To znamená, že vektor s až 1024 prvky může být uložen ve stromu o výšce 1, ve stromu o výšce 2 je celkový (možný) počet prvků vektoru roven 32768 (1024 listů á 32 prvků) atd. Operace vrácení n-tého prvku má tedy složitost O(log₃₂N), což sice není konstantní složitost O(1), ale pro vektory běžných délek můžeme tuto složitost taktéž považovat za konstantní. Předností vektorů je tedy rychlejší přístup k jeho prvkům, ale nesmíme zapomenout ani na paměťové nároky – vektory interně potřebují mnohem méně referencí, než je tomu u seznamů, tudíž i paměťové nároky budou nižší, a to zejména na 64bitových systémech; samozřejmě pokud zde uživatelé nepovolí použití komprimovaných ukazatelů (compressed oops).

Interní strukturu vektoru opět můžeme zjistit přímo ze zdrojových textů programovacího jazyka Clojure:

public class PersistentVector extends APersistentVector implements IObj, IEditableCollection{
    // délka vektoru
    final int cnt;
 
    // výška stromu
    final int shift;
 
    // kořen stromu
    final Node root;
 
    // až 32 posledních prvků vektoru je uloženo v tomto pomocném poli
    final Object[] tail;
 

Zajímavá je implementace funkce nth:

// získání i-tého prvku vektoru
public Object nth(int i){
    // uzel stromu, který obsahuje příslušný prvek
    Object[] node = arrayFor(i);
    // nyní nás zajímá pouze index 0..31
    return node[i & 0x01f];
}
 
// rekurzivní vyhledání příslušného listu
public Object[] arrayFor(int i){
    if(i >= 0 && i < cnt)
        {
        // prvek hledejme v pomocném poli tail
        if(i >= tailoff())
            return tail;
        Node node = root;
        // vlastní rekurzivní průchod stromem
        for(int level = shift; level > 0; level -= 5)
            node = (Node) node.array[(i >>> level) & 0x01f];
        return node.array;
        }
    throw new IndexOutOfBoundsException();
}
 
final int tailoff(){
    if(cnt < 32)
        return 0;
    return ((cnt - 1) >>> 5) << 5;
}

9. Odkazy na Internetu

1. SICP (The Structure and Interpretation of Computer Programs)
   http://mitpress.mit.edu/sicp/
2. Pure function
   http://en.wikipedia.org/wi­ki/Pure_function
3. Funkcionální programování
   http://cs.wikipedia.org/wi­ki/Funkcionální_programová­ní
4. Čistě funkcionální (datové struktury, jazyky, programování)
   http://cs.wikipedia.org/wi­ki/Čistě_funkcionální
5. Clojure Macro Tutorial (Part I, Getting the Compiler to Write Your Code For You)
   http://www.learningclojure­.com/2010/09/clojure-macro-tutorial-part-i-getting.html
6. Clojure Macro Tutorial (Part II: The Compiler Strikes Back)
   http://www.learningclojure­.com/2010/09/clojure-macro-tutorial-part-ii-compiler.html
7. Clojure Macro Tutorial (Part III: Syntax Quote)
   http://www.learningclojure­.com/2010/09/clojure-macro-tutorial-part-ii-syntax.html
8. Tech behind Tech: Clojure Macros Simplified
   http://techbehindtech.com/2010/09/28/clo­jure-macros-simplified/
9. Fatvat – Exploring functional programming: Clojure Macros
   http://www.fatvat.co.uk/2009/02/clo­jure-macros.html
10. Eulerovo číslo
    http://cs.wikipedia.org/wi­ki/Eulerovo_číslo
11. List comprehension
    http://en.wikipedia.org/wi­ki/List_comprehension
12. List Comprehensions in Clojure
    http://asymmetrical-view.com/2008/11/18/list-comprehensions-in-clojure.html
13. Clojure Programming Concepts: List Comprehension
    http://en.wikibooks.org/wi­ki/Clojure_Programming/Con­cepts#List_Comprehension
14. Clojure core API: for macro
    http://clojure.github.com/clo­jure/clojure.core-api.html#clojure.core/for
15. cirrus machina – The Clojure for macro
    http://www.cirrusmachina.com/blog/com­ment/the-clojure-for-macro/
16. Clojure.org: Clojure home page
    http://clojure.org/downloads
17. Clojure.org: Vars and the Global Environment
    http://clojure.org/Vars
18. Clojure.org: Refs and Transactions
    http://clojure.org/Refs
19. Clojure.org: Atoms
    http://clojure.org/Atoms
20. Clojure.org: Agents as Asynchronous Actions
    http://clojure.org/agents
21. A Couple of Clojure Agent Examples
    http://lethain.com/a-couple-of-clojure-agent-examples/
22. Clojure – Functional Programming for the JVM
    http://java.ociweb.com/mar­k/clojure/article.html
23. Clojure quick reference
    http://faustus.webatu.com/clj-quick-ref.html
24. 4Clojure
    http://www.4clojure.com/
25. ClojureDoc
    http://clojuredocs.org/
26. Clojure (Wikipedia EN)
    http://en.wikipedia.org/wiki/Clojure
27. Clojure (Wikipedia CS)
    http://cs.wikipedia.org/wiki/Clojure
28. Riastradh's Lisp Style Rules
    http://mumble.net/~campbe­ll/scheme/style.txt
29. Dynamic Languages Strike Back
    http://steve-yegge.blogspot.cz/2008/05/dynamic-languages-strike-back.html
30. Scripting: Higher Level Programming for the 21st Century
    http://www.tcl.tk/doc/scripting.html
31. Java Virtual Machine Support for Non-Java Languages
    http://docs.oracle.com/ja­vase/7/docs/technotes/gui­des/vm/multiple-language-support.html
32. New JDK 7 Feature: Support for Dynamically Typed Languages in the Java Virtual Machine
    http://java.sun.com/develo­per/technicalArticles/Dyn­TypeLang/
33. JSR 223: Scripting for the Java^TM Platform
    http://jcp.org/en/jsr/detail?id=223
34. JSR 292: Supporting Dynamically Typed Languages on the Java^TM Platform
    http://jcp.org/en/jsr/detail?id=292
35. Java 7: A complete invokedynamic example
    http://niklasschlimm.blog­spot.com/2012/02/java-7-complete-invokedynamic-example.html
36. InvokeDynamic: Actually Useful?
    http://blog.headius.com/2007/01/in­vokedynamic-actually-useful.html
37. A First Taste of InvokeDynamic
    http://blog.headius.com/2008/09/first-taste-of-invokedynamic.html
38. Java 6 try/finally compilation without jsr/ret
    http://cliffhacks.blogspot­.com/2008/02/java-6-tryfinally-compilation-without.html
39. An empirical study of Java bytecode programs
    http://www.mendeley.com/research/an-empirical-study-of-java-bytecode-programs/
40. Java quick guide: JVM Instruction Set (tabulka všech instrukcí JVM)
    http://www.mobilefish.com/tu­torials/java/java_quickgu­ide_jvm_instruction_set.html
41. The JVM Instruction Set
    http://mpdeboer.home.xs4a­ll.nl/scriptie/node14.html
42. Control Flow in the Java Virtual Machine
    http://www.artima.com/under­thehood/flowP.html
43. Root.cz: Využití komprimovaných ukazatelů na objekty v JVM
    http://www.root.cz/clanky/vyuziti-komprimovanych-ukazatelu-na-objekty-v-nbsp-jvm/
44. Root.cz: JamVM aneb alternativa k HotSpotu nejenom pro embedded zařízení a chytré telefony
    http://www.root.cz/clanky/jamvm-aneb-alternativa-k-hotspotu-nejenom-pro-embedded-zarizeni-tablety-a-chytre-telefony/
45. The Java^TM Virtual Machine Specification, Second Edition
    http://java.sun.com/docs/bo­oks/jvms/second_edition/html/VMSpec­TOC.doc.html
46. The class File Format
    http://java.sun.com/docs/bo­oks/jvms/second_edition/html/Clas­sFile.doc.html
47. javap – The Java Class File Disassembler
    http://docs.oracle.com/ja­vase/1.4.2/docs/tooldocs/win­dows/javap.html
48. javap-java-1.6.0-openjdk(1) – Linux man page
    http://linux.die.net/man/1/javap-java-1.6.0-openjdk
49. Using javap
    http://www.idevelopment.in­fo/data/Programming/java/mis­cellaneous_java/Using_javap­.html
50. Examine class files with the javap command
    http://www.techrepublic.com/ar­ticle/examine-class-files-with-the-javap-command/5815354
51. BCEL Home page
    http://commons.apache.org/bcel/
52. BCEL Manual
    http://commons.apache.org/bcel/ma­nual.html
53. Byte Code Engineering Library (Wikipedia)
    http://en.wikipedia.org/wiki/BCEL
54. Java programming dynamics, Part 7: Bytecode engineering with BCEL
    http://www.ibm.com/develo­perworks/java/library/j-dyn0414/
55. Bytecode Engineering
    http://book.chinaunix.net/spe­cial/ebook/Core_Java2_Volu­me2AF/0131118269/ch13lev1sec6­.html
56. BCEL Tutorial
    http://www.smfsupport.com/sup­port/java/bcel-tutorial!/
57. ASM Home page
    http://asm.ow2.org/
58. Seznam nástrojů využívajících projekt ASM
    http://asm.ow2.org/users.html
59. ObjectWeb ASM (Wikipedia)
    http://en.wikipedia.org/wi­ki/ObjectWeb_ASM
60. Java Bytecode BCEL vs ASM
    http://james.onegoodcooki­e.com/2005/10/26/java-bytecode-bcel-vs-asm/
61. Bytecode Outline plugin for Eclipse (screenshoty + info)
    http://asm.ow2.org/eclipse/index.html
62. aspectj (Eclipse)
    http://www.eclipse.org/aspectj/
63. Aspect-oriented programming (Wikipedia)
    http://en.wikipedia.org/wi­ki/Aspect_oriented_program­ming
64. AspectJ (Wikipedia)
    http://en.wikipedia.org/wiki/AspectJ
65. EMMA: a free Java code coverage tool
    http://emma.sourceforge.net/
66. Cobertura
    http://cobertura.sourceforge.net/
67. FindBugs
    http://findbugs.sourceforge.net/
68. GNU Classpath
    www.gnu.org/s/classpath/
69. Java VMs Compared
    http://bugblogger.com/java-vms-compared-160/
70. JSRs: Java Specification Requests – JSR 223: Scripting for the Java Platform
    http://www.jcp.org/en/jsr/de­tail?id=223
71. Scripting for the Java Platform
    http://java.sun.com/develo­per/technicalArticles/J2SE/Des­ktop/scripting/
72. Scripting for the Java Platform (Wikipedia)
    http://en.wikipedia.org/wi­ki/Scripting_for_the_Java_Plat­form
73. Java Community Process
    http://en.wikipedia.org/wi­ki/Java_Specification_Requ­est
74. Java HotSpot VM Options
    http://www.oracle.com/technet­work/java/javase/tech/vmop­tions-jsp-140102.html
75. Great Computer Language Shootout
    http://c2.com/cgi/wiki?Gre­atComputerLanguageShootout
76. Java performance
    http://en.wikipedia.org/wi­ki/Java_performance
77. Trying the prototype
    http://mail.openjdk.java.net/pi­permail/lambda-dev/2010-August/002179.html
78. Better closures (for Java)
    http://blogs.sun.com/jrose/en­try/better_closures
79. Lambdas in Java: An In-Depth Analysis
    http://www.infoq.com/articles/lambdas-java-analysis
80. Class ReflectiveOperationException
    http://download.java.net/jdk7/doc­s/api/java/lang/Reflective­OperationException.html
81. Scala Programming Language
    http://www.scala-lang.org/
82. Run Scala in Apache Tomcat in 10 minutes
    http://www.softwaresecret­weapons.com/jspwiki/run-scala-in-apache-tomcat-in-10-minutes
83. Fast Web Development With Scala
    http://chasethedevil.blog­spot.cz/2007/09/fast-web-development-with-scala.html
84. Top five scripting languages on the JVM
    http://www.infoworld.com/d/developer-world/top-five-scripting-languages-the-jvm-855
85. Proposal: Indexing access syntax for Lists and Maps
    http://mail.openjdk.java.net/pi­permail/coin-dev/2009-March/001108.html
86. Proposal: Elvis and Other Null-Safe Operators
    http://mail.openjdk.java.net/pi­permail/coin-dev/2009-March/000047.html
87. Java 7 : Oracle pushes a first version of closures
    http://www.baptiste-wicht.com/2010/05/oracle-pushes-a-first-version-of-closures/
88. Groovy: An agile dynamic language for the Java Platform
    http://groovy.codehaus.org/Operators
89. Better Strategies for Null Handling in Java
    http://www.slideshare.net/Step­han.Schmidt/better-strategies-for-null-handling-in-java
90. Control Flow in the Java Virtual Machine
    http://www.artima.com/under­thehood/flowP.html
91. Java Virtual Machine
    http://en.wikipedia.org/wi­ki/Java_virtual_machine
92. ==, .equals(), compareTo(), and compare()
    http://leepoint.net/notes-java/data/expressions/22com­pareobjects.html
93. New JDK7 features
    http://openjdk.java.net/pro­jects/jdk7/features/
94. Project Coin: Bringing it to a Close(able)
    http://blogs.sun.com/darcy/en­try/project_coin_bring_clo­se
95. CloseableFinder source code
    http://blogs.sun.com/darcy/re­source/ProjectCoin/Closea­bleFinder.java
96. Joe Darcy blog about JDK
    http://blogs.sun.com/darcy
97. Java 7 – more dynamics
    http://www.baptiste-wicht.com/2010/04/java-7-more-dynamics/
98. New JDK 7 Feature: Support for Dynamically Typed Languages in the Java Virtual Machine
    http://java.sun.com/develo­per/technicalArticles/Dyn­TypeLang/index.html