2

java.lang.Integer.rotateLeftローテーション命令を使用して最適化され、そのベンチマークを作成したかどうかに興味がありました。結果は決定的ではありませんでした。2シフトよりもはるかに高速でしたが、1シフトよりも少し遅くなりました。だから私はそれをC++で書き直して、ほぼ同じ結果を得ました。経由でコンパイルすると、生成されたアセンブラg++ -S -Wall -O3で命令を確認できます。私のCPUはIntelCorei5です。

ベンチマークは非常に長く、確かに最高のコードではありませんが、壊れているとは思いません。またはそれは？ドキュメントによると、ローテーションはシフトと同じように1サイクルかかります。誰かが結果を説明できますか？

rotations:  6860
shift:      5100

最初の2つの答えは間違っています。gccとjavaのJITはどちらもローテーション命令を知っており、それらを使用します。gccについては、上記のリンクを参照してください。javaについては、私のJavaベンチマークとその結果を参照してください。

benchmark   ns linear runtime
   Rotate 3.48 ====================
NonRotate 5.05 ==============================
    Shift 2.16 ============
4

3 に答える 3

7

gccとjavajitが、SHIFTおよびOR演算子のシーケンスをROTATE命令に還元できることを認識できることを知りませんでしたが、これは非常に興味深いことです。

g ++コンパイラは、ループと使用法SHIFT immediateおよびROTATE immediate命令を展開します（定数値でシフトおよびローテーションするため）。

TimeShiftループ展開の場合に繰り返される6つの命令シーケンスは次のとおりです。

movq    %rax, %rbx
salq    $13, %rbx
leaq    (%rbp,%rbx), %rbx
movq    %rdi, %rbp
sarq    $27, %rbp
xorq    %rbx, %rdx

TimeRotateループ展開の場合に繰り返される6つの命令シーケンスは次のとおりです。

movq    %rdx, %rbx
rorq    $45, %rbx
leaq    (%rbp,%rbx), %rbx
movq    %r8, %rbp
rorq    $49, %rbp
xorq    %rbx, %r9

それらは主にsalq/sarqforSHIFTとrorqforの使用法ROTATEが異なるため、タイミングが異なる理由を疑問に思うのは正しいことです。

その答えは、Sandy Bridge（Core i5プロセッサー）のマイクロアーキテクチャーの奥深くにあり、INTEL®64およびIA-32プロセッサーアーキテクチャー最適化リファレンスマニュアル に記載されています。Order Number: 248966-026 April 2012

オペコードを使用するか、を使用するかにかかわらず、SHIFT命令には1サイクルのレイテンシがあります。またはのいずれかからディスパッチできます。このため、スループットは0.5サイクルです。プロセッサは、サイクルごとに2つの命令をディスパッチおよびリタイアできます。条件フラグの結果が必要な場合（gccによって生成されたコードに含まれていない場合）は3つのマイクロオペレーションが必要であり、そうでない場合は2つのマイクロオペレーション（この場合は2つのマイクロオペレーション）が必要です。ただし、命令はからディスパッチすることしかできないため、スループットは1サイクルです。プロセッサは、サイクルごとに1つだけディスパッチおよびリタイアできます。by 1by immediatePort 0Port 1SHIFT immediateROTATEROTATEPort 1ROTATE immediate

以下の関連する画像とセクションをコピーしました。

3.5.1.5ビット単位の回転

ビット単位のローテーションでは、CLレジスタで指定されたカウントでローテーションするか、イミディエート定数でローテーションするか、1ビットでローテーションするかを選択できます。一般に、即時回転およびレジスタ命令による回転は、1ビット回転よりも低速です。1回転命令は、シフトと同じレイテンシを持ちます。 アセンブリ/コンパイラコーディング規則35。（MLの影響、Lの一般性）レジスタによるROTATEまたは即時の指示によるROTATEを回避します。可能であれば、ROTATEby1命令に置き換えてください。 IntelマイクロアーキテクチャコードネームSandyBridgeでは、即時定数によるROL / RORのスループットは1サイクルであり、ソースおよび宛先と同じレジスタを即時定数で使用するSHLD / SHRDのレイテンシは1サイクルで、スループットは0.5サイクルです。「ROL/RORreg、imm8」命令には2つのマイクロオペレーションがあり、ローテーションレジスタの結果が1サイクル、フラグが使用されている場合は2サイクルのレイテンシがあります。IntelマイクロアーキテクチャコードネームIvyBridgeでは、1より大きい「ROL / RORreg、imm8」命令は、オーバーフローフラグの結果が使用される場合、1サイクルのレイテンシを持つ1つのマイクロオペレーションです。イミディエートが1の場合、後続の命令によるROL / RORのオーバーフローフラグの結果への依存は、2サイクルのレイテンシを持つROL/ROR命令を参照します。

2.4.4.2実行ユニットと発行ポート

各サイクルで、コアはµopsを4つの発行ポートの1つ以上にディスパッチする場合があります。マイクロアーキテクチャレベルでは、ストア操作はさらに2つの部分に分けられます。データの保存操作とアドレスの保存操作です。μopsが実行ユニットにディスパッチされ、操作をロードおよび保存するための4つのポートを図2-6に示します。一部のポートは、クロックごとに2 µopsをディスパッチできます。それらの実行ユニットは倍速とマークされています。

ポート0。サイクルの前半で、ポート0は1つの浮動小数点移動µop（浮動小数点スタック移動、浮動小数点交換、または浮動小数点ストアデータ）または1つの算術論理演算装置（ALU）µopのいずれかをディスパッチできます。 （算術、論理、分岐、またはデータの格納）。サイクルの後半では、同様のALU µopを1つディスパッチできます。

ポート1。サイクルの前半で、ポート1は1つの浮動小数点実行（移動を除くすべての浮動小数点演算、すべてのSIMD演算）µopまたは1つの通常速度整数（乗算、シフト、回転）µopまたは1つのALU（算術）µop。サイクルの後半では、同様のALU µopを1つディスパッチできます。

ポート2。このポートは、サイクルごとに1つのロード操作のディスパッチをサポートします。

ポート3。このポートは、サイクルごとに1つのストアアドレス操作のディスパッチをサポートします。

発行帯域幅の合計は、サイクルあたり0〜6 µopsの範囲です。各パイプラインには、いくつかの実行ユニットが含まれています。µopsは、正しいタイプの操作に対応するパイプラインにディスパッチされます。たとえば、整数演算論理演算ユニットと浮動小数点実行ユニット（加算器、乗算器、除算器）はパイプラインを共有できます。

図2-11。 アウトオブオーダーコアの実行ユニットとポート

于 2012-10-07T16:50:48.967 に答える
5

このベンチマークによると、シフトとローテーションはどちらもCPUで同じレイテンシーを持ちますが、ローテーションのスループットは低くなります（「T」としてリストされている結果は相互スループットであり、レイテンシーとより簡単に比較できます）。それはまさにあなたが見ているような結果をもたらす可能性があります-スループットの低下は少し邪魔になりますが、実行ユニットを完全に飽和させていなかったため、2の差の完全な要因を示していません。自分でテストするのは簡単ではありません。特に、コンパイラと戦って必要な命令を出力させる必要がある場合はそうではありません。

于 2012-10-07T19:32:31.163 に答える
1

マイクロベンチマークを見るときは、JITが一般的なパターン（シフトなど）を最適化することを考慮する必要があります。これは、一般的でないパターン（回転など）よりも効率的に認識します。これは、2つの操作で一方が他方よりも大幅に最適化されているため、同じ時間のパフォーマンスはまったく異なる可能性があります。たとえば、ループの展開やデッドコードの削除が増えます。

単純な指示でさえ相互作用して、異なる予期しない結果を生み出す可能性があります。言い換えると、単一の命令を見て、より多くの命令が使用されたときにそれがどのように実行されるかについて非常に多くのことを教えてくれると想定することはできません。このような低レベルでは、コンテキストが重要です。

これらの操作を現実的なプログラムで比較してみることをお勧めします。測定可能な違いを見つけるのは非常に難しいと思います。

于 2012-10-07T19:20:18.900 に答える