[boost] - kikairoyaの日記

移動記録

2/10

住居探しのために前日入り。

607- 都城→鹿児島中央
758- 鹿児島中央→新大阪
1330- 不動産屋で空家探し
1900- 大阪の触手他7名で前夜祭

2/12

徒歩移動のみ。

1100- 本編
1800- 懇親会

2/12

新見市の縄文土器展のついでに鍾乳洞めぐり。

745- 大阪→姫路
909- 姫路→岡山
1005- 岡山→新見
1110- 新見でレンタカー借りる
1150- 井倉洞
1300- 蕎麦屋
1410- 満奇洞
1530- 猪風来美術館
1630- 近くで取れたイノシシを焼いて食べる簡単なおしごと
1830- 撤収
1910- 新見でレンタカー返却
2007- 新見→出雲市

2/13

エクストリーム帰宅

前夜祭

@hotwatermorning先生が前入りして某社を見学するということで到着に合わせて襲撃。そのまま@akineko先生,@decimalbloat先生,@fadis_先生,@aizen76先生、@kyubuns先生と一緒に深夜まで騒いでました。

本編

背景その他

「ネタの指定があれば喋ります」といって参加表明してたら「GCCでなんか」というよくわからない指定をされたので、だいぶ苦し紛れにWindows+GCC(=Mingw)でSEHを使ってみるというネタを絞り出しました。
当初は50分喋らないといけない予定だったのが、どうにもボリューム増えなくて30分に縮めてもらったのが、スケジュールの遅延を相殺して結果的にはまあよかったのかなと。
ただ、絞り出せないとはいっても、一応前日までに一通り資料は完成して一回流して喋ってもいるので、やれるだけのことはちゃんとやってあるつもりです。

Boost.勉強会は割と人数が多くて聴衆のレベルを想定するのが難しいので、技術背景をどこまで説明するかがいつも悩みどころです。
今回はまあx86 アセンブリくらいなら雰囲気で読めるだろうと思っていたら、アセンブリが出てきた瞬間に諦めた人も何人かいたようで、もう少し補足説明するべきだったかなと。
ただ、解らん時は「説明してくれ」ってその場で言ってもらえば最低限の解説はすぐに出来るので、あとでブログで「ついていけなかったです」とか言ってないでちゃんと質問してほしいです。

内容

Operaで大量に開いていたタブはほとんどが今回のネタのリソースです。(覚えてたら)後でまとめてURI出します。

発表資料はこのへん。

終了後、「Cygwinではどうなるの」と質問されましたが、Cygwinも同じやり方で動くはずです。ただし、cygwin1.dllはSEHをトラップしてSIGNALに変換しているので、その辺の挙動はだいぶ怪しくなると思います。

発表中質問のあった_set_se_translatorについては、これは単に常に一番先端の例外ハンドラからebp切り替えてthrowすればいいだけなので非常に簡単です。

ダブルフォルト等の備えに関しては、巻き戻し先探索中はシステムの例外ハンドラが[fs:0]に登録されているのでそっちでトラップされます。巻き戻し中は自分でどうにかしないといけないですが、単にabort()しても全く追跡できないのでどうすべきかはよくわかりません。

実装自体は一応それなりに動くはずですが、コーナーケースをつついたテストは出来ていないのと、DLLを通過させるとどうなるかもテストできていないので、まだネタの域を出ていません。本気で使いたい奇特な人が居たら連絡ください。

C++は黒魔術の無い素敵な言語です。

参考文献

発表時に開いていたページを列挙しただけ。

懇親会

戦果:

めるぽんに少しだけ野菜を食わせた
めるぽんに少しだけ野菜を食わせた
めるぽんに少しだけ野菜を食わせた

新見観光

鍾乳洞(井倉洞、満奇洞)

大都会の大自然やばい
でもなんか寂れてる
探検料高い…

猪風来美術館

満奇洞-方谷駅-美術館の道が狭くて死ぬかと思った(ペーパードライバーです)
！！！芸術だぞ！！！
穴窯が思ったよりずっとでかい
土器であんなに精巧な細工ができるとは思ってなかった
うまい肉いっぱい食わせて頂きました

発表翌日のバタバタの中準備対応していただいた@bolero_MURAKAMI先生、正体不明の集団に快く応対してくださった猪風来先生と奥様、ありがとうございました。

-

C++は黒魔術の無い素敵な言語です。

Permalink | コメント(0) | トラックバック(0) | 22:00

2011-12-26

Lazy Function/Qi Placeholder に頼らない Semantic Action の作り方

C++, 備忘録, boost

解説とか面倒なのでコード片だけ

http://ideone.com/0nuSE

fusion::vector<char, char, ...> が qi::_1, qi:_2, ... に、fusion::at_c<0>(ctx.attributes) が qi::_val に、pass が qi::_pass に対応してます。

結論

Lazy Function使いましょう。

Permalink | コメント(0) | トラックバック(0) | 00:15

2011-12-02

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

C++, ソフトウェア, boost

この記事は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)です。

Permalink | コメント(0) | トラックバック(0) | 00:19