algorithm - 浮動小数点マージと整数マージの違いは何ですか？

Question

この論文では、アルゴリズムを比較するために、整数と浮動小数点の2つのケースを検討しました。

これらのデータ型のストレージに関する違いは理解していますが、なぜこれらの間に違いがあるのか​​わかりません。

次の2つのケースでパフォーマンスに違いがあるのはなぜですか

• 整数でのマージソートの使用
• フローティングポイントでのマージソートの使用

どちらの場合も速度の比較に帰着することを理解しています。問題は、なぜこれらの速度が異なるのかということです。

Answer 1

この論文では、セクション4「結論」で「CPU上の整数をマージするための実行時間は、CPU上の浮動小数点の実行時間より2.5倍速い」と述べています。この大きな違いは、測定に使用されたIntel NehalemXeonE5530では驚くべきことです。ただし、このペーパーでは、ソースコード、マージで使用される特定の命令またはプロセッサ機能、コンパイラバージョン、または使用されるその他のツールに関する情報は提供されていません。プロセッサが効率的に使用されている場合、整数マージと浮動小数点マージのパフォーマンスにはごくわずかな違いしかありません。したがって、テストで使用された浮動小数点コードは非効率的であり、プロセッサの欠点ではなく、使用されたツールが貧弱であることを示しているようです。

Answer 2

マージソートには、かなりの数の命令の内部ループがあります。フロートの比較は少し高価かもしれませんが、1〜2サイクルしかありません。はるかに大量のマージコード間での違いに気付くことはありません。

フロートの比較は、ハードウェアアクセラレーションであり、そのアルゴリズムで実行している他のすべてのものと比較して高速です。

また、比較は他の命令と重複する可能性があるため、実時間の差は正確にゼロ（またはそうでない）になる可能性があります。