benchStrip
Cherry Blossoms

はじめに 

前回は、『ベンチマーク・フレームワーク』を作成しました。
そこで今回は、オリジナルを強敵に変更してフレームワークの検証を行います。

前提条件

お題は、String#strip を使用した文字列の左右空白のトリミングです。

今回も、オリジナルに勝てるかどうかの戦いです。

「敵を知り、己を知れば、百戦して殆(あや)うからず」(孫子)

ということで、オリジナル String#strip を調査しました。
このメソドは、Java 規約に基づいた空白判定(Character.isWhitespace)を使用する所が最大の特徴です。
(ちなみに、String#trim は、半角スペース以下をバッサリ切り捨てており String#strip より 1.7倍高速です)

  1. (1) String の内部データは、byte[] で普通なら強敵になりますが、今回は、配列を直接アクセスしていません。^^);
  2. (16,29) charAt でなく codePointAt, codePointBefore でコードポイントを取得します。
    これらは、String 内部メソドのため APPからの呼び出しは、ラッパー経由となり Jumpが1回増えます。
  3. (17,30) ホワイトスペースの判定は、Character.isWhitespace で行います。(結構、重い処理です)
  4. (20,33) Character.charCount で文字の長さを求めて、インデックスを更新します。
  5. (2,13,26) 配列サイズを求めるシフト演算が統一されいません。(>> にすべきです)
  6. このコードは、while 文が各々 1つあるだけで残りは、メソド呼び出しのためチューニングの余地は、ほとんどありません。
    やるとしたら、(4-6) のショートカットは、レアケースかつ newString で対応済みのため、工夫の余地がありますね。
// ORIGINAL: String#strip (UTF-16 Ver.)
01. public static String strip(byte[] value) {
02.   int length = value.length >>> 1;
03.   int left = indexOfNonWhitespace(value); // 左空白
04.   if (left == length) {
05.     return "";
06.   }
07.   int right = lastIndexOfNonWhitespace(value); // 右空白
08.   boolean ifChanged = (left > 0) || (right < length);
09.   return ifChanged ? newString(value, left, right - left) : null;
10. }

12. public static int indexOfNonWhitespace(byte[] value) { // 左空白
13.   int length = value.length >> 1;
14.   int left = 0;
15.   while (left < length) {
16.     int codepoint = codePointAt(value, left, length);
17.     if (codepoint != ' ' && codepoint != '\t' && !Character.isWhitespace(codepoint)) {
18.       break;
19.     }
20.    left += Character.charCount(codepoint);
21.   }
22.   return left;
23. }

25. public static int lastIndexOfNonWhitespace(byte[] value) { // 右空白
26.   int length = value.length >>> 1;
27.   int right = length;
28.   while (0 < right) {
29.     int codepoint = codePointBefore(value, right);
30.     if (codepoint != ' ' && codepoint != '\t' && !Character.isWhitespace(codepoint)) {
31.       break;
32.     }
33.     right -= Character.charCount(codepoint);
34.   }
35.   return right;
36. }

チャレンジャー

ということで、実績のある Trim をベースにコードを書きましたがオリジナルとほぼ同じコードになりました。
こういう場合は、アルゴリズム勝負になるため、対策は、折り込み済みです。

// CHALLENGER: strip.
01. public static String strip02Challenger(String s) {
02.   int length = s.length();
03.   int start = indexOfNonWhitespaceParts(s, length); // 左空白
04.   int end = lastIndexOfNonWhitespaceParts(s, start, length); // 右空白
05.   return end < length || 0 < start ? s.substring(start, end) : s;
06. }

// left Strip Parts.
08. private static int indexOfNonWhitespaceParts(String s, int end) { // 左空白
09.   int start = 0;
10.   while (start < end) {
11.     int c = s.codePointAt(start);
12.     if (c != SPACE && c != FULL_SPACE && c != TAB &&
13.         !Character.isWhitespace(c)) break;
14.     start += Character.charCount(c);
15.   }
16.   return start;
17. }

// right Strip Parts.
19. private static int lastIndexOfNonWhitespaceParts(String s, int start, int end) { // 右空白
20.   while (start < end) {
21.     int c = s.codePointBefore(end);
22.     if (c != SPACE && c != FULL_SPACE && c != TAB &&
23.         !Character.isWhitespace(c)) break;
24.     end -= Character.charCount(c);
25.   }
26.   return end;
27. }

ベンチマーク

ベンチマーク環境

Core i5 2.6GHz、MEM 8GB、Java 18、Windows 10 (Windows 11 非適合機)

実行オプション

  • JIT オプション
  • -XX:-TieredCompilation
    階層化コンパイル(C1)の使用を無効化(インタプリタ、コンパイラ(C2)かの二択)
    デフォルトでは、このオプションが有効になっています。
  • JIT コンパイラ
    今回のオプションでは、メソドが約1万回近く呼び出されると第1段階のコンパイルは完了します。
    ただしコンパイラは、奥が深くそんなに単純ではありません。(定期的に再コンパイルします。詳細は不明 ^^);

Case.1 最初の測定結果です

ターゲット 相対誤差 2nd 備考
1. strip.Original 0 0 オリジナル
2. strip.Challenger -0.03 -0.01 チャレンジャー
3. strip.Join -0.11 -0.12 チャレンジャーを 1メソドに結合
  • 相対誤差は、(測定値ー理論値)÷理論値(オリジナル値)で計算しています。
  • Join(メソド結合)が苦戦していますが、シンプルな方が効率的なコードに JIT コンパイルされるようです。
  • それでは、射程範囲内のようなので魔法の粉を振りかけます。

Case.2 の測定結果です

ターゲット 相対誤差 2nd 備考
1. strip.Original 0 0 オリジナル
2. strip.Challenger 0.08 0.10 チャレンジャー
3. strip.Join 0.05 0.08 チャレンジャーを一本に結合
  • 魔法の粉
  • ベンチマーク入力データの内、半角スペース 10文字を全角スペースに置き換えただけです。
  • 織り込んだコードは、(12,22) のショートカットに c != FULL_SPACE(全角スペース)を追加しています。

まとめ

今回は、「孫子の兵法」そのままの結末になりました。それでは、このあたりで締めたいと思います。

「う~さん長い間お疲れ様」『楽勝やったな、勝ってなんぼやからな』

オープンソース

インストール

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

実行

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

「Blog top」 2022.7.23