境界チェックを排除するforeach/forループの特殊なケースは何ですか？また、どの境界チェックですか？

状況：

私はLZF圧縮アルゴリズムのpure-java実装を最適化しています。これには、ハッシュと比較のための多くのbyte[]アクセスと基本的なint数学が含まれます。圧縮の目標はI/O要件を減らすことであるため、パフォーマンスは非常に重要です。コードはまだクリーンアップされておらず、大幅に再構築されている可能性があるため、コードを投稿していません。

質問：

• より高速なSSE操作を使用してフォームにJITコンパイルできるようにコードを作成するにはどうすればよいですか？
• コンパイラが配列境界チェックを簡単に排除できるように、どのように構造化できますか？
• 特定の数学演算の相対速度に関する幅広い参考資料はありますか（通常の加算/減算に等しくなるために必要な増分/減分の数、シフトの速度、または配列アクセスの速度）？
• 分岐の最適化にどのように取り組むことができますか？短い本体を持つ多数の条件ステートメント、またはいくつかの長いステートメント、またはネストされた条件を持つ短いステートメントがある方が良いですか？
• 現在の1.6JVMでは、System.arraycopyがコピーループを打ち負かす前に、いくつの要素をコピーする必要がありますか？

私がすでにしたこと：

時期尚早の最適化で攻撃される前に：基本的なアルゴリズムはすでに優れていますが、Javaの実装は同等のCの2/3未満の速度です。コピーループをSystem.arraycopyに置き換え、ループの最適化に取り組み、 -必要な操作。

私は、パフォーマンスのためにビットをいじったり、バイトをintにパックしたり、シフトやマスキングを多用しています。

法的な理由から、同様のライブラリの実装を確認することはできません。また、既存のライブラリのライセンス条項は制限が厳しすぎて使用できません。

良い（受け入れられた）答えの要件：

• 受け入れられない答え：「これはより速い」とは、その量と理由の説明がない場合、またはJITコンパイラでテストされていない場合です。
• 境界線の回答：Hotspot1.4より前では何もテストされていません
• 基本的な答え：一般的なルールと、コンパイラレベルで高速である理由と、おおよそどれだけ高速であるかについての説明を提供します
• 良い答え：デモンストレーション用のコードのサンプルをいくつか含めてください
• 優れた回答： JRE1.5と1.6の両方でベンチマークを実行する
• 完璧な答え： HotSpotコンパイラに取り組んだ人によるもので、使用する最適化の条件と、通常の速度を完全に説明または参照できます。HotSpotによって生成されたJavaコードとサンプルアセンブリコードが含まれる場合があります。

また、ホットスポットの最適化と分岐のパフォーマンスの要点を詳しく説明しているリンクがあれば、それを歓迎します。私はバイトコードについて十分に知っているので、ソースコードレベルではなくバイトコードでパフォーマンスを分析するサイトが役立つでしょう。

（編集）部分的な回答：境界-除去のチェック：

これは、次のHotSpot内部Wikiへの提供されたリンクから取得されます：https ：//wikis.oracle.com/display/HotSpotInternals/RangeCheckElimination

HotSpotは、次の条件ですべてのforループの境界チェックを排除します。

• 配列はループ不変です（ループ内で再割り当てされません）
• インデックス変数は一定のストライドを持ちます（可能な場合は1つのスポットでのみ一定量だけ増加/減少します）
• 配列は、変数の線形関数によってインデックスが付けられます。

例： int val = array[index*2 + 5]

また： int val = array[index+9]

いいえ： int val = array[Math.min(var,index)+7]

コードの初期バージョン：

これはサンプルバージョンです。これはH2データベースプロジェクトの未リリースバージョンのコードであるため、盗まないでください。最終バージョンはオープンソースになります。これは、ここのコードの最適化です：H2CompressLZFコード

論理的には、これは開発バージョンと同じですが、for（...）ループを使用して入力をステップスルーし、if/elseループを使用してリテラルモードと後方参照モードの間の異なるロジックを実行します。アレイへのアクセスを減らし、モード間のチェックを行います。

最終編集：

締め切りが迫っているので、これまでのところ、ベストアンサーをマークしました。私はコードを投稿することを決定する前に非常に長い時間がかかったので、私は可能な限り賛成票を投じてコメントに返信し続けます。 コードが乱雑な場合はお詫びします。これは開発中のコードであり、コミットのために洗練されたものではありません。

「ホットスポットは Java の境界チェックを削除できます。」誰でもこれを説明できますか？実際に C++ と Java の違いを分析しています。それは宿題ではなく、私自身の興味で分析しています。

そこにあるJVMのいくつかは、境界チェックを削除することでコードの実行を最適化できることを読みました。私が理解しようとしているのは、どのコーディング手法がより効果的に機能するかということです。

以下のメソッドexample1では、JVMはそれを理解し、 source [index]参照の境界チェックを排除しますか？

example2はより良いコードプラクティスですか？そう思われるかもしれませんが、ループ内の一部のアルゴリズムでは、インデックスが範囲外になっているのは正常な状態です。したがって、そのループ内で大量のExceptionオブジェクトを生成する必要はありません。

これらのコードフラグメントは、単なる表現です。これらの例では、境界チェックがパフォーマンスにほとんど影響しないことを認識しています。ただし、冗長境界チェックが追加される組み込みプロトコルアプリケーションに取り組んでいます。

私は最近、Dave Detlefs によるこの記事を読んでいました。この記事では、CLR が配列境界チェックの削除を実行するいくつかのケースを紹介しています。これを自分でテストすることにしたので、次のことを行いました。

• Visual Studio 2010 Ultimate SP1 をオープン
• コンソール アプリケーション タイプの新しい C# プロジェクトを作成しました (デフォルトで .NET 4 クライアント プロファイルを対象としています)。

• 次のコードを追加しました (すべてのサブメソッドは記事から直接取得されます)。

  /li>

• リリースモードに切り替えました。ビルドオプションで「コードの最適化」がチェックされていることを確認しました

• 各配列アクセスにブレークポイントを追加し、デバッグを開始 (F5) し、逆アセンブリ ウィンドウを開きました

a[i] = i; の分解は次のとおりです。Test_SimpleAscend で:

cmp/jb/call は境界チェックです。実際に呼び出しを強制的に実行すると、IndexOutOfRangeException がスローされます。

Test_SimpleRedundant の冗長アクセスを含む、すべての配列アクセスについて同じことが言えます。私のテスト方法論に何か問題がありますか、それとも CLR は境界チェックを実際に排除していませんか? 私が間違っていることを願っています。そうであれば、配列の境界チェックの削除を実際に取得する方法を知りたいです。

Boundedインデックスの種類がで、インデックスの範囲が である多数の配列を作成しています(minBound, maxBound)。このような配列の場合、境界チェックは不要です。境界チェックをなくすように GHC を説得するにはどうすればよいですか?

私の特定のアプリケーションでは、ボックス化された不変配列とボックス化されていない不変配列の両方を使用していますが、すべてのタイプの Haskell 配列に興味があります。

sw.ElapsedMilliseconds: ~2930ms

sw.ElapsedMilliseconds: ~3520ms

Win8x64、VS12、.NET4.5、リリースビルド、「コードの最適化」オン。

私の知る限り、配列境界チェックの最適化により、2 番目のアプローチの方が高速です。何か不足していますか？

ILGenerator を使用して記述された配列アクセスを含むシンプルな for ループがあります。この正確なコードでメソッドが作成されたら、逆アセンブリを開きますが、配列の境界チェックはありません。

しかし、最初に他のクラスのインスタンスを評価スタックに置いてから for ループを実行すると、配列の境界チェックが行われます。リリースに向けて動いています。

理由はありますか？配列境界チェックに関するブログ投稿を既に読みました: http://blogs.msdn.com/b/clrcodegeneration/archive/2009/08/13/array-bounds-check-elimination-in-the-clr.aspx

IL コードを生成するときに、クラスのインスタンスを評価スタックまたはローカル変数に保持する方がよいでしょうか?

たとえば、インスタンスを取得し、フィールドを通過し、各フィールドに対して何かを実行してから戻ります。インスタンスをスタックに保持し、次のフィールドを読み取る前に Emit(OpCodes.Dup) を呼び出しました。しかし、それは間違っているようです（少なくとも上記の場合）。

(効率的で整形式の) IL コードの生成に関する記事やブログ投稿を歓迎します。

低レベルのアルゴリズムが .net でどれほど効率的になるかに興味があります。将来的には、C++ ではなく C# でより多くのコードを記述できるようにしたいと考えていますが、1 つの障害は、ループと配列へのランダム アクセスで発生する .net の境界チェックです。

動機付けとなる例は、2 つの配列内の対応する要素の積の合計を計算する関数です (これは 2 つのベクトルの内積です)。

私が知る限り、IL または x86 をチェックするのに十分な知識がないため、コンパイラはX および Yの境界チェックを最適化しません。私は間違っていますか、またはコンパイラーが私を助けてくれるようにコードを書く方法はありますか?

詳細

特定の言語を使用することには賛否両論がありますが、特に、比例定数よりも「大規模な」アルゴリズムのコストに集中する方が良いという議論があり、高レベルの言語はこれを行うのに役立ちます。.net での境界チェックに関して、私が見つけた最良の記事は、MSDNの CLR での配列境界チェックの削除です(最適化を有効にすることの重要性に関するスタック オーバーフローの回答でも参照されています)。

これは2009年のことなので、その後大きく変わったのでしょうか。また、この記事は、私を捕らえたであろういくつかの本当の微妙な点を明らかにしているので、この理由だけでも、専門家のアドバイスを歓迎します.

たとえば、上記のコードi< X.Lengthでは、i < length. foreachまた、単一の配列を使用するアルゴリズムの場合、ループを作成すると、コンパイラに意図を宣言し、境界チェックを最適化する可能性が最も高くなると単純に想定していました。

MSDN の記事によると、SumForBAD最適化されるはずだと思っていた以下の は、そうではありません。一方SumFor、直接最適化され、SumForEach最適化もされますが、自明ではありません (また、配列が として関数に渡された場合、まったく最適化されない可能性がありますIEnumerable<int>)?

doug65536 の回答に基づいて調査を行いました。C++ で、境界チェックを 1 回行う SumProduct の時間を比較しました

2 つの境界チェックを行う別のバージョンに対して

2 番目のバージョンの方が遅いことがわかりましたが、約 3.5% (Visual Studio 2010、最適化されたビルド、既定のオプション) だけでした。しかし、C# では、境界チェックが 3 つある可能性があることに気付きました。1 つは明示的 (この質問の冒頭のi < length関数内)、2 つは暗黙的 ( and ) です。そこで、3 つの境界チェックを使用して 3 つ目の C++ 関数をテストしました。static void SumProduct(double[] X, double[] Y)X[i]Y[i]

これは最初のものより 35% 遅くなりましたが、これは気にする価値があります。この質問でさらに調査を行いました。追加のチェックインループを追加すると、一部のマシンでは大きな違いが生じ、他のマシンでは小さな違いが生じるのはなぜですか? . 興味深いことに、境界チェックのコストはマシンによって大きく異なるようです。

配列がビットごとの and を介して計算されるときに境界チェックを排除できるかどうかを調べるために、簡単なベンチマークを作成しました。これは基本的に、ほぼすべてのハッシュ テーブルが行うことです。

へのインデックスとして、tableはhまたはhashCode派生値です。結果は、境界チェックが排除されていないことを示しています。

私のベンチマークの考え方は非常に単純です。2 つの値iと を計算jします。両方とも有効な配列インデックスであることが保証されています。

• iループカウンターです。配列インデックスとして使用されると、境界チェックがなくなります。
• jとして計算されます。x & (table.length - 1)ここで、xは反復ごとに変化する値です。配列インデックスとして使用される場合、境界チェックは排除されません。

関連する部分は次のとおりです。

他の実験では

代わりは。タイミングの違いはおそらく 15% です (私が試したさまざまなバリアントでほぼ一貫しています)。私の質問:

• これには、バウンドチェックの排除以外に考えられる理由はありますか?
• バウンドチェックの削除がない理由がわからない複雑な理由がありますjか?

回答の要約

MarkoTopolnik の答えは、それがすべてより複雑であり、境界チェックの排除が勝利であるとは限らないことを示しています。特に彼のコンピューターでは、「通常の」コードは「マスクされた」コードよりも遅くなります。これは、この場合実際に有害であることが示されている追加の最適化を許可しているためだと思います（現在のCPUの複雑さを考えると、コンパイラーは確実に知ることさえほとんどありません）。

leventovの答えは、配列の境界チェックが「マスク」で行われ、それを排除することでコードが「通常」と同じくらい高速になることを明確に示しています。

x & (0-1)Donal Fellows は、長さが 0 のテーブルではマスキングが機能しないという事実を指摘していますx。したがって、コンパイラが実行できる最善の方法は、バウンド チェックを長さ 0 のチェックに置き換えることです。しかし、長さゼロのチェックはループから簡単に移動できるため、これはまだ価値があります。

提案された最適化

a[x & (a.length - 1)]if and only ifの等価スローa.length == 0により、コンパイラは次のことを実行できます。

• 配列アクセスごとに、インデックスがビットごとの and を介して計算されているかどうかを確認します。
• その場合、いずれかのオペランドが長さから 1 を引いたものとして計算されたかどうかを確認してください。
• その場合は、境界チェックを長さゼロのチェックに置き換えます。
• 既存の最適化に任せましょう。

このような最適化は、SSAグラフの親ノードのみを参照するため、非常にシンプルで安価です。多くの複雑な最適化とは異なり、1 つのチェックをわずかに単純なチェックに置き換えるだけなので、有害になることはありません。そのため、ループの外に移動できなくても問題はありません。

これを hotspot-dev メーリング リストに投稿します。

ニュース

John Rose がRFEを提出し、すでに「簡単な」パッチがあります。