Generování kódu za běhu (ve Scale)

Někdy je zkrátka potřeba dynamicky generovat kód.

Důvodů pro to může být mnoha: Například můžu mít nějakou formu externího doménového jazyka (DSL), který musí běžet rychle, nebo musí být staticky integrován do zbytku programu bez použití reflexe1, nebo chci provést nějakou instrumentaci nebo statickou analýzu existujícího kódu. V některých případech to může být zbytečné, ale jindy je dynamické generování kódu ta správná věc.

A když říkám dynamické generování kódu, nemyslím během kompilace pomocí klasických maker, ale za běhu, na základě nějakých data, které v době kompilace nejsou a nemohou být známé. Pokud nemluvíme o makrech céčkovského typu, je mezi statickým a dynamickým generováním kódu jen pramalý rozdíl. Oba potřebují kompilátor a program, který vygeneruje jiný program a pak ho nechá zkompilovat.

A jak se tohle dělá ve Scale ukážu právě teď.


Jako příklad budu používat AST reprezentující jednoduché aritmetické výrazy.

sealed trait Expr

case class Const(value: Int) extends Expr
case class Plus(x: Expr, y: Expr) extends Expr
case class Minus(x: Expr, y: Expr) extends Expr
case class Times(x: Expr, y: Expr) extends Expr

V něm můžu zapsat například výraz

val ast = Times(
  Plus(Const(1), Const(2)),
  Minus(Const(3), Const(4))
)

který reprezentuje (1 + 2) * (3 - 4).

Za povšimnutí stojí fakt, že AST reprezentuje program a když chci zjistit jeho hodnotu, musím tento program vykonat. Na to budu potřebovat interpreter, který rekurzivně prochází AST a vyhodnocuje onen program.

def evalExpr(e: Expr): Int = e match {
  case Const(x)    => x
  case Plus(x, y)  => evalExpr(x) + evalExpr(y)
  case Minus(x, y) => evalExpr(x) - evalExpr(y)
  case Times(x, y) => evalExpr(x) * evalExpr(y)
}

Výsledkem volání evalExpr(ast) je pak pochopitelně –3.

Kdybych chtěl, aby můj malý programovací jazyk uměl víc věcí, musel bych přidat další druhy AST uzlů, které by reprezentovaly nové operace nebo koncepty jako podmínky, smyčky nebo proměnné (aby tyto fungovaly, bylo by třeba změnit interpreter, aby jako další parametr bral mapování mezi proměnnými a jejich hodnotami).

Tento přístup funguje, ale interpretace má nezanedbatelnou režii. Program popisuje primitivní operace, které odpovídají jedné procesorové instrukci, ale na to aby ji interpreter vykonal musí procházet stromovou strukturu. volat metody a provádět pattern matching ve funkci evalExpr2.

Když ale program zkompiluji do nějaké nativnější formy (ať už nativního kódu nebo bytekódu, který je vzápětí přeložen JITem virtuálního stroje), zbavím se této režie a program může běžet znatelně rychleji.

V poslední verzi Scaly 2.11 se ke kompilaci dají použít takzvané quasiquotes a ToolBox API.

Nejprve musím importovat pár záludností.

import scala.reflect.runtime.currentMirror
import scala.tools.reflect.ToolBox
val toolbox = currentMirror.mkToolBox()
import toolbox.u._
import toolbox.{ u => universe }

A pak vytvořím metodu, která každou variantu Expr převede na odpovídající fragment kódu.

def compileExpr(e: Expr): universe.Tree = e match {
  case Const(x)    => q"$x"
  case Plus(x, y)  => q"${compileExpr(x)} + ${compileExpr(y)}"
  case Minus(x, y) => q"${compileExpr(x)} - ${compileExpr(y)}"
  case Times(x, y) => q"${compileExpr(x)} * ${compileExpr(y)}"
}

Kód pro kompilaci vypadá skoro stejně, jako kód pro interpretaci3. Jediný rozdíl je v tom, že zatímco program interpreteru se přímo vykoná, program kompilátoru – obalený interpolátorem q"..." se převede na kód. To co vypadá jako interpolace stringů ve skutečnosti nepracuje s textovou reprezentací programu, ale s AST, které Scala kompilátor interně používá k reprezentaci kódu. Obsah q"..." (q jako quasiquotes) je přeložen na potomky universe.Tree a na místa označená ${...} se rekurzivně vloží další kusy AST. A protože nejde o textové šablony, dá se s tím dělat mnohem víc věcí, které jsou popsány v dokumentaci quasiquotes a maker.

compileExpr ale neprovede kompilaci, jen připraví AST, se kterými si umí Scala kompilátor poradit. Ale předtím je ještě nutné výraz zabalit do funkce, kterou bude možné volat.

val qq = q"""
  () => {
    println("running function that was compiled during runtime")
    ${compileExpr(ast)}
  }
"""

Můžu si nechat vypsat, jak by asi vypadal zkompilovaný kód:

println(showCode(qq))

To ukáže něco jako:

(() => (1).+(2).*((3).-(4)))

Samotnou kompilaci pak provedu takto:

val f = toolbox.compile(qq)().asInstanceOf[() => Int]

A teď už mám funkci typu Unit => Int, kterou můžu volat jako jakoukoli jinou funkci.

f() // vypíše hlášku a vrátí -3

f obsahuje jen kód samotného výpočtu bez režie interpretace. A protože jde o jednoduchý bytecode, může být JITem dále optimalizován. I v případě interpreteru mi může JIT trochu pomoct spekulativními optimalizacemi, ale rozhodně nemůže aplikovat celou řadu triků a heuristik a metod, kterými se kompilátory naučily vylepšovat jednoduchý kód bez zbytečných abstrakcí a komplikací5.

Lispeři se teď musí smát, protože se ve Scale objevilo něco, co oni mají už od šedesátých let. Lispeři se však zbytku světa smějí tak jako tak a proto je můžeme ignorovat.


Já se o tyto techniky začal zajímat po jednom obzvláště neklidném snu, kdy jsem se rozhodl naprogramovat hrubý prototyp sloupcové databáze později pojmenované DilettanteDB. V mých testech se ukázalo, že zkompilovaný kód může být 30× rychlejší než naïvní interpretace. Výsledek dokáže skenovat data 10GB/s a vykonává pouhých 1.7 instrukcí za takt a i v jednom vláknu je omezený jen propustností pamětí. To je téměř ideální stav.4 Stejnou techniku ke kompilování SQL dotazů používá optimalizátor Catalyst ze Sparku.

Jediný problém na který jsem narazil byla pomalá kompilace. Scala kompilátor není ani rychlý ani kompaktní a proto, když ho chci na něco použít, musím ho načíst, nechat ho rozhýbat a to nějakou dobu trvá. První kompilace jedné funkce o padesáti řádcích trvala 3 vteřiny. Další už byly rychlejší, ale zdaleka ne tak rychlé, jak by se mi líbilo.


Když už jsem v tom, slušelo by se zmínit projekt Scala.meta, který se snaží vylepšit metaprogramování ve Scale, které má pořád svoje nedostatky. Jeden z nich je například fakt, že Scala kompilátor nezachovává nepotřebné informace jako je formátování nebo syntaktické konstrukce, které použil programátor (ale jejich jednodušší formy) a proto se nehodí pro určitou kategorii nástrojů.


Dále k tématu:


  1. I když jak se ukazuje, tak režii reflexe a metaobjektových protokolů je možné vhodnými technikami téměř zcela odstranit. Viz Zero-Overhead Metaprogramming Reflection and Metaobject Protocols Fast and without Compromises
  2. Pattern matching je možné pochopitelně nahradit metodou eval na třídě Expr. Virtuální volání někdy může být rychlejší než pattern matching, jindy pomalejší. Záleží na detailech a jak se s nimi popere just-in-time kompilátor.
  3. To není úplná náhoda, protože jak Erik Meijer ukazuje ve své poněkud vulgární přednášce The Lost Art of Denotational Semantics, interpreter je možné automaticky převést na kompilátor. Jako další příklad může posloužit pythonovský projekt PyPy, který vytváří tracing JIT kompilátory z interpreterů. PyPy zaznamenává trace akcí interpreteru a výslednou sekvenci instrukcí a operací pak optimalizuje až na binární kód. V PyPy je například napsána implementace PHP HippyVM nebo kompilátor lispovského Racketu.
  4. V takové situaci se dá zrychlit už jedině komprimací dat, jako to třeba dělá například 0×data H₂0. Viz In-Memory Processing, 0×data H20, Efficient Low Latency Java and GCs a An API for Distributed Computing.
  5. Viz poznámky pod Jak JVM volá virtuální metody a jaká temná božstva při tom uctívá. Kompilátor/JIT se jako první snaží zbavit abstrakcí, aby odhalil jádro kódu, které je možné jednoduše optimalizovat.

Flattr this!

This entry was posted in Scala. Bookmark the permalink.

One Response to Generování kódu za běhu (ve Scale)

  1. Tomáš2 says:

    Škoda, že pro podobné techniky nezbývá v komerčním světě tolik prostoru. Díky za příjemný článek.

    Metaprogramování nemusí být tolik vzdálené, i v dnešní době popularizovaný javascript se k tomu dá použít. V praxi jsme dosáhli asi 30% snížení latence, což je proti tvým výsledků popisovaných v článku nesrovnatelné :).

Leave a Reply

Your email address will not be published. Required fields are marked *