0xDEADBEEF

[RSS]

Jak rychlý je čas (v Javě)?

13. 3. 2019

Práce s datem a časem mi přišla vždycky poněkud pomalá. Při parsování dat často hodně času připadlo na zpracování datumů.

V Javě máme dvě možnosti jak na data: Jednak historický artefakt java.util.Date a pak novější java.time.LocalDateTime, které není zas tak nové, když vezmeme v potaz, že si odbylo svou premiéru už v Javě 8.

Otázka zní: Jak rychle můžeme vytvořit instanci každého z nich?

Abych to zodpověděl, napsal jsem malý JMH benchmark, který testuje výrobu Date objektů přes GregorianCalendar nebo s pomocí SimpleDateFormat a výrobu objektů LocalDate přes DateTimeFormatter nebo přímo statickou metodou of.

def calendar_notReused: Date =
  new GregorianCalendar(2018, 11, 25).getTime

def calendar_reused: Date = {
  cal.set(Calendar.YEAR, 2018)
  cal.set(Calendar.MONTH, 11)
  cal.set(Calendar.DAY_OF_MONTH, 25)
  cal.getTime
}

def simpleDateFormat_notReused: Date =
  new SimpleDateFormat("yyyy-MM-dd").parse(str)

def simpleDateFormat_reused: Date =
  simpleDateFormat.parse(str)

def localDateTimeParse_notReused: LocalDate =
  LocalDate.parse(str, DateTimeFormatter.ofPattern("yyyy-MM-dd"))

def localDateTimeParse_reused: LocalDate =
  LocalDate.parse(str, dateTimeFormatter)

def localDateTime: LocalDate =
  LocalDate.of(2018, 11, 25)

Výsledky jsou následující.

Benchmark                               Mode  Cnt     Score    Error  Units
Calendars.calendar_notReused            avgt    4   206,018 ±  3,370  ns/op
Calendars.calendar_reused               avgt    4   144,375 ±  0,422  ns/op
Calendars.simpleDateFormat_notReused    avgt    4  1396,633 ±  2,591  ns/op
Calendars.simpleDateFormat_reused       avgt    4   587,046 ± 15,300  ns/op
Calendars.localDateTimeParse_notReused  avgt    4   534,103 ± 24,506  ns/op
Calendars.localDateTimeParse_reused     avgt    4   346,680 ±  4,762  ns/op
Calendars.localDateTime                 avgt    4     5,771 ±  0,079  ns/op

Je z nich vidět několik věcí:

  1. Znovupoužití objektů GregorianCalendar, SimpleDateFormatDateTimeFormatter je rychlejší než jejich opakované vytváření. Někdy o čtvrtinu, jindy víc než dvakrát. (To není překvapivé, z opakovaného použití benefituje například i XMLStreamWriter nebo regex Matcher).
  2. Parsování stringu zabere ~300 ns času, víc než vytvoření instance Date nebo LocalDate
  3. LocalDate je 30x rychlejší než staré API. Za to může fakt, že LocalDate je trojice čísel den, měsíc, rok, kdežto Date reprezentuje čas jako konkrétní GMT okamžik ve formě počtu milisekund. Proto musí při vytváření brát v potaz časové zóny a musí projít logikou gregoriánského kalendáře, která není úplně triviální. Objektu LocalDate při vytvoření předám tři čísla, on je nastaví do vnitřních proměnných a má hotovo. Neví nic o časových zónách a nemusí počítat vzdálenost od určitého referenčního momentu.

Navíc je nové java.time API immutable a bezpečné při použití ve více vláknech. Není tedy nutné se rozhodovat mezi rychlostí a machinacemi s ThreadLocal proměnnými.

Dodatky:

  1. Pokud potřebujete pracovat s daty jako timestampy, protože například musíte počítat kolik uběhlo mezi dvěma okamžiky vteřin/minut/hodin/dnů, nové API na to má třídu java.time.Instant. LocalDateTime musí timestamp vždy spočítat, což není úplně triviální.
  2. Na druhou stranu, porovnání dvou LocalDateTime objektů je stále velice rychlé.

Really simple RSS

21. 2. 2019

Není žádný důvod, proč by váš web neměl podporovat RSS a tady vám ukážu proč.

RSS (v současnosti) znamená really simple syndicationvelice jednoduchá syndikace. Název nelže, protože i když pracujete v jazyku, který umí jenom zapisovat znaky do StringBuilderu a kromě toho nezvládá nic komplikovanějšího, validní generátor RSS se stále vejde do méně než 40 řádek kódu.

class RSS(title: String, description: String, link: String) {
  val sb = new java.lang.StringBuilder

  sb.append("<?xml version=\"1.0\" encoding=\"utf-8\"?>\n")
  sb.append("<rss version=\"2.0\">")
  sb.append("<channel>")
  element("title", "", title)
  element("description", "", description)
  element("link", "", link)

  def addItem(title: String, url: String, body: String = "") = {
    sb.append("<item>")
    element("title", "", title)
    element("guid", " isPermaLink=\"true\"", url)
    element("description", "", body)
    sb.append("</item>")
  }

  def result() = {
    sb.append("</channel>")
    sb.append("</rss>")
    sb.toString
  }

  private def element(name: String, attr: String, body: String) = {
    sb.append("<").append(name).append(attr).append(">")
    var i = 0; while (i < body.length) {
      body.charAt(i) match {
        case '&' => sb.append("&amp;")
        case '>' => sb.append("&gt;")
        case '<' => sb.append("&lt;")
        case ch  => sb.append(ch)
      }
      i += 1
    }
    sb.append("</").append(name).append(">")
  }
}

Nepoužívá žádnou knihovnu pro XML a s programovacím ekvivalentem provázku a naostřené plaňky je možné přidat vlastní RSS export. Použití není nic překvapivého:

val rss = new RSS("0xDEADBEEF", "programování & tak podobně", "https://deadbeef.k47.cz")
rss.addItem("Really simple RSS", "https://deadbeef.k47.cz/rss.html", "<p>lorem ipsum</p>")
rss.result()

Výsledný feed si můžete zkontrolovat na validátoru w3, projde bez chyb.


+1: O turbulentní historii a vývoji se píše v The Rise and Demise of RSS.

Java, Scala a regulární výrazy #6 - znovupoužití Matcher objektu

26. 1. 2019

Mnoho API v Javě je navrženo s ohledem na znovupoužití vytvořených objektů. Například XMLStreamWriter alokuje nezanedbatelné množství interních struktur a proto je podstatně rychlejší, když je vytvořen jen jednou a pak používán opakovaně.

Stejně tak je možné při práci s regulárními výrazy opětovně používat objekt Matcher metodou reset. Při každém vytvoření Matcher objektu dojde k alokování několika interních polí včetně pole IntHashSet objektů a to pochopitelně stojí čas.

Namísto klasického

val pattern = Pattern.compile("^===+$")
lines.count { line => pattern.matcher(line).matches() }

můžu použít variantu

val pattern = Pattern.compile("^===+$")
val matcher = pattern.matcher("")
lines.count { line => matcher.reset(line).matches() }

Ta vytvoří pouze jeden Matcher objekt a opakovaně ho recykluje.

Abych zjistil, jaký je mezi jednotlivými případy rozdíl, napsal jsem JMH benchmark, který testuje několik případů:

Benchmark                      Mode  Cnt    Score    Error  Units
a.r.notcompiled               thrpt    3   23,619 ±  2,003  ops/s
a.r.compiled_scala_match      thrpt    3   78,393 ±  6,214  ops/s
a.r.compiled_java             thrpt    3   80,988 ±  7,783  ops/s
a.r.reuse_matcher             thrpt    3  163,157 ± 11,151  ops/s
a.r.compiled_with_check       thrpt    3  382,765 ± 14,174  ops/s
a.r.reuse_matcher_with_check  thrpt    3  416,959 ± 17,088  ops/s

V tomto případě, kdy se hledá jednoduchý regex, recyklace vede ke dvojnásobné rychlosti hledání. Rozdíl mezi naivním použitím regexů metodou string.matches(regex) a znovupoužitím Matcheru je 7x.

Jako obvykle je nejrychlejší regexy vůbec neprovádět.


Dodatek: S narůstající složitostí regexů, zdá se, má znovoupoužívání Matcher objetu menší význam. Pro regexy na parsování apache logů, přinesou jen pár procent zrychlení.


Benchmark:

@State(Scope.Thread)
class regex {
  var lines: Array[String] = _
  val regex: util.matching.Regex = """^===+$""".r
  val pattern = regex.pattern
  val matcher = pattern.matcher("")

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

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

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

  @Benchmark
  def compiled_java(): Int =
    lines.count { l => pattern.matcher(l).matches() }

  @Benchmark
  def reuse_matcher(): Int =
    lines.count { l => matcher.reset(l).matches() }

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

  @Benchmark
  def reuse_matcher_with_check(): Int =
    lines.count { l => (l.length >= 3 && l.charAt(0) == '=') && matcher.reset(l).matches() }
}

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 byte 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.

24. 12. 2018Java IO & NIO - jak nejrychleji načíst soubor z disku
3. 11. 2018Průnik množin ve Scale
23. 10. 2018Čím nahradit Scala.XML
11. 10. 2018Novinky kolekcí ve Scale 2.13
4. 8. 2018Co vlastně benchmarkujete?
28. 7. 2018Java, Scala a regulární výrazy #5 - posesivní regexy a StackOverflowError
26. 7. 2018EDGE, TRIPS a hon za vyšším ILP
24. 6. 2018Striktní a líné jazyky
21. 6. 2018Syntéza datových struktur a programů
9. 6. 2018ISPC, SPMD a SIMD
6. 4. 2018Konec Intelu, konec Moorova zákona, konec světa takového jaký známe
31. 1. 2018Meltdown, Spectre a branch prediction
28. 12. 2017Poznámky k výkonu
19. 12. 2017Java, Scala a regulární výrazy #4 - líné regexy a StackOverflowError
5. 12. 2017Java, Scala a regulární výrazy #3 - rychlost
27. 11. 2017Java, Scala a regulární výrazy #2 - rychlost
26. 11. 2017Java, Scala a regulární výrazy
21. 11. 2017Java - zostřování obrázků
7. 10. 2017Koherence cache a atomické operace
5. 10. 2017Nejrychlejší hashmapa pod sluncem
23. 9. 2017Dekódování x86 instrukcí
21. 9. 2017Energetická efektivita programovacích jazyků
19. 9. 2017Programming and Performance podcast
17. 9. 2017B-stromy, persistence, copy-on-write a Btrfs
15. 9. 2017Rust a parsery
13. 9. 2017Velké stránky paměti
11. 9. 2017Deanonymizace agregovaných dat
9. 9. 2017Optimalizující kompilátor
7. 9. 2017Identifikace zašifrovaných videí
5. 9. 2017Heterogenní persistentní kolekce
3. 9. 2017JVM Anatomy Park
1. 9. 2017Datacentrum z mobilů
30. 8. 2017Propustnost pamětí
28. 8. 2017Branch prediction (implementace v procesorech)

píše k47 (@kaja47, k47)