4

楽しみのために、ルールにとらわれないポーカー シミュレーターに取り組んでいます。列挙のボトルネックをテストし、「一意の」配列から常に引き出されるハンドについて、興味深いボトルネックを見つけました。各バリエーションを実行する平均計算時間を 1,000,000,000 回未満で測定し、それを 100 回繰り返して、JIT と Hotspot が魔法のように機能できるようにしました。私が見つけたのは、計算時間（6ns対27ns）に違いがあることでした

public int getRank7(int ... cards) {
  int q = (cards[0] >> 16) | (cards[1] >> 16) | (cards[2] >> 16) | (cards[3] >> 16) | (cards[4] >> 16) | (cards[5] >> 16) | (cards[6] >> 16);
  int product = ((cards[0] & 0xFF) * (cards[1] & 0xFF) * (cards[2] & 0xFF) * (cards[3] & 0xFF) * (cards[4] & 0xFF) * (cards[5] & 0xFF) * (cards[6] & 0xFF));
  if(flushes[q] > 0) return flushes[q];
  if(unique[q] > 0) return unique[q];
  int x = Arrays.binarySearch(products, product);
  return rankings[x];
}

と

public int getRank(int ... cards) {
  int q = 0;
  long product = 1;
  for(int c : cards) {
    q |= (c >> 16);
    product *= (c & 0xFF);
  }
  if(flushes[q] > 0) return flushes[q];
  if(unique[q] > 0) return unique[q];
  int x = Arrays.binarySearch(products, product);
  return rankings[x];
}

問題は間違いなく for ループであり、関数の先頭に乗算を処理することではありません。各シナリオで同じ数の操作を実行しているので、これには少し困惑しています...この関数には常に6枚以上のカードがあることに気付いたので、に変更して物事を近づけました

public int getRank(int c0, int c1, int c2, int c3, int c4, int c5, int ... cards)

しかし、カードの数が増えると同じボトルネックが発生します。この事実を回避する方法はありますか? そうでない場合、同じ数の操作の for ループが非常に遅い理由を誰かが説明してくれませんか?

4

2 に答える 2

3

大きな違いは分岐であることがわかると思います。forループのシナリオでは、forループの反復ごとにチェックと条件分岐が必要です。CPUは、どのブランチが実行されるかを予測し、それに応じてパイプライン命令を実行しますが、予測が誤っている場合（ループが終了すると、関数呼び出しごとに少なくとも1回）、パイプラインストールが停止します。これは非常にコストがかかります。

試してみる1つのことは、（配列の長さに基づくものではなく）固定された上限を持つ通常のforループです。Java JREはそのようなループを展開する可能性があり、その結果、より効率的なバージョンと同じ一連の操作が実行されます。

于 2012-05-02T04:37:24.527 に答える
0

この拡張forループでは、イテレータを設定する必要があります。これは、少数のアイテムしかない場合は比較的コストがかかります。

for従来のループを作成した場合のタイミングを確認するのは興味深いことです。

for (int i = 0; i < cards.length; ++i)
{
    q |= (cards[i] >> 16);
    product *= (cards[i] & 0xFF);
}

ただし、ループのオーバーヘッド（インデックスをインクリメントし、長さと比較し、ループの先頭に分岐する）があるため、それでも最初の例よりもわずかに遅くなる可能性があります。

いずれの場合も、ループオーバーヘッドにより、各反復にインクリメント、比較、および分岐が追加されます。そして、その比較では、に到達するためにポインタの逆参照が必要になる可能性がありますcards.length。ループのオーバーヘッドが、ループで実行している作業よりもはるかに高価であることは非常に妥当です。

于 2012-05-02T03:12:25.503 に答える