0xDEADBEEF

RSS
24. 6.

Striktní a líné jazyky


František Řezáč napsal článek o tom, že Operátory nejsou (vždy) funkce. To je pravda a není k tomu třeba dodávat nic víc.

Stojí to ale za pozornost jen v případě striktních jazycích typu C a Java, kde jsou argumenty funkce vyhodnoceny vždy před jejím zavoláním (applicative order/call by value). V takovém prostředí není jednoduše možné napsat vlastní funkci OR nebo AND, která se chová stejně jako vestavěné operátory || nebo &&. Ty v klasické sortě céčku podobných jazyků vyhodnotí druhý argument jen pokud je to nezbytně nutné. Toho bez funkcí vyššího řádu (jak FR podotknul) není možné dosáhnout. Proto v nich operátory zaujímají speciální místo.

Mě to koplo nedávno, když jsem psal interpret jednoduchého lipovského jazyka1 , kde odloženého vyhodnocování bylo nezbytné k tomu, aby následující kód neskonšil NullPointerException.

(if (and (nil? x) (.nonEmptx x)) (something))

V líných jazycích nebo těch, které podporují call-by-name nebo call-by-need, operátory v principu nemají speciální postavení2 a jsou to jen další metody.

Ve Scale můžu napsat vlastní funkci OR takto:

def OR(a: Boolean, b: => Boolean): Boolean = if (a) true else b

Typ => Boolean označuje call-by-name boolean. b není vyhodnoceno při zavolání funkce, namísto toho bude vyhodnoceno na každém místě, kde je v těle funkce použito. Kompilátor call-by-name parametr zabalí do anonymní funkce, která je pak opakovaně volána.

Nejde ale o plně líné neboli call-by-need vyhodnocování jako například v Haskellu. V něm je nevyhodnocený výraz reprezentován strukturou běžně nazývanou thunk, která ukazuje na kód. Když je přinucena se vyhodnotit (například pattern matchingem), je odkazovaný program vykonán a thunk je atomicky zaměněn na výsledek. Líné jazyky mají tu vlastnost, že nevyhodnocené nemusí být jen argumenty funkce, ale celé datové struktury. Můžu mít masivní strom, ale když jsem četl jen z jedné cesty k listům, všechny nenavštívené odbočky zůstanou jako nevyhodnocené thunky.

Call-by-need je tedy call-by-name doplněné s memoizací.

Ve Scale je to možné emulovat takto:

def f(_a: => X) = {
  lazy val a = _a
  ???
}

Když někde použiji proměnnou a dojde k jejímu vyhodnocení jen jednou a výsledná hodnota se bude recyklovat při každém dalším použití.


Poznámky:


  1. Jmenoval se Lispy a byl zamýšlený jako skriptovací nástroj pro asciiblog. Psalo se v něm příjemně, ale nakonec jsem ho nahradil za javascript vestavěný do Javy.
  2. Kompilátor o nich ví a proto bych si dovolil odhadovat, že pro ně vygeneruje lepší kód.



21. 6.

Syntéza datových struktur a programů


Generalized data structure synthesis stojí za přečtení. Prezentuje nástroj Cozy, který - jak říká název článku - umí syntetizovat datové struktury operace nad nimi, které jsou nejen korektní, ale také efektivní. Nechci opakovat, co už shrnul Adrian Colyer, přečtěte si to, teď hned, je to důležité pro následující odstavce.

Jde o perfektní doplněk k Out of the Tar Pit a možná chybějící článek nutný k tomu, aby vize načrtnutá v tar pit paperu (pokud nechcete číst, tady jsem ho kdysi shrnul).

Autor tar pit paperu mluví o esenciální a vedlejší komplexitě, přičemž ta esenciální je ta důležitá, jde o nutnou složitost problému nebo domény, chcete-li. Vedlejší komplexita nemá žádnou hodnotu pro uživatele, jen je někdy nutná pro dosažení efektivity a dostatečného výkonu. Esenci musíme nějak vyjádřit a vedlejší složitostí bychom se měli vyhnout.

Na tom není nic kontroverzního, ale teď jak toho dosáhnout. V tar pit paperu se mluví o logickém a funkcionálním programování, deklarativním stylu a relačním datovém modelu.

A tady do hry vstupuje Cozy - nadefinuji nezbytný stav bez ohledu na efektivní reprezentaci, tak jak o něm přemýšlejí uživatelé, deklarativně popíšu operace nad ním, jako v tar pit utopii a Cozy, nebo nějaký jeho pokročilý potomek, z této kostry syntetizuje její efektivnější verzi - efektivní datové struktury specializované pro dané operace a efektivní kód. Z esenciálního popisu vygeneruje všechnu vedlejší komplexitu a odvozený stav.


Heuristiky a strategie prohledávání stavového prostoru, můžou být pochopitelně rozšířeny strojovým učením.




9. 6.

ISPC, SPMD a SIMD


Maxime Chevalier tweetla odkaz na zajímavou sérii článků mapující počátky a vývoj kompilátoru ISPC (Intel SPMD program compiler) + do toho vysvětlí jak funguje SPMD programovací model, který je využívaný pro programování grafických karet.

Všechno začalo s Larrabee - prototypem procesoru určeném pro segment, který okupuje GPGPU. Samotné první Larrabee skončilo jen u prototypu a neprodávalo se. Následující mikroarchitektury Knights Corner (57-61 jader) a Knights Landing (64-72 jader), hromadně nazývané produktovým jménem Xeon Phi si však úspěšně našly místo v superpočítačích.

Larrabee a jeho následovníci byli navrženi jako čip, ktrerý nese velké množství jednoduchých in-order jáder1 obohacených o široké SIMD jednotky + 4xSMT. SIMD od počátku mělo šířku 512 bitů (tedy tolik jako AVX-512, které se později dostalo do obyčejných Skylake čipů). Taková šířka znamená, že jedna SIMD instrukce pracuje s 16 čtyřbajtovými inty/floaty. To je hodně práce v jedné operaci.

Teď jak tento spící potenciál využít? Nejde jen o Larrabee určené pro superpočítače, ale i běžné čipy. Když bylo uvedeno AVX, došlo ke zdvojnásobení šířky SIMD jednotek (z 128 butů na 256 bitů) a tedy k ±zdvojnásobení výpočetní síly. Další zdvojnásobení přichází teď s poslední generací procesorů Intel, které podporují AVX-512. Jak podotýká autor odkazovaných článků, takové zrychlení jsme viděli naposledy v devadesátých letech.

Jednou možnost je automatická vektorizace kódu - ta funguje, ale nejde o programovací model, je to jen optimalizace na kterou se uživatel nemůže na 100% spolehnout. Další alternativou je psát přímo v assembleru nebo za pomocí intrinsic funkcí. To ale není příliš produktivní způsob práce.. Další varianta je pak SPMD - single program multiple data. Jde o to, že se paralelní program rozřízne podélně a místo abych se zdržoval explicitním paralelismem, píšu sériový program, který pracuje s jedním elementem vstupu. Mnoho instancí tohoto programu pak může běžet v mnoha vláknech, ale také můžou být přeloženy pro SIMD. V takovém případě SIMD jednotka s 16 lajnami bude provádět 16 instancí programu vedle sebe. Je to jako kdyby 16 vláken pochodovalo zcela identickým rytmem, jednu instrukci za druhou. Překlad je celkem triviální, ale poněkud nezvyklý. V přítomnosti podmínek, smyček, goto, break a continue, je nutné některé SIMD lajny vymaskovat jako neaktivní a tak podobně. Ve své podstatě jde o glorifikovanou funkci map.


Relevantní čtení:


  1. Tyto jádra vycházejí z originálních Pentií, stejně jako z nich vycházely rané Atomy.



6. 4.

Konec Intelu, konec Moorova zákona, konec světa takového jaký známe


Apple oznámil, že plánují opustit procesory Itelu a chtějí přejít k vlastním čipům. Zatím se neví, jakou architekturu zvolí, zda-li to bude ARM nebo nějaká proprietární ISA. Všichni však blahořečí Apple a vyzdvihují, že jejich mobilní procesory jsou v jednovláknovém provozu stejně rychlé jako křemík od Intelu.

Když to čtu, skřípu zuby. Samozřejmě, že mají stejně výkonné čipy, bylo by mnohem víc neobvyklé, kdyby je neměli. To co předvádí Apple ve svých A11 nebo Intel v Xeonech je velice blízko nejzazšího maximum. Za současných podmínek není možné z jednoho vlákna vytěžit nic víc.

Procesor běžící na 2-3 GHz, který dokáže v ideálním případě provést 4 instrukce každý takt (IPC) představuje limit. Nic lepšího křemíkový průmysl nesvede vyprodukovat. Tedy aspoň co se obecného kódu týká.

Vyšší takty vedou k obrovsky narůstajícím ztrátám tepla, proto ty 2-3 GHz, a nespecializovaný kód neobsahuje instrukční paralelismus, který by bylo možno vytěžit, proto ~4 IPC.

Intelovské procesory mají praktické maximální IPC někde mezi 4-5. Power od IBM nebo Sparc od Oraclu jsou širší, plánované pro odpravení 8 instrukcí každý takt, ale to je jen kvlůli 8x SMT (tedy to, čemu Intel říká hyperthreading).

Některé z těchto instrukcí můžou být SIMD, které dokáží o něco navýšit výkon. SIMD ale začínají přesahovat do sféry specializovaných programů, které provádějí masivní množství výpočtů, ne typický general purpose kód plný podmínek a větvení. Pro tyto speciálních trapně paralelní případy už máme ideální nástroj: GPU.

Příslib architektury Mill o tom, že statický velice široký VLIW stroj dokáže vydolovat nebývalý instrukční paralelismus (ILP), se setkává s oprávněnou skepsí. Když už se jim podaří uspět, bude to spíš v oblasti MIPS na watt. Specializace pro danou mikro-architekturu a jádra bez masivní OOO mašinérie (ale zato s obrovským počtem funkčních jednotek), může být energeticky efektivní.

Je ale stále ve hvězdách jestli se něco ze slibů zcela nové architektury skutečně vyplní. Jednovláknový IPC se moc nezlepší a nezáleží kolik plochy čipu tomu věnujeme, změna bude vždy jen v jednotkách procent. Zcela jisté je, že budoucnost bude patřit specializovanému hardwaru. Jinak není možné dosáhnout žádného razantního zvýšení efektivity.

Jsme na konci jedné éry. Všichni mají nejlepší procesory na světě a nestojí to za řeč. Teď je potřeba udělat další velký krok do divočin, kde už neplatí Moorův zákon.


Pozn:


Relevantní čtení:




31. 1.

Meltdown, Spectre a branch prediction


Na Poslední Sobotě, kde jsem mluvil o Meltdown a Spectre (slajdy zde), jsem dostal dotaz jak jsou implementovány branch predictory. Něco jsem odpověděl, ale z trhanců vzpomínek mi nepřipadá, že šlo o uspokojivou odpověď. Proto jsem se rozhodl o tom něco málo napsat a hlavně poskytnout odkazy na autoritativní zdroje.

O branch prediction (BP) jsem se zmiňoval na funkcionálně.cz tady a trochu i tady. Šlo ale jenom o dopady BP na výkon, ne detaily nebo principy implementace. O tom se něco dá vyčíst z článku na wikipedii. Mnohem lepší úvod však poskytuje Dan Luu na svém blogu. Pokud vás toto téma zajímá, rozhodně si jeho článek přečtěte. (Už jsem ho tu vychvaloval)

Zajímavý ja také paper The YAGS Branch Prediction Scheme, který prezentuje, jak může vypadat o něco sofistikovanější, ale přesto klasická implementace.

Branch predictor nemusí být implementován jen pomocí tabulek historie skoků, ale i neuronovými sítěmi. Tím se AMD chlubili při ohlášení své mikroarchitektury Zen. Ale co tím vlastně myslí je otázka, na kterou nikdo nezná přesněou odpověď. Nejspíš nejde o nijak komplikované neuronosítě, ale o perceptrony, jak je popsáno v Dynamic Branch Prediction with Perceptrons. Predikce musí být rychlá, ideálně dostupná v jednom taktu, navíc je vždy tlak na to, aby extra hardware zabíral co nejméně místa čipu a konzumoval co nejméně energie.

x86 procesory mají několik nezávislých mechanismů pro predikci skoků. Jednak je již zmíněný to branch predictor, který odhaduje, zdaji bude skok proveden nebo ne a dále jsou to mechanismy odhadující, kam povede nepřímý skok. Jde jednak o branch target buffer (BTB) pro obecné skoky a pak return stack buffer (RSB) pro predikci cílů ret instrukcí. Protože ret se typicky vrátí na místo call instrukce, je RSB implementován jako jednoduchý zásobník. call na vrchol zásobníku vrazí svojí adresu a ret ji vyjme.

Toho je možné využít pro retpoline chránící před druhou variantou útoku Spectre. Nepřímý skok, který by se zkompiloval jako prosté

jmp *%r11

se se správnými přepínači GCC/LLVM namísto toho zkompiluje jako

  call set_up_target;

capture_spec: // nekonečná smyčka slouží jako trampolína, kde uvázne spekulativní exekuce
  pause;
  jmp capture_spec;

set_up_target:
  mov %r11, (%rsp); // tady se přepíše návratová adresa na zásobníku
  ret; // ret se vrátí na přepsanou adresu

Dojde náhradu za pár korespondujících call/ret instrukcí a na zásobníku se přepíše návratová adresa. To znemožní, aby byl spekulativně vykonán neznámý kód. Predikce ret použije adresu z RSB, která povede do nekonečné smyčky, a procesor poté, co odhalí, že jde o chybu, skočí nespekulativně na správnou adresu. Má to dopady na výkon, protože kód běží, jako kdyby byly spekulace a predikce zakázány.

Relevantní čtení:




28. 12. 2017

Poznámky k výkonu


Před nějakou dobou mi twitterem proletěla prezentace Adventures in efficiency and performance (slajdy, video), kde autor mluvil o tom jak dosáhnout výkonu na JVM a vyprávěl o hardwaru. Některé informace mi přišly nedostatečné, tady jsou moje poznámky.

V části "Good" failed speculations uvádí:

Both branches will be executed in parallel, only one of them will be retired

Ukázkový kód vypadá takhle:

def foo(a: Array[Int], idx: Int) = {
  val s = a[idx]
  if (s < 0) idx + idx
  else idx - idx
}

Záleží, jak bude kód zkompilován. Na jednu stranu může být převeden na compare+branch instrukce, které povedou k tomu, že CPU bude dynamicky spekulovat a bude záležet na branch prediction. Na druhou stranu to může vést k něčemu jkao tohle:

def foo(a: Array[Int], idx: Int) = {
  val s = a[idx]      //
  val add = idx + idx //
  val sub = idx - idx // nezávislé operace, všechny tři můžou běžet najednou

  if (s < 0) add else sub // zkompilováno jako cmov instrukce bez skoku
}

Poslední if nepředstavuje skok, ale instrukci cmov (conditional move), která na základě porovnání přesune buď add nebo sub. Nejde o větvení programu a tedy ani nehrozí žádná penalizace při špatném odhadu skoku (branch mispredict).

Nevím přesně, co myslel těmi good failed speculation. Současné x86 procesory (pokud se nemýlím) se nesnaží spekulativně provést obě větve podmínky a retire jen tu správnou.

Další příklad, který je mnohem komplikovanější než je prezentováno:

val a: Array[Array[Int]] = ...
val i = 0
while (i < n) {
  val j = 0
    while (j < n) {
      if (fast) {
        a[i][j] += a[i][j]
      } else { // slow
        a[j][i] += a[j][i]
      }
      j += 1
    }
  i += 1
}

Autor tvrdí, že rychlá verze (větev fast) byla 3x rychlejší až do příchodu Intel Skylake procesorů, které pak uvedly nějakou blíže nespecifikovanou změnu, která to změnila.

Pomalá větev může být rychlá, záleží na řadě faktorů jako například jak velká jsou data a jak jsou uspořádaná v paměti.

Jde o to, že rychlá verze přečte všechny elementy pole a[i] jeden za druhým než se posune na následující pole a[i+1]. Pomalá verze přečte první element ze všech polí a pak se posune na druhý element. Rychlá verze čte sekvenčně bloky paměti, druhá skáče z místa na místo.

Pokud je dat málo a vejdou se do cache, není moc co řešit (ale rychlá verze je stále preferovaná, protože se dá snáze vektorizovat bez scatter/gather instrukcí).

Rychlá verze funguje tak dobře, protože hardware počítá s tímto chováním. Data z paměti tahá po cache line blocích (64B na současných x86). Když se dotknu prvního intu v poli, dalších 16 jich už čeká v cache, připravené pro rychlé čtení. CPU navíc dopředu načítá data, která budou pravděpodobně potřeba (prefetch), takže sekvenční průchod je zcela ideální.

Prefetcher ale nemusí načítat jen data, která leží těsně vedle, ale dokáže detekovat kroky konstantní délky. Pokud jsou vnitřní pole malá a alokovaná sekvenčně, prefetcher rozpozná vzdálenost k dalšímu požadovanému prvku (stride) a načte ho dopředu. (Je ale méně efektivní, protože pořád musí vytáhnout celou cache line, za které použiji jen první prvek a než se dostanu k jeho sousedu, může být už vyhozená z cache).

     | -- a[0] ----- | -- a[1] ----- | -- a[2] ----- | -- a[3] -----

slow:  ^               ^               ^               ^
       |<-a[0].length->|<-a[0].length->|<-a[0].length->|

fast:  ^^^^^^^^^^^^^   ^^^^^^^^^^^^^

Pokud jsou vnitřní pole alokována různě na haldě, tak to také nemusí být problém. Prefetcher zvládne pracovat na několika místech paměti najednou (něco jako 64 různých stránek). Kdyby tedy vnější pole bylo menší než tento limit, prefetcher by stále pomohl.

I když jsou vnitřní pole rozesetá všude na haldě, ani to nemusí být konec. Záleží totiž i na použitém garbabe collectoru. Některé GC dělají kompakci haldy tak, že přesouvají objekty v pořadí ve kterém na ně narazí při procházení referencí. V tomto případě GC může narazit na pole a, zkopíruje ho na jedno místo a pak z něj začne procházet všechny reference na vnitřní pole a jedno po druhém je kopírovat vedle sebe. To povede k obnovení dobré lokality jako na schématu o něco výše.

Skylake mohl uvést větší cache, prefetch na více stránkách paměti, více paralelních přístupů do paměti, větší OOO okno. Vliv může mít také asociativita cache a cache eviction policy.

Nebudu tady teď mluvit scatter/gather SIMD instrukcích a dalších věcech, protože by to zabralo příliš místa a tenhle článek je už tak dost dlouhý.

Zjistit co je rychlejší a hlavně proč je jako vždycky komplikované.

Relevantní čtení:




19. 12. 2017

Java, Scala a regulární výrazy - líné regexy a StackOverflowError


Jednou z nepříjemných vlastností regexů v Javě je to, že můžou snadno skončit přetečením zásobníku a StackOverflowError. Regexy dělají backtracking, jsou implementovány rekurzivně a proto jde o nevyhnutelnou eventualitu.

Nejběžnější druhy opakování .*, .+ a .{m,n} jsou greedy (lakomé, hladové nebo jak je to česky) a snaží se pojmout co nejdelší vstup. Když následující část regexu selže, začnou s backtrackingem a postupně upouštějí z požraného vstupu, dokud následující část uspěje. Aby to fungovalo, potřebují si pamatovat kam skočit zpátky a tato pozice je (často) uchována na zásobníku při rekurzivním volání.

Když mám například regex .+.{5}, první část .+ pojme celý vstup, pak zjistí, že následující regex .{5} pro pět libovolných znaků nepasuje, ustoupí o jeden znak, zkusí znovu, nepasuje, opět ustoupí a tak dále dokud nepojme všechno kromě pěti posledních znaků. Teprve potom .{5} sedne a celý regex skončí úspěchem.

Naproti tomu líné (anglicky lazy nebo také reluctant) opakování .*?, .+? a .{m,n}? se snaží pojmout jen absolutní minimum, ideálně nic. V případě nouze, kdy následující regex selže, pojme jedno další opakování a pak otestuje následující část regexu.

V regexu .+?.{5} první část .+? nejprve nepožere nic, otestuje následující část, když ta selže, požere jedno opakování víc, zkusí znovu a tak dále.

Hladová a líná opakování nezmění jestli regex selže nebo ne, může změnit jen jak bude vstupní string rozdělen mezi uzávorkované skupiny.

Z výše popsaných důvodů vyplývá, že hladové regexy někdy můžou skončit výjimkou StackOverflowError, zatímco líné proběhnou úspěšně.

Například toto

("\uD83D\uDC09 "*100000).matches(".*")

skončí StackOverflowError. Vstupem je řetězec, ve kterém se sto tisíckrát opakuje symbol draka, který je hned následovaný mezerou. Naproti tomu varianty

("\uD83D\uDC09 "*100000).matches(".*?")
("\uD83D\uDC09 "*100000).matches(".*+")

skončí úspěšně, protože se liší způsobem, jakým je regex prováděn.

Java obsahuje optimalizaci, že když jedno opakování regexu pojme stejný počet znaků jako minulé opakování, nevolá se rekurzivně, ale ve smyčce. Symbol \uD83D\uDC09 zabírá dva chary a je hned následovaný jednocharovou mezerou. . tedy střídavě matchuje jeden a dva chary a proto vždy dělá rekurzivní volání a eventuálně přeteče zásobník (kód ve třídě Curly, metody match0, match1, match2).

Líná varianta si nemusí pamatovat, kam skočit zpátky a proto je implementována smyčkou, která nevyčerpá zásobník a neselže.

Tohle se týká jen případů, kdy se opakuje jednoduchý neuzávorkovaný vzor (jako třeba ., \W, \S atd.) a je to problém/řešení jen pro stringy obsahující několikabajtové znaky. Ale ty nejsou zas tak vzácné v pro texty s emoji.

Něco jako (a|b+)+? se vykonává vždy rekurzivně. Vnitřní implementace regexů je komplikovaná a aktivně se snaží předejít mnoha případům katastrofického backtrackingu. Proto se někdy jednoduchý vzor provádí poměrně překvapivě.

Co přetečení a katastrofickému backtrackingu předchází mnohem spolehlivěji jsou takzvané posesivní regexy, ale o nich něco napíšu příště.




5. 12. 2017

Java, Scala a regulární výrazy #3 - rychlost


Jak je na tom výkon regulárních výrazů ve srovnání s ručně psanými parsery?

Otestoval jsem to na parsování logů webserveru.

Regulární výraz vypadá takhle:

"""^(\S++) (\S++) (\S++) \[([^]]++)\] "((?:\\"|[^"])++)" (\d++) (\d++|-) "((?:\\"|[^"])*+)" "((?:\\"|[^"])*+)".*$""".r

Kód ručně napsaného parseru má 55 řádků a zabral mi přibližně stejně dlouho jako odladění regexu. Obě varianty vyprodukují identické výsledky.

Jako vstupní data jsem použil vzorek 1680000 řádků logu k47.cz. Regex je zpracuje za 9.26 vteřiny. Ruční variantě to trvá 1.3 vteřiny a z toho asi 0.3 vteřiny zabere jen alokace pod-řetězců.

Ve výsledku je regex asi 7x pomalejší než ručně psaný kód.




27. 11. 2017

Java, Scala a regulární výrazy #2 - rychlost


Stará poučka říká, že v Javě bychom měli regulární výrazy vždy dopředu zkompilovat a pak je opakovaně používat, protože kompilování je časově náročné.

V Javě je na to volání Patten.compile("^===+$"). Ve Scale je možné použít kompaktnější zápis za pomocí kouzel implicitních metod "^===+$".r.

Ale jak pomalé to vlastně je? To se dá jednoduše zjistit.

Vytáhl jsem JMH, napsal benchmark, který hledá jednoduchý vzor. Jednou vzor nekompiluje, podruhé používá předkompilovaný vzor a potřetí hledá regex jen když je to nezbytně nutné.

@State(Scope.Thread)
class regex {

  var lines: Array[String] = _
  val regex = """^===+$""".r

  @Setup def prepare() = {
    lines = io.Source.fromFile("export.txt").getLines.toArray
  }

  @Benchmark def notCompiled(): Int =
    lines.count(l => l.matches("^===+$"))

  @Benchmark def compiled(): Int =
    lines.count {
      case regex() => true
      case _ => false
    }

  @Benchmark def compiledWithCheck(): Int =
    lines.count { l => (l.length > 0 && l.charAt(0) == '=') && regex.findFirstMatchIn(l).nonEmpty }
}

Jako testovací data jsem použil kompletní export zdrojových textů blogu k47.cz, které mají dohromady něco kolem 8 MB a 143000 řádek textu.

Výsledky jsou následující:

Benchmark           Mode   Cnt    Score    Error  Units
notCompiled        thrpt     6   28,936 ±  2,298  ops/s
compiled           thrpt     6   94,120 ±  1,195  ops/s
compiledWithCheck  thrpt     6  526,849 ± 96,101  ops/s

Kompilovaný regex je tři-a-něco-krát rychlejší než nekompilovaný. Ale ten zaostává za případem, kdy se vyhodnocování regexu úplně vyhnu. Přitom regex by měl selhat hned potom, co přečte první znak a tedy by neměl dělat víc práce, než explicitní kontrola. Ale očividně má nezanedbatelnou režii.

Pokud regex nebude často prováděn, je rychlejší dělat něco jako:

// zkompilovaný regex
val linkRegex = """(?x) " ([^"]+?) " : \[ ([^\]\n]+?) \]""".r
val linkCheck = "\":["

// používat ho následovně
if (txt.contains(linkCheck)) {
  linkRegex.replaceAllIn(txt, m => makeLink(m))
}

Narychlo zkontrolovat, jestli zdrojový řetězec obsahuje nějakou fixní část regexu a teprve potom nechat regex dělat těžkou práci. Ale jako v případě každé optimalizace je třeba profilovat a benchmarkovat.

Tento přístup zrychlil renderování textu asciiblogu o 75%.

Relevantní čtení:




26. 11. 2017

Java, Scala a regulární výrazy


Poslední dobou zjišťuji, že práce s regulárními výrazy v Javě a Scale je neuspokojivá, matoucí a API nikdy nenabízí přesně to, co bych chtěl.

Scala má krásně vypadající metodu Regex#replaceAllIn(String, Match => String). Na první pohled je všechno jasné: Každý výskyt regulárního výrazu v prvním argumentu je předán funkci Match => String. Objekt typu Match reprezentuje výskyt vzoru. Funkce ho vezme jako argument a vyprodukuje string, který ho nahradí. Co by na tom mohlo být komplikovaného, žeano?

Jednoduché volání, které na první pohled vypadá jako identita, není bezpečné:

regex.replaceAllIn(str, (m: Match) => m.group(0))

m.group(0) představuje celou shodu (ostatní indexy jsou uzávorkované výrazy v regexu, m.group(1) jsou první závorky, m.group("named") jsou závorky pojmenované named) .

V čem je problém?

V tom, že výsledek funkce se nepoužije verbatim pro nahrazení, ale je interpretován. Každý výskyt řetězců $0 - $9 je interpretován jako podvýraz a \$ znamená literál $. Když vstupní data obsahují dolar následovaný číslem, skončí to přinejlepším výjimkou, přinejhorším to udělá něco nečekaného. A to není to, co by člověk čekal nebo chtěl. V dokumentaci je toto chování dobře popsané, ale nepůsobí to, že by to tak mělo být.

Korektní verze by měla vypadat takhle:

regex.replaceAllIn(str, (m: Match) => Regex.quoteReplacement(m.group(0)))

Interpretace stringu je přežitek starších API, které nenabízely nahrazení přes fukci:

regex.replaceAllIn(str, replace: String)

V tomto případě nemůžu specifikovat logiku, která vypočítá nahrazovací string a proto jsou použity zpětné reference jako $0 - $9. Ty poskytují aspoň nějakou rudimentární flexibilitu.

Problém je v tom, že výsledný string musí být escapován a hned potom je interpretován (pro $ a \$), což je zbytečná práce, která stojí zbytečný čas.

Ocenil bych jasné API s metodami jako

které jasně říkají, co dělají a uživatel si může vybrat přesně to chování, které potřebuje.


21. 11. 2017 Java - zostřování obrázků
7. 10. 2017 Koherence cache a atomické operace
5. 10. 2017 Nejrychlejší hashmapa pod sluncem
23. 9. 2017 Dekódování x86 instrukcí
21. 9. 2017 Energetická efektivita programovacích jazyků
19. 9. 2017 Programming and Performance podcast
17. 9. 2017 B-stromy, persistence, copy-on-write a Btrfs
15. 9. 2017 Rust a parsery
13. 9. 2017 Velké stránky paměti
11. 9. 2017 Deanonymizace agregovaných dat
9. 9. 2017 Optimalizující kompilátor
7. 9. 2017 Identifikace zašifrovaných videí
5. 9. 2017 Heterogenní persistentní kolekce
3. 9. 2017 JVM Anatomy Park
1. 9. 2017 Datacentrum z mobilů
30. 8. 2017 Propustnost pamětí
28. 8. 2017 Branch prediction (implementace v procesorech)