funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

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

20. 7. 2015 — k47

Někdy je zkrátka po­třeba dy­na­micky ge­ne­ro­vat kód.

Důvodů pro to může být mnoha: Na­pří­klad můžu mít ně­ja­kou formu ex­ter­ního do­mé­no­vého jazyka (DSL), který musí běžet rychle, nebo musí být sta­ticky in­te­gro­ván do zbytku pro­gramu bez po­u­žití re­flexe1, nebo chci pro­vést ně­ja­kou in­stru­men­taci nebo sta­tic­kou ana­lýzu exis­tu­jí­cího kódu. V ně­kte­rých pří­pa­dech to může být zby­tečné, ale jindy je dy­na­mické ge­ne­ro­vání kódu ta správná věc.

A když říkám dy­na­mické ge­ne­ro­vání kódu, ne­mys­lím během kom­pi­lace pomocí kla­sic­kých maker, ale za běhu, na zá­kladě ně­ja­kých data, které v době kom­pi­lace nejsou a ne­mo­hou být známé. Pokud ne­mlu­víme o makrech céč­kov­ského typu, je mezi sta­tic­kým a dy­na­mic­kým ge­ne­ro­vá­ním kódu jen pra­malý rozdíl. Oba po­tře­bují kom­pi­lá­tor a pro­gram, který vy­ge­ne­ruje jiný pro­gram a pak ho nechá zkom­pi­lo­vat.

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


Jako pří­klad budu po­u­ží­vat AST re­pre­zen­tu­jící jed­no­du­ché arit­me­tické 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 na­pří­klad výraz

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

který re­pre­zen­tuje (1 + 2) * (3 - 4).

Za po­všim­nutí stojí fakt, že AST re­pre­zen­tuje pro­gram a když chci zjis­tit jeho hod­notu, musím tento pro­gram vy­ko­nat. Na to budu po­tře­bo­vat in­ter­pre­ter, který re­kur­zivně pro­chází AST a vy­hod­no­cuje onen pro­gram.

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ý­sled­kem volání evalExpr(ast) je pak po­cho­pi­telně -3.

Kdy­bych chtěl, aby můj malý pro­gra­mo­vací jazyk uměl víc věcí, musel bych přidat další druhy AST uzlů, které by re­pre­zen­to­valy nové ope­race nebo kon­cepty jako pod­mínky, smyčky nebo pro­měnné (aby tyto fun­go­valy, bylo by třeba změnit in­ter­pre­ter, aby jako další pa­ra­metr bral ma­po­vání mezi pro­měn­nými a jejich hod­no­tami).

Tento pří­stup fun­guje, ale in­ter­pre­tace má ne­za­ne­dba­tel­nou režii. Pro­gram po­pi­suje pri­mi­tivní ope­race, které od­po­ví­dají jedné pro­ce­so­rové in­strukci, ale na to aby ji in­ter­pre­ter vy­ko­nal musí pro­chá­zet stro­mo­vou struk­turu. volat metody a pro­vá­dět pat­tern matching ve funkci evalExpr2.

Když ale pro­gram zkom­pi­luji do nějaké na­tiv­nější formy (ať už na­tiv­ního kódu nebo by­te­kódu, který je vzá­pětí pře­lo­žen JITem vir­tu­ál­ního stroje), zbavím se této režie a pro­gram může běžet zna­telně rych­leji.

V po­slední verzi Scaly 2.11 se ke kom­pi­laci dají použít tak­zvané quasiquo­tes a Tool­Box API.

Nej­prve musím im­por­to­vat pár zá­lud­ností.

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

A pak vy­tvo­řím metodu, která každou va­ri­antu Expr pře­vede na od­po­ví­da­jící frag­ment 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 kom­pi­laci vypadá skoro stejně, jako kód pro in­ter­pre­taci3. Jediný rozdíl je v tom, že za­tímco pro­gram in­ter­pre­teru se přímo vykoná, pro­gram kom­pi­lá­toru – oba­lený in­ter­po­lá­to­rem q"..." se pře­vede na kód. To co vypadá jako in­ter­po­lace stringů ve sku­teč­nosti ne­pra­cuje s tex­to­vou re­pre­zen­tací pro­gramu, ale s AST, které Scala kom­pi­lá­tor in­terně po­u­žívá k re­pre­zen­taci kódu. Obsah q"..." (q jako quasiquo­tes) je pře­lo­žen na po­tomky universe.Tree a na místa ozna­čená ${...} se re­kur­zivně vloží další kusy AST. A pro­tože nejde o tex­tové ša­b­lony, dá se s tím dělat mnohem víc věcí, které jsou po­psány v do­ku­men­taci quasiquo­tesmaker.

compileExpr ale ne­pro­vede kom­pi­laci, jen při­praví AST, se kte­rými si umí Scala kom­pi­lá­tor po­ra­dit. Ale před­tím je ještě nutné výraz za­ba­lit 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 vy­pa­dal zkom­pi­lo­vaný kód:

println(showCode(qq))

To ukáže něco jako:

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

Sa­mot­nou kom­pi­laci pak pro­vedu takto:

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

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

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

f ob­sa­huje jen kód sa­mot­ného vý­po­čtu bez režie in­ter­pre­tace. A pro­tože jde o jed­no­du­chý by­te­code, může být JITem dále op­ti­ma­li­zo­ván. I v pří­padě in­ter­pre­teru mi může JIT trochu pomoct spe­ku­la­tiv­ními op­ti­ma­li­za­cemi, ale roz­hodně nemůže apli­ko­vat celou řadu triků a heu­ris­tik a metod, kte­rými se kom­pi­lá­tory na­u­čily vy­lep­šo­vat jed­no­du­chý kód bez zby­teč­ných abs­trakcí a kom­pli­kací5.

Lispeři se teď musí smát, pro­tože se ve Scale ob­je­vilo něco, co oni mají už od še­de­sá­tých let. Lispeři se však zbytku světa smějí tak jako tak a proto je můžeme ig­no­ro­vat.


Já se o tyto tech­niky začal za­jí­mat po jednom ob­zvláště ne­klid­ném snu, kdy jsem se roz­hodl na­pro­gra­mo­vat hrubý pro­to­typ sloup­cové da­ta­báze poz­ději po­jme­no­vané Di­let­tan­teDB. V mých tes­tech se uká­zalo, že zkom­pi­lo­vaný kód může být 30x rych­lejší než naïvní in­ter­pre­tace. Vý­sle­dek dokáže ske­no­vat data 10GB/s a vy­ko­nává pou­hých 1.7 in­strukcí za takt a i v jednom vláknu je ome­zený jen pro­pust­ností pamětí. To je téměř ide­ální stav.4 Stej­nou tech­niku ke kom­pi­lo­vání SQL dotazů po­u­žívá op­ti­ma­li­zá­tor Ca­ta­lyst ze Sparku.

Jediný pro­blém na který jsem na­ra­zil byla pomalá kom­pi­lace. Scala kom­pi­lá­tor není ani rychlý ani kom­paktní a proto, když ho chci na něco použít, musím ho načíst, nechat ho roz­hý­bat a to ně­ja­kou dobu trvá. První kom­pi­lace jedné funkce o pa­de­sáti řád­cích trvala 3 vte­řiny. Další už byly rych­lejší, ale zda­leka ne tak rychlé, jak by se mi líbilo.


Když už jsem v tom, slu­šelo by se zmínit pro­jekt Scala.meta, který se snaží vy­lep­šit me­ta­pro­gra­mo­vání ve Scale, které má pořád svoje ne­do­statky. Jeden z nich je na­pří­klad fakt, že Scala kom­pi­lá­tor ne­za­cho­vává ne­po­třebné in­for­mace jako je for­má­to­vání nebo syn­tak­tické kon­strukce, které použil pro­gra­má­tor (ale jejich jed­no­dušší formy) a proto se nehodí pro ur­či­tou ka­te­go­rii ná­strojů.


Dále k tématu:


  1. I když jak se uka­zuje, tak režii re­flexe a me­t­a­ob­jek­to­vých pro­to­kolů je možné vhod­nými tech­ni­kami téměř zcela od­stra­nit. Viz Zero-Overhead Me­ta­pro­gra­m­ming Re­flection and Me­t­a­ob­ject Pro­to­cols Fast and wi­thout Com­pro­mi­ses
  2. Pat­tern matching je možné po­cho­pi­telně na­hra­dit me­to­dou eval na třídě Expr. Vir­tu­ální volání někdy může být rych­lejší než pat­tern matching, jindy po­ma­lejší. Záleží na de­tai­lech a jak se s nimi popere just-in-time kom­pi­lá­tor.
  3. To není úplná náhoda, pro­tože jak Erik Meijer uka­zuje ve své po­ně­kud vul­gární před­nášce The Lost Art of De­no­tati­o­nal Se­man­tics, in­ter­pre­ter je možné au­to­ma­ticky pře­vést na kom­pi­lá­tor. Jako další pří­klad může po­slou­žit py­tho­nov­ský pro­jekt PyPy, který vy­tváří tra­cing JIT kom­pi­lá­tory z in­ter­pre­terů6. PyPy za­zna­me­nává trace akcí in­ter­pre­teru a vý­sled­nou sek­venci in­strukcí a ope­rací pak op­ti­ma­li­zuje až na bi­nární kód. V PyPy je na­pří­klad na­psána im­ple­men­tace PHP Hip­pyVM nebo kom­pi­lá­tor lis­pov­ského Racketu.
  4. V takové si­tu­aci se dá zrych­lit už jedině kom­pri­mací dat, jako to třeba dělá na­pří­klad 0xdata H₂0. Viz In-Memory Pro­ces­sing, 0xdata H20, Ef­fi­ci­ent Low La­tency Java and GCsAn API for Dis­tri­bu­ted Com­pu­ting.
  5. Viz po­známky pod Jak JVM volá vir­tu­ální metody a jaká temná bož­stva při tom uctívá. Kom­pi­lá­tor/JIT se jako první snaží zbavit abs­trakcí, aby od­ha­lil jádro kódu, které je možné jed­no­duše op­ti­ma­li­zo­vat.
  6. Funkce tra­cing JITu je do de­tailu po­psána na­pří­klad v Trace-based Just-in-time Com­pi­lation for Lazy Functi­o­nal Pro­gra­m­ming Lan­gu­ages
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články