RychlostGraalVM

Z Denik

Verze z 20. 4. 2018, 17:32

Jsou opravdu GraalVM jazyky tak rychlé, jak o sobě tvrdí? A jak vůbec měřit rychlost jazyka?

Objektivně měřit něco takového je přetěžký úkol. Téměř každý jazyk poskytuje dodatečné vestavěné operace, které již nejsou implementovány v daném jazyce, ale volají do vysoce optimalizované knihovny napsané v Céčku či assembleru. Její autoři si pak dávají dost záležet, aby zrovna ten jejich výpočet byl co nejrychlejší. Tudíž porovnávat rychlost jazyků na základě takovýchto specializovaných vychytávek nedává moc smysl. Na druhou stranu každý řádný programovací jazyk musí být turingovský úplný (musí podporovat obecné programovací konstrukce jako if, for a while), a tak navrhuji, abychom turingovskou rychlost jazyka měřili na základě obecného výpočtu, který pokud možno bude co nejméně využívat zabudovaných zkratek. To je samozřejmě těžké. Pokud se takový obecný výpočet stane známým, tak na něj začnou tvůrci jazyka cílit, speciálně optimalizovat a bude opět po nezávislosti. Tomu lze asi nejlépe zabránit tím, že si člověk napíše svůj vlastní algoritmus a provede si měření sám. Tak jako jsem to já udělal s Eratosthénovým sítem na výpočet prvočísel.

Ruby

Když jsem se k OracleLabs před pár lety přidal, moji kolegové hrdě tvrdili, že jejich implementace Ruby je desetkrát rychlejší než jakákoli jiná. "To určitě!" pomyslel jsem si. "Možná je rychlá na nějakém speciálním příkládku, ale jinak to přeci není možné" a řekl jsem si, že to vyzkouším. Chvíli jsem přemýšlel o nějakém vhodném příkladu a Eratosthénovo síto mi přišlo ideální. Je to výpočet, který může běžet libovolně dlouho (dokud nedojdou prvočísla), který provádí aritmetické operace a který (v mé verzi) alokuje objekty do spojového seznamu. Vcelku vhodný kandidát na měření turingovské rychlosti, řekl jsem si a začal psát svůj první program v Ruby:

class Natural
  def initialize
    @x = 1
  end

  def next
    @x += 1
  end
end

class Filter
  attr_reader :number
  attr_accessor :next

  def initialize(number)
    @number = number
    @next = nil
    @last = self
  end

  def acceptAndAdd(n)
    filter = self
    upto = Math.sqrt(n)
    while filter
      if n % filter.number == 0
        return false
      end
      if filter.number > upto
        break
      end
      filter = filter.next
    end
    filter = Filter.new(n)
    @last.next = filter
    @last = filter
    true
  end
end

class Primes
  def initialize(natural)
    @natural = natural
    @filter = nil
  end

  def next
    while true
      n = @natural.next
      if @filter == nil
        @filter = Filter.new(n)
        return n
      end
      if @filter.acceptAndAdd(n)
        return n
      end
    end
  end
end

def ms(start)
  ((Time.now - start) * 1000).floor
end

def fewthousands
  natural = Natural.new
  primes = Primes.new(natural)

  start = Time.now
  cnt = 0
  prntCnt = 97
  begin
    res = primes.next
    cnt += 1
    if cnt % prntCnt == 0
      puts "Computed #{cnt} primes in #{ms(start)} ms. Last one is #{res}."
      prntCnt = prntCnt * 2
    end
  end while cnt < 100000
  ms(start)
end

puts "Ready!"

count = -1
if ARGV.length == 1
then
  count = ARGV[0].to_i
end

while count != 0
  puts "Hundred thousand prime numbers in #{fewthousands} ms"
  count = count - 1
end

Jeho první komponentou je generátor, zvaný Natural, přirozených čísel od dvojky do nekonečna. Další částí je Filter - to je prvek spojového seznamu do něhož se ukládají již nalezená prvočísla. Ten má i operaci acceptAndAdd, jež zkouší dělitelnost nového čísla již známými prvočísly a případně nové prvočíslo přidá do seznamu. Třída Primes si pak udržuje hlavu spojového seznamu a umí vydat další prvočíslo. Nakonec je v programu smyčka, která počítá sto tisíc prvočísel a měří čas, jaký to zabralo.

Tato smyčka se opakuje stále dokola. Proč? Protože, a to jsem zatím nezmínil, je hlavním cílem GraalVM zrychlit dlouhotrvající výpočty na serverech. Takové výpočty stále do kola opakují to samé a tudíž nevadí, když prvních pár (tisíců) výpočtů je pomalejších. To, co je důležité, je rychlost, které program dosáhne po zahřátí na provozní teplotu. Což je právě případ GraalVM: s dalším výpočtem se zrychluje a zrychluje. Proto je třeba provést několik výpočtů na zahřátí a teprve pak změřit dosaženou rychlost.

A jak to měření dopadlo? Ruby, které mám na svém Ubuntu dokáže jednu smyčku provést asi tak za dvě sekundy:

$ ruby -v
ruby 2.3.1p112 (2016-04-26) [x86_64-linux-gnu]
$ ruby ruby/sieve.rb
Hundred thousand prime numbers in 2055 ms

Ruby, které je součástí enterprise GraalVM to dokáže za méně než 150 ms:

$ /graalvm-0.33/bin/ruby ruby/sieve.rb 
Hundred thousand prime numbers in 119 ms

Tudíž, světe div se, moji kolegové nekecali. Opravdu je GraalVM Ruby alespoň desetkrát rychlejší než jakákoli jiná implementace.

JavaScript

Rychlé Ruby je sice hezká věc, ale kdo dnes píše v Ruby? Ten jazyk už je hezkých pár let za zenitem. Dnes přeci všichni píší v JavaScriptu, že!?

Ano, JavaScript je v současnosti vcelku populární a tudíž jej GraalVM také podporuje. A to buď jako čistý jazyk bez knihoven a nebo v kombinaci s node.js, který poskytuje rozhraní pro přístup k operačnímu systému. Přepsat moje síto do JavaScriptu nebylo těžké. Struktura programu zůstala zachována: stále je tam generátor přirozených čísel, spojový seznam s prvočísly i smyčka, jež měří čas potřebný pro výpočet prvních sto tisíc prvočísel. Kód tedy máme a můžeme měřit. Obecně je za nejrychlejší virtuální stroj pro běh JavaScriptu považována V8 od Googlu, která je také součástí standardní distribuce Ubuntu v podobě systému node.js. Můžeme se tedy zkusit porovnat s ní:

$ nodejs -v
v6.14.1
$ nodejs js/sieve.js 
Hundred thousand prime numbers in 108 ms
$ /graalvm-0.33/bin/js js/sieve.js 
Hundred thousand prime numbers in 106 ms

Nechci tvrdit, že by GraalVM byla vždy rychlejší než V8, ale když se ten program správně napíše, tak může být. Určitě však není o moc pomalejší. To by nás šéf hnal - v mládí si na prázdniny odskočil do Googlu napsat CrankShaft kompilátor - a teď nedá pokoj, dokud nejsme alespoň stejně rychlí. Zvláště po tom, co mu CrankShaft nahradili TurboFanem, se z toho stala otázka cti.

GraalVM JavaScript je tedy rychlejší než GraalVM Ruby, ale jen o kousíček. Je tak vhodné položit si otázku: Má cenu přepisovat celé programy z Ruby do JavaScriptu? Ne, nemá. Stačí přepsat jen část!

Ruby a JavaScript

Tak a teď se dostáváme k tomu, v čem je GraalVM opravdu jedinečná. Zkusíme napsat kus programu v Ruby, zbytek v JavaScriptu a propojit obě části pomocí GraalVM polyglotního rozhraní. Nejprve vyhodnotíme Ruby kód, který vyexportuje symbol Natural pro použití z ostatních jazyků:

class Natural
  def initialize
    @x = 1
  end

  def next
    @x += 1
  end
end

def create
  Natural.new
end

Truffle::Interop.export("Natural", method(:create));

no a nyní provedeme část napsanou v JavaScriptu. V té chybí definice generátoru přirozených čísel, kterou si proto vyzvedneme z Ruby:

var natural = Interop.import('Natural');

do JavaScriptové proměnné natural se tedy přiřadí objekt z Ruby a my jej nyní můžeme přirozeně používat, tak jako by to byl normální JavaScriptový objekt:

var n = this.natural.next();

Tak a můžeme se podívat na rychlost. GraalVM nabízí binárku polyglot, která dokáže spouštět všechny podporované jazyky:

$ /graalvm-0.33/bin/polyglot --file ruby+js/sieve.rb --file ruby+js/sieve.js
Hundred thousand prime numbers in 113 ms

A hle! Je to rychlejší než samotné Ruby a jen maličko pomalejší než čistý JavaScript. To je asi tak jediné, s čím se můžeme porovnávat, protože neexistuje žádný jiný systém, který by mohl míchat jazyky takovýmto způsobem a při tom zachovat tak vysokou rychlost běhu. Pokud vás napadají UNIXové roury, tak je možné, že by v tomto případě šlo napsat program, který vygeneruje přirozená čísla a druhý, který je používá, a propojit je rourou. To je však pouze jednosměrná asynchronní komunikace. Avšak GraalVM zvládne volat funkce synchronně a to i s parametry, což by bylo jako přičítat jedna pomocí expr příkazu běžícího pokaždé v novém externím procesu. To bychom se asi nedočkali ani prvního tisíce prvočísel.

Java

GraalVM tedy zřejmě běhá dynamické jazyky jako je JavaScript či Ruby vcelku rychle (mimochodem k tomu také nabízíme experimentální verze jazyka R, Python a mnoha dalších) a navíc je lze mezi sebou ještě bezostyšně míchat. Má vůbec cenu používat ještě nějaké jiné jazyky?

Samotný překladač GraalVM je napsán v Javě. Je tedy na místě se zeptat: Jak rychle běhá na GraalVM Java? Přepsat Eratosthénovo síto do souborů Natural.java, Filter.java a Primes.java je snadné. Spustit tento projekt také:

$ mvn -f java/pom.xml install
$ java -version
java version "1.8.0_171"
$ mvn -f java/algorithm/pom.xml exec:java
Hundred thousand primes computed in 86 ms

na mém počítači se v pohodě dostaneme pod 90ms. To znamená, že Java je stále ještě rychlejší než JavaScript & spol. A to jsme ještě neběželi na GraalVM! Zkusme:

$ JAVA_HOME=/graalvm-1.0.0-rc1/ mvn -f java/algorithm/pom.xml exec:java
Hundred thousand primes computed in 79 ms

ano, je to tak. GraalVM dokáže být ještě rychlejší než klasická JVM se serverovým C2 překladačem. To je samo o sobě dost těžké, neboť C2 překladač je velmi výkonný, ale GraalVM překladač dokáže ještě více oddálit alokaci objektů a občas je nealokovat vůbec. Stačí místo klasického JDK8 použít enterprise GraalVM a váš Java program může okamžitě běžet rychleji.

Céčko

To je všechno hezké, ale není lepší ten program stejně napsat v Céčku? Také mne to zajímalo, a tak jsem to tedy zkusil: main.c je stejný jako ostatní, akorát po sobě musí uklízet, neboť C ještě nemá garbage collector. Jinak je struktura toho programu stejná a výsledek také není špatný...

$ make -C c
$ ./c/sieve
Hundred thousand prime numbers in 101 ms

...100 ms, to je dobré. To je tak na úrovni JavaScriptu. No čekali byste to? Většina lidí si myslí, že dynamické jazyky jsou pomalé, ale v posledních deseti letech udělal vývoj virtuálních strojů pro dynamické jazyky obrovský skok kupředu a rychlost již není problém.

S GraalVM lze vcelku snadno vytvořit velmi rychlý interpret jakéhokoli jazyka. Jde to tak snadno, že bychom třeba mohli napsat interpret Céčka. Interpret jazyka C? To už zní úplně šíleně! Proč by to někdo dělal? Tak za prvé asi dokázat si, že to jde. Takže jsme to skutečně zkusili. V rámci podprojektu Sulong umíme interpretovat jakýkoli jazyk, který se dá přeložit pomocí LLVM - tedy C, C++, Rust, Julia, atd., atd. Nejprve se vygeneruje LLVM bitkód a ten se pak může interpretovat. Zkuste si:

$ clang -c -emit-llvm -o c/sieve.bc c/main.c
$ /graalvm-0.33/bin/lli c/sieve.bc
Hundred thousand prime numbers in 115 ms

Je to jen o 10-20% pomalejší. To je vcelku slušné na interpret, že? Ale hlavní výhodou je, že tento interpret je pro GraalVM stejně průhledný jako ostatní interpretery a tudíž lze optimalizovat skrz naskrz JavaScript, Ruby a jejich Cčkové knihovny. Dohromady to pak celé může běžet ještě rychleji, neboť se ušetří na přepínání z jednoho systému do druhého. Raději než úplně vyoptimalizovat C (což dokáže běh jednoho kola srazit na 75 ms), tak je lepší vše převést na jeden dynamický systém a optimalizovat to celé dohromady. GraalVM si s tím už poradí.