Kompaktní stringy

S tímhle blogem možná skončím. Možná. Rozhodně sem vysypu všechny rozepsané články z bufferu a pak se uvidí.

Četl jsem Java 9: Compact Strings Vojtěcha Růžičky o kompaktní reprezentaci řetězců. Stringy, jejichž znaky spadají do ASCII, jsou reprezentovány kompaktně jako byte[]. V článku jsem narazil na:

Java 9 brings a new improved string, which in most cases, will reduce String memory consumption to half.

To není tak úplně pravda. Platí to asymptoticky pro nekonečně dlouhé stringy, ale pro ty kratší to nebude tak slavné. String má konstantní režii, která není úplně zanedbatelná. Javě je String tvořen dvěma objekty. String objekt obsahuje ukazatel na pole charů (v Javě 9 pole bytů). V paměti to vypadá takhle (na 64 bitovém stroji s komprimovanými pointery):

Oba objekty začínají 12B hlavičkami. Pole obsahuje 4B s informací o délce. String objekt obsahuje 4B komprimovaný pointer, 4B kešovaný hashCode a nevyužité 4B ztracené kvůli zarovnání objektů na 8B hranice.

Prázdný string tedy zabere 40 bajtů, krátké stringy budou tuhle cenu platit a relativní úspora kompaktních stringů bude o něco méně výrazná. Bude záležet jaké délky řetězců budou v aplikaci převládat.


K tématu:

Flattr this!

Posted in Java, JVM | 6 Comments

Iterace křížem krážem

Tenhle článek bych klidně mohl začít clickbait titulkem: „Jeden neuvěřitelný trik, který zrychlí vaše programy,“ a ani bych se za to nestyděl. Asi takhle: Když zpracovávám hromadu dat v několika průchodech (které z nějakých důvodů není možné spojit do jednoho), může nastat následující situace:

for (x <- xs) f(x)
for (x <- xs) g(x)
for (x <- xs) h(x)
-> 1. iterace ->
|---------------------------|-cache na konci iterace-|
-> 2. iterace ->
|---------------------------|-cache na konci iterace-|
-> 3. iterace ->
|---------------------------|-cache na konci iterace-|

Jak iteruji kolekcí, CPU načítá data z paměti do cache a postupně vyhazuje staré cache-line, na které dlouho nesáhlo, aby uvolnil místo novým objektům. Protože kolekcí jen prolétávám, na každý objekt sáhnu jen jednou a musím něco starého vyhodit. Když začnu další iteraci, objekty ze začátku kolekce jsou s největší pravděpodobností už dávno vyhozeny z cache a začnu tedy přistupovat ke studeným datům. V cache jsou jen data z konce předchozí iterace. Proto může dávat smysl iterovat ve střídavých směrech.

for (x <- xs)         f(x)
for (x <- xs.reverse) g(x)
for (x <- xs)         h(x)
-> 1. iterace ->
|---------------------------|-cache na konci iterace-|
                                      <- 2. iterace <-
|-cache na konci iterace-|---------------------------|
-> 3. iterace ->
|---------------------------|-cache na konci iterace-|

Začátek následující iterace využije obsah cache, který tam zůstal po minulém průchodu. Přístup do cache je rychlejší než čtení z RAM i v těch nejlepších případech, kdy jen streamuji souvislý bok paměti.

Tohle jsem momo jiné aplikoval na radix sort (první iterace, která jen sbírá statistiky, běží pozpátku) a když jsou data 2× větší než L3 cache, vede to ke ~10% zrychlení. V extrémně specifických situacích to může nakopnout výkon až o 50%, Když jsou však data mnohem větší než cache, efekt je zanedbatelný. Na druhou stranu je to jen malá změna, která neuškodí (hardwarový prefetch umí pracovat i pozpátku).

Když je všechno ostatní optimalizované na kost, tohle může v určitých případech přinést nějaké zrychlení. Ale jako v případě každé mikro-optimalizace je třeba měřit a profilovat.


Dále k tématu:

Flattr this!

Posted in Algo, CPU, low level | Leave a comment

Mikrobenchmarky jsou těžké

Na Twitteru jsem zaznamenal vtipnou etudu. Stalo se to už před nějakou dobou, ale tenhle článek mi nedokončený ležel na disku. Nicméně začalo to tímhle tweetem.

Podle všeho je v Javascriptu

if (obj !== undefined) { return obj.x }

v průměru o 15% rychlejší než stručné

if (obj) { return obj.x }

Je to proto, že ke kontrole proti undefined jsou potřeba jen 2 x86 instrukce (cmp a jz). Naproti tomu kontrola pravdivosti obnáší kontrolu jestli to není undefined, null, nula, prázdný string a nejspíš ještě něco dalšího.

To ale není zajímavé. Sranda začala v okamžiku kdy DHH napsal mikrobenchmark, který podle něj prokázal, že zrychlení není patrné. Velice rychle mu někdo začal důrazně vysvětlovat, že jeho benchmark je k ničemu a nic nedokazuje.

Zmíněný benchmark vypadal následovně. Já jen přidal třetí test nihilist-friendly.

const Benchmark = require('benchmark')
const suite = new Benchmark.Suite

let a = undefined

suite
  .add('human-friendly',    function () { if (a) true })
  .add('machine-friendly',  function () { if (a !== undefined) true })
  .add('nihilist-friendly', function () {})
  .on('complete', function () { console.log('Fastest is ' + this.filter('fastest').map('name')) })
  .on('cycle', function(event) { console.log(String(event.target)) })
  .run()

Výsledky jsou takovéto:

human-friendly    x 103,629,158 ops/sec ±0.79% (93 runs sampled)
machine-friendly  x 105,345,660 ops/sec ±1.00% (90 runs sampled)
nihilist-friendly x 110,587,292 ops/sec ±1.07% (92 runs sampled)

Z čísel je vidět, že benchmark benchmarkuje hlavně sám sebe a neměří nic užitečného. Rozdíl mezi noop funkcí a dvěma ostatními je jen minimální. To znamená, že se v nich něco děje, ale režie benchmarkovacího nástroje je veliká a všechno utopí.

Mikrobenchmarkování je zrádné, zvlášť v prostředí s agresivním JITem, jako jsou všechny Javovské nebo JS virtuální stroje stojící za pozornost. Jediným posláním JITu je optimalizovat a on je v tom zatraceně dobrý. Když si člověk nedá pozor, JIT může kompletně odstranit testovaný kód, protože ten například nemá žádné vedlejší efekty nebo nic nevrací. V testu můžu volat nějaké funkce, JIT je spekulativně inlinuje, zjistí, že kód je zbytečný, protože nedělá nic viditelného zvenčí a odstraní ho, tělo smyčky najednou můře být prázdné, tak ji také odstraní a takto může pokračovat dál, dokud kompletně nevyhlodá měřený kód a nezůstanou jen chapadla benchmarkovacího nástroje, který měří svou vlastní režii.

Když člověk chce měřit výkon takhle šíleně maličkého kusu kódu – jde doslova jen o hrstku instrukcí – musí si dávat zatraceně velký pozor a i přesto je třeba se podívat na dekompilovaný assembler, protože jinak si nikdy nemůže být jistý.

Pokud bych se cítil odvážně, mohl bych z oněch tří čísel vydedukovat, že cena noop funkce je 29 ns, cena rychlé funkce je 30.5 ns a pomalé 31.1 ns. Když odečtu těch 29 ns, je to 2.1 ns proti 1.5 ns, to je zrychlení o 30%, přesně podle výchozí teze. Ale jak říkám: Bůh ví, co se vlastně měří. Mikrobenchmarkování je zrádné a člověk nesmí mít slepou důvěru v použité nástroje a musí jim dobře rozumět, aby výsledná čísla byla k něčemu.


Dále k tématu:

Flattr this!

Posted in VM | Leave a comment

Jak v Javě na náhledy obrázků, ze kterých si lidé nebudu chtít vydloubat oči a prázdné oční důlky vypláchnout kyselinou

Jedna rychlovka, která je spíš poznámkou pro mě v budoucnosti než pro kohokoli jiného: Funkcionalita ve standardní knihovně v Javy není příliš dobrá pro vytváření náhledů obrázků. Zmenšený obrázek má výrazný aliasing.

To se dá jednoduše obejít tím, že obrázek napřed rozmažu a pak teprve zmenším. Výsledek není perfektní, ale aspoň není tak zubatý a hlavně: jde jen o minimální změnu.

def resizeImage(src: BufferedImage, width: Int, height: Int) = {
  val blur = new ConvolveOp(
    new Kernel(5, 5, Array.fill[Float](25)(1f/25)),
    ConvolveOp.EDGE_NO_OP, null
  )

  val zoom = math.min(1.0 * src.getWidth / width, 1.0 * src.getHeight / height)
  val wz = (width * zoom).toInt
  val hz = (height * zoom).toInt
  val x = (src.getWidth - wz) / 2
  val y = (src.getHeight - hz) / 2

  val crop = blur.filter(src.getSubimage(x, y, wz, hz), null)

  val tpe = if (crop.getType == BufferedImage.TYPE_CUSTOM) BufferedImage.TYPE_INT_ARGB else crop.getType
  val thumb = new BufferedImage(width, height, tpe)
  val g = thumb.createGraphics()
  g.drawImage(crop, 0, 0, width, height, null)
  g.dispose()

  thumb
}

Flattr this!

Posted in Java | Leave a comment

Lokalita v grafech a negrafech

Dneska jen krátce a stručně.

posledních dnech jsem hodně četl o garbage collectorech. Byla to zajímavá exkurze do pulzujících střev virtuálních strojů, ale o tom teď nechci psát. Chci se zmínit o něčem mnohem menším a skromnějším, co mě nejspíš napadlo po masáži GC algoritmy, kdy se mi začaly zdát sny o nekonečných mark and sweep cyklech.

Situace je následující: Zpracovávám nějaká data, která mají potenciálně překrývající se okolí. Každá položka má reference na objekty, které můžou být sdílené jinými položkami. Při zpracování dané položky musím načíst všechny tyhle referované informace. Schématicky to může vypadat nějak takhle:

Černé fleky jsou moje položky, kruh znázorňuje okolí a kosočtverce jsou dílčí objekty. Jak je vidět některé jsou sdílené, jiné jsou exkluzivní. Když je zpracovávám v daném externím pořadí, lokalita je mizivá. V diagramu sousední položky nesdílí nic ze svého okolí a přistupuji k nim v podstatě v náhodném pořadí. To ve větším měřítku, může vést ke špatném využití CPU cache nebo opakovaným IO operacím (pokud se všechno nevejde do paměti) a to může věci značně zpomalit.

Klasickým řešením je zatnout zuby a lifrovat víc peněz Amazonu. To může fungovat, ale není to vůbec intelektuálně uspokojivé.

Právě ve spojení s GC algoritmy, které musí projít graf objektů na haldě, aby označily/zkopí­rovaly živé objekty, mě napadlo si to představit jako graf a začít to procházet jako graf.

Nemusí jít o přesné prohledávání do šířky nebo do hloubky, stačí libovolná heuristika, která skáče z jednoho uzlu na druhý a zaručí, že proleze všechno (graf nemusí být spojitý). Pokud platí, že uzly často sdílí podstatnou část svého okolí, může to zvýšit lokalitu a to povede ke zrychlení.

Přesně tohle jsem použil v knihovně sketches jako strategii hromadného vyhodnocování (sekvenční a dokonce i paralelní) a vedlo to ke zrychlení o 25%. Jedna čtvrtina není zas tak moc, ale v tomto případě to byla čtvrtina skoro zadarmo.

Jako v případě každé (mikro)optimalizace i tady platí: profilovat, profilovat, profilovat.


K tématu:

Flattr this!

Posted in Algo, CPU | Leave a comment