0xDEADBEEF

[RSS]
««« »»»

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

27. 11. 2017

Stará poučka říká, že v Javě bychom měli re­gu­lární výrazy vždy do­předu zkom­pi­lo­vat a pak je opa­ko­vaně po­u­ží­vat, pro­tože kom­pi­lo­vání je časově ná­ročné.

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

Ale jak pomalé to vlastně je? To se dá jed­no­duše zjis­tit.

Vytáhl jsem JMH, napsal ben­chmark, který hledá jed­no­du­chý vzor. Jednou vzor ne­kom­pi­luje, po­druhé po­u­žívá před­kom­pi­lo­vaný vzor a po­třetí hledá regex jen když je to ne­zbytně 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 tes­to­vací data jsem použil kom­pletní export zdro­jo­vých textů blogu k47.cz, které mají do­hro­mady něco kolem 8 MB a 143000 řádek textu.

Vý­sledky jsou ná­sle­du­jí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

Kom­pi­lo­vaný regex je tři-a-něco-krát rych­lejší než ne­kom­pi­lo­vaný. Ale ten za­o­stává za pří­pa­dem, kdy se vy­hod­no­co­vá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ž ex­pli­citní kon­t­rola. Ale oči­vidně má ne­za­ne­dba­tel­nou režii.

Pokud regex nebude často pro­vá­děn, je rych­lejší 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))
}

Na­rychlo zkon­t­ro­lo­vat, jestli zdro­jový ře­tě­zec ob­sa­huje ně­ja­kou fixní část regexu a teprve potom nechat regex dělat těžkou práci. Ale jako v pří­padě každé op­ti­ma­li­zace je třeba pro­fi­lo­vat a ben­chmar­ko­vat.

Tento pří­stup zrych­lil ren­de­ro­vání textu as­cii­blogu o 75%.


Re­le­vantní čtení:

píše k47 (@kaja47, k47)