2

私は物理エンジンに取り組んでおり、多くの単純または複雑な数学演算を実行する速度とパフォーマンスへの影響をよりよく理解するのに役立つと感じています。

  1. 物理エンジンの大部分は不要な計算を取り除いていますが、比較チェックが必要ないほど計算が小さいのはどの時点でしょうか?

    • 例: 2 つの線分が交差するかどうかのテスト。簡単な計算に入る前に、それらが互いに近くにあるかどうかを確認する必要がありますか?それとも、余分な操作により、長期的にはプロセスが遅くなりますか?

  2. さまざまな数学的計算にかかる時間

    • 例: (3+8) vs (5x4) vs (log(8)) など

  3. 不等式チェックにはどのくらいの時間がかかりますか?

    • 例: >、<、=
4

6 に答える 6

4

  1. プロファイリングを行う必要があります。

  2. 加算や乗算などの基本的な操作は、1 つのasm命令のみで行う必要があります。

    編集: コメントによると、1 つの asm 命令を使用しますが、乗算はマイクロ命令に拡張できます。

    対数は時間がかかります。

  3. asm指示も一つ。

コードをプロファイリングしない限り、ボトルネックがどこにあるかを知る方法はありません。

数学演算を何百万回も呼び出さない限り (そしておそらく呼び出したとしても)、アルゴリズムを適切に選択するか、その他の高レベルの最適化を行うと、小さなものを最適化するよりも速度が大幅に向上します。

読みやすく、変更しやすいコードを作成する必要があります。パフォーマンスに満足できない場合にのみ、最適化を開始します。最初は高レベルで、その後は低レベルです。

また、動的プログラミングまたはキャッシングを試すこともできます。

于 2011-12-14T08:19:22.647 に答える
2

まあ、これはハードウェアに依存します。命令レイテンシーのある非常に優れたテーブルはhttp://www.agner.org/optimize/instruction_tables.pdfです。

1.コードに大きく依存します。また、計算だけに依存するのではなく、比較結果がどれだけうまく予測できるかにも依存することを忘れないでください。

2.一般に、加算/減算は非常に高速ですが、浮動小数点数の乗算は少し遅くなります。浮動小数点除算はかなり遅いです (定数 c で除算する必要がある場合は、1/c を事前に計算して乗算する方がよい場合がよくあります)。コンパイラーが SSE を使用することを決定しない限り、ライブラリー関数は通常 (あえて言えば常に) 単純な演算子よりも遅くなります。たとえば、sqrt() と 1/sqrt() は、1 つの SSE 命令を使用して計算できます。

3. 1サイクル程度から数十サイクル程度。現在のプロセッサは、条件に基づいて予測を行います。予想が当たれば早い。ただし、予測が間違っている場合、プロセッサはプリロードされた命令をすべて破棄し (IIRC Sandy Bridge は最大 30 命令をプリロードします)、新しい命令の処理を開始する必要があります。

つまり、ほとんどの場合条件が満たされるコードがある場合、それは高速になります。同様に、ほとんどの場合条件が満たされないコードがある場合、高速になります。単純な交互条件 (TFTFTF…) も通常は高速です。

于 2011-12-14T08:24:48.850 に答える
2

2 と 3 に関しては、Intel® 64 and IA-32 Architectures Optimization Reference Manualを参照してください。付録 C では、さまざまな命令のレイテンシとスループットを示します。ただし、アセンブリ コードを手作業でコーディングしない限り、コンパイラは独自の最適化を適用するため、この情報を直接使用することはかなり困難です。

さらに重要なことは、SIMD を使用してコードをベクトル化し、計算を並列実行できることです。また、メモリ レイアウトが理想的でない場合、メモリ パフォーマンスがボトルネックになる可能性があります。私がリンクしたドキュメントには、両方の問題に関する章があります。

ただし、@ Ph0en1x が言ったように、最初のステップは効率的なアルゴリズムを選択 (または作成) し、問題を解決することです。そうして初めて、低レベルの最適化について考え始める必要があります。

1 に関しては、一般的なケースとして、特定のテストをいつ実行するかについて、調整可能なしきい値があるような方法でアルゴリズムが機能する場合、プロファイリングを実行して、何らかのパフォーマンス グラフを出力できます。これらのしきい値の最適値を決定します。

于 2011-12-14T08:33:12.703 に答える
1
  1. これは、シミュレートしようとしているシナリオによって異なります。あなたはいくつのオブジェクトを持っていますか、そしてそれらはどれくらい近くにありますか？それらはクラスター化されていますか、それとも均等に分散されていますか？オブジェクトはたくさん動き回っていますか、それとも静的ですか？テストを実行する必要があります。近接性を高速にチェックするために考えられるデータ構造は、kdツリーまたは局所性鋭敏型ハッシュです（他にもある場合があります）。これらがアプリケーションに適しているかどうかはわかりません。データ構造の保守とルックアップコストに問題がないかどうかを確認する必要があります。
  2. テストを実行する必要があります。ベクトル化を使用できるかどうか、またはCUDAなどを使用してGPUで計算の一部を実行できるかどうかを確認することを検討してください。
  3. 上記と同じ-テストする必要があります。
于 2011-12-14T08:22:05.133 に答える
1

一般に、不等式チェック、インクリメント、デクリメント、ビット シフト、加算、減算は非常に安価であると考えることができます。掛け算と割り算は、一般的にもう少しコストがかかります。対数のような複雑な数学演算は、はるかにコストがかかります。

プラットフォームのベンチマークを確認してください。タイトなループを持つ人工的なテストを使用したベンチマークには注意してください。誤解を招く結果になる傾向があります。できるだけ現実的なコードでベンチマークするようにしてください。理想的には、現実的な条件下で実際のコードをプロファイリングします。

線の交差などの最適化に関しては、データ セットに依存します。多くのチェックを行い、ほとんどの行が短い場合は、X または Y の範囲が重なっていないケースを除外するために簡単なチェックを行う価値があります。

于 2011-12-14T08:24:54.927 に答える
0

私が知っている限り、すべての「不等式チェック」には同じ時間がかかります。
残りの計算に関しては、次のようないくつかのテストを実行することをお勧めします

  1. タイムスタンプAを取る
  2. 1,000,000の「+」計算（またはその他）を行います。
  3. タイムスタンプBを取る
  4. AとBの間の差分を計算します。

次に、計算を比較できます。

覚えておいてください：

  1. 異なる数学的ライブラリを使用すると、変更される可能性があります（一部の数学ライブラリは、パフォーマンス指向であり、精度指向です）
  2. コンパイラの最適化によって変更される場合があります。
  3. 各プロセッサはそれを異なる方法で実行しています。
于 2011-12-14T08:20:57.100 に答える