[解決済み] なぜJavaでは2 * (i * i)の方が2 * i * iより速いのですか？

2022-03-20 01:24:03

質問

次のJavaプログラムの実行時間は平均0.50秒から0.55秒である。

public static void main(String[] args) {
    long startTime = System.nanoTime();
    int n = 0;
    for (int i = 0; i < 1000000000; i++) {
        n += 2 * (i * i);
    }
    System.out.println((double) (System.nanoTime() - startTime) / 1000000000 + " s");
    System.out.println("n = " + n);
}

を置き換えると 2 * (i * i) で 2 * i * i の場合、0.60秒から0.65秒の間で実行されます。なぜでしょうか？

各バージョンを交互に15回ずつ実行しました。以下はその結果です。

 2*(i*i)  |  2*i*i
----------+----------
0.5183738 | 0.6246434
0.5298337 | 0.6049722
0.5308647 | 0.6603363
0.5133458 | 0.6243328
0.5003011 | 0.6541802
0.5366181 | 0.6312638
0.515149  | 0.6241105
0.5237389 | 0.627815
0.5249942 | 0.6114252
0.5641624 | 0.6781033
0.538412  | 0.6393969
0.5466744 | 0.6608845
0.531159  | 0.6201077
0.5048032 | 0.6511559
0.5232789 | 0.6544526

の最速ラン 2 * i * i の最も遅い実行よりも時間がかかりました。 2 * (i * i) . もし、両者の効率が同じであれば、このようなことが起こる確率は、以下のようになります。 1/2^15 * 100% = 0.00305% .

解決方法は？

バイトコードの順番に若干の違いがあります。

2 * (i * i) :

     iconst_2
     iload0
     iload0
     imul
     imul
     iadd

対 2 * i * i :

     iconst_2
     iload0
     imul
     iload0
     imul
     iadd

一見したところ、これは違いがないように見えます。むしろ、2番目のバージョンの方が1スロット少なく使えるので、より最適です。

そこで、下位レベル（JIT）をもっと掘り下げる必要があります。 ¹ .

JITは小さなループを積極的にアンロールする傾向があることを思い出してください。実際、ループを16倍に展開することができます。 2 * (i * i) の場合です。

030   B2: # B2 B3 <- B1 B2  Loop: B2-B2 inner main of N18 Freq: 1e+006
030     addl    R11, RBP    # int
033     movl    RBP, R13    # spill
036     addl    RBP, #14    # int
039     imull   RBP, RBP    # int
03c     movl    R9, R13 # spill
03f     addl    R9, #13 # int
043     imull   R9, R9  # int
047     sall    RBP, #1
049     sall    R9, #1
04c     movl    R8, R13 # spill
04f     addl    R8, #15 # int
053     movl    R10, R8 # spill
056     movdl   XMM1, R8    # spill
05b     imull   R10, R8 # int
05f     movl    R8, R13 # spill
062     addl    R8, #12 # int
066     imull   R8, R8  # int
06a     sall    R10, #1
06d     movl    [rsp + #32], R10    # spill
072     sall    R8, #1
075     movl    RBX, R13    # spill
078     addl    RBX, #11    # int
07b     imull   RBX, RBX    # int
07e     movl    RCX, R13    # spill
081     addl    RCX, #10    # int
084     imull   RCX, RCX    # int
087     sall    RBX, #1
089     sall    RCX, #1
08b     movl    RDX, R13    # spill
08e     addl    RDX, #8 # int
091     imull   RDX, RDX    # int
094     movl    RDI, R13    # spill
097     addl    RDI, #7 # int
09a     imull   RDI, RDI    # int
09d     sall    RDX, #1
09f     sall    RDI, #1
0a1     movl    RAX, R13    # spill
0a4     addl    RAX, #6 # int
0a7     imull   RAX, RAX    # int
0aa     movl    RSI, R13    # spill
0ad     addl    RSI, #4 # int
0b0     imull   RSI, RSI    # int
0b3     sall    RAX, #1
0b5     sall    RSI, #1
0b7     movl    R10, R13    # spill
0ba     addl    R10, #2 # int
0be     imull   R10, R10    # int
0c2     movl    R14, R13    # spill
0c5     incl    R14 # int
0c8     imull   R14, R14    # int
0cc     sall    R10, #1
0cf     sall    R14, #1
0d2     addl    R14, R11    # int
0d5     addl    R14, R10    # int
0d8     movl    R10, R13    # spill
0db     addl    R10, #3 # int
0df     imull   R10, R10    # int
0e3     movl    R11, R13    # spill
0e6     addl    R11, #5 # int
0ea     imull   R11, R11    # int
0ee     sall    R10, #1
0f1     addl    R10, R14    # int
0f4     addl    R10, RSI    # int
0f7     sall    R11, #1
0fa     addl    R11, R10    # int
0fd     addl    R11, RAX    # int
100     addl    R11, RDI    # int
103     addl    R11, RDX    # int
106     movl    R10, R13    # spill
109     addl    R10, #9 # int
10d     imull   R10, R10    # int
111     sall    R10, #1
114     addl    R10, R11    # int
117     addl    R10, RCX    # int
11a     addl    R10, RBX    # int
11d     addl    R10, R8 # int
120     addl    R9, R10 # int
123     addl    RBP, R9 # int
126     addl    RBP, [RSP + #32 (32-bit)]   # int
12a     addl    R13, #16    # int
12e     movl    R11, R13    # spill
131     imull   R11, R13    # int
135     sall    R11, #1
138     cmpl    R13, #999999985
13f     jl     B2   # loop end  P=1.000000 C=6554623.000000

スタック上に"spilled"されているレジスタが1つあることがわかります。

また 2 * i * i のバージョンになります。

05a   B3: # B2 B4 <- B1 B2  Loop: B3-B2 inner main of N18 Freq: 1e+006
05a     addl    RBX, R11    # int
05d     movl    [rsp + #32], RBX    # spill
061     movl    R11, R8 # spill
064     addl    R11, #15    # int
068     movl    [rsp + #36], R11    # spill
06d     movl    R11, R8 # spill
070     addl    R11, #14    # int
074     movl    R10, R9 # spill
077     addl    R10, #16    # int
07b     movdl   XMM2, R10   # spill
080     movl    RCX, R9 # spill
083     addl    RCX, #14    # int
086     movdl   XMM1, RCX   # spill
08a     movl    R10, R9 # spill
08d     addl    R10, #12    # int
091     movdl   XMM4, R10   # spill
096     movl    RCX, R9 # spill
099     addl    RCX, #10    # int
09c     movdl   XMM6, RCX   # spill
0a0     movl    RBX, R9 # spill
0a3     addl    RBX, #8 # int
0a6     movl    RCX, R9 # spill
0a9     addl    RCX, #6 # int
0ac     movl    RDX, R9 # spill
0af     addl    RDX, #4 # int
0b2     addl    R9, #2  # int
0b6     movl    R10, R14    # spill
0b9     addl    R10, #22    # int
0bd     movdl   XMM3, R10   # spill
0c2     movl    RDI, R14    # spill
0c5     addl    RDI, #20    # int
0c8     movl    RAX, R14    # spill
0cb     addl    RAX, #32    # int
0ce     movl    RSI, R14    # spill
0d1     addl    RSI, #18    # int
0d4     movl    R13, R14    # spill
0d7     addl    R13, #24    # int
0db     movl    R10, R14    # spill
0de     addl    R10, #26    # int
0e2     movl    [rsp + #40], R10    # spill
0e7     movl    RBP, R14    # spill
0ea     addl    RBP, #28    # int
0ed     imull   RBP, R11    # int
0f1     addl    R14, #30    # int
0f5     imull   R14, [RSP + #36 (32-bit)]   # int
0fb     movl    R10, R8 # spill
0fe     addl    R10, #11    # int
102     movdl   R11, XMM3   # spill
107     imull   R11, R10    # int
10b     movl    [rsp + #44], R11    # spill
110     movl    R10, R8 # spill
113     addl    R10, #10    # int
117     imull   RDI, R10    # int
11b     movl    R11, R8 # spill
11e     addl    R11, #8 # int
122     movdl   R10, XMM2   # spill
127     imull   R10, R11    # int
12b     movl    [rsp + #48], R10    # spill
130     movl    R10, R8 # spill
133     addl    R10, #7 # int
137     movdl   R11, XMM1   # spill
13c     imull   R11, R10    # int
140     movl    [rsp + #52], R11    # spill
145     movl    R11, R8 # spill
148     addl    R11, #6 # int
14c     movdl   R10, XMM4   # spill
151     imull   R10, R11    # int
155     movl    [rsp + #56], R10    # spill
15a     movl    R10, R8 # spill
15d     addl    R10, #5 # int
161     movdl   R11, XMM6   # spill
166     imull   R11, R10    # int
16a     movl    [rsp + #60], R11    # spill
16f     movl    R11, R8 # spill
172     addl    R11, #4 # int
176     imull   RBX, R11    # int
17a     movl    R11, R8 # spill
17d     addl    R11, #3 # int
181     imull   RCX, R11    # int
185     movl    R10, R8 # spill
188     addl    R10, #2 # int
18c     imull   RDX, R10    # int
190     movl    R11, R8 # spill
193     incl    R11 # int
196     imull   R9, R11 # int
19a     addl    R9, [RSP + #32 (32-bit)]    # int
19f     addl    R9, RDX # int
1a2     addl    R9, RCX # int
1a5     addl    R9, RBX # int
1a8     addl    R9, [RSP + #60 (32-bit)]    # int
1ad     addl    R9, [RSP + #56 (32-bit)]    # int
1b2     addl    R9, [RSP + #52 (32-bit)]    # int
1b7     addl    R9, [RSP + #48 (32-bit)]    # int
1bc     movl    R10, R8 # spill
1bf     addl    R10, #9 # int
1c3     imull   R10, RSI    # int
1c7     addl    R10, R9 # int
1ca     addl    R10, RDI    # int
1cd     addl    R10, [RSP + #44 (32-bit)]   # int
1d2     movl    R11, R8 # spill
1d5     addl    R11, #12    # int
1d9     imull   R13, R11    # int
1dd     addl    R13, R10    # int
1e0     movl    R10, R8 # spill
1e3     addl    R10, #13    # int
1e7     imull   R10, [RSP + #40 (32-bit)]   # int
1ed     addl    R10, R13    # int
1f0     addl    RBP, R10    # int
1f3     addl    R14, RBP    # int
1f6     movl    R10, R8 # spill
1f9     addl    R10, #16    # int
1fd     cmpl    R10, #999999985
204     jl     B2   # loop end  P=1.000000 C=7419903.000000

ここでは、より多くのquot;spilling"とスタックへのより多くのアクセスを観察します。 [RSP + ...] これは、保存する必要のある中間結果が多いためです。

したがって、質問の答えは簡単です。 2 * (i * i) よりも高速です。 2 * i * i なぜなら、JITは最初のケースでより最適なアセンブリコードを生成するからです。

x86-64のCPUは少なくともSSE2をサポートしているので、ループはベクトル化の恩恵を受けることができるのです。

つまり、オプティマイザの問題です。よくあることですが、オプティマイザは積極的にアンロールしすぎて、他のさまざまな機会を逃しながら、自分の足を撃ってしまうのです。

実際、最新のx86-64 CPUでは、命令がさらにマイクロオプス（μops）に分解され、レジスタのリネーム、μopsキャッシュ、ループバッファなどの機能により、ループ最適化は、最適なパフォーマンスを得るために単純なアンロールよりもずっと繊細な作業が必要です。 Agner Fogの最適化ガイドによると :

μopキャッシュによる性能向上は、かなり大きいです。平均的な命令長が4バイト以上であれば、かなりの効果が期待できます。 μopキャッシュの使用を最適化する方法として、以下のようなものが考えられます。が考えられます。

重要なループは、µopキャッシュに収まるように十分に小さくしてください。

最も重要なループエントリと関数エントリを32で整列させる。

不要なループのアンロールを避ける。

余分なロード時間のかかる命令を避ける
. . .

ロードタイムについて最速のL1Dヒットでも4サイクルのコストがかかるそのため、メモリへのアクセスが数回あっただけでも、タイトなループではパフォーマンスが低下します。

しかし、ベクトル化の機会に話を戻しましょう。同じような C アプリケーションを GCC でコンパイルしてみましょう。 AVX2が表示され、SSE2が類似しています。 ² :

  vmovdqa ymm0, YMMWORD PTR .LC0[rip]
  vmovdqa ymm3, YMMWORD PTR .LC1[rip]
  xor eax, eax
  vpxor xmm2, xmm2, xmm2
.L2:
  vpmulld ymm1, ymm0, ymm0
  inc eax
  vpaddd ymm0, ymm0, ymm3
  vpslld ymm1, ymm1, 1
  vpaddd ymm2, ymm2, ymm1
  cmp eax, 125000000      ; 8 calculations per iteration
  jne .L2
  vmovdqa xmm0, xmm2
  vextracti128 xmm2, ymm2, 1
  vpaddd xmm2, xmm0, xmm2
  vpsrldq xmm0, xmm2, 8
  vpaddd xmm0, xmm2, xmm0
  vpsrldq xmm1, xmm0, 4
  vpaddd xmm0, xmm0, xmm1
  vmovd eax, xmm0
  vzeroupper

ランタイム付き

SSE：0.24秒、つまり2倍の速さです。
AVX：0.15秒、つまり3倍速。
AVX2: 0.08秒、または5倍速。

¹ <サブ JITで生成されたアセンブリ出力を取得する。デバッグJVMを取得するで実行し -XX:+PrintOptoAssembly

² <サブ Cバージョンは、コンパイル時に -fwrapv フラグを使用すると、GCC は符号付き整数のオーバーフローを 2 の補集合の折り返しとして扱います。

[解決済み] なぜJavaでは2 * (i * i)の方が2 * i * iより速いのですか？

質問

解決方法は？

関連

undefinedeclipse エラー。この行に複数のアノテーションが見つかりました: - 文字列を型解決に解決できない

スレッド "main" で例外発生 java.lang.ArrayIndexOutOfBoundsException: 0 at One1.main(One1.java:3)

Maven Pluginの実行がライフサイクル設定の対象外であるエラーの解決

[解決済み] この2回（1927年）を引き算すると、なぜおかしな結果になるのでしょうか？

[解決済み] JavaでInputStreamを読み込んでStringに変換するにはどうすればよいですか？

[解決済み] JavaでNullPointerExceptionを回避する方法

[解決済み] B "の印刷が "#"の印刷より劇的に遅いのはなぜですか？

[解決済み] 要素ごとの加算は、結合ループよりも分離ループの方がはるかに高速なのはなぜですか？

[解決済み] なぜC++はPythonよりもstdinからの行の読み込みが遅いのですか？

[解決済み] <は<=より速いのか？

最新

nginxです。[emerg] 0.0.0.0:80 への bind() に失敗しました (98: アドレスは既に使用中です)

htmlページでギリシャ文字を使うには

ピュアhtml+cssでの要素読み込み効果

純粋なhtml + cssで五輪を実現するサンプルコード

ナビゲーションバー・ドロップダウンメニューのHTML+CSSサンプルコード

タイピング効果を実現するピュアhtml+css

htmlの選択ボックスのプレースホルダー作成に関する質問

html css3 伸縮しない画像表示効果

トップナビゲーションバーメニュー作成用HTML+CSS

html+css 実装サイバーパンク風ボタン

おすすめ

springboot project MIMEタイプ text/htmlで転送された静的ファイルを読み込む。

java の例外が発生しました java

undefinedeclipse エラー。この行に複数のアノテーションが見つかりました: - 文字列を型解決に解決できない

java Mail send email smtp is not authenticated by TLS encryption solution.

eclipse の実行時に java 仮想マシンが見つからなかった

エラーの解決方法 jarfile XXX.jarにアクセスできません。

spring aop アドバイスからの Null 戻り値が、サマリーのプリミティブ戻り値と一致しない。

javaでクラスを作成すると、enclosing classでないように見える

[解決済み] Javaで正しいマイクロベンチマークを書くには？

[解決済み] 各種キャッシュやメインメモリにアクセスするためのコストの目安は？