第２章５８キャッシュ、メモ化を使用してのプログラム高速化

#C11仕様 #C言語 #ゲームプログラミング

イチからゲーム作りで覚えるC言語

連載ページ一覧へ

第２章５７キャッシュを利用した図形描画 : PREV

NEXT : 第２章５９ファイルへの書き込み :

概要

複雑で重たい計算を何度も実行して使用するとき、処理を高速化する様々なテクニックがあります。

今回はプログラムの高速化のため、キャッシュ（Caching）やメモ化（Memoization）について確認していきます。

キャッシュ、メモ化

キャッシュやメモ化は高速化のテクニックとしてあちこちで使われています。

どちらも求められるデータを保存しておき、同じデータが求められたときに、すばやく保存されたデータを返すテクニックです。

キャッシュの例として、たとえば、ネットワーク上の大きな画像などをブラウザで難度も閲覧するとき、画像はローカルにダウンロードしておけば、２回目以降ではローカルにダウンロード済みの画像を表示するようにすれば、素早く画像を表示できます。

このようにキャッシュはネットワークのデータや、ファイル内容、データベースの内容をメモリなどの高速にアクセス可能な領域に保存しておき、高速にアクセスできる仕組みです。

マップ自動生成へのキャッシュ利用例えばローグ系やサンドボックス系のゲームで、マップを自動生成する場合、まずはマップ生成プログラムによってマップを生成し、生成されたデータをキャッシュして使いまわすと効率的です。画面に表示するすべてのマップデータをリアルタイムに生成するのは非常に負荷が高いためです。
メモ化は、キャッシュの一種とも言えます。メモ化の特徴として、処理のパラメータと処理の結果をペアでデータに保存し、再度同じパラメータの処理が求められたとき、保存しておいたデータを返します。
パラメータにいろんなパターンがある場合は、そのぶん結果データを保存しておくためのメモリ領域が必要となりますが、そのぶんプログラムの処理を高速化できる可能性があります。

メモ化もキャッシュを使わない例

特にメモ化もキャッシュも使わずに、三角関数を使って適当な計算を大量に行い、 3 回ほど果を確認するプログラムです。

nocache_nomemo.c

#include <stdio.h>
#include <time.h>
#include <math.h>
// なんか重たい計算
double f() {
    double r = 0.0;
    for ( int c = 0; c < 10000 * 10000; c++ ) {
        r += cos( (double)c ) * cos( (double)(c+1) ) + cos( (double)c ) * cos( (double)(c+1) );
    }
    return r;
}

int main() {
    clock_t start, stop;
    start = clock();    // 時間計測開始
    for ( int i = 1; i < 5 ; i++ ) {
        double calc = f();
        printf("%d 回目の計算です。関数 f() の結果は %f です。\n", i, calc);
    }
    stop = clock();     // 時間計測終了
    double timer = (double)(stop - start) / CLOCKS_PER_SEC;
    printf("計算にかかった時間は合計で %6.3f 秒でした。\n", timer);
    return 0;
}

実行結果は下のようになりました。

実行結果

1 回目の計算です。関数 f() の結果は 54030230.18446 です。
2 回目の計算です。関数 f() の結果は 54030230.18446 です。
3 回目の計算です。関数 f() の結果は 54030230.18446 です。
4 回目の計算です。関数 f() の結果は 54030230.18446 です。
計算にかかった時間は合計で 70.692 秒でした。

お、重たいです・・。

関数にキャッシュを使う例

関数 f が重たい演算をしていますが、この関数 f は実行すれば同じ結果が得られます。関数 f の結果はキャッシュとしてメモリ上に保存しておき、2 回目以降に実行された時はキャッシュされたデータを返すようにしてみます。

cache_ex.c

#include <stdio.h>
#include <stdbool.h>
#include <time.h>
#include <math.h>
// なんか重たい計算
double f() {
    static bool isCacheExist = false;
    static double cache; 
    if ( isCacheExist == true ) {
        return cache;
    }

    double r = 0.0;
    for ( int c = 0; c < 10000 * 10000; c++ ) {
        r += cos( (double)c ) * cos( (double)(c+1) ) + cos( (double)c ) * cos( (double)(c+1) );
    }
    isCacheExist = true;
    cache = r;    
    return r;
}

int main() {
    clock_t start, stop;
    start = clock();    // 時間計測開始
    for ( int i = 1; i < 5 ; i++ ) {
        double calc = f();
        printf("%d 回目の計算です。関数 f() の結果は %f です。\n", i, calc);
    }
    stop = clock();     // 時間計測終了
    double timer = (double)(stop - start) / CLOCKS_PER_SEC;
    printf("計算にかかった時間は合計で %6.3f 秒でした。\n", timer);
    return 0;
}

実行結果は下のようになりました。

実行結果

1 回目の計算です。関数 f() の結果は 54030230.18446 です。
2 回目の計算です。関数 f() の結果は 54030230.18446 です。
3 回目の計算です。関数 f() の結果は 54030230.18446 です。
4 回目の計算です。関数 f() の結果は 54030230.18446 です。
計算にかかった時間は合計で 17.557 秒でした。

最初に関数 f を実行したときは、まだキャッシュがないので、通常通り f を実行します。実行した結果はキャッシュとして変数 cache に格納され、次回からは cache に格納された結果が返ります。

メモ化の例

続いて、cos 関数をメモ化した新しい関数 myCos 関数を作成して使うように変更してみます。

基本的な myCos の処理の流れはこちらです。

myCos(A) と呼び出されたら、cos(A) を計算します。
cos(A) の答えが B でしたら、結果[A] = B のような形で配列に記憶しておきます。
次回から myCos(A) が呼び出されたら、配列に記憶した（メモした）答えである結果[A] を返します。

cos 関数で計算した結果は記憶しておく（メモしておく）のがミソです。このように計算した結果を配列に格納しておくような、A → B の対応表はルックアップテーブルと呼ばれます。

memo_ex.c

#include <stdio.h>
#include <time.h>
#include <stdbool.h>
#define _USE_MATH_DEFINES
#include <math.h>
static double COS_MEMO[360];
static bool isCosMemo[360] = { false };
double myCos(double rad) {
    // ラジアンを 0度 ～ 359度 の整数、弧度法に変換
    int degree = (int)round((180.0 * rad) / M_PI) % 360;

    if (degree < 0) degree = 360 + degree;
    // メモ化されているかを確認
    if (isCosMemo[degree] == false) {
        isCosMemo[degree] = true;
        COS_MEMO[degree] = cos((double)degree * M_PI / 180);
    }
    return COS_MEMO[degree];
}

double f() {
    double r = 0.0;
    for (int c = 0; c < 10000 * 10000 ; c++) {
        r += myCos((double)c) * myCos((double)(c + 1)) + myCos((double)c) * myCos((double)(c + 1));
    }
    return r;
}

int main() {
    clock_t start, stop;

    start = clock();    // 時間計測開始
    for (int i = 1; i < 5; i++) {
        double calc = f();
        printf("%d 回目の計算です。関数 f() の結果は %f です。\n", i, calc);
    }
    stop = clock();     // 時間計測終了
    double timer = (double)(stop - start) / CLOCKS_PER_SEC;
    printf("計算にかかった時間は合計で %6.3f 秒でした。\n", timer);

    // myCos と cos の計算結果比較
    for ( double d = -360 ; d < 360; d = d + 33.3 ) {
        double rad =  (d * M_PI) / 180.0;
        printf("myCos( %2.1lf 度) は %1.6lf, cos( %2.0lf 度） は %1.6lf で差は %lf です。\n"
            , d, myCos(rad), d, cos(rad), myCos(rad) - cos(rad) );
    }
}

実行すると下の結果となります。

実行結果

1 回目の計算です。関数 f() の結果は 5402851.802120 です。
2 回目の計算です。関数 f() の結果は 5402851.802120 です。
3 回目の計算です。関数 f() の結果は 5402851.802120 です。
4 回目の計算です。関数 f() の結果は 5402851.802120 です。
計算にかかった時間は合計で 47.512 秒でした。
myCos( -360.0 度) は 1.000000, cos( -360 度） は 1.000000 で差は 0.000000 です。
myCos( -326.7 度) は 0.838671, cos( -327 度） は 0.835807 で差は 0.002863 です。
myCos( -293.4 度) は 0.390731, cos( -293 度） は 0.397148 で差は -0.006417 です。
myCos( -260.1 度) は -0.173648, cos( -260 度） は -0.171929 で差は -0.001719 です。
myCos( -226.8 度) は -0.681998, cos( -227 度） は -0.684547 で差は 0.002549 です。
myCos( -193.5 度) は -0.974370, cos( -193 度） は -0.972370 で差は -0.002000 です。
myCos( -160.2 度) は -0.939693, cos( -160 度） は -0.940881 で差は 0.001188 です。
myCos( -126.9 度) は -0.601815, cos( -127 度） は -0.600420 で差は -0.001395 です。
myCos( -93.6 度) は -0.069756, cos( -94 度） は -0.062791 で差は -0.006966 です。
myCos( -60.3 度) は 0.500000, cos( -60 度） は 0.495459 で差は 0.004541 です。
myCos( -27.0 度) は 0.891007, cos( -27 度） は 0.891007 で差は -0.000000 です。
myCos( 6.3 度) は 0.994522, cos(  6 度） は 0.993961 で差は 0.000561 です。
myCos( 39.6 度) は 0.766044, cos( 40 度） は 0.770513 で差は -0.004469 です。
myCos( 72.9 度) は 0.292372, cos( 73 度） は 0.294040 で差は -0.001669 です。
myCos( 106.2 度) は -0.275637, cos( 106 度） は -0.278991 で差は 0.003354 です。
myCos( 139.5 度) は -0.766044, cos( 140 度） は -0.760406 で差は -0.005638 です。
myCos( 172.8 度) は -0.992546, cos( 173 度） は -0.992115 で差は -0.000431 です。
myCos( 206.1 度) は -0.898794, cos( 206 度） は -0.898028 で差は -0.000766 です。
myCos( 239.4 度) は -0.515038, cos( 239 度） は -0.509041 で差は -0.005997 です。
myCos( 272.7 度) は 0.052336, cos( 273 度） は 0.047106 で差は 0.005230 です。
myCos( 306.0 度) は 0.587785, cos( 306 度） は 0.587785 で差は -0.000000 です。
myCos( 339.3 度) は 0.933580, cos( 339 度） は 0.935444 で差は -0.001864 です。

cos 関数は double 型ですが、全ての引数のパターンをメモ化するのは沢山のメモリ領域が必要になるので、一度今回は int 型に一度四捨五入して変換してから、ルックアップテーブルに代入して記憶しています。

こうすることで、厳密な計算には向きませんが、360パターンの角度に対応した近似値をメモしておいた myCos 関数が作成されました。

ちょっとしたグラフィックの計算などであれば、近似値でも十分問題なく使えたりします。

また、実行時間はなにも工夫していない時の 70.692 秒 → 47.512 秒と縮まっています。

実際に、myCos 関数と cos 関数の差がどれくらいあるのか、参考値として、最後に出力してみています。

myCos 関数は小数点以下を切り捨てているので、小数点以下を指定すると差が出てきていることがわかります。

純粋関数のプリキャッシュ

myCos 関数のように、計算結果があらかじめ分かっており、引数のパターンもそれほど多くないのであれば、全て事前に計算して、結果をテキストファイルなどで読み込んだり、定数から読み込むことで高速化できます。

高速な疑似 cos 関数

cos、sin の結果を事前に 0～359 度ぶん、1度づつ計算して、結果を全てキャッシュする関数を定義する例です。

厳密な数学の計算には使用できませんが、ゲームエンジンで大量な三角関数の計算をこなす場合には高速化が望めます。

#include <stdio.h>
#include <time.h>
#include <stdbool.h>
#define _USE_MATH_DEFINES
#include <math.h>

void initCosSinCache() {
    static double FASTCOS[360];
    static double FASTSIN[360];
    for (int i = 0; i < 360; i++) {
        FASTCOS[i] = cos((double)i * M_PI / 180);
        FASTSIN[i] = sin((double)i * M_PI / 180);
    }
}

double fastCos(double rad) {
    int degree = (int)round((180.0 * rad) / M_PI) % 360;
    if (degree < 0) degree = 360 + degree;
    return FASTCOS[degree];
}

double fastSin(double rad) {
    int degree = (int)round((180.0 * rad) / M_PI) % 360;
    if (degree < 0) degree = 360 + degree;
    return FASTSIN[degree];
}


int main() {
    // fastCos、fastSin の初期化
    initCosSinCache();

    // fastCos と cos の計算結果比較
    for (double d = -360; d < 360; d = d + 60 ) {
        double rad = (d * M_PI) / 180.0;
        printf("fastCos( %2.1lf 度) は %1.6lf, cos( %2.0lf 度） は %1.6lf で差は %lf です。\n"
            , d, fastCos(rad), d, cos(rad), fastCos(rad) - cos(rad));
        printf("fastSin( %2.1lf 度) は %1.6lf, sin( %2.0lf 度） は %1.6lf で差は %lf です。\n"
            , d, fastSin(rad), d, sin(rad), fastSin(rad) - sin(rad));
    }
}

実行すると下のような結果になります。

実行結果

fastCos( -360.0 度) は 1.000000, cos( -360 度） は 1.000000 で差は 0.000000 です。
fastSin( -360.0 度) は 0.000000, sin( -360 度） は 0.000000 で差は -0.000000 です。
fastCos( -300.0 度) は 0.500000, cos( -300 度） は 0.500000 で差は 0.000000 です。
fastSin( -300.0 度) は 0.866025, sin( -300 度） は 0.866025 で差は 0.000000 です。
fastCos( -240.0 度) は -0.500000, cos( -240 度） は -0.500000 で差は 0.000000 です。
fastSin( -240.0 度) は 0.866025, sin( -240 度） は 0.866025 で差は 0.000000 です。
fastCos( -180.0 度) は -1.000000, cos( -180 度） は -1.000000 で差は 0.000000 です。
fastSin( -180.0 度) は 0.000000, sin( -180 度） は -0.000000 で差は 0.000000 です。
fastCos( -120.0 度) は -0.500000, cos( -120 度） は -0.500000 で差は -0.000000 です。
fastSin( -120.0 度) は -0.866025, sin( -120 度） は -0.866025 で差は 0.000000 です。
fastCos( -60.0 度) は 0.500000, cos( -60 度） は 0.500000 で差は 0.000000 です。
fastSin( -60.0 度) は -0.866025, sin( -60 度） は -0.866025 で差は 0.000000 です。
fastCos( 0.0 度) は 1.000000, cos(  0 度） は 1.000000 で差は 0.000000 です。
fastSin( 0.0 度) は 0.000000, sin(  0 度） は 0.000000 で差は 0.000000 です。
fastCos( 60.0 度) は 0.500000, cos( 60 度） は 0.500000 で差は 0.000000 です。
fastSin( 60.0 度) は 0.866025, sin( 60 度） は 0.866025 で差は 0.000000 です。
fastCos( 120.0 度) は -0.500000, cos( 120 度） は -0.500000 で差は 0.000000 です。
fastSin( 120.0 度) は 0.866025, sin( 120 度） は 0.866025 で差は 0.000000 です。
fastCos( 180.0 度) は -1.000000, cos( 180 度） は -1.000000 で差は 0.000000 です。
fastSin( 180.0 度) は 0.000000, sin( 180 度） は 0.000000 で差は 0.000000 です。
fastCos( 240.0 度) は -0.500000, cos( 240 度） は -0.500000 で差は 0.000000 です。
fastSin( 240.0 度) は -0.866025, sin( 240 度） は -0.866025 で差は 0.000000 です。
fastCos( 300.0 度) は 0.500000, cos( 300 度） は 0.500000 で差は 0.000000 です。
fastSin( 300.0 度) は -0.866025, sin( 300 度） は -0.866025 で差は 0.000000 です。