C の switch ステートメントのオーバーヘッド
https://stackoverflow.com/questions/927403
-
06-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私はかなり有能な Java プログラマーですが、C についてはまったくの初心者です。4 つの動作モードがあるルーチンを最適化しようとしています。
画像内のすべてのピクセルをループし、渡された「モード」に応じて新しいピクセル値を計算します。
私の質問は、2 つのネストされた for ループ内の switch ステートメントのオーバーヘッドに関するものです。基本的な C ステートメント、数学、論理演算の相対的な効率に関するドキュメントへのリンクに興味があります。
コードは次のようになります。
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
switch (mode) /* select the type of calculation */
{
case 0:
weight = dCentre / maxDistanceEdge;
case 1:
weight = (float)x/width;
break;
case 2:
weight = (float)y/height;
break;
case 3:
weight = dBottomLeft / maxDistanceCorner;
break;
case 4:
weight = dTopRight / maxDistanceCorner;
break;
default:
weight = 1;
break;
}
// Calculate the new pixel value given the weight
...
}
}
これが 5000 x 5000 ピクセルの画像を超える場合、多くのオーバーヘッドが発生すると予想されますか?いくつかのテストを実行しようとしましたが、システム（モバイルデバイス）がバックグラウンドで実行しているあらゆる種類のものが結果を歪める可能性があるため、結果はバラバラです。
もう 1 つのオプションは、各モードに個別のメソッドを用意し、それぞれに独自の 4 つのループを持たせることです。これにより明らかに冗長なコードが導入されますが、ここでは効率が重要です。
前もって感謝します！
ガブ
解決
switch文は、連続した値のためとスパース値についてのif-else文の束にジャンプテーブルにコンパイルします。あなたは、パフォーマンスを気にしている場合いずれにせよ、あなたは画像処理のためにあなたの内側のループ内のswitch文を望んでいません。代わりに以下のようにしたい。
また、Iは、内側ループのうちウエイト計算を移動（そしてこれを達成するために、ケース2のためのループを入れ替え）ことに注意してください。内側のループの外にものを動かす思考のこのタイプは、Cのうち、あなたが望むパフォーマンスを取得します。
switch (mode) /* select the type of calculation */
{
case 0:
weight = dCentre / maxDistanceEdge;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
case 1:
for (x = 0; x < width; x++) {
weight = (float)x/width;
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
case 2:
// note - the loops have been swapped to get the weight calc out of the inner loop
for (y = 0; y < height; y++) {
weight = (float)y/height;
for (x = 0; x < width; x++) {
// Calculate the new pixel value given the weight
...
}
}
break;
case 3:
weight = dBottomLeft / maxDistanceCorner;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
case 4:
weight = dTopRight / maxDistanceCorner;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
default:
weight = 1;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
// etc..
}
他のヒント
、[はい、あなたは冗長なルーチンを作成する必要があります。 case文を使用すると、Cで行うことができます下のオーバーヘッドものの一つですが、それはゼロではない - モードに基づいて分岐しているつもりだし、それには時間がかかるだろう。あなたは本当に最高のパフォーマンスをしたい場合は、でもループを複製のコストで、ループの外ケースを取得します。
switch文は、彼らはおそらく可能と同じくらい効率的です。これらは、ジャンプテーブルにコンパイルしています。実際には、スイッチは、それがある限り制限されている理由です：あなたはあなたがを対象のスイッチを書くことができます。の固定値に基づいてジャンプテーブルをコンパイルすることができます。
。あなたがループの中でやっている数学と比較すると、スイッチのオーバーヘッドは、おそらく最小限になります。それらを確認するための唯一の方法は、2つの異なるアプローチのための異なるバージョンを作成することである、と述べた、と時間た。
スイッチ/ケースは他/場合と同等に比べて非常に高速です。しかし、それはまだコストがあります。
あなたは物事を最適化しているもののます：
1）列（ループ「の」スイッチX、Y）の上に、一つの解決策が原因キャッシュメモリ管理に、他よりも非常に速いかもしれない、回線上のループしようとします。
2）（事前計算された）逆の乗算により、全部門を交換すると、あなたの重要なゲイン、およびおそらく許容可能な精度の損失が得られます。
効率を考えると移動したほうがいいです switch ループの外側。
私なら次のように関数ポインターを使用します。
double fun0(void) { return dCentre/maxDistanceEdge; }
double fun1(void) { return (float)x/width; }
/* and so on ... */
double (*fun)(void);
switch (mode) /* select the type of calculation */
{
case 0: fun = fun0;
break;
case 1: fun = fun1;
break;
case 2: fun = fun2;
break;
case 3: fun = fun3;
break;
case 4: fun = fun3;
break;
default : fun = fun_default;
break;
}
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
weight = fun();
// Calculate the new pixel value given the weight
...
}
}
関数呼び出しのオーバーヘッドが追加されますが、関数にパラメータを渡さないため、あまり大きくならないはずです。パフォーマンスと読みやすさの間の良いトレードオフだと思います。
編集： GCC を使用している場合、関数呼び出しを取り除くには、次のように使用できます。 goto そして 値としてのラベル: スイッチ内で適切なラベルを見つけて、毎回そこにジャンプするだけです。もう少しサイクルを節約できるはずだと思います。
スイッチは、任意の大きなオーバーヘッドをもたらすはずの、彼らはそれが効果的の場合ですが、ローエンドでのポインタの配列のソートにコンパイルされます：
JMP {BASEADDRESS} + switchcasenum
これはおそらく、あなたのコンパイラがスイッチ用のコードを生成し、どのように良いあなたのCPUの分岐予測があり、そしてどのように依存するであろう。例、このような少数の場合は、通常のCPUの分岐予測がオーバーヘッドの大部分を除去することができるはず、その場合、決定木を生成することがあります。それはスイッチ・テーブルを作成する場合は、物事は少しより悪いかもしれません...
を見つけるための最善の方法は、それをプロファイルして見ることである、と述べたこと。
Jimのアドバイスに加えて、ループの順序を交換してみてください。ループスワップは、ケース1のための理想的であるかどうかのテストが必要だろうが、私はそれがあると思います。あなたは、ほとんどの場合、これは、同じ一般的なメモリ領域に各反復滞在するには良い傾向を持っているあなたの関数を引き起こすので、あなたのxは、ページング性能を向上させるために、あなたの内側のループ内座標たいです。そしてlimittedリソースを持つモバイルデバイスは、この違いが強調されることを十分に低いラムを持っているかもしれません。
申し訳ありませんが、スイッチがFAR問題からであるように私には思える。
その場合の効率の本当の問題は部門です。除算の分母がすべての定数（幅、高さ、最大...）であり、これらは画像の過程を通じて変更されませんように私には思えます。私の推測が正しければ、これらは任意のサイズの画像が実行時に使用できるようにロードされた画像に基づいて変更することができ、単純な変数であり、その後、今、これがロードされる任意の画像サイズが可能になりますが、これはまた、コンパイラがそれらを最適化することができないことを意味します彼らは「CONST」を宣言した場合、それは行うことができますはるかに単純な乗算演算に。私の提案は、これらの定数の逆数を事前に計算し、乗算することであろう。私の知る限り覚えているとして、乗算演算は、除算が周りのピクセルあたり60サイクルの増加だ70をとり、約10クロック・サイクルを取り、そして上記の5000x5000で、それは、1.5秒の推定速度の増加が上です1 GHzのCPUます。
は、チップとコンパイラとコードの詳細に依存する、と...しかし、これは多くの場合、かなり高速である必要がありますジャンプテーブルとして実装されます。
BTW--この種のものを理解することはあなたのキャリアの中でいくつかの点でいくつかのアセンブリを学んで数週間を過ごすためのかなり良いの引数がある...
スイッチを使用すると、おそらく速度やプログラマの時間の両方に優れています。あなたはあまり冗長なコードを作っているし、それはおそらく、新しいスタックフレームを必要としません。
多くの良い点は、すでに与えられています。私はこれに追加すると考えることができる唯一の事は、スイッチおよび少なくとも頻繁に上下にまで最も頻繁に例を移動することです。
ケース4は、より頻繁にケース1より発生した場合、だから、それはそれより上である必要があります：
switch (mode) {
case 4:
// ..
break;
case 1:
// ..
break;
}
残念その後、switch文は、多型と置換することができるので、あなたは、C ++のを使用していませんでした。
乾杯！
5つの別々の機能を記述する必要がない方法のこのスレッドで創造的な提案がたくさんあります。
あなたは、ファイルまたは型指定された入力から「モード」を読んでいない限り、の計算方法は、コンパイル時に決定することができます。一般的なルールとして、あなたは時間を実行するために、コンパイル時から計算を移動する必要はありません。
コードが容易になるだろういずれかの方法で読み取り、誰があなたが最初のケースにbreak文を入れたりしないように意図か否かを混同しないであろう。
あなたは、周囲のコードのバグを取得するときにまた、あなたは、列挙型が間違った値に設定されたかどうかを調べる必要はありません。
内部ループに関して... 0->変数は、良好> 0 var-が行われます。このアプローチは、「幅」はXにロードされると、同じことが「高さ」のために行くことを忘れできることを意味します。また、メモリ内のピクセルは間違いなくあなたの内側のループとしてのxを持っているので、通常は左>右、トップ>下です。
for (y = height; y--;) {
for (x = width; x--;) {
weight = fun();
// Calculate the new pixel value given the weight
...
}
}
...また、非常に重要なあなたのswitch文だけxまたはyを使用して2例を持っています。残りは定数である。
switch (mode) /* select the type of calculation */
{
case 0:
weight = dCentre / maxDistanceEdge;
break;
//case 1:
// weight = (float)x/width;
// break;
//case 2:
// weight = (float)y/height;
// break;
case 3:
weight = dBottomLeft / maxDistanceCorner;
break;
case 4:
weight = dTopRight / maxDistanceCorner;
break;
default:
weight = 1;
break;
}
したがって、基本的にモード1又は2重量はループの前に計算されていない限ります。
... Y loop code here
if (mode == 2) { weight = (float)y/height; } // calc only once per Y loop
... X loop here
if (mode == 1) { weight = (float)x/width; } // after this all cases have filled weight
calc_pixel_using_weight(weight);
私は、データがまばらである場合には非常に不親切であることをswitch文を発見しました。 <4つの要素のために私はのために行くのif-then-elseと最も一般的な例は、トップアップしていることを確認してくださいと思います。最初の条件は、例の90％をキャッチする場合は、基本的にホームランを打ってきました。他のいくつかの条件が同様にあれば、<1％が、最後にそれを置きます。
