C言語編 目次

　関数設計

　

・関数名の命名規則
・プログラミングに出る！英単語

　ポインタ

　

・データ型とポインタ

　データ型

　

・char *とconst char *は違う

　演算子

　

・三項演算子とデータ型の問題

　制御構文

　

・条件式で代入する
・三項演算子を使ったswitch

　構造体

　

・構造体のサイズとアライメント
・構造体メンバのサイズを知る

　配列

　

・配列使用時の注意
・配列の要素数を知る

　メモリ管理

　

・メモリスタック
・動的メモリ確保とメモリリーク

　モジュール設計

　

・モジュール分割
・汎用モジュールとアプリ依存モジュール

　パフォーマンス
　　徹底チューニング

　


・どんな処理に時間がかかるのか
・ファイル入出力の効率化
・アルゴリズムを考える１
・アルゴリズムを考える２

　プリプロセッサの便利機能


・2重インクルード防止

　


トップページへ戻る

アルゴリズムを考える２

　前回は次のようなプログラムを作り、反転コピー処理のチューニングをしてきました。今回は、さらにこのプログラムを高速化していきます。

#include <windows.h>
#include <stdio.h>

int _tmain(int argc, _TCHAR* argv[])
{
    const int       datNum = 32768, iMax = datNum -1;
    short           *srcP = NULL;
    short           *dstP = NULL;
    short           *srcCP = NULL;
    short           *dstCP = NULL;
    int             i, j;
    unsigned int    bt, et;
    int             err = 0;
    
    if (!err) if ((srcP = (short *)malloc(sizeof(short) *datNum)) == NULL) err = 1;
    if (!err) if ((dstP = (short *)malloc(sizeof(short) *datNum)) == NULL) err = 1;
    
    if (!err) for (i = 0; i < datNum; i++) srcP[i] = (short)i;
    // 反転コピー処理 x20000回 (3)
    if (!err)
    {
        bt = GetTickCount();
        for (j = 0; j < 20000; j++)
        {
            srcCP = &srcP[0];
            dstCP = &dstP[iMax];
            for (i = 0; i < datNum; i++)
            {
                *dstCP = *srcCP;
                srcCP++;
                dstCP--;
            }
        }
        et = GetTickCount() -bt;
        printf("(3)%d\n", et);
    }
    
    if (srcP) {free(srcP), srcP = NULL;}
    if (dstP) {free(dstP), dstP = NULL;}
    return 0;
}

　では、メインのループ処理をもう一度見てみましょう。

for (i = 0; i < datNum; i++)
{
    *dstCP = *srcCP;
    srcCP++;
    dstCP--;
}

　srcCP、dstCPは、代入した後にそれぞれアドレスをシフトさせています。ここで、インクリメント、デクリメント演算は、次のように代入処理と一緒に書くことができます。

for (i = 0; i < datNum; i++)
{
    *dstCP-- = *srcCP++;
}

　こうすると、代入した後にインクリメント／デクリメントが実行されます。では、このように変更して実行速度を計測してみます。管理人の環境では、7.531[S]かかりました。明らかに遅くなってしまっています。どうやらこのような書き方をすると効率が悪くなってしまうようです。

　書き方を変えただけで、演算量は変わっていないはずなので、あまり期待はできませんでしたが、やはり効果がないことがわかりました。では、もうこれ以上は速くならないのでしょうか。もう一度アルゴリズムをよく考えてみます。

for (j = 0; j < 20000; j++)
{
    srcCP = &srcP[0];
    dstCP = &dstP[iMax];
    for (i = 0; i < datNum; i++)
    {
        *dstCP = *srcCP;
        srcCP++;
        dstCP--;
    }
}

　ここで、ループカウンタのiに注目してみます。これは１ループごとに一回インクリメントされ、datNumと比較されます。ループ回数は全体で32,768x20,000=655,360,000回です。つまり、このループカウンタだけで6億5千万回のインクリメントと比較処理をしていることになります。これはかなりの負荷となります。なんとかこれを減らせないでしょうか。

　よく見ると、srcCPも１ループごとに一回インクリメントしています。ということは、ループカウンタを使わないで、srcCPをカウンタとして兼用することができます。このように考えると、次のように実装することができます。

short    *srcEP = NULL;

...

// 反転コピー処理 x20000回 (4)
if (!err)
{
    bt = GetTickCount();
    for (j = 0; j < 20000; j++)
    {
        srcCP = &srcP[0];
        dstCP = &dstP[iMax];
        
        for (srcEP = srcCP +datNum; srcCP < srcEP; srcCP++)
        {
            *dstCP = *srcCP;
            dstCP--;
        }
    }
    et = GetTickCount() -bt;
    printf("(4)%d\n", et);
}

　では、これで処理時間を計測してみます。管理人の環境では、6.453[S]でした。2万回の加算処理が増えた代わりに、6億5千万回のインクリメント処理を省くことができたので、かなり高速化されました。

　このように、クリティカルな部分の処理が減らせるなら、クリティカルでない部分の処理は多少増えてもかまわないのです。今回の例では、for文の中の各処理の実行回数は、次のようになっています。

for (1回; 2万回; 2万回)
{
    2万回
    for (2万回; 6億5千万回; 6億5千万回)
    {
        6億5千万回
    }
}

　1回しか実行されない部分をチューニングしても、ほとんど効果は無いでしょう。実行回数の多いところを狙ってチューニングしていけば、それだけの効果があることがわかったと思います。

　さて、srcEPは定数なので、毎回計算する必要はありません。これをループの外に出すと、次のようになります。

// 反転コピー処理 x20000回 (5)
if (!err)
{
    bt = GetTickCount();
    srcCP = &srcP[0];
    srcEP = srcCP +datNum;
    
    for (j = 0; j < 20000; j++)
    {
        srcCP = &srcP[0];
        dstCP = &dstP[iMax];
        for (; srcCP < srcEP; srcCP++)
        {
            *dstCP = *srcCP;
            dstCP--;
        }
    }
    et = GetTickCount() -bt;
    printf("(5)%d\n", et);
}

　これで、20000回の加算と代入処理を減らすことができます。これで計測すると、管理人の環境では6.453[S]でした。まったく変わりません。やはり6億5千万回の処理を減らすのに比べたら、20000回の処理を減らしてもほぼ効果はないということでしょう。

　これで、この例題のチューニングは終了します。最初のバージョンで計測した、8.688[S]に比べたら、1.35倍まで高速化されたことになります。実は今回の例題は、マルチメディア処理にそのまま応用できるものです。short型配列の反転コピーというのは、16bit画像の180度回転処理に相当します。