constexpr と LUT

## ことの発端

LUT（Look Up Table）って結構使うんですが、こいつを constexpr （コンパイル時定数）にできないものかと調べていた時期があって、結果的に「何だか難しそうだし」という理由で放置していた。
まぁ、最近はゲームみたいな速度を要求するコードを書いている訳じゃないんで（たまにあるけど）、 std::unordered_map のお世話になっていたりする。
で、Qiitaさんで記事を書いていて、久々に template やら constexpr に真摯に向き合う機会があったので、ちょっと試してみようと思った。

## 書いてみた

```cpp
#include <iostream>
#include <chrono>
#include <unordered_map>
#include <map>

template <typename KEY, typename VALUE> class LUT {
public:
  struct KeyValue {
    KEY     key;
    VALUE   value;
  };

  using Comparator = bool(*)(KEY, KEY);

private:
  const KeyValue*     m_keyValues;
  const std::size_t   m_length;
  Comparator          m_comparator;

public:
  constexpr LUT(const KeyValue* keyValues, std::size_t length, Comparator comparator) :
    m_keyValues(keyValues),
    m_length(length),
    m_comparator(comparator)
    {}

  constexpr VALUE operator [] (KEY key) const {
    for(std::size_t i = 0; i < m_length; i++){
      if(m_comparator(m_keyValues[i].key, key)){
        return m_keyValues[i].value;
      }
    }
    return VALUE{};
  }
};

int main(void){
  const auto TEST_COUNT = 100000;

  std::cout << "std::map -> ";
  {
    static std::map<int, const char*> lut = {
      { 1, "白い犬" },
      { 2, "黒い犬" },
      { 3, "茶色い犬" },
      { 101, "白い猫" },
      { 102, "黒い猫" },
      { 103, "茶色い猫" }
    };
    auto t1 = std::chrono::system_clock::now();
    for(auto i = 0; i < TEST_COUNT; i++){
      (lut[1], lut[2], lut[3], lut[101], lut[102], lut[103]);
      auto x = 1; (lut[x], lut[x + 100]);
           x = 2; (lut[x], lut[x + 100]);
           x = 3; (lut[x], lut[x + 100]);
    }
    auto t2 = std::chrono::system_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count() << std::endl;
  }

  std::cout << "const std::map -> ";
  {
    static const std::map<int, const char*> lut = {
      { 1, "白い犬" },
      { 2, "黒い犬" },
      { 3, "茶色い犬" },
      { 101, "白い猫" },
      { 102, "黒い猫" },
      { 103, "茶色い猫" }
    };
    auto t1 = std::chrono::system_clock::now();
    for(auto i = 0; i < TEST_COUNT; i++){
      (lut.find(1), lut.find(2), lut.find(3), lut.find(101), lut.find(102), lut.find(103)); 
      auto x = 1; (lut.find(x), lut.find(x + 100));
           x = 2; (lut.find(x), lut.find(x + 100));
           x = 3; (lut.find(x), lut.find(x + 100));
    }
    auto t2 = std::chrono::system_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count() << std::endl;
  }

  std::cout << "std::unordered_map -> ";
  {
    static std::unordered_map<int, const char*> lut = {
      { 1, "白い犬" },
      { 2, "黒い犬" },
      { 3, "茶色い犬" },
      { 101, "白い猫" },
      { 102, "黒い猫" },
      { 103, "茶色い猫" }
    };
    auto t1 = std::chrono::system_clock::now();
    for(auto i = 0; i < TEST_COUNT; i++){
      (lut[1], lut[2], lut[3], lut[101], lut[102], lut[103]);
      auto x = 1; (lut[x], lut[x + 100]);
           x = 2; (lut[x], lut[x + 100]);
           x = 3; (lut[x], lut[x + 100]);
    }
    auto t2 = std::chrono::system_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count() << std::endl;
  }

  std::cout << "const std::unordered_map -> ";
  {
    static const std::unordered_map<int, const char*> lut = {
      { 1, "白い犬" },
      { 2, "黒い犬" },
      { 3, "茶色い犬" },
      { 101, "白い猫" },
      { 102, "黒い猫" },
      { 103, "茶色い猫" }
    };
    auto t1 = std::chrono::system_clock::now();
    for(auto i = 0; i < TEST_COUNT; i++){
      (lut.find(1), lut.find(2), lut.find(3), lut.find(101), lut.find(102), lut.find(103)); 
      auto x = 1; (lut.find(x), lut.find(x + 100));
           x = 2; (lut.find(x), lut.find(x + 100));
           x = 3; (lut.find(x), lut.find(x + 100));
    }
    auto t2 = std::chrono::system_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count() << std::endl;
  }

  std::cout << "LUT -> ";
  {
    using lut_t = LUT<int, const char*>;
    
    static const lut_t::KeyValue keyValues[] = {
      { 1, "白い犬" },
      { 2, "黒い犬" },
      { 3, "茶色い犬" },
      { 101, "白い猫" },
      { 102, "黒い猫" },
      { 103, "茶色い猫" }
    };
    
    constexpr lut_t  lut(keyValues, sizeof(keyValues) / sizeof(keyValues[0]), [](auto a, auto b){
      return a == b;
    });
    
    // std::cout << lut[1] << ","
    //           << lut[2] << ","
    //           << lut[3] << ","
    //           << lut[101] << ","
    //           << lut[102] << ","
    //           << lut[103] << std::endl;
    auto t1 = std::chrono::system_clock::now();
    for(auto i = 0; i < TEST_COUNT; i++){
      (lut[1], lut[2], lut[3], lut[101], lut[102], lut[103]);
      auto x = 1; (lut[x], lut[x + 100]);
           x = 2; (lut[x], lut[x + 100]);
           x = 3; (lut[x], lut[x + 100]);
    }
    auto t2 = std::chrono::system_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count() << std::endl;
  }

  const char* animals[] = {
      "白い犬", "黒い犬", "茶色い犬", "白い猫", "黒い猫", "茶色い猫"
  };

  std::cout << "const std::map (reverse) -> ";
  {
    static const std::map<const char*, int> lut = {
      { "白い犬", 1 },
      { "黒い犬", 2 },
      { "茶色い犬", 3 },
      { "白い猫", 101 },
      { "黒い猫", 102 },
      { "茶色い猫", 103 }
    };
    auto t1 = std::chrono::system_clock::now();
    for(auto i = 0; i < TEST_COUNT; i++){
      (lut.find("白い犬"), lut.find("黒い犬"), lut.find("茶色い犬"), lut.find("白い猫"), lut.find("黒い猫"), lut.find("茶色い猫"));
      auto x = 0; (lut.find(animals[x]), lut.find(animals[x + 3]));
           x = 1; (lut.find(animals[x]), lut.find(animals[x + 3]));
           x = 2; (lut.find(animals[x]), lut.find(animals[x + 3]));
    }
    auto t2 = std::chrono::system_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count() << std::endl;
  }

  std::cout << "const std::unordered_map (reverse) -> ";
  {
    static const std::unordered_map<const char*, int> lut = {
      { "白い犬", 1 },
      { "黒い犬", 2 },
      { "茶色い犬", 3 },
      { "白い猫", 101 },
      { "黒い猫", 102 },
      { "茶色い猫", 103 }
    };
    auto t1 = std::chrono::system_clock::now();
    for(auto i = 0; i < TEST_COUNT; i++){
      (lut.find("白い犬"), lut.find("黒い犬"), lut.find("茶色い犬"), lut.find("白い猫"), lut.find("黒い猫"), lut.find("茶色い猫"));
      auto x = 0; (lut.find(animals[x]), lut.find(animals[x + 3]));
           x = 1; (lut.find(animals[x]), lut.find(animals[x + 3]));
           x = 2; (lut.find(animals[x]), lut.find(animals[x + 3]));
    }
    auto t2 = std::chrono::system_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count() << std::endl;
  }

  std::cout << "LUT (reverse) -> ";
  {
    using lut_t = LUT<const char*, int>;
    
    static const lut_t::KeyValue keyValues[] = {
      { "白い犬", 1 },
      { "黒い犬", 2 },
      { "茶色い犬", 3 },
      { "白い猫", 101 },
      { "黒い猫", 102 },
      { "茶色い猫", 103 }
    };
    
    constexpr lut_t  lut(keyValues, sizeof(keyValues) / sizeof(keyValues[0]), [](const char* a, const char* b){
      for(; *a == *b; a++, b++){
        if(*a == '\0') return true;
      }
      return false;
    });

    // std::cout << lut["白い犬"] << ","
    //           << lut["黒い犬"] << ","
    //           << lut["茶色い犬"] << ","
    //           << lut["白い猫"] << ","
    //           << lut["黒い猫"] << ","
    //           << lut["茶色い猫"] << std::endl;

    auto t1 = std::chrono::system_clock::now();
    for(auto i = 0; i < TEST_COUNT; i++){
      (lut["白い犬"], lut["黒い犬"], lut["茶色い犬"], lut["白い猫"], lut["黒い猫"], lut["茶色い猫"]);
      auto x = 0; (lut[animals[x]], lut[animals[x + 3]]);
           x = 1; (lut[animals[x]], lut[animals[x + 3]]);
           x = 2; (lut[animals[x]], lut[animals[x + 3]]);
    }
    auto t2 = std::chrono::system_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count() << std::endl;
  }
}
```

## 計測結果

いつもお世話になっている paiza さんで実施した結果は下記のとおり。

| テーブルの種類 | 使用クラス | 時間（nano sec.） |
| :---: | :---: | ---: | 
| 数値 -> 文字列 | std::map | 3,720,004 |
| 数値 -> 文字列 | const std::map | 288 |
| 数値 -> 文字列 | std::unordered_map | 9,863,037 |
| 数値 -> 文字列 | const std::unordered_map | 225 |
| 数値 -> 文字列 | 自作LUT | 37 |
| 文字列 -> 数値 | const std::map | 260 |
| 文字列 -> 数値 | const std::unordered_map | 249 |
| 文字列 -> 数値 | 自作LUT | 265 |


## 考察

```const std::map``` と ```const std::unordered_map``` の差が予想よりも僅差と思ったけど、元々データがソートされた状態で構築されているし、データ数が少ないから検索コストがあんまし変わらないみたい。
ただ、mutable の ```std::map``` と ```std::unordered_map``` はやっぱり凄い差だな。。。
まぁ、 ```std::map``` と ```std::unordered_map``` も ```operator []``` が const じゃないし、何かやってるな。

で、自作LUTは「数値 -> 文字列」には強いが、「文字列 -> 数値」は大差ない。というか、負けてる。
これは lut に渡している comparator がボトルネックになっていることは下記のテストコードで分かる。

```cpp:正しく動かないけどね
    constexpr lut_t  lut(keyValues, sizeof(keyValues) / sizeof(keyValues[0]), [](const char* a, const char* b){
     return true;
//      for(; *a == *b; a++, b++){
//        if(*a == '\0') return true;
//      }
//      return false;
    });
```

これだと 40ns になる。
まぁ、 operator [] に lvalue 渡しているから、検索するコードが動くから、コストが発生するに決まっているよな〜
う〜ん、となると、どこまでがコンパイル時定数なんだ？？　
というか、lvalue 渡したらコンパイル時に評価ができないから、そもそもこれ constexpr として機能していないし、 コンパイルエラーになるんじゃないのか？？

## ここで constexpr を再度確認

こういう時は、ストラウストラップ氏著「プログラミング言語C++」を読んで見る。
すると「§12.1.6 constexpr関数」という章がある。
あれれ？ 関数の constexpr って定数式における constexpr と違うってこと？？

ふむ。。。
この本によると、 「constexpr関数は、引数に定数が渡されたら定数式（constexpr）から呼び出しOKにする（即ち評価する）。」となっていて、テストコードはしれっと実行に関数呼ばれてますね。（爆）

つまり、 lut で引っ張ってきた値を constexpr として取り扱いたいとき、operator [] が評価されて定数となるけど、そうじゃなきゃ普通に、実行時評価になりまっせ。。。と

ちゅうことで、```constexpr auto value = lut[1];``` と書いてみたら。。。

```
error: constexpr variable 'value' must be initialized by a constant expression
    constexpr auto value = lut[1];
                   ^       ~~~~~~
note: read of non-constexpr variable 'keyValues' is not allowed in a constant expression
      if(m_comparator(m_keyValues[i].key, key)){
                      ^
note: in call to '&lut->operator[](1)'
    constexpr auto value = lut[1];
```

。。。ですよね。（苦笑）

脳内では、constexpr 関数って、算出された結果が定数となるかと思ったんだけど,そんな機能じゃない。
定数式で使用できる関数だよというマーキングで、そうじゃなきゃ普通の関数として、実行時評価となる。
で、定数式で使用された場合には、関数内の全ての変数は定数式で構成されていなきゃエラーにするぞと。コンストラクタも関数だから同様ですね。
const 変数や const 関数は普通に使っていて、もはやデフォルトで const を付加する癖があるくらいだが、 constexpr はムズいけど、やってみて少し仲良くなれた気がする。


## 戒め

constexpr で LUT なんて生意気言ってごめんなさい。
青二才は ```const std::map``` を使います。


####　2020/02/23 追記

## 恥ずかしい指摘を受け

もはや、constexpr なんて「何の話ですか？」状態ですが、こんなゴミ記事を読んで指摘をくださる方に、お詫びと感謝を込めて、続けます。
先に投稿したコードから下記の変更を実施してます。

* int -> const char* の連想配列を int -> int に変更（恥ずかしいので理由は聞かないでください）
* volatile でオプティマイザに目をつぶってもらう（念のためvolatile外したらオプティマイザの目に留まったっぽい結果になりました）
* 逆引きはもはや不要なので削除

```cpp
#include <iostream>
#include <chrono>
#include <unordered_map>
#include <map>

template <typename KEY, typename VALUE> class LUT {
public:
  struct KeyValue {
    KEY     key;
    VALUE   value;
  };

  using Comparator = bool(*)(KEY, KEY);

private:
  const KeyValue*     m_keyValues;
  const std::size_t   m_length;
  Comparator          m_comparator;

public:
  constexpr LUT(const KeyValue* keyValues, std::size_t length, Comparator comparator) :
    m_keyValues(keyValues),
    m_length(length),
    m_comparator(comparator)
    {}

  constexpr VALUE operator [] (KEY key) const {
    for(std::size_t i = 0; i < m_length; i++){
      if(m_comparator(m_keyValues[i].key, key)){
        return m_keyValues[i].value;
      }
    }
    return VALUE{};
  }
};

int main(void){
  const auto TEST_COUNT = 100000;

  std::cout << "std::map -> ";
  {
    static std::map<int, int> lut = {
      { 1, 1001 },
      { 2, 1002 },
      { 3, 1003 },
      { 101, 1101 },
      { 102, 1102 },
      { 103, 1103 }
    };
    auto t1 = std::chrono::system_clock::now();
    for(auto i = 0; i < TEST_COUNT; i++){
      volatile int k;
      k = lut[1];   k = lut[2];   k = lut[3];
      k = lut[101]; k = lut[102]; k = lut[103];
      auto x = 1; k = lut[x]; k = lut[x + 100];
           x = 2; k = lut[x]; k = lut[x + 100];
           x = 3; k = lut[x]; k = lut[x + 100];
    }
    auto t2 = std::chrono::system_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count() << std::endl;
  }

  std::cout << "const std::map -> ";
  {
    static std::map<int, int> lut = {
      { 1, 1001 },
      { 2, 1002 },
      { 3, 1003 },
      { 101, 1101 },
      { 102, 1102 },
      { 103, 1103 }
    };
    auto t1 = std::chrono::system_clock::now();
    for(auto i = 0; i < TEST_COUNT; i++){
      volatile int k;
      k = lut.find(1)->second;   k = lut.find(2)->second;   k = lut.find(3)->second;
      k = lut.find(101)->second; k = lut.find(102)->second; k = lut.find(103)->second;
      auto x = 1; k = lut.find(x)->second; k = lut.find(x + 100)->second;
           x = 2; k = lut.find(x)->second; k = lut.find(x + 100)->second;
           x = 3; k = lut.find(x)->second; k = lut.find(x + 100)->second;
    }
    auto t2 = std::chrono::system_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count() << std::endl;
  }

  std::cout << "std::unordered_map -> ";
  {
    static std::unordered_map<int, int> lut = {
      { 1, 1001 },
      { 2, 1002 },
      { 3, 1003 },
      { 101, 1101 },
      { 102, 1102 },
      { 103, 1103 }
    };
    auto t1 = std::chrono::system_clock::now();
    for(auto i = 0; i < TEST_COUNT; i++){
      volatile int k;
      k = lut[1];   k = lut[2];   k = lut[3];
      k = lut[101]; k = lut[102]; k = lut[103];
      auto x = 1; k = lut[x]; k = lut[x + 100];
           x = 2; k = lut[x]; k = lut[x + 100];
           x = 3; k = lut[x]; k = lut[x + 100];
    }
    auto t2 = std::chrono::system_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count() << std::endl;
  }

  std::cout << "const std::unordered_map -> ";
  {
    static const std::unordered_map<int, int> lut = {
      { 1, 1001 },
      { 2, 1002 },
      { 3, 1003 },
      { 101, 1101 },
      { 102, 1102 },
      { 103, 1103 }
    };
    auto t1 = std::chrono::system_clock::now();
    for(auto i = 0; i < TEST_COUNT; i++){
      volatile int k;
      k = lut.find(1)->second;   k = lut.find(2)->second;   k = lut.find(3)->second;
      k = lut.find(101)->second; k = lut.find(102)->second; k = lut.find(103)->second;
      auto x = 1; k = lut.find(x)->second; k = lut.find(x + 100)->second;
           x = 2; k = lut.find(x)->second; k = lut.find(x + 100)->second;
           x = 3; k = lut.find(x)->second; k = lut.find(x + 100)->second;
    }
    auto t2 = std::chrono::system_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count() << std::endl;
  }

  std::cout << "LUT -> ";
  {
    using lut_t = LUT<int, int>;

    static const lut_t::KeyValue keyValues[] = {
      { 1, 1001 },
      { 2, 1002 },
      { 3, 1003 },
      { 101, 1101 },
      { 102, 1102 },
      { 103, 1103 }
    };

    constexpr lut_t  lut(keyValues, sizeof(keyValues) / sizeof(keyValues[0]), [](auto a, auto b){
      return a == b;
    });

    // std::cout << lut[1] << ","
    //           << lut[2] << ","
    //           << lut[3] << ","
    //           << lut[101] << ","
    //           << lut[102] << ","
    //           << lut[103] << std::endl;
    auto t1 = std::chrono::system_clock::now();
    for(auto i = 0; i < TEST_COUNT; i++){
      volatile int k;
      k = lut[1];   k = lut[2];   k = lut[3];
      k = lut[101]; k = lut[102]; k = lut[103];
      auto x = 1; k = lut[x]; k = lut[x + 100];
           x = 2; k = lut[x]; k = lut[x + 100];
           x = 3; k = lut[x]; k = lut[x + 100];
    }
    auto t2 = std::chrono::system_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count() << std::endl;
  }
}
```

## 計測結果

| 使用クラス | 時間（nano sec.） |
| :---: | ---: | 
| std::map | 3,982,120 |
| const std::map | 3,951,096 |
| std::unordered_map | 9,774,373 |
| const std::unordered_map | 555,193 |
| 自作LUT | 396,244 |

余談ですが、volatile 外すと。。。

| 使用クラス | 時間（nano sec.） |
| :---: | ---: | 
| std::map | 3,839,171 |
| const std::map | 292 |
| std::unordered_map | 9,643,271 |
| const std::unordered_map | 185 |
| 自作LUT | 40 |

## 考察というかなんと言うか。。。

コンテナの性能としては、要素の出し入れがなく、要素数も少ないので、正直分かったことは、paizaさんはオプティマイズが有効だったって事だけかも知れない。
全くの余談ですが、コメント頂いた記事読んで、 std::map って、平衡二分探索木使っているって知りました。
てっきり、キーのハッシュをソートしているんだと思いました。
（こんな長く使っているんだからコード読めって話ですよね。。。確かに。。。）
その後、出たのが unorderd_map だったんで、 std::map は stable sort　で std::unordered_map は unstable sort （または、もはやソートしない）なのかと思っていたのですが、とんだ間違いでした。はぁ。。。

## 戒め

知らない事とか思い込みが多すぎる。。。

#### 2021/02/24 追記

## もう一度考える

よくよく考えると速度云々じゃなくて、 変数宣言時に constexpr 使えればゴールということを理解した。
更に、templateみたいな小洒落たものを使う前に、まず動くものを作ってみようと思って書いてみた。

```cpp
#include <iostream>
#include <stdexcept>

class LUT {
public:
  struct KeyValue {
    int               key;
    const char* const value;
  };

private:
  static constexpr KeyValue s_keyValues[] = {
    { 1, "白い犬" },
    { 2, "黒い犬" },
    { 3, "茶色い犬" },
    { 101, "白い猫" },
    { 102, "黒い猫" },
    { 103, "茶い猫" }
  };

public:
  constexpr LUT() {}

  constexpr const char* const operator [] (int key) const {
    const auto len = sizeof(s_keyValues) / sizeof(s_keyValues[0]);
    for(std::size_t i = 0; i < len; i++){
      if(s_keyValues[i].key == key){
        return s_keyValues[i].value;
      }
    }
    throw std::out_of_range("out of range");
    return 0;
  }
};

int main(void){
  constexpr LUT lut;

  constexpr auto x1 = lut[1];
  constexpr auto x2 = lut[2];
  constexpr auto x3 = lut[3];
  constexpr auto x101 = lut[101];
  constexpr auto x102 = lut[102];
  constexpr auto x103 = lut[103];

  std::cout << x1 << ","
            << x2 << ","
            << x3 << ","
            << x101 << ","
            << x102 << ","
            << x103 << std::endl;

  /* コンパイル時にエラー */
  /* error: constexpr variable 'x999' must be initialized by a constant expression */
  // constexpr auto x999 = lut[999]; 

  /* 実行時に out of range エラー */
  // const auto n = 0;
  // const auto x = lut[n];

  /* 実行時に out of range エラー */
  // std::cout << lut[999] << std::endl;
}
```

このクラスを template にできるかどうかはさて置き、挙動を見てみると、constexprの変数宣言時にコンパイル時にエラーが出るのは嬉しいが、実行時処理を考えて検索（operator []）はちゃんと書かなきゃ速度的なパフォーマンスに影響アリですね。
constexpr を使い慣れていると当たり前なんだと思うけど、```std::cout << lut[999] << std::endl;```みたいに、コードの文脈でlutが登場すると見落としそう。この場合、一旦 constexpr 変数に代入してから使用するって感じになるんかな～　まぁ、コンパイラ君の立場で考えたら、こんなんコンパイル時に評価するか知らんって感じでしょうね。
それか、常にコンパイル時定数とするみたいなことできるんかしら？って、利用箇所多いからLUTにするケースが多いんだから、コンパイル時間が物凄いことになりそうだけど。（苦笑）

あ！！！
そう言えば、演算した結果を```const```定義する際に、こんな書き方することがあるのですが

```cpp
const auto setting = [](){
  switch(CONST_GLOBAL_SETTING) {
    case 1: return "foo";
    case 2: return "bar";
  }
  return "n/a";
}();
```

このラムダ式の中が、コンパイル時に確定する要素だったら、```const```を```constexpr```にすることで効率化を図れるかも知れないですね。