C言語可変長配列の実装による速度の違い #C

この記事はC言語 Advent Calendar 2017の7日目の記事です。

前置き：C言語の悩み

可変長の要素を扱う型が用意されていない

開発をしていると任意のクラスや構造体について可変長の要素を扱いたいときがどうしても出てきます。
リストなどのいわゆるコレクション型が定義されている言語であれば簡単に実装できますが、C言語には用意されていません。そのため可変長の要素を扱う方法を何かしらの形で実装する必要があります。

自由に書けてしまう

実装する必要があると言っても、実装の方法はいくらでもあります。
ただし、実装できればそれで良いというわけでもありません。C言語は書いた通りに動いてしまう言語なので、書き方が悪ければ速度などにも影響します。

情報がありすぎる

C言語は歴史が長い言語です。そのため新しい情報も古い情報も多く存在しています。
その歴史の間で、プログラムの実行環境は大きく変わっています。
例えば10年前に有効だったアルゴリズムを見つけたとして、そのアルゴリズムが現代でも有効だと言えるでしょうか？

前置きが長くなりましたが、可変長配列って結局どう書くのがいいんだというのが前からモヤモヤして気になってましたので、この機会に調べてみようと思いました。

今回調べること

可変長配列のメモリの確保頻度による実行速度への影響を調べます。
メモリの確保頻度が多ければ多いほど遅くなりそうというのは容易に想像できますが、それがどこまでの影響なのかを調べます。

考えたパターン

以下の3パターンを考えました。

A.都度確保パターン

要素数が変化する度に配列の要素数分の合計メモリを確保し直す
確保頻度：高
ソースはこんな感じ

void allocate_by_time(int size){
    int i;
    const int sz = size;
    STTEST *ptstruct;

    for(i = 0; i < sz ;i++){
        if(i == 0) {
            /* 初回のみmalloc */
            ptstruct = (STTEST*)malloc(sizeof(STTEST));
        } else {
            ptstruct = (STTEST*)realloc(ptstruct, sizeof(STTEST)*(i + 1));
        }
        /* 適当な処理 */
        ptstruct[i].str[0] = '/0';
    }
    free(ptstruct);
}

B.一挙確保パターン

最初に十分な要素数分を確保し、以降は確保し直さない
~~思ったんだがこれって可変って言わなくね？~~
確保頻度：低
ソースはこんな感じ

void allocate_bigmemory(int size){
    int i;
    const int sz = size;
    const int BIGSIZE = LIST_SIZE;
    STTEST *ptstruct;

    /* 最大要素数分のメモリを確保 */
    ptstruct = (STTEST*)malloc(sizeof(STTEST) * BIGSIZE);

    for(i = 0; i < sz ;i++){
        /* 適当な処理 */
        ptstruct[i].str[0] = '/0';
    }
    free(ptstruct);
}

C.折衷案パターン

最初にある程度の要素数を確保し、足りなくなったタイミングで大き目の量を追加して確保しなおす
確保頻度：中
ソースはこんな感じ

void allocate_by_span(int size){
    int i;
    const int sz = size;
    STTEST *ptstruct;

    for(i = 0; i < sz ;i++){
        if(i == 0) {
            /* 初回のみmalloc */
            ptstruct = (STTEST*)malloc(sizeof(STTEST)*ALLOC_COUNT);
        } else if (i % ALLOC_COUNT == 0){
            ptstruct = (STTEST*)realloc(ptstruct, sizeof(STTEST)*(i + ALLOC_COUNT));
        }
        /* 適当な処理 */
        ptstruct[i].str[0] = '/0';
    }
    free(ptstruct);
}

実際に書いたソースはこちら。

実験方法

A~Cの3パターンについて、要素数と構造体のサイズを変化させて、それぞれの関数の速度を計測します。
今回は時間の都合上、以下の3つの組合せについて調査しました。

	要素数	構造体のサイズ
組合せ1	100	10000
組合せ2	1000	1000
組合せ3	10000	100

環境

コンパイラ

Microsoft(R) C/C++ Optimizing Compiler Version 19.00.24215.1 for x86

実行環境

OS：Windows 10 64bit
RAM：16GB
CPU： Intel(R) Core(TM) i7-3520 2.90GHz

結果

折れ線グラフで表すと以下のようになります。

組合せ1
組合せ2
組合せ3

考察

ループ回数が多い場合→A.都度確保パターンでは遅くなる

実験結果から明らかなのが、ループ回数が増えると「A.都度確保パターン」の実行速度が長くなります。
ループ回数が大きくなると予めわかっている場合は、メモリの確保回数を少なくする方が良さそうです。

構造体のサイズが小さく、ループ数が多くなければ大差は無い

組合せ3は構造体のサイズが100byteですが、ループ回数3000回までにかかっている時間はどのアルゴリズムでもほぼ変わりませんでした。構造体のサイズが小さく、ループ数も多くない場合であれば、少なくともこの3パターンに関しては大きな差は出ないと考えられます。

結論

通常の場合は「A.都度確保パターン」が良いのかなと思いました。
というのも、「B.一挙確保パターン」や「C.折衷案パターン」を採用するためには要素の最大個数や再確保の基準などのマクロ定義が必要になります。仕様変更などで最大数が変わった時にいちいちメンテナンスしなければならなくなってしまうことを考えると、あまり積極的には使いたくないです。
ループ数が多い場合は「B.一挙確保パターン」or「C.折衷案パターン」を考えても良いかもしれません。

余談

余談ですが、今回書いたソースのrealloc()関数の使い方はあまりいい使い方ではありません。
今回の記事を書く上でreallocについても調べていたのですが、こちらの記事を見かけました。詳しく知らずに使っていたので、今後は気をつけたいと思います。。。

C言語 可変長配列の実装による速度の違い