はじめに
ネットで調べると本格的なベンチマークは、難しいと言われていますが、突っ込んだ HOW TO は、あまり見かけません。 そこで、う~さんは、こういうのが好物なので、腕の見せどころとして挑戦することにしました。
前提条件
お題は、文字列の左右空白のトリミングです。
最初に断っておきますが、4~6は、同じようなアルゴリズムで性能差は、無いはずです。瞬間風速でもオリジナルを上回るかどうかの勝負です。
- regex.Classic(右トリム、伝統的な正規表現 /[\s]+$/)
- regex.New(右トリム、カスタマイズ正規表現 /[\0- ]+$/)
- Trim.Original(トリム、オリジナル)
- Trim.String(トリム、オリジナルのカスタマイズ Ver.)
- Trim.CharSeq(トリム、CharSequence Ver.)
- rTrim.String(右トリム)
- rTrim.Builder(右トリムの StringBuilder Ver.)
「敵を知り、己を知れば、百戦して殆(あや)うからず」(孫子)
ということで、オリジナル(String#trim) の実装を調べました。
// ORIGINAL: String#trim (LATIN1 Ver.)
public static String trim(byte[] value) {
int len = value.length;
int st = 0;
while ((st < len) && ((value[st] & 0xff) <= ' ')) {
st++;
}
while ((st < len) && ((value[len - 1] & 0xff) <= ' ')) {
len--;
}
return ((st > 0) || (len < value.length)) ?
newString(value, st, len - st) : null;
}
- String は、文字列を byte[] で実装しておりこれは、強敵です。 (APP からは、charAt しか無く toCharArray などは、論外です)
- 空白判定にスペース以下を使用しており、これは、#trim 仕様で速い、標準的な仕様は、String#strip で実装しています。
- このコードは、見た目のシンプルさを優先しているようで、ループの中で変数を2度演算しています。 ネイティブでは差が無いかもしれませんがここは、ツッコミ所ですね。
- は、ベンチマーク前に、JIT化し少しでも悪あがきしましょう。
- 仕様を丸呑みしましょう。
- 楽勝ですね。
- 文字サーチと最後の文字生成が処理のポイントです。
ベンチマーク フレームワーク(用語定義)
※テストケース: JIT オプションと APP オプションの組み合わせ
※ベンチマーク: クルーを複数回呼び出してベンチマークを実施
※クルー: ドライバを順番に呼び出してベンチマークを実施
※ドライバ: 担当のターゲットでベンチマークを実施
※ターゲット: ベンチマーク対象のメソド
実行オプション
- JIT オプション
- -XX:-TieredCompilation
階層化コンパイル(C1)の使用を無効化(インタプリタ、コンパイラ(C2)かの二択)
デフォルトでは、このオプションが有効になっています。
- -XX:CompileThreshold=invocations
コンパイル前の解析対象メソッドの呼出しの数を指定
デフォルトで、サーバーJVMでは、JITコンパイラは、Solarisで 10,000回の解析対象メソッドの呼出しを実行して、効率的なコンパイルのための情報を収集します。
階層コンパイルが有効な場合、このオプションは無視されます。
(※10,000の根拠は、見つけられないため。モグラ叩きしましたが差異は、見つけられませんでした)
- -XX:MaxInlineSize=35(Byte)
標準サイズでターゲットは、インライン化されます。(次に指定するなら、48B)
- APP ウオームアップ オプション
- -warmup - ウオームアップの無効化
- -prefetch=11,000回 - プレフェッチ (charAt など、お守りとして実装します)
- -loop=100(ms) - 本番環境に負荷をかける実行時間(目安は、10,000回以上、時間指定のため CPU依存です)
- APP クールダウン オプション
- JITに働いてもらうためと、CPUの寿命を延ばすために使用します ^^)
ベンチマーク環境
Core i5 2.6GHz、MEM 8GB、Java 18、Windows 10 (Windows 11 非適合機)
ベンチマーク ターゲット・ドライバの例
呼び出し元のコンパクト化とインライン化を期待して、小さなパーツに分割しています。
// left Trim Parts. (左トリム、パーツ)
private static int leftTrimParts(CharSequence s, int end) {
int start = 0;
while (start < end && ' ' >= s.charAt(start))
start++;
return start;
}
// right Trim Parts. (右トリム、パーツ)
private static int rightTrimParts(CharSequence s, int start, int end) {
while (start <= --end)
if (' ' < s.charAt(end)) break;
return end + 1;
}
// 4. trim. (ターゲット、String#trim相当)
public static String trim04String(String s) {
int length = s.length();
int start = leftTrimParts(s, length);
int end = rightTrimParts(s, start, length);
return end < length || 0 < start ? s.substring(start, end) : s;
}
// 4. trim. (ドライバ、単位時間当たりの実行数を求める)
private static void bench4TrimString() {
long nano = loop_time;
int counter = 0;
String rs;
do {
long start = System.nanoTime();
rs = Trim.trim04String(test_data);
nano -= System.nanoTime() - start;
counter++;
} while (0 < nano);
assert ans_both.equals(rs) : rs;
if (isPrint)
System.err.println("\t4. Trim.String\t" + counter);
}
ベンチマーク
ベンチマークは、他からの影響を避けるために高優先度で起動します。(Linux なら nice)
start /realtime cmd /c make bench1
Java Thread で優先度を変更できるのを思い出し、APPで設定するよう修正しました。
#1 まずは、ジャブで様子を見ます
- JITオプション: 無し
- APPオプション: ウオームアップ無効 (-warmup)、クールダウン無効 (-cool=0、-ice=0)
ターゲット |
相対性能 |
相対誤差 |
番付 |
備考 |
1. regex.Classic |
0.2 (0.23) |
ー |
✗ |
正規表現は、思いの外時間がかかります |
2. regex.New |
0.3 (0.35) |
ー |
✗ |
JIT化すると 1.2.の順序は、逆転します |
3. Trim.Original |
0.9 (0.89) |
0 |
ー |
|
4. Trim.String |
0.8 (0.84) |
-0.05 |
★ |
4~7 は、同じパーツを使用しています |
5. Trim.CharSeq |
0.8 (0.83) |
-0.06 |
★ |
|
6. rTrim.String |
0.8 (0.84) |
-0.05 |
★ |
|
7. rTrim.Builder |
1 (1) |
ー |
◎ |
結果の文字列化が不要なため最も高速です |
素の状態では、オリジナルと圧倒的な差があり勝負になりません。
#2 JITオプションの指定
まずは、分かりやすいオプションを指定してみます。
- JITオプション: -XX:-TieredCompilation (インタプリタかC2かの二択)
(インタプリタ → C1 → C2 とコンパイルされます)
- APPオプション: ウオームアップ・クールダウン オプションの有効化 (既定値)
ターゲット |
相対性能 |
相対誤差 |
番付 |
備考 |
1. regex.Classic |
0.1 (0.15) |
ー |
✗ |
|
2. regex.New |
0.1 (0.08) |
ー |
✗ |
|
3. Trim.Original |
1.0 (1.00) |
0 |
④ |
|
4. Trim.String |
1.0 (1.05) |
0.05 |
① |
当たり |
5. Trim.CharSeq |
1.0 (1.01) |
0.01 |
② |
トリプルですね |
6. rTrim.String |
1.0 (1.01) |
0.01 |
② |
|
7. rTrim.Builder |
1 (1) |
ー |
◎ |
|
次のベンチマークで安定した数値を叩き出せれば本物です。
#3 これでトリプルが出れば決まりです
- JITオプション
- -XX:CompileThreshold=10,000 (コンパイル前に解析対象メソッドの呼出しの数を設定)
- -XX:-TieredCompilation (インタプリタかC2かの二択)
- -XX:MaxInlineSize=48 (インライン化のしきい値を指定)
- APPオプション: ウオームアップ・クールダウン オプションの有効化 (既定値)
ターゲット |
相対性能 |
相対誤差 |
番付 |
備考 |
1. regex.Classic |
0.1 (0.12) |
ー |
✗ |
|
2. regex.New |
0.1 (0.07) |
ー |
✗ |
|
3. Trim.Original |
0.8 (0.80) |
0 |
④ |
|
4. Trim.String |
0.9 (0.85) |
0.06 |
① |
トリプルになる確率は、結構高いですよ |
5. Trim.CharSeq |
0.8 (0.85) |
0.06 |
① |
|
6. rTrim.String |
0.8 (0.84) |
0.05 |
③ |
|
7. rTrim.Builder |
1 (1) |
ー |
◎ |
|
安定しているようなので、ベンチマークの標準パターンは、これに決定です。
まとめ
ズルは、していませんよ! ただしウオームアップで、charAtなどを単独で JIT化するのでなく、
オリジナルのライバル達を最初にJIT化しています。 正直ここまでチューニングできるとは、思いませんでした。おかげで JITコンパイラの実力と難しさを再認識しました。
ベンチマークの鉄則
- 目標を決めて実施する
- ベンチマークは、優先度を上げたスレッドで実行する
- ウオームアップを実装し、ターゲット・ドライバを、JIT化する
- クールダウンを実装し、ウオームアップ及び本番時のクーリングを行う
- インライン化 (標準で 35B)を意識したコードを書く
- ベンチマークの解析
- 誤差を小さくするため、母集団を大きくする (今回は、12クルー、ターゲットは、約350万回/クルー)
- 性能は、基準となるターゲットとの相対値で判断する
- 誤差は、相対誤差=(測定値ー理論値)÷理論値で計算する
- 待ち時間が長いとシンドイので、1分になるように設定しています
最後に、う~さんの感想は、『しんど、かっった』だそうです。
オープンソース
インストール
- Java をダウンロード(環境を汚さない .zip 版を推奨、複数の Javaもインストールできます)「Java Downloads」
- benchTrim をダウンロード「benchTrim - Benchmark
framework」 (コマンドを添付しています)
- benchTrim フォルダ中の makefile の JAVAHOME 変数に Javaホームパスを設定する。
実行
エクスプローラーで benchTrim フォルダを開き、上部のパンくずに と入力してターミナルを開き
と入力します。