0xDEADBEEF

RSS

Poznámky ke slajdům k přednášce, kterou jsem nikdy nepřednášel

12. 1. 2019

Před nějakou dobou jsem na twitter hodil slajdy z lightning talku, který bych mohl mít na jOpenSpace, kdybych tam jel. Poskládal jsem ho za pár minut a byl strukturovaný jako seznam témat, o kterých bych mohl z patra mluvit, ale nebudu (možná jen pod pohrůžkou střelnou zbraní) a potom nakonec jedno téma, které si zaslouží rozvedení. Tento článek je komentář k jednotlivým slajdům.

První bod se věnoval novinkám a vývoji architektur CPU, GPU a dalších procesorů. Protože, ač to tak nemusí vypadat, děje se toho poměrně hodně. Chipzilla může mít problémy, ale to nic neznamená.

Vektorové procesory se vrací na výsluní. NEC vyrábí SX-Aurora TSUBASA (info), RISC-V finišuje Vector Extension Proposal a dokonce se pro ARM chytá vektorové rozšíření SVE. I Agner Fog přihodil své želízko do ohně s návrhem architektury ForwardCom, která také počítá s vektory.

Objevilo se několik zmínek o dataflow strojích. Microsoft už roky koketuje s experimentálním čipem E2 (který vzešel z výzkumného projektu TRIPS) a také se objevily kusé zprávy o projektu dataflow CPU od Intelu. Nebylo by to poprvé, co myšlenky Chipzilly zabrousily mimo svět x86.

Divoce se spekuluje o PIM neboli Processor-in-memory. V současných architekturách většinu energie spotřebují přesuny dat z RAM do procesoru a zpátky. Dává proto smysl obohatit paměť o výpočetní prostředky a přesunout na ně určité nepříliš komplikované kalkulace/transformace, zvlášť v době, kdy paměťové moduly mají několik vrstev propojených TSV a jedna z nich již obsahuje logiku.

První návrhy PIM čipů předpokládaly že na jednom kusu křemíku se bude vedle pamětí nacházet i hlavní vektorové CPU, které využije vysokou interní propustnost. To by znamenalo zcela novou architekturu a proto se nikdy nedočkaly realizace.

Modernější návrhy počítají s běžnými CPU doplněnými o chytré paměti. Jedna publikace od Googlu ukázala, že PIM by mohla značně snížit spotřebu energie a zrychlit některé aplikace na mobilních telefonech. Typicky všechny rutiny, které se dotýkají velkého množství paměti by mohly benefitovat z PIM: memset, memmove, transpozice matic, nulování paměti, rutiny garbage collectoru (sen o HW podpoře pro GC žije dál). Reálná a použitelná implementace má své problémy, které ke třeba vyřešit (koherence cache, mapování virtuální paměti a TLB), ale i tak by to mělo stát za vynaložené úsilí.

Tady bych se mohl věnovat některým řadícím algoritmům, které nejsou tak známé, jak by si zasloužily: 3-way radix quicksort, LSD radix sort, RMS, burst sort, radix sort na komprimovaných prefixech a paralelní řazení.

Ale možná nic z toho brzy nebude důležité. Google publikoval paper o tom, jak se stroj naučil řadící algoritmus efektivnější než quicksort.

Tony Hoare je jediný člověk, jehož wiki stránky pravidelně kontroluji, abych se přesvědčil, že je stále naživu. Bojím se světa ve kterém nebude bít srdce člověka, který objevil quicksort v roce 1959 jako sázku se svým nadřízeným. Tony Hoare dostal za úkol napsat shellsort, ale řekl, že má lepší a rychlejší algoritmus. Jeho šéf nevěřil a vsadil se o šestipenci, že to není možné. Tony sázku vyhrál a s ním i my všichni. V dnešní měně vsazená částka odpovídá přibližně polovině libry a tedy 16 korunám. Jeden z nejdůležitějších algoritmů nestál ani dvacku.

Tohle mělo být něco o benchmarkování, mechanical sympathy, virtuálních strojích a tak podobně, jak psát rychlý kód + zajímavostianomálie (jako třeba, že regexy jsou pomalé) na které jsem v poslední době narazil.

Něco o umělé inteligenci, automatizaci a nutnosti komunismu. O tom píšu jinde..

Tady se konečně dostávám k pořadu večera: Odhadůmlocality sensitive hashing - technice, která umožňuje rychle najít (většinu) podobných položek podle určité metriky bez toho, abych musel počítat podobnost se vším. LSH je založena na hašování, ale jiném než to, na kterém staví hashmapy. Klasická hash funkce nezachovává korelace vstupů - dva podobné vstupy nemají stejné hashe. LSH je vystaveno na opaku - hashe podobných vstupů jsou si podobné a čím jsou si vstupy podobnější, tím větší šance je, že hashe budou identické.

To bylo ale hlavní téma, ne jen série preambulí a nemám prostor tu psát víc.


+1: Za pozornost stojí tento článek, o tom jak rozšířit klasický minhash pro reálné váhy.

Minifikace HTML5

4. 1. 2019

HTML5 standard je poměrně laxní v tom, co vyžaduje po validních dokumentech. Mnoho prvků, které jsou nutné pro náležité XML, je možné vynechat a trochu tak zmenšit výsledný soubor.

Uvozovky kolem hodnot atributů můžeme opominout, pokud ty neobsahují mezeru nebo znaky \t \r \n \f " ' = < > `. Následující tagy jsou v očích HTML5 zcela validní.

<div class=x></div>
<a href=https://k47.cz></a>
<a href=../index.html></a>
<a href=#fn1></a>

To ale také znamená, že fragment <br class=xx/> odpovídá <br class="xx/"> - zpětné lomítko ukončující nepárový tag se bere jako součást atributu.

HTML5 naštěstí dovoluje u takzvaných void elementů (area, base, br, col, embed, hr, img, input, link, meta, param, source, track, wbr) toto lomítko vynechat. <br><br/> jsou podle nekonečné moudrosti HTML5 identické, jen jeden z nich je o bajt kratší.

Mnoho párových tagů není třeba uzavírat nebo dokonce uvádět, protože je parser dokáže vyvodit z kontextu. Jde především o html, head, body nebo koncové </p></td>.

Následující dokument představuje korektní exemplář moderního webu.

<!DOCTYPE html>
<meta charset=utf-8>
<title>0xDEADBEEF</title>
<h1>Minifikace HTML5</h1>
<p>lorem ipsum
<p>dolor blablabla

Pochopitelně, když se podíváte do typických stránek, ty obsahují mnoho jiných neefektivit. Url bývají absolutní, řádky začínají mezerami kopírující zanoření zdrojového kódu, který dokument vyprodukoval a tak podobně. Komprese rozdíly částečně vyrovná, ale podle toho, co jsem vypozoroval, tak velikosti komprimovaného dokumentu nepomůže zkrácení tokenů (gzip je nahradí nehledě na délku), ale jejich eliminace.

Poslední tip: HTML entity je možné nahradit ekvivalentními unicode znaky, které bývají kratší. Například místo místo &nbsp; je možné použít NO-BREAK SPACE, které je v utf-8 zapsáno dvěma bajty 0xC2 0xA0.

Efektivita této minifikace je ale přinejlepším sporná, když typický web začne tím, že stáhne 1MB javascriptu.

Java IO & NIO - jak nejrychleji načíst soubor z disku

24. 12. 2018

Bez většího důvodu jsem se začal zajímat jak v Javě co nejrychleji načíst data z disku. Java nabízí několik způsobů, jednak starý java.io způsob přes FileInputStreamBufferedInputStream a pak novou java.nio cestu přes FileChannel. Je v nich nějaký rozdíl, popřípadě jak velký?

Proto jsem napsal JMH benchmark (zdroják níže), který načte zdrojové texty části k47čky sražené do jednoho souboru (9.7 MB textu) a počítá kolik je v něm '\n' bajtů. Není nijak důležité, co se s daty dělá, jen s nimi chci dělat co nejmenší množství práce, která může být aspoň okrajově užitečná.

Na OpenJDK 10.0.2 jsou výsledky následující:

Benchmark                                     (bufferSize)   Mode  Cnt    Score    Error  Units
readFile.countNewlines_io_InputStream                 1024  thrpt    4  108,321 ±  2,235  ops/s
readFile.countNewlines_io_InputStream                 8192  thrpt    4  206,031 ±  1,553  ops/s
readFile.countNewlines_io_InputStream                65536  thrpt    4  219,326 ±  4,065  ops/s
readFile.countNewlines_io_BufferedInputStream         1024  thrpt    4  177,596 ± 36,830  ops/s
readFile.countNewlines_io_BufferedInputStream         8192  thrpt    4  206,120 ±  8,747  ops/s
readFile.countNewlines_io_BufferedInputStream        65536  thrpt    4  226,468 ±  1,681  ops/s
readFile.countNewlines_nio                            1024  thrpt    4  119,426 ±  1,142  ops/s
readFile.countNewlines_nio                            8192  thrpt    4  213,778 ±  1,433  ops/s
readFile.countNewlines_nio                           65536  thrpt    4  168,841 ±  3,932  ops/s
readFile.countNewlines_nio_newInputStream             1024  thrpt    4  108,176 ±  4,005  ops/s
readFile.countNewlines_nio_newInputStream             8192  thrpt    4  176,283 ±  0,728  ops/s
readFile.countNewlines_nio_newInputStream            65536  thrpt    4  220,651 ±  1,712  ops/s
readFile.countNewlines_nio_newInputStream_buffered    1024  thrpt    4  173,761 ± 36,901  ops/s
readFile.countNewlines_nio_newInputStream_buffered    8192  thrpt    4  199,666 ± 13,302  ops/s
readFile.countNewlines_nio_newInputStream_buffered   65536  thrpt    4  220,418 ±  0,790  ops/s

Je z nich vidět, že mezi jednotlivými metodami není více méně žádný rozdíl. Záleží jen na granularitě operací. Když čtu data do pole/ByteBufferu velikosti 64kB, je to rychlejší než v případě 1kB bufferu. BufferedInputStream obsahuje vlastní buffer (ve výchozím stavu 8kB) a to zlepší výkon, když čteme data do malých 1kB polí.

Nějaká anomálie se vyskytuje v případě nio a 64kB bufferu, ale té bych nepřikládal velkou váhu. Možná jde o důsledek použití přímého buffer alokovaného v nativní paměti (OS by do něj měl přímo zkopírovat data a nemusí je nejdřív kopírovat do C pole a z něj pak do Java pole, takže by to mohlo být o něco efektivnější), kdo ví. Když čtu data s 8kB bufferem, v tomto případě nezáleží, jakým způsobem se to děje. Pokud se tedy soubor nachází v cache OS a nejsem limitován propustností disku (testy čtou téměř 2GB/s).

To je jedna věc. Druhou je, co se s těmi bajty bude dít potom. Protože když do rovnice započítám utf-8 dekódování, propustnost spadne 5-10x.


Benchmark:

import org.openjdk.jmh.annotations._

@State(Scope.Thread)
class readFile {
  import java.nio.file._
  import java.nio._
  import java.io._

  val f = "k47merged.txt"

  @Param(Array("1024", "8192", "65536"))
  var bufferSize: Int = _

  @Benchmark
  def countNewlines_nio = {
    var count = 0
    val bb = ByteBuffer.allocateDirect(bufferSize)
    val ch = new RandomAccessFile(f, "r").getChannel
    while (ch.read(bb) != -1) {
      bb.flip()
      while (bb.hasRemaining) {
        if (bb.get == '\n') count += 1
      }
      bb.clear()
    }
    ch.close()
    count
  }

  @Benchmark
  def countNewlines_nio_newInputStream =
    countNewlines(Files.newInputStream(Paths.get(f)), bufferSize)

  @Benchmark
  def countNewlines_nio_newInputStream_buffered =
    countNewlines(new BufferedInputStream(Files.newInputStream(Paths.get(f))), bufferSize)

  @Benchmark
  def countNewlines_io_InputStream =
    countNewlines(new FileInputStream(f), bufferSize)

  @Benchmark
  def countNewlines_io_BufferedInputStream =
    countNewlines(new BufferedInputStream(new FileInputStream(f)), bufferSize)

  def countNewlines(is: InputStream, buffer: Int) = {
    var count = 0
    val bb = new Array[Byte](buffer)
    var n = is.read(bb)
    while (n != -1) {
      var i = 0; while (i < n) {
        if (bb(i) == '\n') count += 1
        i += 1
      }
      n = is.read(bb)
    }
    is.close()
    count
  }
}

+1: Dodatek pro úplnost: mmap v případě takto velkého souboru není rychlejší.

Průnik množin ve Scale

3. 11. 2018

Dneska je čas na jeden malý trik jak ve Scale vypočítat velikost průniku dvou množin. Když mám dvě množiny asbs, dá se to zařídit vytvořením množiny průniku.

as.intersect(bs).size

Jde o přímé řešení, které popisuje, o přesně dělá, ale je je třeba alokovat dočasnou kolekci a to není nejrychlejší. Bez alokací se to samé dá zařídit takhle:

var i = 0
for (a <- as if bs.conains(a)) i += 1

To je zase poněkud zdlouhavé, nefunkcionální a také není na první pohled jasně vidět, co smyčka přesně dělá. Existuje ale ještě jedno řešení, které využívá bohatého API kolekcí Scaly, která je mnohem elegantnější:

as.count(bs)

Metoda count spočítá kolik prvků z množiny as odpovídá predikátu. Místo funkce je ale zadána druhá množina. Funguje to proto, že množina je ve Scale zároveň funkce testující členství elementu:

class Set[T] extends T => Boolean

Kompilátor pod kapotou kód přepíše na

as.count { a => bs.apply(a) }

což dělá to samé, co

as.count(bs.contains)

tedy počítá to počet prvků první množiny, které jsou přítomny v té druhé, neboli velikost průniku.

Podobné kousky je možné provádět i s mapami, které jsou ze své podstaty (parciální) funkce z klíčů na mapované hodnoty:

class Map[K, V] extends K => V

Dá se tak napsat třeba jednoduché generování slugů do url z titulků článků:

val from = "áčďéěíňóřšťúůýž "
val to   = "acdeeinorstuuyz-"
val txl = (from zip to).toMap withDefault (x => x)
def makeSlug(title: String) = title.map(txl)

pozn: Když chcete počítat průniky množin opravdu rychle, mám na tohle téma celý článek.

Čím nahradit Scala.XML

23. 10. 2018

Ve Scale je možné v programu zapisovat přímo XML literály. Ještě pořád, ale už ne příliš dlouho. Martin Odersky (a jeho gang) není jejich fanda, už roky se jich chce zbavit a ve verzi 2.13 se mu to možná konečně podaří.

Technicky vzato XML literály nejsou třeba. Jazyk od verze 2.10 disponuje interpolace stringů, která dokáže tuto funkcionalitu beze zbytku nahradit. S ní bychom psali místo

val t = <tag>body</tag>

o něco málo delší

val t = xml"<tag>body</tag>"

Když padne vestavěné XML, parser se zjednoduší, XML v něm nebude mít výsadní postavení a nebude vázané na neohrabané API scala.xml. Půjde jen o další z mnoha uživatelských knihoven. Z těchto důvodů bychom s ním neměli dlouhodobě počítat. Čím ho tedy můžeme nahradit?

XML literály jsou často používané na generování RSS, Atomu a jiných XML výstupů. Vytvoří se DOM, pak je okamžitě přeměněn na řetězec a zahozen.

(<rss version="2.0">
<channel>
  <title>{blog.title}</title>{
    articles.map(a => <item>
      <title>{a.title}</title>
      <guid isPermaLink="true">{urlOf(a)}</guid>
      <pubDate>{rssDate(a.date)}</pubDate>
      <description>{mkBody(a)}</description>
    </item>)
  }</channel>
</rss>).toString

To vypadá přehledně, ale má to jeden nedostatek: Postaví se kompletní DOM se všemi alokacemi jen proto, aby byl okamžitě zahozen. V případě generování výstupů bude stačit něco jednoduššího. Nepotřebuji reprezentaci XML stromu, nepotřebuji ho zkoumat a měnit, stačí jen přímo vypsat jeho obsah. Pokud možno přehledně.

Tento účel splní starý dobrý XMLStreamWriter zabalený do přehledného API. Vytvoření stejného RSS dokumentu pak může vypadat nějak takhle:

XMLSW.document { w =>
  w.element("rss", Seq("version" -> "2.0")) { w =>
    w.element("channel") { w =>
      w.element("title", blog.title)
      for (a <- articles) {
        w.element("item") { w =>
          w.element("title", a.title)
          w.element("guid", Seq(("isPermaLink", "true")), urlOf(a))
          w.element("pubDate", rssDate(a.date))
          w.element("description", makeBody(a))
        }
      }
    }
  }
}

Není třeba volat writeStartElement a pak odpovídající writeEndElement, tak aby se nekřížily, lexikální blok se o postará o uzavírání tagů a jejich vnořování. Výsledek je měřitelně rychlejší než generování pomocí scala.xml, ale ukázalo se, že čísla jsou nestálá a někdy divoce skáčou.

Příčinu odhalí pohled do zdrojáků. Z nich je vidět, že XMLStreamWriter je (jako mnoho javovských API) určený pro znovupoužití, ne jako jednoduchý nástroj, který se použije jednou a pak je zahozen. Interní implementace alokuje mnoho objektů, některé z nich nutné pro správné zacházení s komplikacemi XML (jmenné prostory), jiné nutné pro správné fungování rozhraní (zásobník otevřených tagů) a další zcela zbytečné (neptejte, hrůzy, na které jsem narazil, mě do dneška budí ze spaní).

Když ale používám zjednodušené API, které samo uzavírá tagy, můžu pod ním podtrhnout ubrus a nahradit XMLStreamWriter za vlastní kód. Když vynechám některé záludnosti XML jako jmenné prostory, není to nic komplikovaného. Escapování XML je triviální - stačí si hlídat jen znaky & < > " a ten poslední jen v některých případech. Dohromady pod 80 řádků kódu, který generuje XML za letu, nealokuje skoro nic a je rychlejší než XMLStreamWriter.


+1: Pro extrakci dat z XML je stále nejšikovnější starý dobrý XPath. Kdysi jsem napsal malou knihovnu xpath.scala, která XPath dodá trochu typovosti.

Novinky kolekcí ve Scale 2.13

11. 10. 2018

Nadcházející verze Scaly 2.13 přinese jednu velkou změnu: Nový framework kolekcí. Došlo k jejich internímu překopání, zjednodušení a celkovému uhlazení (konečně funkční mechanismus pohledů). Velká část z těchto změn by měla být interní záležitostí. Nové kolekce sice nebudou binárně kompatibilní s těmi ve verzi 2.12 (zmizí například (ne)oblíbený hlavolam CanBuildFrom). Bude třeba překompilovat, ale na úrovni zdrojových textů by kompatibilita měla být z velké části zachována.

Kromě toho, ale přibylo několik metod, které mi vždycky chyběly a musel jsem je tisíckrát obcházet a nahrazovat. Tady je seznam těch, které jsem objevil.

In place operace nad měnitelnými kolekcemi

O řazení na místě se stará scala.util.Sorting.stableSort, který interně používá buď java.util.Arrays.sort nebo, pokud používám vlastní Ordering, merge sort. To je malý nedostatek, protože merge sort potřebuje alokovat pomocné pole a není tedy úplně in place.

Vylepšené groupBy metody:

def groupMap[K, B](key: A => K)(f: A => B): immutable.Map[K, Seq[B]]
def groupMapReduce[K, B](key: A => K)(f: A ⇒ B)(reduce: (B, B) ⇒ B): immutable.Map[K, B]

groupMap je přesně to, co mi chybělo. Následující dva řádky mají identické chování.

xs.groupMap(key)(f)
xs.groupBy(key).map { case (k, vs) => (k, vs.map(f)) }

Je to jednak kratší a navíc nejsou třeba alokace dočasných kolekcí.

xs.groupMapReduce(keyF)(mapF)(redF)
xs.groupBy(keyF).map { case (k, vs) => vs.map(mapF).reduce(redF) }

collectFirst

collect je užitečná metoda, která kombinuje mapfilter. Jako argument se ji předá parciální funkce, elementy, pro které je definovaná budou zachovány a transformovány. Následující dva řádky se chovají identicky:

xs.collect { case x if f(x) => g(x) }
xs.filter(f).map(g)

Není třeba vytvářet kolekci mezivýsledku + parciální funkce nemusí obsahovat jen jeden predikát, ale libovolný pattern matching (ideální například pro regexy)

Pro souměrnost přibyla collectFirst, které funguje jako find po níž následuje map.

Bezpečná maxima a minima

Dřívě existovaly jednak metody headlast, které pro prázdnou kolekci vyhodily výjimku a pak bezpečné metody headOptionlastOption, ale pro získání minim a maximu existovaly jen výjimky házející verze. Ve verzi 2.13 bude tento nedostatek napraven a přibudou metody maxOption, minOption, maxByOption, minByOption.

V podobném duchu se nesou nové metody parsující string na čísla: toInt přibude bezpečný bratříček toIntOption. Možná jde o drobnosti, ale na druhou stranu vyplňují mezery v ortogonalitě.

Různé užitečné drobnosti

xs.distinctBy(f)

// je identické jako

val ys = xs.reverse.map { x => (f(x), x) }.toMap.values.toSet
xs.filter(ys)
xs.partitionWith(f)

// stejné jako

val ys = xs.map(f)
val ls = ys.collect { case Left(l) => l }
val rs = ys.collect { case Right(r) => r }
(ls, rs)

Nové datové struktury

To jsou některé zajímavé změny, které přijdou. Scala 2.13 je zase jedna verze, která po dlouhé době vypadá zajímavě.


Dodatek: Pořád mi chybí metoda top(k), která by vrátila k největších elementů (a její varianty topkBy(k, f) atd). Nejpohodlněji se to samé dá zařídit pomocí xs.sortBy(f).take(10), ale jde o neoptimální řešení s komplexitou O(n log(n)). To samé se dá zařídit přes haldu nebo quickselect v čase O(n log(k)), ale musím všechno napsat sám.

Co vlastně benchmarkujete?

4. 8. 2018

Před nějakou dobou jsem narazil na článek, který se snažil testovat rychlost a paměťové nároky asociativních polí a různých variant objektů v PHP. Závěr byl ten, že objekty jsou skoro ve všech ohledech buď srovnatelné nebo lepší než asociativní pole, hlavně co se týká paměťových nároků1 .

Ale stačil jediný pohled, abych věděl, že je něco špatně. Benchmark asociativních polí vypadal takhle:

<?php
declare(strict_types=1);
error_reporting(E_ALL | E_STRICT);
const TEST_SIZE = 1000000;
$list = [];
$start = $stop = 0;

$start = microtime(true);

for ($i = 0; $i < TEST_SIZE; ++$i) {
  $list[$i] = [
    'a' => random_int(1, 500),
    'b' => base64_encode(random_bytes(16)),
  ];
}

ksort($list);

usort($list, function($first, $second) {
  return [$first['a'], $first['b']] <=> [$second['a'], $second['b']];
});

$stop = microtime(true);
$memory = memory_get_peak_usage();
printf("Runtime: %s\nMemory: %s\n", $stop - $start, $memory);

Co tento kus kódu měl měřit? Vytváření asociativních polí (v dalších variantách pak objektů) a pak práci s nimi, přece.

Ne tak docela. Děje se toho podstatně víc. Vytváření polí, volání funkce random_int, random_bytes, base64_encode, pak řazení podle klíče, která je více méně noop, další řazení podle obsahu interních struktur a alokace dočasných polí.

Na mém Haswell stroji s PHP 7.2.4 měřený úsek běží 8 vteřin. Znamená to, že to co mě zajímá trvá 8 vteřin? Ne, celá ta věc trvá osm vteřin. Kolik z nich jsem strávil měřením rychlosti přístupů do polí/objektů? To není bez podrobnějšího zkoumání možné říct.

Začal jsem se proto vrtat, kolik času zaberou jednotlivé fáze a výsledky jsou zajímavé (kdyby nebyly, nic bych nepsal).

PHP je naštěstí primitivní runtime, který se nesnaží o chytré optimalizace a měření je proto jednoduché (jak říkal Aleksey Shipilёv). Můžu například udělat v podstatě jakoukoli změnu a nebát se, že chytrý JIT kompletně eliminuje veškerý kód bez pozorovatelných efektů.

Samotná konstrukce polí/objektů je v podstatě zdarma. ksort řadí podle již seřazeného numerického klíče, je také zadarmo a nepřináší žádnou užitečnou informaci o chování datových struktur.

A pak jsou tu také funkce random_int, random_bytes, base64_encode. První dvě generují kryptograficky bezpečná náhodná čísla, což nejspíš nebude zadarmo. A také není. Jen tyto funkce zaberou jednu vteřinu času, tedy ±12% zbytečné režie, která opět neříká nic užitečného.

Teď poslední řazení. Porovnávací funkce uvnitř využívá spaceship operátor <=> mezi dvěma nově vytvořenými poli. To je velice elegantní, ale dočasné datové struktury je třeba alokovat a i když každá alokace je levná (viz pár odstavců výše), provádí se jich O(nlog(n)) a to se nastřádá.

Když to změním na

usort($list, function($first, $second) {
  $cmp = $first['a'] <=> $second['a'];
  if ($cmp !== 0) return $cmp;
  return $first['b'] <=> $second['b'];
});

test běží o 3 vteřiny rychleji. Nejde jen o případ optimalizace benchmarku, ale důkaz, že ±37% času tráví alokacemi, dealokacemi a počítáním referencí, tedy ne tím, co měl měřit. Dohromady tráví 50% času zbytečnou režií a výsledky jsou v ní utopené.

Závěry benchmarku o relativních rychlostech polí a různých objektů jsou v tomto případě stále platné, jen poměry se liší. Režie je částečně maskovala a bez ní jsou přibližně dvakrát větší.

Benchmarkování je komplikované a takhle by se to nemělo dělat. Je nutné izolovat měřený efekt a i tak čísla jsou pouhá data, bez pochopení, proč jsou taková jaká jsou, nemají význam. Říct "X je z nějakého důvodu rychlejší než Y a proto bychom ho měli používat", není dobrý nápad.

Jak varuje JMH: Do not assume the numbers tell you what you want them to tell.


  1. Ale i toto je možné optimalizovat. Virtuální stroj může asociativní pole se stejnou strukturou zkompilovat do podoby, která je interně k nerozeznání od objektů. Self to začal dělat v osmdesátých letech a dnes na tom stojí všechny moderní JavaScriptové VM. Pokud se chcete dozvědět víc, sledujte tento kurz.

Java, Scala a regulární výrazy #5 - posesivní regexy a StackOverflowError

28. 7. 2018

Minule jsem psal o hladových a líných regexech, naznačil jejich implementaci a ukázal případ, kdy líný regex může předejít přetečení zásobníku a StackOverflowError.

V java implementaci regexů existuje ještě třetí druh opakování, vedle greedylazy (hladových a líných), jsou ještě possesive regexy. Zapisují se jako .*+, .++, .?+.{m,n}+, jsou hladové, nikdy nedělají backtracking a v případech, kdy by obyčejné hladové opakování backtrackovalo, selžou.

Například regex (ve Scale string se třemi uvozovkami je brán jak je, není třeba v něm skoro nic escapovat, ideální pro regexy)

"""(?x)  " ( \\" | [^"] )++ "  """.r

začne hledat od první dvojité uvozovky, hladově konzumuje všechno, co je escapovaná uvozovka nebo jakýkoli jiný znak kromě uvozovky, až narazí na ukončovací uvozovku a když ji najde, nikdy neustoupí o krok zpět. Chová se tedy do jisté míry atomicky (kdo neví, tak (?x) na začátku znamená, že mezery se ignorují).

Posesivní regexy mohou vést k odmítnutí některých stringů, které by hladové nebo líné regexy přijaly. Ale na druhou stranu regex selže brzo a nebude zkoušet všechny permutace. Jde tedy o druh optimalizace.

Často právě posesivní regexy jsou to, co člověk chce. Hodí se, když chci hledat až do určitého symbolu, který jasně indikuje, kde posesivní regex skončí. Často mívají formu a [^a]++ a.

Protože nedělají backtracking jsou implementovány iterativně a nemůžou skončit StackOverflowError.

Například následující dva regexy testují to samé.

("a " * 1000000).matches("(a+ )+")
("a " * 1000000).matches("(a+ )++")

První skončí StackOverflowError, ale druhý doběhne v pořádku. (Kdo neví, tak násobení stringu ve Scale ho opakuje.)

Navíc: Protože nedělají backtracking, logicky u nich nehrozí případy katastrofického backtrackingu.

Opět dva případy: První je obyčejný hladový regex, druhý je possesive regex.

"ACCCCCCCCCCCCCCCCCCCCCCCCCCCCCCX".matches("A(B|C+)+D")
"ACCCCCCCCCCCCCCCCCCCCCCCCCCCCCCX".matches("A(B|C++)+D")

Druhý dojede v mikrosekundě, ale první bude trvat celou věčnost právě proto, že začne zkoušet všechny možnosti a dojde ke kombinatorické explozi.

Posesivní regex bude vyhodnocován takto: A pasuje, zkusí B, nic, C++ sedne a sebere všechna C, zkusí D, selže, ++ zajistí, že nevrátí žádné C zpátky, nezkusí další varianty a celý regex selže.


Pozn:

EDGE, TRIPS a hon za vyšším ILP

26. 7. 2018

Tiskem proletěla zpráva, že Microsoft portoval Windows a Linux na vlastní experimentální CPU architekturu E2. Pročetl jsem pár publikací o architektuře a na pohled vypadá zajímavě. Tedy aspoň z technického pohledu je ambiciózní, jestli povede k reálnému produktu, si netroufám odhadovat.

To nejlepší na začátek: Microsoft se rozhodl vytvořit dataflow stroj. I když ne tak úplně, jde o omezený dataflow v technickém žargonu označovaný EDGE - Explicit data graph execution.

Článek An Evaluation of the TRIPS Computer System poskytne detaily o prvotní EDGE architektuře TRIPS, vyvíjené v akademickém prostředí. Její autoři se snažili dosáhnout vysokého ILP (instrukční paralelismus) v malém a úsporném procesoru a mít všechny výhody out-of-order bez křemíkové a energetické režie OoO.

CPU provádí bloky až 128 instrukcí bez skoků (kompilátor se je snaží nahradit predikací). Blok commitne atomicky jako celek a uvnitř se chová jako dataflow. Instrukce nezapisují výsledky do registrů, ale přímo je směřují závislým instrukcím. Pokud je blok dostatečně velký, může obsahovat velké množství instrukčního paralelismu (TRIPS jádro má 16 ALU) a díky jeho explicitní dataflow povaze je prováděn jako na OoO jádře. Závislosti mezi instrukcemi nemusí za běhu analyzovat procesor, ale jsou identifikovány už v procesoru.

Pro představu to může vypadat nějak takhle (hypotetický pseudokód):

i1: READ R1 i3     // přečte z globálního registru a data nasměruje instrukci i3
i2: READ R2 i3 i4  // to samé, ale pošle je instrukcím i3 a i4 najednou
i3: ADD i4         // až obdrží data, sečte je a výsledek pošle instrukci i4

Toto uspořádání řeší problémy, kterými trpěly obecné dataflow architektury. Ale jako obvykle komplikované větvení kódu se nekamarádí s ILP, protože vede k malým blokům instrukcí.

Paper Dynamic Vectorization in the E2 Dynamic Multicore Architecture představuje další pokrok již pod taktovkou Microsoftu. Jde o první nástřel z roku 2010, ale přesto ukazuje několik zajímavých inovací, jako například dynamické spojování několika fyzických jader do jednoho logického. Jedno fyzické jádro v gangu provádí nespekulativní kód a ty ostatní jsou použité pro spekulace. Po spojení jader tak vznikne agresivní superskalární OoO CPU. To dodá procesoru flexibilitu - na jedné straně v něm může běžet mnoho malých jader na druhé několik málo velice mocných jader pro jednovláknové programy.

Další chuťovkou je vektorový mód, kterého je dosaženo kombinací všech skalárních ALU v jádře. Nepotřebuje tedy novou sadu registrů nebo nové funkční jednotky, ale používá všechny existující hardwarové prostředky.

Všechno tohle EDGE šílenství je honem za stále ILP - TRIPS měl 16 ALU a výzkumníci dospěli k závěru, že ideální stroj s nekonečným množstvím funkčních jednotek a masivním instrukčním blokem by dokázal provádět desítky až stovky instrukcí každý takt. Jeden z prototypů E2 měl údajně mít 32 ALU.

Za ILP se dříve hnalo Itanium a všichni víme jak to s tímto dítkem Intelu a HP dopadlo. O podobný kousek se snaží i architektura Mill, ale jde cestou kompletně statického VLIW. Historie nedává příliš optimismu, že by to mohlo vyjít.

Jedním z mnoha problémů Itania byl fakt, že potřebovalo pokročilý kompilátor, který by dokázal ohnout kód tak, aby sedl na masivně paralelní spekulativní predikované srdce čipu. Stejně to budou potřeboval EDGE (a Mill) procesory. Pokud nebudou k dispozici, můžou skončit jako produkty s nevyužitým potenciálem.

Ale také nemusí, když končí moorův zákon, efektivita, i když v porovnání s exponenciálními zisky minulosti jen marginální, může hrát značnou roli.


K tématu:

Striktní a líné jazyky

24. 6. 2018

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. 2018 Syntéza datových struktur a programů
9. 6. 2018 ISPC, SPMD a SIMD
6. 4. 2018 Konec Intelu, konec Moorova zákona, konec světa takového jaký známe
31. 1. 2018 Meltdown, Spectre a branch prediction
28. 12. 2017 Poznámky k výkonu
19. 12. 2017 Java, Scala a regulární výrazy #4 - líné regexy a StackOverflowError
5. 12. 2017 Java, Scala a regulární výrazy #3 - rychlost
27. 11. 2017 Java, Scala a regulární výrazy #2 - rychlost
26. 11. 2017 Java, Scala a regulární výrazy
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)



píše k47 (@kaja47, k47)