12

私はかなり有能な 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 つのループを持たせることです。これにより明らかに冗長なコードが導入されますが、ここでは効率が重要です。

前もって感謝します！

ガブ

4

16 に答える 16

19

Switch ステートメントは、連続する値の場合はジャンプ テーブルにコンパイルされ、スパース値の場合は一連の if-else ステートメントにコンパイルされます。いずれにせよ、パフォーマンスを気にする場合は、画像処理の内側のループに switch ステートメントは必要ありません。代わりに以下のようにしたい。

また、重みの計算を内側のループの外に移動したことに注意してください (これを実現するためにケース 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..
}
于 2009-05-29T18:30:29.547 に答える
5

ループで行っている計算と比較すると、スイッチのオーバーヘッドはおそらく最小になります。そうは言っても、確実にする唯一の方法は、2 つの異なるアプローチに対して異なるバージョンを作成し、時間を計ることです。

于 2009-05-29T18:20:34.683 に答える
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、ラベルを使用できます。スイッチ内で適切なラベルを見つけて、毎回それにジャンプします。あと数サイクル節約できるはずだと思います。

于 2009-05-29T20:17:32.420 に答える
1

Jim のアドバイスに加えて、ループの順序を入れ替えてみてください。ケース 1 でループスワッピングが理想的かどうかをテストする必要がありますが、理想的だと思います。ほとんどの場合、ページングのパフォーマンスを向上させるために、内部ループ内に x 座標を配置する必要があります。これにより、関数が反復ごとに同じ一般的なメモリ領域にとどまる傾向が向上するためです。また、リソースが限られているモバイル デバイスでは、RAM が十分に小さいため、この違いが強調される場合があります。

于 2009-05-29T19:24:59.903 に答える
1

このスレッドをぶつけて申し訳ありませんが、スイッチは問題から遠いようです。

その場合の効率に関する本当の問題は分割です。除算演算のすべての分母は定数 (幅、高さ、最大 ...) であり、これらは画像全体で変化しないようです。私の推測が正しければ、これらはロードされたイメージに基づいて変更できる単純な変数であるため、実行時に任意のサイズのイメージを使用できます。これにより、任意のイメージ サイズをロードできますが、これはコンパイラがそれらを最適化できないことも意味します。それらが「const」と宣言されている場合に実行できる、はるかに単純な乗算演算に変換されます。私の提案は、これらの定数の逆数を事前に計算して乗算することです。私が覚えている限り、乗算演算には約 10 クロック サイクルかかりますが、除算には約 70 サイクルかかります。これは、ピクセルあたり 60 サイクルの増加です。

于 2010-09-08T03:31:28.127 に答える
0

このスレッドには、5つの別々の関数を書く必要がない方法の創造的な提案がたくさんあります。

ファイルまたは入力された入力から「モード」を読み取らない限り、計算方法はコンパイル時に決定できます。原則として、計算をコンパイル時から実行時に移動することは望ましくありません。

どちらの方法でも、コードは読みやすくなり、最初のケースでbreakステートメントを挿入するつもりであるかどうかについて誰も混乱することはありません。

また、周囲のコードにバグが発生した場合、列挙型が間違った値に設定されているかどうかを調べる必要はありません。

于 2012-04-23T15:34:01.193 に答える
0

しかし、ここでのゲームの名前は効率です。

新しいピクセル値を計算するために画像バッファーを反復処理することは、典型的な驚異的並列問題のように聞こえます。この意味で、作業の一部をワーカースレッドにプッシュすることを検討することをお勧めします。これにより、マイクロ最適化よりも操作が大幅に高速化されます。スイッチ/ケースの懸念など。

また、毎回分岐命令を実行する代わりに、関数ポインターの配列から関数ポインターを呼び出すことができます。ここで、インデックスはモード識別子として機能します。

そのため、次のような呼び出しが発生します。

computeWeight[mode](pixel);

5000x5000ピクセルの場合、個々のピクセルではなく、ある範囲のピクセルに対して関数を呼び出すことで、関数呼び出しのオーバーヘッドを減らすこともできます。

これをさらに最適化するために、ループ展開と参照/ポインターによるパラメーターの受け渡しを使用することもできます。

于 2009-05-29T20:10:02.607 に答える
0

すでに多くの良い点があります。これに追加することを考えることができる唯一のことは、スイッチで最も頻度の高いケースを上に移動し、最も頻度の低いケースを下に移動することです。

したがって、ケース4がケース1よりも頻繁に発生する場合は、その上にある必要があります。

switch (mode) {
    case 4:
        // ..
        break;
    case 1:
        // ..
        break;
}

残念ながら、c ++を使用していなかったのは、switchステートメントをポリモーフィズムに置き換えることができたためです。

乾杯 ！

于 2009-05-29T21:11:50.143 に答える