原文はこちら。
The original article was written by Uberto Barbini (JVM and Kotlin independent consultant).
https://medium.com/javarevisited/graal-vs-c2-who-runs-kotlin-faster-82f03f1b11dd
［訳注］原文は2020/3に記載されたものです。時間の経過や期間などは原文の表記に従っています。
1年以上前、Java Advent Calendar 2018でKotlinにおけるGraalVMのパフォーマンスという内容のエントリを書きました。
COMPARING KOTLIN PERFORMANCE WITH GRAAL AND C2
https://www.javaadvent.com/2018/12/comparing-kotlin-performance-with-graal-and-c2.html
GraalVM v20.0のCommunity EditionとEnterprise Editionで前回の結果を再評価する時期です。
Graalについてご存知かと思いますが、これはJavaで記述されたJVMのための新しいJITコンパイラです。JDK内部でJava 10以後で利用でき、将来的にはJDKの標準コンパイラになるかもしれません。
詳細に興味がある方は、以下の記事をどうぞ。
Javaの新JITコンパイラ、Graalを解説 （翻訳は @jyukutyo ）
https://www.infoq.com/jp/articles/Graal-Java-JIT-Compiler/
Getting to Know Graal, the New Java JIT Compiler
https://www.infoq.com/articles/Graal-Java-JIT-Compiler/
Quick introduction
Java 1.3以後、HotSpotには2種類のJITコンパイラが含まれています。一つが非常に素早く呼び出されるC1、もう一つが呼び出されるタイミングは遅いもののより最適化されたコードを生成するC2と呼ばれるJITコンパイラです。JVMはC1を迅速な起動に使用し、C2はパフォーマンスを向上させるために後から使用します。
GraalはJVMバイトコードのための新しいコンパイラで、Javaで記述されています。Java 9で導入されたJVMCICompilerインターフェースを利用します。JITモードもしくはネイティブアプリケーションを生成するためのAOT（Ahead Of Time）モードで実行できます。
GraalVMは標準的なJDKを完全に置き換えるもので、GraalコンパイラおよびTruffleやSubstrate VMなどの関連テクノロジーを使います。
GraalVM
https://www.graalvm.org/
では、どのようにしてGraalを実行するのでしょうか？Java 10以降、 -XX:+UnlockExperimentalVMOptions -XX:+UseJVMCICompiler という2個のVMオプションを使用すれば、JDKでGraalコンパイラを有効にできます。残念ながら、JDKに含まれているGraalコンパイラは常に最新のバージョンとは限らないので、より良い解決策はJDKとしてGraalVMに切り替えることです。
SDKMAN!をインストール済みであれば、以下の3行のコマンドを打つだけです。
SDKMAN!
https://sdkman.io/install
sdk list java
//choose the right GraalVM version
sdk install java 20.0.0.r11-grl
//install it
sdk use java 20.0.0.r11-grl
//select it as current JDKSDKMAN!をインストールしていないのであれば、GraalをOracleのWebサイトからダウンロードし、展開して、JAVA_HOMEを設定すればOKです…が、そんなことするなら、本当にSDKMAN!をインストールすればいいじゃない！
GraalVMにはCEとEEの2種類があり、詳細はFAQに記載されていますが、要点は、CEは完全にオープンソースであるのに対し、EEは評価用と非運用環境に対してのみ無料であるという点です。
GraalVM FAQ
https://www.graalvm.org/faq/
EEはCEをベースに追加の最適化を加えていますが、それはあなたにとって重要であるかもしれないし、重要でないかもしれません。
Enterprise Editionをダウンロードするためには、Oracleに登録してライセンス契約書にサインする必要があります。
コンパイラのテストのために以下の3個のアルゴリズムを用意しました。
- a Mandelbrot Set generator（マンデルブロ集合生成器）
- a Knapsack solver （ナップサック問題のソルバー）
- a Modular Algebra calculator（モジュラ代数計算器）
完全なコードはGitHubにあります。
uberto/kotlin-perf
https://github.com/uberto/kotlin-perf
拡張関数、データクラス、コンテキストプログラミング、for eachループを利用して、Kotlinの最も熟達した方法でコードを書くようにしました。結果として得られたコードは非常に読みやすいだけでなく、Cのような構文を使う場合に比べてパフォーマンスの大幅な劣化もありません。
これら3つのアルゴリズムを選んだのは、全く異なるCPU負荷の高いタスクの現実的な例があるためです。そしてコードは完全にKotlinでのみ記述しており、Javaライブラリを一切使用していません。
Mandelbrot Set （マンデルブロ集合）
マンデルブロ集合はおそらく最も有名なフラクタル図形であり、その名前を知らずとも一度はご覧になったことがあるかもしれません。
Mandelbrot set
https://en.wikipedia.org/wiki/Mandelbrot_set
マンデルブロ集合
https://ja.wikipedia.org/wiki/マンデルブロ集合
数学的には、関数 z <- z²+c が反復しても発散しない複素平面上のすべての点の集合として定義されます。複素平面上のいくつかの点に対して関数を反復処理して、それらの点からイメージを作成することで、この集合を生成するのは非常に簡単です。
ここでのゴールはパフォーマンスであってグラフィックスではないため、簡単のためにテキストグラフィックをつかいます。
ではマンデルブロ集合のコードを見てみましょう。以下は複素数を表現するための型（Complexクラス）の定義です。
data class Complex(val r: Double, val i: Double){
operator fun times(other: Complex) =
Complex(
r = this.r * other.r - this.i * other.i,
i = this.i * other.r + this.r * other.i
)
operator fun plus(other: Complex) =
Complex(r = this.r + other.r, i = this.i + other.i)
operator fun minus(other: Complex) =
Complex(r = this.r - other.r, i = this.i - other.i)
fun squared() = this * this
fun squaredModule() = r * r + i * i
fun Double.toComplex() = Complex(r=this, i=0.0)
}続いて、集合の各点の実際の計算です。
fun mandelSet(initZ: Complex, c:Complex, maxIter: Int): Int {
var z = initZ
(1..maxIter).forEach{
z = z.squared() + c
if (z.squaredModule() >= 4)
return it
}
return maxIter
}ここでは、演算子のオーバーロードとデータクラスを使って複素数を表現することで、いかにコードが簡単になり、理解しやすくなるかがご覧いただけます。
Complexクラスで複素数の演算ルールを定義すると、mandelSet関数は、演算 z <- z²+c がしきい値を超えるかどうかをチェックしているだけです。何回反復した後にしきい値 4 を超えるかどうかをチェックしています。
ここでは、AsciiArtでレンダリングされた出力でマンデルブロ集合の特徴的なカーディオイド形状を見ることができます。
Knapsack problem （ナップサック問題）
ナップサック問題にはいくつかの定義があります。
Knapsack problem
https://en.wikipedia.org/wiki/Knapsack_problem
ナップサック問題
https://ja.wikipedia.org/wiki/ナップサック問題
時計店に押し入った泥棒を想像してみてください。彼はナップサックに入れて持ち運べる最大重量を超えない限り，欲しいだけの時計を盗むことができます。
合理的な泥棒であれば、間違いなくナップサックの中の時計の価値を最適化したいと考えています。すべての時計には値段と重さが備わっています。そこで、指定された重量に対して最大の合計価格を持つ時計の集合を見つけるアルゴリズムが必要です。
実世界でのこのアルゴリズムの適用先としては、CNC（コンピュータ数値制御）機械のための切断や材料の最適化、広告予算を割り当てるためのマーケティング戦略などがあります。
例えば、以下のように定義された3個の時計しか持たない時計店で考えてみましょう。
val shop = Knapsack.shop(
Watch(weight = 1, price = 1),
Watch(weight = 3, price = 2),
Watch(weight = 1, price = 3)
)最大重量が1の場合は、1番よりも3番の方が価格が高いので、3番の時計を手に取った方が良いでしょう。
最大重量が3の場合は、2番（価格2）か、1番と3番（価格は1＋3）のどちらかを選ぶことになります。この場合、1番と3番の合計重量が最大重量以下であっても、1と3を選んだ方が良いでしょう。
以上がこの店における完全な解答です。
assertEquals(3, selectWatches(shop, maxWeight = 1))
assertEquals(4, selectWatches(shop, maxWeight = 2))
assertEquals(4, selectWatches(shop, maxWeight = 3))
assertEquals(5, selectWatches(shop, maxWeight = 4))
assertEquals(6, selectWatches(shop, maxWeight = 5))ご覧のように、選択できる時計の数が増えると、可能な選択肢の数は非常に早く増大します。これは古典的なNP-Hard（NP困難）問題です。
この問題を合理的な時間で解くためには，少しごまかしてDynamic Programming（動的計画法）を使う必要があります。時計の集合ごとに最適化された解を持つマップを作成できるので、毎回の再計算を回避できます。
一般的なアルゴリズムは、再帰に基づく網羅的な探索に基づいています。これはこの問題を解くためのKotlinのコードで、メモ化関数と最大値の再帰探索で区切っています。
typealias Memoizer = MutableMap<String, Int>fun priceAddingElement(memo: Memoizer, shop: Set<Watch>, choice: Set<Watch>, maxWeight: Int, priceSum: Int): Int =
shop.filter { !(it in choice) && it.weight <= maxWeight }
.map {
selectWatches(
memo,
shop,
maxWeight - it.weight,
choice + it,
priceSum + it.price) }
.filter { it > priceSum }
.max() ?: priceSum
fun selectWatches(memo: Memoizer, shop: Set<Watch>, maxWeight: Int, choice: Set<Watch>, priceSum: Int): Int =
memoization(memo, generateKey(choice)) {
priceAddingElement(memo, shop, choice, maxWeight, priceSum)}
private fun memoization(memo: Memoizer, key: String, f: () -> Int): Int = when (val w = memo[key]) {
null -> f().also { memo[key] = it }
else -> w
}Kotlinでは、自分の意思を明確に表現することができるので、何度も繰り返さなくてもいい点がとても気に入っています。
Modular Algebra （モジュラ代数、合同算術）
モジュラー代数は数学の中でも非常に便利で興味深い分野です。
Modular arithmetic
https://en.wikipedia.org/wiki/Modular_arithmetic
合同算術
https://ja.wikipedia.org/wiki/合同算術
時計の時間の演算に似ているので「時計代数」とも呼ばれています。 例えば、7 + 6は通常13に等しいが、時間の話をしている場合は1に等しくなります。ここでは時計は12を法とする代数ですが、この考え方は任意の数に一般化できます。
例えば、moduloに対して素な数を足し続けると、moduloまでのすべての数の列が生成されるなど、興味深い性質を持っています。これは、時計代数で12とは互いに素な数を12に足すと、すべての時間の数列が生成されることを意味します。例えば、5は12と互いに素な数の中で最も小さい数なので、12を法とする場合において5の数列は次のようで、以後繰り返します。
5, 10, 3, 8, 1, 6, 11, 4, 9, 2, 7, 0以下はモジュラー数とその演算を定義するクラスです．モジュラー代数では除算が非常に問題になるので、近道としてブルートフォース法を使っています。
Modular Arithmetic [Math in Network Security: A Crash Course]
https://www.doc.ic.ac.uk/~mrh/330tutor/ch03.html
data class ModularNumber(val num: Int, val modulo: Int): Comparable<ModularNumber> {
override fun compareTo(other: ModularNumber): Int = num.compareTo(other.num)
operator fun plus(other: ModularNumber) = (num + other.num).toModularNumber()
operator fun minus(other: ModularNumber) = (num - other.num).toModularNumber()
operator fun times(other: ModularNumber) = (num * other.num).toModularNumber()
operator fun div(other: ModularNumber) = ((1..modulo).first { (it * other.num) % modulo == (this.num % modulo) }).toModularNumber()
operator fun inc() = (num + 1).toModularNumber()
fun squared() = (num*num).toModularNumber()
fun Int.toModularNumber(): ModularNumber =
ModularNumber(this % modulo, modulo)
}そんな魅力的な代数で何ができるのでしょうか？素敵なパターンを描くことができます。そのためには、モジュラー代数の中の2つの数の2乗を比較すればよいのです。
2+2 = 1? PATTERNS IN MODULAR ARITHMETIC
https://maxwelldemon.com/2011/11/20/22-1-patterns-in-modular-arithmetic/
data class PlaneGrid(val size: Int, val initPredicate: (Int) -> Boolean) {
private val grid = BooleanArray(size*size, initPredicate)
operator fun get(x: Int, y: Int): Boolean = grid[coord(x,y)]
private fun coord(x: Int, y: Int) = (y-1) * size + x -1
fun count(): Int = grid.count {it}
}
val compareSquares: (ModularNumber, ModularNumber) -> Boolean =
{ x, y -> x.squared() >= y.squared() }
fun compareSquares(size: Int, modulo: Int): Int =
ModularField(modulo).applyFunction(compareSquares)(size).count()
fun sumOfFunction(from: Int, to: Int, f: (Int) -> Int) =
(from..to)
.map { f(it) }
.sum()data class ModularField(val modulo: Int) { fun applyFunction(f: (ModularNumber, ModularNumber) -> Boolean): (Int) -> PlaneGrid =
{ size ->
PlaneGrid(size) { index ->
val xMod = (index % size).toModularNumber()
val yMod = (index / size).toModularNumber()
f(xMod, yMod)
}
} fun Int.toModularNumber(): ModularNumber =
ModularNumber(this % modulo, modulo)
}これらは上記関数が生成したモジュラーパターンの例です。
Modulo 5 Modulo 15 Modulo 12
@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@
@@@@ @@@@ @@@@ @@@@ @@@@@@@@@@@@@@ @@@@ @@@@@ @@@@@ @@@@@ @
@@ @@ @@ @@ @@ @@@@@@ @@ @@ @@@ @@@ @@@
@@ @@ @@ @@ @ @ @ @ @ @ @ @
@@@@ @@@@ @@@@ @@@@ @@@@@@@@@@@@@@ @@@@ @@@ @@@ @@@
@@@@@@@@@@@@@@@@@@@@ @ @ @@@@@ @@@@@ @@@@@ @
@@@@ @@@@ @@@@ @@@@ @ @@ @@ @ @ @@@@@@@@@@@@@@@@@@@@
@@ @@ @@ @@ @@ @@@@@@ @@ @@ @@@@@ @@@@@ @@@@@ @
@@ @@ @@ @@ @@ @@@@@@ @@ @@ @@@ @@@ @@@
@@@@ @@@@ @@@@ @@@@ @ @@ @@ @ @ @ @ @
@@@@@@@@@@@@@@@@@@@@ @ @ @@@ @@@ @@@
@@@@ @@@@ @@@@ @@@@ @@@@@@@@@@@@@@ @@@@ @@@@@ @@@@@ @@@@@ @
@@ @@ @@ @@ @ @ @ @ @ @@@@@@@@@@@@@@@@@@@@
@@ @@ @@ @@ @@ @@@@@@ @@ @@ @@@@@ @@@@@ @@@@@ @
@@@@ @@@@ @@@@ @@@@ @@@@@@@@@@@@@@ @@@@ @@@ @@@ @@@
@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@ @ @ @
@@@@ @@@@ @@@@ @@@@ @@@@@@@@@@@@@@ @@@@ @@@ @@@ @@@
@@ @@ @@ @@ @@ @@@@@@ @@ @@ @@@@@ @@@@@ @@@@@ @
@@ @@ @@ @@ @ @ @ @ @ @@@@@@@@@@@@@@@@@@@@
@@@@ @@@@ @@@@ @@@@ @@@@@@@@@@@@@@ @@@@ @@@@@ @@@@@ @@@@@ @Benchmarks
お待たせしました。2つのコンパイラの性能を比較してみましょう。
GraalはJavaで書かれており、コンパイラの分野での新しい研究を利用していますが、まだ比較的若いことを覚えておきましょう。一方のC2は非常によく調整されており、成熟しています。
さて、テスト方法論について一言申し上げます。すべてのテストは、i7 4.4GHz 32GBのノートPCで実行しました。異なるパラメータで数回テストを実行しましたが、結果は一貫しています。グラフの実際の値は、他のアプリケーションを実行していない同じセッションで取得したものです。
エンド・ツー・エンドのベンチマークを連続的に実行するパフォーマンステストと称されるテストを各プロジェクトで実行しています。この方法では、コンパイラが特定のケースに合わせてコードを最適化できません。そして、GCやOSの一時停止がないものと仮定して、より速い結果を選択しています。すべてのテストはモノスレッド（シングルスレッド）で実行しています。
以下は、多数回実行結果の平均をマイクロ秒の単位でグラフ化したものです。
での結果を示します。
これらの結果は、HotspotよりもGraalを使用した方が明らかにパフォーマンスが向上していることを示しています。その主な理由は、より洗練されたインライン化とエスケープ解析の最適化にあります。
Under the hood of GraalVM JIT optimizations
https://medium.com/graalvm/under-the-hood-of-graalvm-jit-optimizations-d6e931394797
いくつかのケースでは、Graal EE の特別な最適化（ループの展開など）がさらに有利に働いています。
An Interesting Case of Loop Unrolling
https://medium.com/wix-engineering/an-interesting-case-of-loop-unrolling-8ea04cf08959
方法論として、常にエンド・ツー・エンドの連続運転のベンチマークから始めることを提案しています。というのも、これがパフォーマンス・メトリクスを収集する最も安全な方法であり、これにより運用環境におけるパフォーマンスの最良の近似値を提供してくれるからです。
もしボトルネックがどこにあるのかをよりよく理解したいのであれば、より具体的なマイクロベンチマークを作成する必要があります。幸いなことに、これを正確に行うための非常に優れたライブラリがあります。
JMH
Java Micro-benchmark Harnessの登場です。JMHはJavaマイクロベンチマークを正しく実装するための作業を簡略化できるライブラリです。JMHはJVM開発者が作成したもので、JVM内部の性能テストに利用されています。このことはJMHの品質の高さを示していると捉えることができます。
Gradle（とKotlin）を使ってJMHをセットアップするには？
build.gradle ファイルを編集すればOKです。まずは依存関係を追加します。
testImplementation("org.openjdk.jmh:jmh-core:1.23")
testImplementation("org.openjdk.jmh:jmh-generator-annprocess:1.23")続いて、Gradle JMHプラグインを追加します。
plugins {
kotlin("jvm") version "1.3.70"
id("me.champeau.gradle.jmh") version "0.5.0"
}最後に、設定したいプロパティを持つセクションを追加します。完全なリストは以下のURLから確認いただけます。
JMH Gradle Plugin
https://github.com/melix/jmh-gradle-plugin
jmh {
jmhVersion = "1.23"jvmArgs = listOf(
"-Xms6g",
"-Xmx6g",
"-Dgraal.ShowConfiguration=info",
"-XX:+AlwaysPreTouch",
"-XX:+UnlockExperimentalVMOptions",
"-XX:+UseJVMCICompiler"
)
warmupForks = 0
fork = 2
warmupIterations = 5
iterations = 5
}How to create a test for JMH?
新たなベンチマークを作成するには、関数にアノテーションを付けるだけでOKです。
@Benchmark
fun knapsack(blackhole: Blackhole) {
blackhole.consume(Knapsack.selectWatches(shop, 199))
}ベンチマークのアノテーションには多くのオプションのパラメータがあり、デフォルトモードでは1秒間の演算をカウントしますが、テストを実行する方法は他にもたくさんあります。
このテストでは、計算結果を使って何もしていないため、blackholeクラスを使用してコンパイラがベンチマークを「デッドコード」とみなさないようにしていることがわかります。
結果を見てみましょう。
このグラフから、連続実行テストに比べて素のCPUパフォーマンスのほうが差が大きくなっていることがわかります。
これは、JMHがGCサイクルを避けるためにいくつかのテクニックを使用しているからです。対して、連続実行（通常は数秒から数分）の連続実行により、すべてのメモリが埋め尽くされ、full GCが必要になります。
GraalのGCは現在のところHotspotのものほど良くないので、これが結果の一端を説明することができます。良い面としては、Red Hatは現在、彼らの開発した優れたGCであるShenandoahをGraalVMに導入するために投資を行っています。これが実現するときには、新しいベンチマークを期待してください。
参考までに、書くテストの正確な設定は以下の通りです。
Hotspot /C2
# JMH version: 1.23
# VM version: JDK 11.0.6, OpenJDK 64-Bit Server VM, 11.0.6+9-jvmci-20.0-b02
# VM invoker: /home/ubertobarbini/.sdkman/candidates/java/20.0.0.r11-grl/bin/java
# VM options: -Xms6g -Xmx6g -Dgraal.ShowConfiguration=info -XX:+AlwaysPreTouch -XX:+UnlockExperimentalVMOptions -XX:-UseJVMCICompiler
# Warmup: 1 iterations, 10 s each
# Measurement: 1 iterations, 10 s each
# Timeout: 10 min per iteration
# Threads: 1 thread, will synchronize iterations
# Benchmark mode: Throughput, ops/timeBenchmark Mode Cnt Score Error Units
PerformanceMicroBenchmark.knapsack thrpt 10 12.686 ± 0.719 ops/s
PerformanceMicroBenchmark.mandelbrot thrpt 10 49.591 ± 1.796 ops/s
PerformanceMicroBenchmark.modularAlgebra thrpt 10 37.240 ± 3.422 ops/sGraal 20.0 CE
# JMH version: 1.23
# VM version: JDK 11.0.6, OpenJDK 64-Bit Server VM, 11.0.6+9-jvmci-20.0-b02
# VM invoker: /home/ubertobarbini/.sdkman/candidates/java/20.0.0.r11-grl/bin/java
# VM options: -Xms6g -Xmx6g -Dgraal.ShowConfiguration=info -XX:+AlwaysPreTouch -XX:+UnlockExperimentalVMOptions -XX:+UseJVMCICompiler
# Warmup: 5 iterations, 10 s each
# Measurement: 5 iterations, 10 s each
# Timeout: 10 min per iteration
# Threads: 1 thread, will synchronize iterations
# Benchmark mode: Throughput, ops/timeBenchmark Mode Cnt Score Error Units
PerformanceMicroBenchmark.knapsack thrpt 10 19.060 ± 1.854 ops/s
PerformanceMicroBenchmark.mandelbrot thrpt 10 85.828 ± 4.836 ops/s
PerformanceMicroBenchmark.modularAlgebra thrpt 10 71.653 ± 10.713 ops/sGraal 20.0 EE
# JMH version: 1.23
# VM version: JDK 11.0.6, Java HotSpot(TM) 64-Bit Server VM, 11.0.6+8-LTS-jvmci-20.0-b02
# VM invoker: /home/ubertobarbini/jvm/graalvm-ee-java11-20.0.0/bin/java
# VM options: -Xms6g -Xmx6g -Dgraal.ShowConfiguration=info -XX:+AlwaysPreTouch -XX:+UnlockExperimentalVMOptions -XX:+UseJVMCICompiler
# Warmup: 5 iterations, 10 s each
# Measurement: 5 iterations, 10 s each
# Timeout: 10 min per iteration
# Threads: 1 thread, will synchronize iterations
# Benchmark mode: Throughput, ops/timeBenchmark Mode Cnt Score Error Units
PerformanceMicroBenchmark.knapsack thrpt 10 24.595 ± 2.797 ops/s
PerformanceMicroBenchmark.mandelbrot thrpt 10 92.343 ± 8.087 ops/s
PerformanceMicroBenchmark.modularAlgebra thrpt 10 170.381 ± 106.960 ops/sConclusions
昨年はGraalは興味を引く新しいテクノロジーでしたが、今では本番に向けての準備ができているか、少なくとも真剣に検討される準備ができていると思います。興味深いことに、Kotlinを使用すると、Graalの採用に対する主要な障害の1つがなくなります。はっきり言うと、それはサポート対象のJavaバージョンです。現在GraalではJava8とJava11の2種類が利用できます。Graalが現在のJDKのバージョンと同等になるまでにはしばらく時間がかかるでしょうが、Kotlinの開発者にとってはこれは大きな問題ではありません。
いつものように、この記事のすべてのコードは私のGitHubリポジトリにあります。
uberto/kotlin-perf
https://github.com/uberto/kotlin-perf
類似の投稿に興味をお持ちでしたら、Mediumをフォローいただくか、Twitterアカウント @ramtop をフォローしてください。
Medium
https://medium.com/@ramtop
Twitter
https://twitter.com/ramtop
Logico Inside 