C++の関数オブジェクトが関数よりどれだけ速いか

C++では関数オブジェクトのほうが関数より速い。呼び出しの時間に差がある様子。
数回呼ぶだけなら誤差だが呼ぶ回数が増えるとその速度は有利。

ソート

std::sortの比較関数に関数や関数オブジェクトを与える。

関数

bool cmp(int x, int y) {
    return x < y;
}

関数オブジェクト

struct cmp_c {
    bool operator()(int x, int y) {
        return x < y;
    }
} cmp;

ファンクタとかファンクショノイドとか呼ばれる。cmpは上の関数のcmpと同じように呼ぶことができる。

ラムダ式

auto cmp = [](int x, int y) -> bool {
    return x < y;
};

C++11の記法。関数オブジェクトが作られる。
cmpの型はfunction< bool(int,int) >かと思われるがautoで宣言しないと性能が何故か低下する。

計測

int main() {
    int N = 1e7;
    vector<int> v(N);
    for (int i=0; i<N; i++) v[i] = rand();

    clock_t s, t;
    s = clock();
    sort(v.begin(), v.end(), cmp);
    t = clock();
    printf("%f\n", (double)(t-s) / CLOCKS_PER_SEC);
    return 0;
}

int型 1e7個のvectorをソートするだけの時間を測る。

"コールバックなし"はsortのコールバック関数を渡さず昇順ソートした結果。
関数を使った場合だけ遅い。

再帰関数

fibonacci数を二重再帰で定義する。

関数

LL fib(int n) {
    if (n<2) return n;
    return fib(n-1) + fib(n-2);
}

関数オブジェクト

関数オブジェクトの再帰は4通り考えたので全部書く。

関数オブジェクトfib_c()

struct fib_c {
    LL operator()(int n) {
        if (n<2) return n;
        return fib_c()(n-1) + fib_c()(n-2);
    }
} fib;

fib_c()でオブジェクトを作りまくって一見遅そうにも見えるが実際は速い。

関数オブジェクト(*this)

struct fib_c {
    LL operator()(int n) {
        if (n<2) return n;
        return (*this)(n-1) + (*this)(n-2);
    }
} fib;

関数オブジェクトthis->operator()

struct fib_c {
    LL operator()(int n) {
        if (n<2) return n;
        return this->operator()(n-1) + this->operator()(n-2);
    }
} fib;

関数オブジェクトコールバック

struct fib_c {
    LL operator()(fib_c f, int n) {
        if (n<2) return n;
        return f(f, n-1) + f(f, n-2);
    }
} fib;

再帰関数のない言語などで再帰する方法。
ただし呼ぶときにはfib(fib, 45)の様に、第一引数に自身を与える。
おそらくオブジェクトを新しく作っているだけ。

ラムダ式

function<LL(int)> fib = [](int n) -> LL {
    if (n<2) return n;
    return fib(n-1) + fib(n-2);
};

ラムダ式は再帰にする場合autoで宣言できない。
autoで宣言しない場合、ラムダ式は遅い。

その他Yコンビネータ使う方法もあるが面倒。

計測

各実装でfib(45)を計算するのにかかる時間は以下のとおり。

スタックオーバーフロー

ラムダ式の再帰関数は再帰が比較的浅くても手元の環境だとsegmentation faultした。
関数と関数オブジェクトについては関数オブジェクトの方が若干深くまで再帰できたが、そもそも関数がスタックオーバーフローするなら実装が悪い・誤りだと思った方がいい。

考察

実際関数オブジェクトは関数より速い。実装コストも対して変わらないので関数オブジェクトを使うのも良い。関数の呼び出しがボトルネックになる場合はあまり経験ないが、sortのコールバック関数を関数オブジェクトにする程度の実装はしようと思う。
またラムダ式の再帰は致命的に性能が悪いので避けたい所。
再帰関数は関数オブジェクト自身をコールバック関数にするのが最も速いが、あまり綺麗な実装とは言いづらい。再帰の呼び出しが多くなる場合はループかスタックで対処するほうがよっぽど良い。

余談ではあるが、int列を絶対値でソートしたり、複素数列を角度でソートするような、加工した値を規準にソートしたいときは、専用の比較関数を作るよりも、pairのfirstに加工した値・secondに元の値を置いてソートしたほうが大抵速い。同じ値を何度も絶対値取るのは無駄。