0xDEADBEEF

RSS

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 as a bs, 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 map a filter. 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 head a last, které pro prázdnou kolekci vyhodily výjimku a pak bezpečné metody headOption a lastOption, 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 greedy a lazy (hladových a líných), jsou ještě possesive regexy. Zapisují se jako .*+, .++, .?+ a .{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.

Syntéza datových struktur a programů

21. 6. 2018

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.

ISPC, SPMD a SIMD

9. 6. 2018

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.

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

6. 4. 2018

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
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)