constexpr関数を高速化する方法

constexpr関数ではほとんど何でもできてしまうので、可読性を損なうことなく多くの仕事をコンパイル時にこなすことができます。しかし多くのC++コンパイラでは、インタプリタ上で実行する実装となっており、非常に低速です。constexprで多くのことをやりたい場合、速度がネックになることがあります。

そこで、constexpr関数の(コンパイル時の)実行速度を向上させるテクニックを書いてみます。

constexpr関数の良いところとして、実行時にも同じ関数が使えるという点があげられます。しかし、紹介するテクニックの中には実行時の効率を犠牲にしているものがあるので注意が必要です。

コンパイラは、clang++またはcl.exe(MSVC)を使うものとします。g++はconstexpr関数をメモ化するという性質があるため、竹内関数やフィボナッチ数列を計算するのは速いですが、大規模な計算をするためには膨大なメモリが必要になり、不適です。

変数をなるべく書き換えない

C++14からはconstexpr関数内での変数書き換えが可能になりましたが、変数の書き換えは極力しない方が高速になります。

初期化は統一初期化構文とパック展開を使う

constexpr関数内では未初期化変数は使えないので、必ず初期化する必要があります。そのため、以下のようにfor文を使って値を書き込む場合、「最初の無駄な初期化」「値の書き込み」の二回変数を書き換えていることになります(ついでに、ループ変数を書き換えているのも時間がかかる原因になります)。

constexpr auto f() {
    std::array<std::size_t, 100> arr {};
    for( std::size_t i = 0; i < 100; ++i ) {
        arr[i] = i;
    }
    return arr;
}

こうではなく、index_tupleイディオムとパック展開を用いて、必要な値を初期化時にいきなり書き込むことで高速化することができます。

template<std::size_t... Indeces>
constexpr auto f_impl( std::index_sequence<Indeces...> ) {
    return std::array<std::size_t, 100> arr { Indeces... };
}
constexpr auto f() {
    return f_impl( std::make_index_sequence<100>() );
}

とてもC++11らしいコードになりますが、C++14の新機能を使っても速くならないのでしょうがないです。

このようにした場合、コンパイル時の実行速度は稼げますが、実行時のコードはループアンローリングしたものになるため、プログラムサイズが肥大化します。今回の例はそれほどひどいことにはなりませんが、複雑なコードをアンローリングすることは性能低下につながります。

constexprで行いたい重たい処理のうち、大部分は配列的処理だと思います。関数型言語的に言ってmap関数にあたる処理を行う場合はindex_tupleイディオムとパック展開で一気に処理するのが最も高速です。Indexを扱えるので、ランダムアクセス的な処理も一部可能です。たとえば、並列ソートであるバイトニックソートはこの方法で実装できます。

関数呼び出しを避ける

関数呼び出しには一定のオーバーヘッドがあるため、関数呼び出しを減らすほど高速になります(constexpr関数を使うという点では本末転倒ですが)。可読性を保つこととはトレードオフとなりますが、プログラム高速化の原則「一番実行されるところだけ最適化する」を守ってやればそれほどひどいことにはならないでしょう。

畳み込み式を活用する

map関数の適用のような、完全に並列な処理は先ほど書いたパック展開のテクニックによって高速化が望めますが、「全部足す」のような処理はfor文を使うか、再帰関数呼び出しを行うかのどちらかとなり、いずれも低速です。ここはC++17で導入された畳み込み式を活用する以外ありません。

注意点として、パック展開と同様ループアンローリングをしたことになるので、実行時のコードは肥大化します。

生配列を使う

C++で固定長配列を扱いたいときは、std::array<T, N>を使うのが良いとされ、C言語由来の生配列を使うことは時代遅れとされます。実際、最適化をかければ実行時のパフォーマンスには全く差が出ないのですが、constexpr関数のコンパイル時実行の際には生配列を使った方が高速となります。これは、配列アクセスをする際、std::array<T, N>::operator[](std::size_t)関数(またはat関数)を呼び出していることによるオーバーヘッドが主要因です。一方生配列の場合は単純なポインタ演算により配列アクセスが可能であり、高速になります。

とはいっても配列を関数の返り値として返却することはできないので、返り値の部分にはstd::array<T, N>のような、配列をメンバに持つ構造体を返す必要があります。そこから生配列を取り出すことを一回だけ行えば、それ以降は高速な配列アクセスを利用できるようになります。ただし、std::array<T, N>::data()関数はなぜかconstexpr指定されていないので、自作のArrayクラスなどを利用する必要があります。