funkcionálně.cz

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

I ve Scale se dá psát rychlý generický kód za použití typeclass

12. 12. 2015 — k47

Ne­dávno jsem tu psal o tom, jak se dá rychle vy­po­čí­tat Jac­car­dova po­dob­nost. Rychle bylo klí­čové slova a jediná věc na které sku­tečně zá­le­želo. Právě kvůli rych­losti jsem do knihovny sket­ches přidal verzi této rutiny (a pár dal­ších funkcí) spe­ci­a­li­zo­va­nou pro jediný pri­mi­tivní typ. Vý­sle­dek je na jednu stranu rychlý, ale na druhou stranu ne­fle­xi­bilní. Co když budu chtít udělat to samé, ale místo čtyř­baj­to­vých intů s os­mi­baj­to­vými longy? V tom pří­padě mám smůlu a musím du­pli­ko­vat kód.

Na­štěstí Scala nabízí dvě vlast­nosti – ty­pec­lassy a spe­ci­a­li­zaci, které přesně tento pro­blém v kom­bi­naci s chyt­rým a agre­siv­ním JITem do­ká­žou vy­ře­šit. S tro­chou snahy je možné psát kód, který je obecný a zá­ro­veň stejně rychlý jako verze ručně spe­ci­a­li­zo­vaná pro každý pri­mi­tivní typ.

Ručně spe­ci­a­li­zo­vaná metoda vy­pa­dala takhle:

def intersectionSize(a: Array[Int], b: Array[Int]): Int = {
  var size, ai, bi = 0
  while (ai != a.length && bi != b.length) {
    val av = a(ai)
    val bv = b(bi)
    size += (if (av == bv) 1 else 0)
    ai   += (if (av <= bv) 1 else 0)
    bi   += (if (av >= bv) 1 else 0)
  }
  size
}

Když bych to pře­psal na ge­ne­ric­kou verzi, se sig­na­tu­rou

def intersectionSize[T](a: Array[T], b: Array[T]): Int

pole Array[T] stále budou poli pří­sluš­ných pri­mi­tiv­ních typů. V tomto pří­padě ge­ne­rický typ ne­způ­sobí, že obsah polí bude bo­xo­ván do ob­jektů, ale k pří­stupu do nich budou po­u­žité sta­tické metody array_applyarray_length ze třídy Sca­la­Run­Time, které mají efek­ti­vitě velice daleko.

Ale na tom teď ale příliš ne­zá­leží, pro­tože to stejně nebude fun­go­vat, pro­tože bych v těle metody po­ží­val po­rov­nání ==, <=, >= na ob­jek­tech ge­ne­ric­kého typu T. T může být cokoli a tedy nemůže ga­ran­to­vat, že na něm budou tyhle ope­race de­fi­no­vány. To se dá vy­ře­šit im­pli­cit­ním pa­ra­me­t­rem, který ob­sa­huje im­ple­men­taci těchto ope­rací pro daný typ. Jde o tak­zva­nou ty­pec­lass.

def intersectionSize[T](a: Array[T], b: Array[T])(implicit num: Num[T]): Int

Num je něco jako Nu­me­ric ze stan­dardní knihovny. Při za­vo­lání metody bez po­sled­ního bloku pa­ta­me­trů bude au­to­ma­ticky do­pl­něn kom­pi­lá­to­rem. V těle metody se to po­u­žije ná­sle­dovně:

size += (if (num.eq (av, bv)) 1 else 0)
ai   += (if (num.lte(av, bv)) 1 else 0)
bi   += (if (num.gte(av, bv)) 1 else 0)

Tohle už je správně a kom­pi­lá­tor si pře­stane stě­žo­vat. I když jsem vy­ře­šil pro­blém ge­ne­ri­city, pro­blém s rych­lostí stále zů­stává. Každý ele­ment pole je au­to­bo­xo­ván, jako objekt předán me­to­dám třídy Num, které je roz­balí a pro­ve­dou na něm jednu in­strukci uži­tečné práce.

I když i v tomto pří­padě není všechno ztra­ceno a JIT může trochu pomoct – když pro­fi­lo­vání ukáže, že se metoda volá jen pro jeden typ a je tedy po­u­žitá jedna a ta samá in­stance Num, JIT může metody eq, ltegte in­li­no­vat, po in­li­no­vání je možné od­stra­nit zby­tečný au­to­bo­xing a dostat něco, co vypadá celkem efek­tivně. Pro­blém je v tom, že jde o velice křeh­kou rov­no­váhu sil. Takhle to fun­guje, když je Num ar­gu­ment vždycky in­stancí jedné třídy a call­site pro eq, ltegte jsou mo­no­morfní. Když intersectionSize po­u­ží­vám v mnoha kon­tex­tech a s mnoha typy, JIT to s in­li­no­vá­ním pře­stane mít lehké, na­jed­nou musí po­čí­tat se všemi va­ri­an­tami, musí do kódu vklá­dat roz­skoky, použít inline cache nebo použít kla­sické volání vir­tu­ál­ních metod. Vý­sledná bi­nárka začne trpět a efek­ti­vita začne klesat.

Ale na druhou stranu, když se JIT roz­hodne celou metodu intersectionSize in­li­no­vat a tedy zko­pí­ro­vat její tělo na místo odkud je volána, všechno může být zase dobré. In­li­no­vá­ním se vy­tvoří nový kon­text a nové call­site metod eq, ltegte, které na­jed­nou nejsou uvěz­něné v těle metody a tedy sdí­lené pro všechna možná po­u­žití intersectionSize.

A tady do hry vstu­puje spe­ci­a­li­zace.

Je třeba spe­ci­a­li­zo­vat jak ty­pec­lass Num, tak metodu, která ji po­u­žívá:

trait Num[@specialized(Int, Long, Float, Double) T] {
  def eq (a: T, b: T): Boolean
  def gt (a: T, b: T): Boolean
  def gte(a: T, b: T): Boolean = !gt(b, a)
  def lt (a: T, b: T): Boolean =  gt(b, a)
  def lte(a: T, b: T): Boolean = !gt(a, b)
}

def intersectionSize[@specialized(Int, Long, Float, Double) T](a: Array[T], b: Array[T])(implicit num: Num[T]): Int = ???

Sig­na­tura metody spe­ci­a­li­zo­vané pro čtyři pri­mi­tivní typy1 má na délku ki­lo­metr, ale každé pís­meno za to stojí. Tady se totiž do­stá­vám k jádru pudla.

Spe­ci­a­li­zace vy­ge­ne­ro­vala ne­zá­vis­lou metodu pro každý typ zvlášť. Verze pro Int bude vy­pa­dat nějak takhle:

def intersectionSize$mIc$sp(a: Array[Int], b: Array[Int])(implicit num: Num[Int]): Int = {
  var size, ai, bi = 0
  while (ai != a.length && bi != b.length) {
    val av = a(ai)
    val bv = b(bi)
    size += (if (num.eq$mIc$sp (av, bv)) 1 else 0)
    ai   += (if (num.lte$mIc$sp(av, bv)) 1 else 0)
    bi   += (if (num.gte$mIc$sp(av, bv)) 1 else 0)
  }
  size
}

Jak je vidět, místo eq se teď volá metoda eq$mIc$sp spe­ci­a­li­zo­vaná pro Int. Ta je nejen efek­tivní tím, že jako ar­gu­ment chce nahý pri­mi­tivní int, ale také tím, že na jejím místě se vždycky za kaž­dých okol­ností volá jedna jediná im­ple­men­tace po­chá­ze­jící z jedné ty­pec­lassy Num[Int]. Kon­krétní call­site je tedy za­ru­čeně mo­no­morfní, JIT s ní může za­chá­zet jako se sta­tic­kou metodu a velice snadno in­li­no­vat její tělo. A v tomto pří­padě jde o sta­bilní a ga­ran­to­va­nou op­ti­ma­li­zaci, kterou ne­roz­bije za­vo­lání metody intersectionSize v na­prosto ne­sou­vi­se­jící části pro­gramu.

JVM v tomto pří­padě odvede tak dobrou práci, že vý­sledná bi­nárka, kterou vy­pro­du­ko­val JIT, je k ne­ro­ze­znání od bi­nárky ručně spe­ci­a­li­zo­vané verze.

Ale za­tímco tohle skvěle fun­guje pro ty­pec­lassy, nemusí to vůbec platit pro funkce vyš­ších řádů. Ty­pec­lass má ty­picky pro každý typ jednu im­ple­men­taci a v metodě spe­ci­a­li­zo­vané pro jeden typ se po­u­žije právě jedna ty­pec­lassa. Funkce vyš­ších řádů fun­gují na­proti tomu vět­ši­nou při­jí­mají spoustu růz­ných funkcí jako ar­gu­ment a spe­ci­a­li­zace tedy ne­ga­ran­tuje dobré in­li­no­vání, jen eli­mi­nuje zby­teč­nou režii au­to­bo­xingu.


Dále k tématu:

Pozn:

  1. Po­u­ží­vám jen čtyři nej­čas­tější typy, abych omezil množ­ství tříd a ve­li­kost by­te­kódu, kterou spe­ci­a­li­zace vy­pro­du­kuje. Tohle je jedna ze sla­bých strá­nek spe­ci­a­li­zace, pro­tože je třeba vy­ge­ne­ro­vat všechny kom­bi­nace všech typů a pa­ra­me­trů pro které je spe­ci­a­li­zo­váno. Z tohoto důvodu bylo na­vr­žena al­ter­na­tiva – tzv. mi­ni­bo­xing (viz & viz).
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články