Code Style No.7

Boost.Variant - recursiveの続きでsmall objectに対応してみた。

実装時の縛りは、

• Boost.Variantのソースコードに直接手を加えない。
• 一応、C++03まで。

というわけで、部分特殊化で忍びこみまくった結果 → http://ideone.com/eJI0q
構文的にはもうすこしいじれると思うので、そのうち修正するかも。
っていうか、残りは基本的にVariadic Templates（かBoost.Preprocessor）でなんとかする話なので、C++0x解禁したらやる気出す。

現在の構文は、

// original
typedef boost::make_recursive_variant_over<
  boost::mpl::list<
    boost::blank,
    std::string,
    std::list<boost::recursive_variant_>,
    boost::array<char, sizeof(std::list<boost::recursive_variant_>)> // hack
  >
>::type old_variant;

// new
typedef morla::variant::make_recursive_variant_over<
  boost::mpl::list<
    boost::blank,
    std::string,
    morla::variant::recursive_wrapper<std::list<boost::recursive_variant_> >::type,
    boost::array<char, sizeof(std::list<boost::recursive_variant_>)> // hack
  >
>::type new_variant;

ちなみに結論は、

• この例題は（有利になるようにしてあるので）malloc/freeの回数が減って速くなる。
  • 例題だと回数が10%くらい減少。
• 現実のケースでは、目立って効率が良くなることはないと思う。
• 小サイズのmallocが遅ければ速くなるかも。

以下、ちょっとした解説。

---

まず、Boost.Variantの再帰時の挙動について簡単に。

• 再帰したらboost::recursive_wrapper<T>に入れられる。
• boost::recursive_wrapper<T>はT*を保持する。
• つまりsizeof(boost::recursive_wrapper<T>) == sizeof(T*)
• new Tする。って、おまえ、boost::anyといっしょじゃん！

次に、Boost.Variantのストレージについて簡単に。

• 保持しうる型のなかで最大のもののサイズのストレージを確保。
• ただし、再帰している場合は、型T自体ではなくboost::recursive_wrapper<T>のサイズ（ポインタのサイズ）になる。

これらのことから、基本コンセプトは、

1. まず、ストレージサイズを計算してみる。
2. 任意の型Tについて、sizeof(T)がストレージサイズ以下であればスタック上で扱う。
3. そうでなければ、ヒープに確保する。

これらを実現するために、

• boost::detail::variant::substitute
• boost::unwrap_recursive
• boost::recursive_wrapper

を部分特殊化した。