Javaでint l、rの条件l + 1＆lt; rをチェックする最速の方法

StackOverflow https://stackoverflow.com/questions/1017480

  •  06-07-2019
  •  | 
  •  

質問

状態をチェックする最速の方法は何ですか

l + 1 < r

Javaの int l、r の場合

l と r は一定ではなく、 l＆lt; = r であることは知っています。比較は、バイナリ検索実装の while ループの停止条件です。もちろん、個別のテスト（大きな配列を検索）とそれを使用するコードの両方で、コードのベンチマークを行っています。

私が探しているのは、現在の状態よりも高速なビット操作の一種です。しかし、私は知りません。

役に立ちましたか？

解決

おそらく、それはすぐに得られると思います。それは非常に単純なバイトコードに削減され、JIT（ジャストインタイムコンパイラー）はおそらくそれを非常に単純なネイティブ実装に削減します。

（無関係： 'quant dev'がJava btwを使用しているのを見るのは興味深い。それほど頻繁には起こらない）

他のヒント

この種のマイクロ最適化は、ほとんど常に悪い考えです。そのような小さなビットのパフォーマンスは、ホットスポットコンパイラがコードを最適化する方法と、周囲のコードに関係する微妙なキャッシュ効果に完全に依存します。

基本的な比較は次のいずれかでなければなりません：

lに1を追加し、結果をrと比較します

または

rから1を減算し、結果をlと比較します

すべての最新のハードウェアは、どちらの操作でも同じ生のパフォーマンスを持ちます（ネイティブデータ型の加算と減算は、完了するサイクルとパイプラインの副作用に関して同一のパフォーマンスです）。

これが効果を発揮する唯一の方法は、次の場合です。

lまたはrのいずれかは、コンパイル時の既知の定数です。例：

l + 1 < 5
5 + 1 < r

この場合、貧弱な最適化コンパイラは、最初のコンパイラを l＆lt; 4

しかし、 all Javaコンパイラは、2番目のケースが 6＆lt;であることを見つける必要があります。 r

もう1つは、lとrのデータ型が異なる場合です。

の操作：

  1. 浮動小数点の加算/減算、intとの比較
    詩
  2. 整数の加算/減算とdoubleとの比較は異なる場合があります。

これらのいずれかのサイクルコストは、決定に関連する分岐予測ミスのパイプラインヒットと比較して小さいため、これがアプリケーションで深刻な問題になる可能性は無視できると言っても過言ではありません。

まともなJITは、実行されるマイクロ最適化を上回る周囲のコードに関連して、あらゆる種類の最適化を行う場合があります。

常に（l-r + 1）と等しい変数 lr1 を用意します。 l をインクリメントまたはデクリメントするたびに、 lr1 に対して同じことを行います。 r についても同様です。

テストは（lr1＆lt; 0）になり、 lr1 を変更する命令は必要以上に実行されません。

私はあなたに微最適化を与えるのは少しばかげていると感じますが、ほとんどの場合、それはペニーワイズで、馬鹿げています。文字列を比較する場合と同様に、そのテストは完全に圧倒されます。

追加：バイナリ検索をしているので、Jon Bentleyのクールなバイナリ検索の展開について言及します。最初に、テーブル A を1024などの2の累乗までパディングします。次に、次のように記述します。

i = 0;
if (X >= A[i+512]) i += 512;
if (X >= A[i+256]) i += 256;
   . . .
if (X >= A[i+  1]) i +=   1;

そして最後に（X == A [i]）かどうかをテストします。または、パディングしない場合は、 if ステートメントを
if（i + 512＆lt; N＆amp;＆amp; X＆gt; = A [ i + 512]）i + = 512;

これらすべての人が言ったこと。コンパイラはそれをあなたのために最適化します。見た目と読み方が適切になるように書き、次に進んでください。

最善の策は、これがあなたのボトルネックであることを考えると、コードではなくJVMを微調整することです。

引数 -server -XX：+ AggressiveOpts でjvmを起動してみてください。

等価性テストをwhileループの外側に移動して、終了後にのみ .equals（）をチェックする方法について。ちなみに、l + 1＆lt; rかどうかをテストする方法を少し工夫することはできませんでした。配列の長さが特定のサイズより小さいことがわかっている場合、インデックスに異なるデータ型を使用するとどうなりますか？ char / short / byte？

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top