constexprよりTMPが有利かもしれない例

## 発端

先日このツイートでBuild Benchの存在を知った

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">C++ ソースコードのビルド時間を比較できる Web サイト「Build Bench」の紹介を追加 | C++ の歩き方<a href="https://t.co/ZNzioBuWwh">https://t.co/ZNzioBuWwh</a> <a href="https://t.co/oK3TMAVPox">pic.twitter.com/oK3TMAVPox</a></p>&mdash; Ryo Suzuki (@Reputeless) <a href="https://twitter.com/Reputeless/status/1277886325039849474?ref_src=twsrc%5Etfw">June 30, 2020</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script> 

他言語に比べてコンパイルが圧倒的に長い[要出展]C++についにビルド時間専門のベンチツールができてしまった

## 試しに使ってみる

試しに`template` `constexpr` `consteval` で同じコード結果になるコードを比較してみた

```c++:template
template <int x>
struct F {
    static constexpr int y = F<x-1>::y + x;
};

template <>
struct F<0> {
    static constexpr int y = 0;
};

constexpr int x = F<500>::y;

int main() {
    return x;
}
```

```c++:constexpr
constexpr int f(int x) {
    if (x == 0) return 0;
    return f(x-1) + x;
}

constexpr int x = f(500);

int main() {
    return x;
}
```

```c++:consteval
consteval int f(int x) {
    if (x == 0) return 0;
    return f(x-1) + x;
}

constexpr int x = f(500);

int main() {
    return x;
}
```

本当はもう少し大きい数値で比較したかったが、`template`と`constexpr`の再帰深度が制限にかかってしまった
どうやらコンパイルオプションが細かく指定できないみたいなので諦めて小さい数字でやってみた(もしかしたら`#pragma`とかで指定できるのかな？)

https://build-bench.com/b/ZjfDg1AkqPiUdPsVDvdw8og2rMo

![ZjfDg1AkqPiUdPsVDvdw8og2rMo.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/68544/0cee04ac-0a1e-ece9-6cfe-eed3a8d287d2.png)

`constexpr`と`consteval`が同じなのはまあ当然として、`template`が他2つより少しコンパイルに時間がかかった

`const...`は値だけ管理すればよいのに対して`template`は型情報をいろいろやりくりする必要がある分だけ時間がかかるのだろう

## もうちょっと使ってみる

constexprとtemplateの再帰深度に制限があるので再帰深度を抑えつつ関数呼び出しの回数が爆増するフィボナッチ数を求めてみた

``` c++:template.cpp
template <int x>
struct Fib {
    static constexpr int y = Fib<x-1>::y + Fib<x-2>::y;
};
template <>
struct Fib<1> {
    static constexpr int y = 1;
};
template <>
struct Fib<2> {
    static constexpr int y = 1;
};

constexpr int x = Fib<33>::y;

int main() {
    return x;
}
```

``` c++:constexpr
constexpr int f(int x) {
    if (x == 1 || x == 2) return 1;
    return f(x-1) + f(x-2);
}

constexpr int x = f(33);

int main() {
    return x;
}
```

``` c++:consteval
consteval int f(int x) {
    if (x == 1 || x == 2) return 1;
    return f(x-1) + f(x-2);
}

constexpr int x = f(33);

int main() {
    return x;
}
```

https://build-bench.com/b/4xhwut5MisH8FjRtpD9vHBrh6VI
![4xhwut5MisH8FjRtpD9vHBrh6VI.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/68544/fdb9a4e4-8e9b-4222-94a3-24048e37ba2f.png)

すごい差がついた templateが他２つを圧倒してる

もしやと思ってwandboxで次を実行してみる

``` c++
#include <iostream>

template <std::int64_t x>
struct Fib {
    static constexpr std::int64_t y = Fib<x-1>::y + Fib<x-2>::y;
};
template <>
struct Fib<1> {
    static constexpr std::int64_t y = 1;
};
template <>
struct Fib<2> {
    static constexpr std::int64_t y = 1;
};

constexpr std::int64_t x = Fib<80>::y;

int main() {
    std::cout << x;
    return 0;
}
```
https://wandbox.org/permlink/zjfeyh5UrYDr5gr0

現実的な時間でコンパイルできた

当たり前といえば当たり前だが、TMPによる計算ではテンプレート引数が同一なら同じ型なので再計算の必要がなくメモ化再帰のようなことが起きていると考えられる

TMPだと遅延評価が可能なのもあるのでそれとあわせてconstexprに対する優位点になる...かも？

constevalも副作用がない（はず）なのでポインタや参照が絡まない限りメモ化できそうなものだが、今の所そういったコンパイルはされないようだ

ただ`std::vector`がconstexprで扱えるようになるので、（プログラマがめちゃくちゃ頑張れば）constexprにメモ化を行えるかもしれない