webdevqa.jp.net

ループ命令が遅いのはなぜですか? Intelはそれを効率的に実装できなかったでしょうか?

LOOP( Intel ref手動入力 )ecx/rcxをデクリメントし、 およびゼロ以外の場合はジャンプ 。遅いですが、Intelが安く高速にできなかったでしょうか? dec/jnzすでに 単一のuopへのマクロヒューズ Sandybridge-family;唯一の違いは、フラグを設定することです。

loopさまざまなマイクロアーキテクチャで、 Agner Fogの命令テーブル から:

  • K8/K10:7 m-ops
  • Bulldozer-family/Ryzen:1 m-op(マクロ融合テストアンドブランチと同じコスト、またはjecxz

  • P4:4 uops(jecxzと同じ)

  • P6(PII/PIII):8 uops
  • Pentium M、Core2:11 uops
  • ネハレム:6 uops。 (loope/loopneの場合は11)。スループット= 4c(loop)または7c(loope/ne)。
  • SnB-family:7 uops。 (loope/loopneの場合は11)。 スループット= 5サイクルに1つ、ループカウンターをメモリに保持するのと同じくらいのボトルネック! jecxzは、通常のjccと同じスループットの2 uopのみです。
  • シルバーモント:7 uops
  • AMD Jaguar(低電力):8 uops、5cスループット
  • Nano3000経由:2 uops

デコーダーはlea rcx, [rcx-1]/jrcxzと同じものをデコードできませんでしたか?それは3 uopsです。少なくとも、アドレスサイズのプレフィックスがない場合は、ecxを使用し、ジャンプが行われる場合はRIPEIPに切り捨てる必要があります。 デクリメントの幅を制御するアドレスサイズの奇妙な選択は、多くのuopsを説明していますか?

または、フラグを設定しない融合12進分岐としてデコードするだけですか? SnBのdec ecx/jnzは、単一のuop(フラグを設定する)にデコードします。

実際のコードでは使用されないことは知っています(少なくともP5かそれ以降は遅いので)が、AMDはブルドーザーで高速化する価値があると判断しました。簡単だったからでしょう。


  • SnBファミリのuarchが高速loopを持っているのは簡単でしょうか?そうだとしたら、なぜそうしませんか?そうでない場合、なぜ難しいのですか?デコーダートランジスターがたくさん?それとも、フラグが設定されていないことを記録するために、融合されたdec&branch uopの余分なビットですか?これら7つのuopは何をしているのでしょうか?それは本当に簡単な指示です。

  • 高速loopを簡単/価値のあるものにしたブルドーザーの特別な点は何ですか?または、AMDはloop fast?もしそうなら、おそらく誰かがそれは良い考えだと思った。


loopが速い場合BigInteger任意精度adcループ、部分的なフラグストール/スローダウンを避ける (私の回答に関する私のコメントを参照)、またはフラグに触れずにループしたいその他のケース。また、dec/jnzよりもコードサイズが小さいという利点があります。 (およびdec/jnz SnBファミリのマクロヒューズのみ)。

ADCループでdec/jnzが問題にならない現代のCPUでは、loopはADCX/ADOXループでは(OFを保持するために)依然として適切です。

loopが高速だった場合、コンパイラは既にマクロ融合なしのCPUのコードサイズ+速度のピープホール最適化としてそれを使用していました。


ループ内に別のカウンターが必要な場合でも、すべてのループにloopを使用する16ビットのコードが悪いと、すべての質問に悩まされることはありません。しかし、少なくともasにはなりません。

50
Peter Cordes

グーグルでafterで質問を書いたので、 comp.Arch の質問とまったく同じであることがわかりました。グーグルにするのは難しいと思っていました(「なぜループが遅いのか」というヒットがたくさんあります)が、最初の試行(why is the x86 loop instruction slow)で結果が得られました。

これは良い答えでも完全な答えでもありません。

それは私たちが得る最高のものかもしれませんし、誰かがそれについてもう少し光を当てることができない限り、十分でなければなりません。私はこれをanswer-my-own-questionの投稿として書くつもりはありませんでした。


そのスレッドでさまざまな理論を持つ良い投稿:

ロバート

かなりのパイプライン処理が開始されたとき、LOOPは初期のマシン(486年頃)のいくつかで遅くなり、パイプラインで最も単純な命令以外を効率的に実行することは技術的に非実用的でした。そのため、LOOPは多くの世代で低速でした。だから誰も使わなかった。したがって、それを高速化することが可能になったとき、実際にそれを使用している人はいなかったため、そうする本当のインセンティブはありませんでした。


アントンアートル

一部のソフトウェアでは、IIRC LOOPがタイミングループに使用されていました。 LOOPが速すぎるCPUで動作しない(重要な)ソフトウェアがありました(これは90年代前半頃でした)。そこで、CPUメーカーはLOOPを遅くすることを学びました。


(ポール、および他の誰も:あなたはあなた自身の文章をあなた自身の答えとして再投稿することを歓迎します。私はそれを私の答えから削除し、あなたの賛成票を投じます。)

@Paul A. Clayton(ときどき SOポスター およびCPUアーキテクチャーの男) 多くのuopの使用方法を推測しました 。 (これは、カウンターをチェックするloope/neのように見えますand ZF):

おそらく賢明な6-µopバージョンを想像できます。

virtual_cc = cc; 
temp = test (cc); 
rCX = rCX - temp; // also setting cc 
cc = temp & cc; // assumes branch handling is not 
       // substantially changed for the sake of LOOP 
branch 
cc = virtual_cc 

(これはLOOPE/LOOPNEのSnBの11ではなく、6 uopsであり、SnBのperfカウンターから既知のものを考慮に入れようとすることさえしない、完全な推測であることに注意してください。)

それからポールは言った:

短いシーケンスが可能であることに同意しますが、minimal microarchitecturalの調整が許可されている場合に意味があるかもしれない肥大化したシーケンスを考えていました。

要約:設計者は、loopをサポートすることを望んでいましたonlyマイクロコードを介して、ハードウェア自体の調整は一切行いません。

役に立たない互換性のみの命令がマイクロコード開発者に渡された場合、そのような命令を改善するために内部マイクロアーキテクチャに軽微な変更を提案することは合理的または不可能です。 「変更提案資本」をより生産的に使用するだけでなく、役に立たないケースに対する変更の提案は、他の提案の信頼性を低下させます。

(私の意見:インテルはおそらく意図的にそれを遅くしており、マイクロコードをlongの間書き換えることを気にしていません。現代のCPUは、おそらくloop素朴な方法で正しく動作します。)

...ポールは続けます:

Nanoの設計者は、LOOPの特別なケーシングを避けることで、面積または消費電力の観点から設計が簡素化されていることに気付いたかもしれません。または、(コード密度の利点のために)迅速な実装を提供する組み込みユーザーからのインセンティブがあったかもしれません。これらは単なる[〜#〜] wild [〜#〜]推測です。

LOOPの最適化が他の最適化(比較と分岐の融合など)から外れた場合、LOOPのパフォーマンスが重要ではない場合でも、マイクロコードでLOOPを処理するよりも、LOOPを高速パス命令に微調整する方が簡単な場合があります。

そのような決定は、実装の特定の詳細に基づいていると思います。そのような詳細についての情報は一般的に入手可能ではないようであり、そのような情報の解釈はほとんどの人のスキルレベルを超えています。 (私はハードウェアの設計者ではありません。テレビで遊んだり、Holiday Inn Expressに泊まったことはありません。:-)


その後、スレッドはトピックの範囲を超えてAMDの領域に移動し、x86命令エンコーディングの問題を解決する1つのチャンスを吹き飛ばしました。すべての変更はデコーダがトランジスタを共有できない場合であるため、それらを非難することは困難です。 Intelがx86-64を採用する前は、それが普及するかどうかさえ明確ではありませんでした。 AMDは、AMD64が追いつかなければ誰も使用していないハードウェアでCPUに負担をかけたくありませんでした。

しかし、それでも、非常に多くの小さなことがあります:setccは32ビットに変更される可能性があります。 (通常、xor-zero/test/setccを使用して、誤った依存関係を回避するか、ゼロ拡張regが必要なため)。シフトは、シフトカウントがゼロの場合でも、無条件に書き込まれたフラグを持つことができます(OOO実行の可変カウントシフトのeflagsへの入力データ依存性を削除します)。前回このペットpeevesのリストを入力したとき、3番目のものがあったと思います...ああ、メモリオペランドを持つbt/btsなどは、上位ビットに依存するアドレスを持ちます。インデックス(マシンWord内のビットだけでなく、ビット文字列)。

bts命令はビットフィールドの場合に非常に有用であり、必要以上に遅いため、ほとんど常にレジスタにロードしてから使用します。 (通常、Skylakeで10 uop bts [mem], regを使用する代わりに、自分でアドレスを取得するためにシフト/マスクする方が高速ですが、追加の命令が必要です。したがって、K8ではなく386で意味があります。アトミックビット操作ではmemory-dest形式を使用する必要がありますが、lockedバージョンでは多くのuopが必要です。動作しているdwordの外部にアクセスできなかった場合よりも、まだ遅いです。

26
Peter Cordes

1988年、IBMの仲間 Glenn Henry は、当時数百人の従業員を抱えていたDellに入社したばかりで、彼の最初の月に386の内部についての技術講演を行いました。私たちの多くのBIOSプログラマーは、なぜLOOPがDEC/JNZより遅いのか疑問に思っていたので、質問/回答セクションで誰かが質問を出しました。

彼の答えは理にかなっています。ページングに関係していました。

LOOPは2つの部分で構成されます。CXをデクリメントし、CXがゼロでない場合はジャンプします。最初の部分ではプロセッサ例外を発生させることはできませんが、ジャンプ部分では可能です。 1つは、セグメント境界外のアドレスにジャンプ(またはフォールスルー)して、SEGFAULTを引き起こす可能性があります。 2つの場合、スワップアウトされたページにジャンプできます。

通常、SEGFAULTはプロセスの終了を意味しますが、ページフォールトは異なります。ページフォールトが発生すると、プロセッサは例外をスローし、OSはハウスキーピングを実行して、ディスクからRAMにページをスワップします。その後、restarts障害の原因となった命令を再起動します。

再起動とは、プロセスの状態を問題のある命令の直前の状態に復元することを意味します。特にLOOP命令の場合、CXレジスタの値を復元することを意味していました。 CXが減少したことがわかっているので、CXに1を追加するだけでよいと思うかもしれませんが、どうやらそれはそれほど単純ではありません。たとえば、これをチェックしてください Intelのエラッタ

関係する保護違反は通常、可能性のあるソフトウェアバグを示しており、これらの違反のいずれかが発生した場合、再起動は望ましくありません。バスサイクル中に待機状態の保護モード80286システムでは、特定の保護違反が80286コンポーネントによって検出され、コンポーネントが制御を例外処理ルーチンに転送すると、CXレジスタの内容が信頼できない場合があります。 (CXの内容が変更されるかどうかは、内部マイクロコードが保護違反を検出したときのバスアクティビティの関数です。)

安全にするために、LOOP命令を繰り返すたびにCXの値を保存し、必要に応じて確実に復元する必要がありました。

LOOPを非常に遅くしたのは、CXを保存するこの余分な負担です。

Intelは、当時の他のすべての人々と同様に、RISCをますます増やしていました。古いCISC命令(LOOP、ENTER、LEAVE、BOUND)は段階的に廃止されていました。手動でコーディングされたアセンブリでそれらを使用しましたが、コンパイラはそれらを完全に無視しました。

14
I. J. Kennedy

Dr. Dobb's Journal March 1991 v16 n3 p16(8)に掲載されたマイケルのAbrashによる素敵な記事を参照してください: http://archive.gamedev.net/archive/reference/articles/article369.html =

記事の概要は次のとおりです。

8088、80286、80386、および80486マイクロプロセッサのコードを最適化することは困難です。これは、チップが大幅に異なるメモリアーキテクチャと命令実行時間を使用しているためです。 80x86ファミリ向けにコードを最適化することはできません。むしろ、コードは、さまざまなシステムで良好なパフォーマンスが得られるように設計するか、プロセッサとメモリの特定の組み合わせに対して最適化する必要があります。プログラマは、8088でサポートされている、後続のチップでパフォーマンスエッジを失った異常な命令を避ける必要があります。文字列命令を使用する必要がありますが、依存しないでください。メモリ操作ではなくレジスタを使用する必要があります。 4つのプロセッサすべての分岐も遅くなります。パフォーマンスを改善するには、メモリアクセスを調整する必要があります。一般に、80886の最適化には、8088の最適化とまったく逆の手順が必要です。

「8088でサポートされている異常な命令」とは、著者も「ループ」を意味します。

8088プログラマーは、本能的に次のように置き換えます。DEC CX JNZ LOOPTOPは、LOOP LOOPTOPに置き換えられます。LOOPは8088で非常に高速です。LOOPは286でも高速です。振り子は486でさらに揺れます。ループはDEC/JNZの約2倍遅いので、80x86命令セット全体でおそらく最も明白な最適化について話しています。

これは非常に良い記事であり、強くお勧めします。 1991年に公開されたにもかかわらず、今日では驚くほど関連性が高い。

しかし、この記事はアドバイスを提供するだけであり、実行速度をテストし、より高速なバリアントを選択することを推奨します。一部のコマンドが非常に遅くなる理由は説明されていないため、質問に完全には対応していません。

答えは、80386(1985年にリリースされた)などの以前のプロセッサは、命令を1つずつ順番に実行したということです。

その後、プロセッサは命令パイプラインを使用し始めました。最初は804086でシンプルで、最後にPentium Pro(1995年にリリース)は根本的に異なる内部パイプラインを導入し、命令を小さなフラグメントに変換するOut Of Order(OOO)コアと呼びますマイクロ操作またはマイクロ操作と呼ばれる操作を実行し、異なる命令のすべてのマイクロ操作は、相互に依存しない限り同時に実行されるはずのマイクロ操作の大きなプールに入れられました。このOOOパイプラインの原理は、現在のプロセッサでもほとんど変更されずに使用されています。このすばらしい記事で、命令のパイプライン処理の詳細を確認できます。 https://www.gamedev.net/resources/_/technical/general-programming/a-journey-through-the-cpu-pipeline-r3115

チップ設計を簡素化するために、Intelは、1つの命令が非常に効率的な方法でマイクロオペレーションに変換され、他の命令はそうではない方法でプロセッサを構築することを決定しました。

命令からマイクロオペレーションへの効率的な変換にはより多くのトランジスタが必要であるため、Intelは一部の「複雑な」または「まれに使用される」命令のデコードと実行を遅くするコストでトランジスタを節約することにしました。

たとえば、「インテル®アーキテクチャ最適化リファレンスマニュアル」 http://download.intel.com/design/PentiumII/manuals/24512701.pdf では、次のことに言及しています。 、入力、脱退、またはループ)。通常は4つ以上のµopがあり、デコードに複数のサイクルが必要です。代わりに簡単な指示のシーケンスを使用してください。」

そのため、Intelはどういうわけか「ループ」命令が「複雑」であると判断し、それ以降、非常に遅くなりました。ただし、命令の内訳に関する公式のIntelのリファレンスはありません。各命令が生成するマイクロオペレーションの数、およびデコードに必要なサイクル数です。

また、「Intel®64およびIA-32アーキテクチャ最適化リファレンスマニュアル」でOut-of-Order Execution Engineについて読むこともできます http://www.intel.com/content/dam/www/public/ us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf セクション2.1.2。

6
Maxim Masiutin