benchTrim
Cherry Blossoms

はじめに 

ネットで調べると『本格的なベンチマークは、難しい』と言われていますが、突っ込んだ HOW TO は、あまり見かけません。 そこで、う~さんは、こういうのが大好物なので、腕の見せどころとして挑戦することにしました。

前提条件

お題は、文字列の左右空白のトリミングです。

最初に断っておきますが、4~6は、同じようなアルゴリズムで性能差は、無いはずです。瞬間風速でもオリジナルを上回るかどうかの勝負です。

  1. regex.Classic(右トリム、伝統的な正規表現 /[\s]+$/)
  2. regex.New(右トリム、カスタマイズ正規表現 /[\0- ]+$/)
  3. Trim.Original(トリム、オリジナル)
  4. Trim.String(トリム、オリジナルのカスタマイズ Ver.)
  5. Trim.CharSeq(トリム、CharSequence Ver.)
  6. rTrim.String(右トリム)
  7. 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;
}
  1. String は、文字列を byte[] で実装しておりこれは、強敵です。 (APP からは、charAt しか無く toCharArray などは、論外です)
  2. 空白判定にスペース以下を使用しており、これは、#trim 仕様で速い、標準的な仕様は、String#strip で実装しています。
  3. このコードは、見た目のシンプルさを優先しているようで、ループの中で変数を2度演算しています。 ネイティブでは差が無いかもしれませんがここは、ツッコミ所ですね。
  1. は、ベンチマーク前に、JIT化し少しでも悪あがきしましょう。
  2. 仕様を丸呑みしましょう。
  3. 楽勝ですね。
  4. 文字サーチと最後の文字生成が処理のポイントです。

ベンチマーク フレームワーク(用語定義)

※テストケース: JIT オプションと APP オプションの組み合わせ
  ※ベンチマーク: クルーを複数回呼び出してベンチマークを実施
    ※クルー: ドライバを順番に呼び出してベンチマークを実施 (ウオームアップでも使用します)
      ※ドライバ: 担当のターゲットでベンチマークを実施
        ※ターゲット: ベンチマーク対象のメソド

実行オプション

  • JIT オプション
  • -XX:-TieredCompilation
    階層化コンパイル(C1)の使用を無効化(インタプリタ、コンパイラ(C2)かの二択)
    デフォルトでは、このオプションが有効になっています。
  • -XX:CompileThreshold=invocations
    コンパイル前の解析対象メソッドの呼出しの数を指定
    デフォルトで、サーバーJVMでは、JITコンパイラは、Solarisで 10,000回の解析対象メソッドの呼出しを実行して、効率的なコンパイルのための情報を収集します。 階層コンパイルが有効な場合、このオプションは無視されます。
    (※10,000の根拠は、見つけられないため。モグラ叩きしましたが差異は、見つけられませんでした)
  • -XX:MaxInlineSize=35(Byte)
    標準サイズでターゲットは、インライン化されます。(次に指定するなら、48Byte)
  • 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で設定するよう修正しました。

Case.1 まずは、ジャブで様子を見ます

  • JITオプション: 無し
  • APPオプション: ウオームアップ無効 (-warmup)、クールダウン無効 (-cool=0、-ice=0)
ターゲット 相対性能 相対誤差 番付 備考
1. regex.Classic 0.2 (0.23) ー ✗ 正規表現は、思いの外時間がかかります
2. regex.New 0.3 (0.35) ー ✗
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) ー ◎ 結果の文字列化が不要なため最も高速です
素の状態では、オリジナルと圧倒的な差があり勝負になりません。

Case.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) ー ◎
次のベンチマークで安定した数値を叩き出せれば本物です。

Case.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コンパイラの実力と難しさを再認識しました。

ベンチマークの鉄則

  1. 目標を設定して実施する
  2. ベンチマークは、優先度を上げたスレッドで実行する
  3. ウオームアップを実装し、ターゲット・ドライバを、JIT化する
  4. クールダウンを実装し、ウオームアップ及び本番時のクーリングを行う
  5. インライン化 (標準で 35Byte)を意識したコードを書く
  6. ベンチマークの解析
    • 誤差を小さくするため、母集団を大きくする (今回は、12クルー、ターゲットは、約350万回/クルー)
    • 性能は、基準となるターゲットとの相対値で判断する
    • 誤差は、相対誤差=(測定値ー理論値)÷理論値で計算する
  7. 待ち時間が長いとシンドイので、約1分になるように設定しています

最後に、う~さんの感想は、『しんど、かっった』だそうです。

「ベンチマーク」は、「リファクタリング」の必須ツールのため、この記事が皆様のお役に立てば幸いです。

オープンソース

インストール

  1. Java をダウンロード(環境を汚さない .zip 版を推奨、複数の Javaもインストールできます)「Java Downloads」
  2. benchTrim をダウンロード「benchTrim - Benchmark framework」 (コマンドを添付しています)
  3. benchTrim フォルダ中の makefile の JAVAHOME 変数に Javaホームパスを設定する。

実行

エクスプローラーで benchTrim フォルダを開き、上部のパンくずに と入力してターミナルを開き と入力します。

「Blog top」 2022.6.7