performance - 掛け算と割り算のどちらを使うべきですか?

Question

ここにばかげた楽しい質問があります：

変数の値の半分が必要な単純な操作を実行する必要があるとしましょう。これには通常、次の 2 つの方法があります。

y = x / 2.0;
// or...
y = x * 0.5;

言語で提供されている標準の演算子を使用していると仮定すると、どちらがより優れたパフォーマンスを発揮しますか?

通常は乗算の方が優れていると思うので、コーディングするときはそれに固執しようとしますが、これを確認したいと思います。

個人的にはPython 2.4-2.5 の回答に興味がありますが、他の言語の回答も投稿してください。また、必要に応じて、他のより洗練された方法 (ビットごとのシフト演算子の使用など) も自由に投稿してください。

score 84 · Accepted Answer

パイソン:

time python -c 'for i in xrange(int(1e8)): t=12341234234.234 / 2.0'
real    0m26.676s
user    0m25.154s
sys     0m0.076s

time python -c 'for i in xrange(int(1e8)): t=12341234234.234 * 0.5'
real    0m17.932s
user    0m16.481s
sys     0m0.048s

乗算は 33% 高速です

ルア:

time lua -e 'for i=1,1e8 do t=12341234234.234 / 2.0 end'
real    0m7.956s
user    0m7.332s
sys     0m0.032s

time lua -e 'for i=1,1e8 do t=12341234234.234 * 0.5 end'
real    0m7.997s
user    0m7.516s
sys     0m0.036s

=>実際の違いはありません

ルアジット:

time luajit -O -e 'for i=1,1e8 do t=12341234234.234 / 2.0 end'
real    0m1.921s
user    0m1.668s
sys     0m0.004s

time luajit -O -e 'for i=1,1e8 do t=12341234234.234 * 0.5 end'
real    0m1.843s
user    0m1.676s
sys     0m0.000s

=>わずか 5% 高速です

結論: Python では、除算よりも乗算の方が高速ですが、より高度な VM または JIT を使用して CPU に近づくと、その利点はなくなります。将来の Python VM で不要になる可能性は十分にあります。

score 71 · Accepted Answer

常に最も明確なものを使用してください。それ以外のことは、コンパイラの裏をかこうとすることです。コンパイラが少しでもインテリジェントであれば、結果を最適化するために最善を尽くしますが、次の人があなたのくだらないビットシフトソリューションを嫌いになることはありません (ちなみに、私はビット操作が大好きです。それは楽しいです。しかし、楽しい != 読み取り可能)

時期尚早の最適化は諸悪の根源です。最適化の 3 つのルールを常に覚えておいてください。

最適化しないでください。
あなたが専門家なら、ルール＃1を参照してください
あなたが専門家であり、その必要性を正当化できる場合は、次の手順を使用してください。
- 最適化されていないコード
- 「十分に速い」とはどのくらいの速さであるかを判断します。どのユーザー要件/ストーリーがそのメトリックを必要としているかに注意してください。
- 速度テストを書く
- 既存のコードをテストします。十分に高速であれば、完了です。
- 最適化された再コーディング
- 最適化されたコードをテストします。基準を満たしていない場合は、破棄して元のものを保管してください。
- テストを満たしている場合は、元のコードをコメントとして保持します

また、不要な内部ループを削除したり、挿入ソートのために配列よりもリンクされたリストを選択したりすることは、最適化ではなく、単なるプログラミングです。

score 49 · Accepted Answer

これは非常につまらないものになっているので、コードを読みやすくするために何かをしたほうがよいと思います。何百万回とは言わないまでも、何千回も操作を実行しない限り、誰も違いに気付くことはないと思います。

本当に選択しなければならない場合は、ベンチマークが唯一の方法です。どの関数が問題を引き起こしているかを見つけ、関数のどこで問題が発生しているかを調べ、それらのセクションを修正します。ただし、1 つの数学演算 (何度も何度も繰り返される演算であっても) がボトルネックの原因になるとは思えません。

score 40 · Accepted Answer

乗算は高速で、除算はより正確です。数値が 2 のべき乗でない場合、精度がいくらか失われます。

y = x / 3.0;
y = x * 0.333333;  // how many 3's should there be, and how will the compiler round?

コンパイラに逆定数を完全な精度で計算させたとしても、答えは異なる場合があります。

x = 100.0;
x / 3.0 == x * (1.0/3.0)  // is false in the test I just performed

速度の問題は、C/C++ または JIT 言語でのみ問題になる可能性が高く、その場合でも操作がボトルネックでループしている場合にのみ問題になります。

score 26 · Accepted Answer

コードを最適化したいが明確にしたい場合は、これを試してください。

y = x * (1.0 / 2.0);

コンパイラはコンパイル時に除算を実行できる必要があるため、実行時に乗算が行われます。y = x / 2.0精度はケースと同じになると思います。

これが問題になる可能性があるのは、浮動小数点演算を計算するために浮動小数点エミュレーションが必要な組み込みプロセッサです。

score 21 · Accepted Answer

「他の言語」オプションに何かを追加するだけです。
C: これは単なるアカデミックな演習であり、実際には何の違いもありません。

最適化なしでアセンブリにコンパイルし、結果を確認しました。
コード：

int main() {

    volatile int a;
    volatile int b;

    asm("## 5/2\n");
    a = 5;
    a = a / 2;

    asm("## 5*0.5");
    b = 5;
    b = b * 0.5;

    asm("## done");

    return a + b;

}

でコンパイルgcc tdiv.c -O1 -o tdiv.s -S

2 による除算:

movl    $5, -4(%ebp)
movl    -4(%ebp), %eax
movl    %eax, %edx
shrl    $31, %edx
addl    %edx, %eax
sarl    %eax
movl    %eax, -4(%ebp)

および 0.5 による乗算:

movl    $5, -8(%ebp)
movl    -8(%ebp), %eax
pushl   %eax
fildl   (%esp)
leal    4(%esp), %esp
fmuls   LC0
fnstcw  -10(%ebp)
movzwl  -10(%ebp), %eax
orw $3072, %ax
movw    %ax, -12(%ebp)
fldcw   -12(%ebp)
fistpl  -16(%ebp)
fldcw   -10(%ebp)
movl    -16(%ebp), %eax
movl    %eax, -8(%ebp)

ただし、これらintの s をdoubles に変更すると (これはおそらく python が行うことです)、次のようになりました。

分割：

flds    LC0
fstl    -8(%ebp)
fldl    -8(%ebp)
flds    LC1
fmul    %st, %st(1)
fxch    %st(1)
fstpl   -8(%ebp)
fxch    %st(1)

乗算：

fstpl   -16(%ebp)
fldl    -16(%ebp)
fmulp   %st, %st(1)
fstpl   -16(%ebp)

このコードのベンチマークは行っていませんが、コードを調べるだけで、整数を使用すると、2 で除算する方が 2 で乗算するよりも短いことがわかります。おそらく、同じ操作にそれらを使用しないよりも高速に実行されます (ただし、実際にはわかりません)。したがって、最終的にこの回答は、0.5 による乗算と 2 による除算のパフォーマンスは、言語の実装とそれが実行されるプラットフォームに依存することを示しています。最終的に、違いは無視できるほどのものであり、読みやすさを除いて、ほとんど気にする必要はありません。

main()補足として、私のプログラムではが返されることがわかりますa + b。volatile キーワードを取り除くと、アセンブリがどのように見えるかを推測することはできなくなります (プログラムのセットアップを除く)。

## 5/2

## 5*0.5
## done

movl    $5, %eax
leave
ret

除算、乗算、および加算の両方を 1 つの命令で実行しました。明らかに、オプティマイザーがなんらかの立派なものであれば、これについて心配する必要はありません。

長すぎる回答で申し訳ありません。

score 10 · Accepted Answer

まず、C や ASSEMBLY で作業している場合を除き、メモリストールやゼネラルコールのオーバーヘッドにより、乗算と除算の違いが無意味になる高水準言語を使用している可能性があります。したがって、その場合に読みやすいものを選択してください。

非常に高いレベルから話している場合、それを使用する可能性が高いものに対して測定可能なほど遅くなることはありません. 他の回答でわかるように、2つのミリ秒未満の差を測定するためだけに、100万回の乗算/除算を行う必要があります。

低レベルの最適化の観点から、まだ興味がある場合は、次のようにします。

除算は、乗算よりもパイプラインが大幅に長くなる傾向があります。これは、結果を得るのに時間がかかることを意味しますが、プロセッサを非依存タスクでビジー状態に保つことができれば、乗算以上のコストはかかりません。

パイプラインの違いの長さは、完全にハードウェアに依存します。私が最後に使用したハードウェアは、FPU 乗算に 9 サイクル、FPU 除算に 50 サイクル程度でした。たくさん聞こえるかもしれませんが、メモリミスで 1000 サイクルを失うことになるので、大局的に考えることができます。

たとえば、テレビ番組を見ながら電子レンジにパイを入れます。テレビ番組から離れた合計時間は、テレビ番組を電子レンジに入れ、電子レンジから取り出すまでの時間です. 残りの時間は、まだテレビ番組を見ています。したがって、パイが調理するのに 1 分ではなく 10 分かかった場合、実際には、テレビを見る時間をそれ以上使い果たしたことにはなりません。

実際には、乗算と除算の違いを気にするレベルに到達するには、パイプライン、キャッシュ、ブランチストール、アウトオブオーダー予測、およびパイプラインの依存関係を理解する必要があります。これが、この質問で意図していたところと異なるように思われる場合、正しい答えは、2 つの違いを無視することです。

何年も前は、除算を避け、常に乗算を使用することが絶対に重要でしたが、当時はメモリヒットの関連性は低く、除算ははるかに悪かったです。最近は読みやすさを高く評価していますが、読みやすさに違いがない場合は、乗算を選択するのが良い習慣だと思います。

score 7 · Accepted Answer

あなたの意図をより明確に述べている方を書いてください。

プログラムが動作したら、何が遅いのかを突き止め、それを高速化します。

逆にしないでください。

score 6 · Accepted Answer

必要なことは何でもしてください。読者のことを第一に考えてください。パフォーマンスに問題があると確信できるまでは、パフォーマンスについて心配する必要はありません。

コンパイラにパフォーマンスを任せてください。

score 4 · Accepted Answer

実際には、一般的な経験則として、乗算は除算よりも高速であるという十分な理由があります。ハードウェアの浮動小数点除算は、シフトおよび条件付き減算アルゴリズム（2進数の「長除算」）を使用するか、最近ではゴールドシュミットのアルゴリズムのような反復を使用して行われます。シフトと減算には、精度のビットごとに少なくとも1サイクルが必要です（乗算のシフトアンドアドのように、反復を並列化することはほぼ不可能です）。反復アルゴリズムは、反復ごとに少なくとも1つの乗算を実行します。。いずれの場合も、分割にはさらに多くのサイクルがかかる可能性が高くなります。もちろん、これはコンパイラの癖、データの移動、または精度を考慮していません。ただし、概して、プログラムの時間に敏感な部分で内部ループをコーディングしている場合は、書くの0.5 * xで1.0/2.0 * xはなく、書くx / 2.0のが合理的なことです。「最も明確なものをコード化する」という衒学は絶対に真実ですが、これら3つはすべて読みやすさが非常に近いため、この場合は衒学者にすぎません。

score 4 · Accepted Answer

整数型または非浮動小数点型を使用している場合は、ビットシフト演算子を忘れないでください: << >>

    int y = 10;
    y = y >> 1;
    Console.WriteLine("value halved: " + y);
    y = y << 1;
    Console.WriteLine("now value doubled: " + y);

score 3 · Accepted Answer

乗算は通常より高速です - 確かに決して遅くはありません。ただし、速度が重要でない場合は、最も明確な方を記述してください。

score 2 · Accepted Answer

「通常は乗算の方が優れていると推測するので、コーディングするときはそれに固執するようにしています」と注意してください。

この特定の質問のコンテキストでは、ここでより良いとは「より速い」ことを意味します。これはあまり役に立ちません。

速度について考えるのは重大な間違いです。計算の特定の代数形式には重大なエラーの意味があります。

エラー分析による浮動小数点演算を参照してください。浮動小数点演算とエラー解析の基本的な問題を参照してください。

一部の浮動小数点値は正確ですが、ほとんどの浮動小数点値は近似値です。それらは、理想的な値に誤差を加えたものです。すべての操作は、理想値と誤差値に適用されます。

最大の問題は、ほぼ等しい 2 つの数を操作しようとすることです。右端のビット (エラービット) が結果を支配するようになります。

>>> for i in range(7):
...     a=1/(10.0**i)
...     b=(1/10.0)**i
...     print i, a, b, a-b
... 
0 1.0 1.0 0.0
1 0.1 0.1 0.0
2 0.01 0.01 -1.73472347598e-18
3 0.001 0.001 -2.16840434497e-19
4 0.0001 0.0001 -1.35525271561e-20
5 1e-05 1e-05 -1.69406589451e-21
6 1e-06 1e-06 -4.23516473627e-22

この例では、値が小さくなるにつれて、ほぼ等しい数の間の差により、正解がゼロである非ゼロの結果が作成されることがわかります。

score 2 · Accepted Answer

2

掛け算がより効率的であることを私はいつも学びました。

于 2008-10-22T16:07:12.597 に答える

score 2 · Accepted Answer

これは、アセンブリやおそらく C でプログラミングしている場合に、より大きな問題になります。最近のほとんどの言語では、このような最適化が行われていると思います。

score 2 · Accepted Answer

浮動小数点除算は (一般に) 特に遅いため、浮動小数点乗算も比較的低速ですが、おそらく浮動小数点除算よりも高速です。

しかし、プロファイリングで除算が乗算よりもボトルネックであることが示されない限り、「それはあまり重要ではありません」と答える傾向があります。ただし、乗算と除算のどちらを選択しても、アプリケーションのパフォーマンスに大きな影響はないと思います。

score 1 · Accepted Answer

除数が0でないことを確認するためにサイクルを費やす必要がないため、一般的に乗算をお勧めします。もちろん、除数が定数の場合、これは当てはまりません。

score 1 · Accepted Answer

C/C++ では乗算がより効率的であるとどこかで読んだことがあります。インタープリター言語についてはわかりません-他のすべてのオーバーヘッドのために、違いはおそらく無視できます。

それがより保守可能/読みやすいものに固執する問題にならない限り、人々が私にこれを言うのは嫌いですが、それは本当です。

score 1 · Accepted Answer

違いはありますが、コンパイラに依存します。最初は vs2003 (c++) で double 型 (64 ビット浮動小数点) に大きな違いはありませんでした。しかし、vs2010 で再度テストを実行すると、大きな違いが検出されました。乗算では最大 4 倍速くなりました。これを追跡すると、vs2003 と vs2010 は異なる fpu コードを生成するようです。

Pentium 4、2.8 GHz、vs2003:

乗算: 8.09
ディビジョン: 7.97

Xeon W3530、vs2003:

乗算: 4.68
分割: 4.64

Xeon W3530、vs2010 の場合:

乗算: 5.33
分割: 21.05

vs2003 では、ループ内の除算 (したがって、除数が複数回使用された) が逆数の乗算に変換されたようです。vs2010 では、この最適化は適用されなくなりました (2 つの方法で結果がわずかに異なるためだと思います)。また、分子が 0.0 になるとすぐに CPU が除算を高速に実行することにも注意してください。チップに組み込まれている正確なアルゴリズムはわかりませんが、数値に依存している可能性があります。

編集 18-03-2013: vs2010 の観察

score 1 · Accepted Answer

投稿 #24 (掛け算の方が速い) と #30 と同様に - ただし、どちらも同じように理解しやすい場合があります。

1*1e-6F;

1/1e6F;

~ どちらも読みやすく、何十億回も繰り返さなければなりません。したがって、乗算は通常より高速であることを知っておくと便利です。

score 1 · Accepted Answer

Java アンドロイド、Samsung GT-S5830 でプロファイリング

public void Mutiplication()
{
    float a = 1.0f;

    for(int i=0; i<1000000; i++)
    {
        a *= 0.5f;
    }
}
public void Division()
{
    float a = 1.0f;

    for(int i=0; i<1000000; i++)
    {
        a /= 2.0f;
    }
}

結果？

Multiplications():   time/call: 1524.375 ms
Division():          time/call: 1220.003 ms

割り算は掛け算よりも約 20% 高速です (!)

score 0 · Accepted Answer

このような長く興味深い議論の後、これについての私の見解は次のとおりです。この質問に対する最終的な答えはありません。一部の人々が指摘したように、それはハードウェア ( piotrkおよびgast128を参照) とコンパイラー ( @Javierのテストを参照) の両方に依存します。速度が重要でない場合、アプリケーションが大量のデータをリアルタイムで処理する必要がない場合は、除算を使用して明確にすることを選択できますが、処理速度またはプロセッサの負荷が問題になる場合は、乗算が最も安全な場合があります。最後に、アプリケーションがデプロイされるプラットフォームを正確に把握していない限り、ベンチマークは無意味です。また、コードを明確にするために、1 つのコメントで十分です。

score -1 · Accepted Answer

追加/サブトラック操作のコストが 1 であると仮定すると、コストを 5 倍し、コストを除算すると約 20 になります。

score -3 · Accepted Answer

技術的には、除算などはなく、逆要素による乗算だけがあります。たとえば、2 で割ることはなく、実際には 0.5 を掛けます。

「除算」 - それが存在することをちょっと冗談にしましょう - 1 で「除算」xするには、最初にそのようなy値を計算してから乗算を行う必要があるため、常に乗算よりも困難です。すでに知っている場合は、それを計算しないことは最適化に違いありません。y^{-1}y*y^{-1} = 1x*y^{-1}y^{-1}y

performance - 掛け算と割り算のどちらを使うべきですか?

25 に答える 25

Related

Reference