boost::lexical_castの涙ぐましい最適化

この記事はBoost Advent Calendar 2011の参加記事です。

本稿では、Boostのコンポーネントの一つ、lexical_castの涙ぐましい最適化について解説します。

lexical_castとは

この辺見てください。

安直な実装

まずは一番簡単な実装から見ていきましょう。

template <typename Target, typename Source>
Target lexical_cast(const Source &arg) {
  std::stringstream ss;
  Target result;
  if (!(ss << arg && ss >> result)) throw boost::bad_lexical_cast();
  return result;
}

この実装には、iostreamの遅さに由来する重大なパフォーマンスの問題があります。幾ら便利でも、「遅い」ことは利用をためらう主要因になりますから、sprintf/sscanfを使える場合はこれを使ってみるようにします。

簡単な最適化

一言でsprintf/sscanfを使うと言っても、文字型の違いを吸収したり、フォーマット文字列を切り替えたりする必要があるので、それなりに面倒です。

template <typename Target, typename Source>
struct lexical_cast_fallback {
  static Target convert(const Source &arg) {
    std::stringstream ss;
    Target result;
    if (!(ss << arg && ss >> result)) throw boost::bad_lexical_cast();
    return result;
  }
};
template <typename Target, typename Source>
struct lexical_cast_sprintf {
  static int snprintf(const char *str, std::size_t n, const Source &x) { return std::snprintf(str, n, fmtstr(boost::identity<Source>()), x); }
  static int snprintf(const wchar_t *str, std::size_t n, const Source &x) { return std::swprintf(str, n, fmtstrw(boost::identity<Source>()), x); }
  static const char *fmtstr(boost::identity<int>) { return "%d"; }
  static const wchar_t *fmtstrw(boost::identity<int>) { return "%d"; }
  static const char *fmtstr(boost::identity<double>) { return L"%f"; }
  static const wchar_t *fmtstrw(boost::identity<double>) { return L"%f"; }
    // 他の型は省略
  static Target convert(const Source &arg) {
    boost::array<typename Target::char_type, 128> buf; // バッファ長は本来は型からメタ関数で求める
    if (snprintf(buf.data(), buf.size(), arg)<=0) throw boost::bad_lexical_cast();
    return Target(buf.data());
  }
};
template <typename Target, typename Source>
struct lexical_cast_sscanf {
  static const char *fmtstr(boost::identity<int>) { return "%d"; }
  static const wchar_t *fmtstrw(boost::identity<double>) { return L"%lf"; }
  static const char *fmtstr(boost::identity<int>) { return "%d"; }
  static const wchar_t *fmtstrw(boost::identity<double>) { return L"%lf"; }
  // ここも他の型は省略
  static int sscanf(const char *s, Target &p) { return std::sscanf(s, fmtstr(boost::identity<Target>()), p); }
  static int sscanf(const wchar_t *s, Target &p) { return std::wsscanf(s, fmtstrw(boost::identity<Target>()), p); }
  static int sscanf(const std::string &s, Target &p) { return std::sscanf(s.c_str(), fmtstr(boost::identity<Target>()), p); }
  static int sscanf(const std::wstring &s, Target &p) { return std::wsscanf(s.c_str(), fmtstrw(boost::identity<Target>()), p); }
  static Target convert(const Source &arg) {
    Target x;
    if (std::sscanf(arg, &x)!=1) throw boost::bad_lexical_cast();
    return x;
  }
};

template <typename T> struct is_string_type { typedef boost::false_type type; };
template <typename charT> struct is_string_type<std::basic_string<charT> > { typedef boost::true_type type; };
template <> struct is_string_type<const char *> { typedef boost::true_type type; };
template <> struct is_string_type<const wchar_t *> { typedef boost::true_type type; };
template <> struct is_string_type<char *> { typedef boost::true_type type; };
template <> struct is_string_type<wchar_t *> { typedef boost::true_type type; };

template <typename Target, typename Source>
Target lexical_cast(const Source &arg) {
  using namespace boost;
  return if_<and_<is_string_type<Target>, is_numeric<Source> >,
    lexical_cast_sprintf<Target, Source>,
    typename if_<and_<is_numeric<Target>, is_string_type<Source> >,
      lexical_cast_sscanf<Target, Source>,
      lexical_cast_fallback<Target, Source>
    >::type
  >::type::convert(arg);
}

大量のヘルパ関数が必要になっているあたりでCライブラリとGenericインタフェースの相性の悪さが分かりますね。

Boostの実装

さて、真面目に最適化するのは少し面倒だというのが分かったところで、Boostの実装を見ていきましょう。まずは外部インタフェースからです(読みやすいようにマクロ展開して整形してあります)。

template <typename Target, typename Source>
inline Target lexical_cast(const Source &arg) {
  typedef typename detail::array_to_pointer_decay<Source>::type src;
  typedef typename ::boost::type_traits::ice_or<
    detail::is_xchar_to_xchar<Target, src>::value,
    detail::is_char_array_to_stdstring<Target, src>::value,
    ::boost::type_traits::ice_and<
      is_same<Target, src>::value,
      detail::is_stdstring<Target>::value
    >::value
  > do_copy_type;
  typedef typename detail::is_arithmetic_and_not_xchars<Target, src> do_copy_with_dynamic_check_type;
  typedef typename ::boost::mpl::if_c<
    do_copy_type::value,
    detail::lexical_cast_copy<src>,
    typename ::boost::mpl::if_c<
      do_copy_with_dynamic_check_type::value,
      detail::lexical_cast_dynamic_num<Target, src>,
      detail::lexical_cast_do_cast<Target, src>
    >::type
  >::type caster_type;
  return caster_type::lexical_cast_impl(arg);
}

さていきなりtypedefの山ですね。SourceとTargetの型によってcaster_typeを切り替え、場合によって最適な変換を呼び出しています。
ここでは、lexical_cast_copy/lexical_cast_dynamic_num/lexical_cast_do_castの三か所に分岐していますので、一つづつ追いかけてみましょう。

lexical_cast_copy::lexical_cast_impl

これは、何もしない場合です。

static inline Source lexical_cast_impl(const Source &arg) {
  return arg;
}

そのまま返しているだけです。変換が必要ないときに呼ばれます。

lexical_cast_dynamic_num::lexical_cast_impl

これは、算術的な変換のみを行い、字句的な変換は行わない場合です。

static inline Target lexical_cast_impl(const Source &arg) {
  typedef typename ::boost::mpl::if_c<
    ::boost::type_traits::ice_and<
      ::boost::type_traits::ice_or<::boost::is_signed<Source>::value, ::boost::is_float<Source>::value>::value,
      ::boost::type_traits::ice_not<is_same<Source, bool>::value>::value,
      ::boost::type_traits::ice_not<is_same<Target, bool>::value>::value,
      ::boost::is_unsigned<Target>::value
    >::value,
    lexical_cast_dynamic_num_ignoring_minus<Target, Source>,
    lexical_cast_dynamic_num_not_ignoring_minus<Target, Source>
  >::type caster_type;
  return caster_type::lexical_cast_impl(arg);
}

符号付きの算術型から符号無しの算術型へ変換するときに範囲チェック時に元の符号を無視する以外はcaster_type::lexical_cast_implの中で単にboost::numeric::converterに投げているだけです。

lexical_cast_do_cast::lexical_cast_impl

これは、字句的に変換を行う場合です。

static inline Target lexical_cast_impl(const Source &arg) {
  typedef typename detail::array_to_pointer_decay<Source>::type src;
  typedef typename detail::widest_char<typename detail::stream_char<Target>::type, typename detail::stream_char<src>::type>::type char_type;
  typedef detail::lcast_src_length<src> lcast_src_length;

  std::size_t const src_len = lcast_src_length::value;
  char_type buf[src_len + 1];
  lcast_src_length::check_coverage();

  typedef typename deduce_char_traits<char_type, Target, Source>::type traits;
  typedef typename remove_pointer<src>::type removed_ptr_t;
  const bool requires_stringbuf =
    !(
      ::boost::type_traits::ice_or<
        is_stdstring<src>::value,
        is_arithmetic<src>::value,
        ::boost::type_traits::ice_and<
          is_pointer<src>::value,
          is_char_or_wchar<removed_ptr_t>::value,
          ::boost::type_traits::ice_eq<sizeof(char_type), sizeof(removed_ptr_t)>::value
        >::value
      >::value
    );
  detail::lexical_stream_limited_src<char_type, traits, requires_stringbuf> interpreter(buf, buf + src_len);

  Target result;
  if (!(interpreter.operator << (arg) && interpreter.operator >> (result))) {
    throw_exception(bad_lexical_cast(typeid(Source), typeid(Target)));
  }
  return result;
}

一番重要な変換ルーチンの入口です。実際の変換処理は、lexical_stream_limited_srcのメンバ関数から呼び出されています。
lexical_castは変換元がstd::basic_stringであるか、算術型であるか、変換先と同じ文字幅のゼロ終端文字列である場合は、バッファを別に確保することはせずに、srcまたはdstの領域を直接読み書きして変換を行います。
lexical_stream_limited_srcでバッファが必要な場合と不要な場合の変換処理のインタフェースを共通化しています。

lexical_stream_limited_src::operator <<
bool operator<<(char ch) {
  return shl_char(ch);
}
bool operator<<(unsigned char ch) {
  return ((*this) << static_cast<char>(ch));
}

operator << 自体はこのような単なる転送関数です(他の型も同様です)。転送された先を見ていきましょう。

まずは文字型です。

bool shl_char(CharT ch) {
  Traits::assign(*start, ch);
  finish = start + 1;
  return true;
}

template <class T>
bool shl_char(T ch) {
  typedef ::boost::static_assert_test < sizeof(::boost::STATIC_ASSERTION_FAILURE < ((( sizeof(T) <= sizeof(CharT))) == 0 ? false : true) > ) > boost_static_assert_typedef_1146;
  std::locale loc;
  wchar_t w = std::use_facet< std::ctype<wchar_t> >(loc).widen(ch);
  Traits::assign(*start, w);
  finish = start + 1;
  return true;
}

入出力の文字型が同じ場合は、単にバッファにコピーします(start/finishは内部バッファの先頭・終端です)。違う型の場合は、facetを使ってコード変換を行っています(ここでwchar_tを決め打ちしているけれど、バグなのでは???)。

一方、文字列の場合はこうなります。

bool shl_char_array(CharT const *str) {
  start = const_cast<CharT *>(str);
  finish = start + Traits::length(str);
  return true;
}
template <class T>
bool shl_char_array(T const *str) {
  typedef ::boost::static_assert_test < sizeof(::boost::STATIC_ASSERTION_FAILURE < ((( sizeof(T) <= sizeof(CharT))) == 0 ? false : true) > ) > boost_static_assert_typedef_1172;
  return shl_input_streamable(str);
}

template <typename InputStreamable>
bool shl_input_streamable(InputStreamable &input) {
  std::basic_ostream<CharT> stream(&stringbuffer);
  bool const result = !(stream << input).fail();
  start = stringbuffer.pbase();
  finish = stringbuffer.pptr();
  return result && (start != finish);
}

入出力の文字型が同じ場合は入力を直接参照するようにします。入出力で文字型が違う場合は、一度内部のstringbufにコピーしてから参照します。

整数型の場合は次のようになります。

template <class T>
inline bool shl_signed(T n) {
  start = lcast_put_unsigned<Traits>(lcast_to_unsigned(n), finish);
  if (n < 0) {
    --start;
    CharT const minus = lcast_char_constants<CharT>::minus;
    Traits::assign(*start, minus);
  }
  return true;
}

lcast_put_unsignedはitoaの再実装です。ライブラリ関数は呼ばずに全て自前で変換しています。一方、浮動小数点型の場合は

template <class T>
bool shl_double(double val, T *out) {
  using namespace std;
  if (put_inf_nan(start, finish, val)) {
    return true;
  }
  finish = start + sprintf(out, "%.*lg", static_cast<int>(boost::detail::lcast_get_precision<double >()), val );
  return finish > start;
}

となっていて、普通にCライブラリのsprintfを呼び出しています(最大バッファ長は型から静的に計算しているのでオーバーフローの危険はありません)。

出力方向も、基本的に入力と同じです。入出力で文字型が同じ文字・文字列の場合は直接コピー、違う文字型の場合はfacet/streamを介してコピー、整数型の場合は自前で変換、浮動小数点型の場合はsscanfを使って変換しています。


複雑になってしまったので、ちょっと表にしてみましょう。次のTarget/Sourceの組み合わせがサポートされています。

Target\Source Char WChar Char[] WChar[] String WString Integral Float
Char copy n/a stream n/a copy n/a internal sprintf
WChar facet copy stream stream n/a copy internal sprintf
String copy n/a copy n/a copy n/a internal sprintf
WString facet n/a stream copy n/a copy internal sprintf
Integral internal internal internal internal internal internal numeric numeric
Float sscanf sscanf sscanf sscanf sscanf sscanf numeric numeric

※表の見方

    • Char: char, signed char, unsigned char
    • WChar: wchar_t, char16_t, char32_t
    • Char[]: (const) char *
    • WChar[]: (const) wchar_t *, (const) char16_t *, (const) char32_t *
    • String: std::string
    • WString: std::wstring
    • Integral: bool, (unsigned) short, (unsigned) int, (unsigned) long, (unsigned) long long
    • Float: float, double, long double
    • copy: ノーチェックで元の値を返すだけ
    • facet: デフォルトロケールでのnarrow/wide変換
    • sprintf: std::s(w)printfを使った変換
    • sscanf: std::s(w)scanfを使った変換
    • internal: 自前実装のitoa/atoiモドキによる変換
    • stream: streambufを介しての変換
    • numeric: オーバーフロー・桁落ちチェック付きのboost::numeric_cast
    • n/a: 変換不可(boost::localeを使いましょう)

このような複雑なディスパッチの末に、可能な限りiostreamには頼らずに変換を行って高速化を図っていることが分かります。

まとめ

lexical_castが変換方法を選択する流れを軽く追いかけてみましたが、実際のコードを読んでみると古いコンパイラのworkaroundも混じってくるのでかなりカオスになっています。
しかし、コードは複雑でも実行パス自体は大変シンプルで、一番ポピュラーと思われる算術型とstd::stringの相互変換は変換部そのもの(sprintf/sscanf相当部分)以外は完全にインライン化されてしまうので、特に整数型の場合は自前でsprintf/sscanfを呼び出すより高速であることが多いです。
速度が気になって今まで利用を躊躇っていた人も、この機会に試してみてはいかがでしょうか。


明日の担当は、札幌の魔法少女ほっとちゃん(id:heisseswasser)です。