std::threadをMinGWで使えるようにした
libgcc の GThreads wrapper が pthreads 以外の環境では Condition-Variable に対応していないため std::thread が使えなかったが、必要になったので Condition-Variable を Windows (Mingw32, Mingw64 両方) で動くようにした。
GCC's std::thread didn't work on Windows due to unsupported Condition-Variable functions of libgcc's GThread wrapper on non-pthreads environments. So, I did implement these functions. It seems to work fine (on Mingw32/64 environments each).
ただし、recursive_mutex と condition_variable を組み合わせた場合の正しい挙動が理解できなかったので、そこはテストしていません。誰か突っ込みいれてくれる人募集。
However, because it is beyond my comprehension that what is the correct behavior under the combination of recursive_mutex and condition_variable, I haven't tested it yet. If anyone knows about that, I would certainly like them to contact me. (mailto: kikairoya at gmail.com)
ところで、この規模のパッチを取り込んでもらうにはどうするのがいいんですかね。。。いきなりBTSに放り投げてもスルーされるのがオチだと思うのだけれど。 (英訳: @zakkas783先生 thanks a lot!)
Lazy Function/Qi Placeholder に頼らない Semantic Action の作り方
解説とか面倒なのでコード片だけ
fusion::vector
結論
Lazy Function使いましょう。
'11年代のMPL
この記事はC++11 Advent Calendar 2011の参加記事です。
※注: やたらと長いコードが貼ってありますが、実装についての解説は無いので読み飛ばしてください。
Boost.MPL
Boost.MPLはBoostを使っている人なら(魔クロ界の住人を除く)ほぼ全員が間接的にお世話になっているライブラリです。
これはC++03で Variadic Templates をエミュレートするためにいろいろエグいことをやっているのですが、これをそのままC++11で書き直すとどうなるか少しだけ見てみましょう。
シーケンス
まずはMPLシーケンスのmpl::vectorを見てみましょう。C++03では次のようになっています。
// boost/mpl/vector/vector10.hpp # include <boost/mpl/aux_/config/typeof.hpp> # include <boost/mpl/aux_/config/ctps.hpp> # include <boost/preprocessor/iterate.hpp> namespace boost { namespace mpl { # define BOOST_PP_ITERATION_PARAMS_1 \ (3,(0, 10, <boost/mpl/vector/aux_/numbered.hpp>)) # include BOOST_PP_ITERATE() }}
おっと、これは単にPP_ITERATEしているだけですね。実体はこっちです。
// boost/mpl/vector/aux_/numbered.hpp # define AUX778076_VECTOR_TAIL(vector, i_, T) \ BOOST_PP_CAT(vector,i_)< \ BOOST_PP_ENUM_PARAMS(i_, T) \ > \ /**/ #if i_ > 0 template< BOOST_PP_ENUM_PARAMS(i_, typename T) > struct BOOST_PP_CAT(vector,i_) : v_item< BOOST_PP_CAT(T,BOOST_PP_DEC(i_)) , AUX778076_VECTOR_TAIL(vector,BOOST_PP_DEC(i_),T) > { typedef BOOST_PP_CAT(vector,i_) type; };
簡単に見えますか? だとしたらそれは全て魔クロの成果です。ちなみに、この実装はtypeof拡張が使えるときのもの(つまりgcc限定)で、それ以外の場合はこれの10倍の記述が必要です。また、実際にこのPP_ITERATEを毎回行うとそれだけでコンパイル時間がBoostするので、通常使う場合はあらかじめマクロ展開されたヘッダが使われます。ちょっとプリプロセスされたものを見てみましょう。
// boost/mpl/vector/aux_/preprocessed/typeof_based/vector10.hpp namespace boost { namespace mpl { template< typename T0 > struct vector1 : v_item< T0 , vector0< > > { typedef vector1 type; }; template< typename T0, typename T1 > struct vector2 : v_item< T1 , vector1<T0> > { typedef vector2 type; }; template< typename T0, typename T1, typename T2 > struct vector3 : v_item< T2 , vector2< T0,T1 > > { typedef vector3 type; }; template< typename T0, typename T1, typename T2, typename T3 > struct vector4 : v_item< T3 , vector3< T0,T1,T2 > > { typedef vector4 type; }; template< typename T0, typename T1, typename T2, typename T3, typename T4 > struct vector5 : v_item< T4 , vector4< T0,T1,T2,T3 > > { typedef vector5 type; }; template< typename T0, typename T1, typename T2, typename T3, typename T4 , typename T5 > struct vector6 : v_item< T5 , vector5< T0,T1,T2,T3,T4 > > { typedef vector6 type; }; template< typename T0, typename T1, typename T2, typename T3, typename T4 , typename T5, typename T6 > struct vector7 : v_item< T6 , vector6< T0,T1,T2,T3,T4,T5 > > { typedef vector7 type; }; template< typename T0, typename T1, typename T2, typename T3, typename T4 , typename T5, typename T6, typename T7 > struct vector8 : v_item< T7 , vector7< T0,T1,T2,T3,T4,T5,T6 > > { typedef vector8 type; }; template< typename T0, typename T1, typename T2, typename T3, typename T4 , typename T5, typename T6, typename T7, typename T8 > struct vector9 : v_item< T8 , vector8< T0,T1,T2,T3,T4,T5,T6,T7 > > { typedef vector9 type; }; template< typename T0, typename T1, typename T2, typename T3, typename T4 , typename T5, typename T6, typename T7, typename T8, typename T9 > struct vector10 : v_item< T9 , vector9< T0,T1,T2,T3,T4,T5,T6,T7,T8 > > { typedef vector10 type; }; }}
(´・_・`)
※これは0-10要素版で、11-20要素版...41-50要素版に同じだけの記述があります。
さて、これをC++11で書き直してみましょう。
namespace boost { namespace mpl { template <typename ...Types> struct vector; template <> struct vector<> { // from boost/mpl/vector/aux_/vector0.hpp typedef aux::vector_tag tag; typedef vector type; typedef long_<32768> lower_bound_; typedef lower_bound_ upper_bound_; typedef long_<0> size; static aux::type_wrapper<void_> item_(...); }; template <typename T0> struct vector<T0>: v_item<T0, vector<>> { typedef vector type; }; template <typename T0, typename ...Types, typename Tn> struct vector<T0, Types..., Tn>: v_item<Tn, vector<T0, Types...>> { typedef vector type; }; template <typename = na> using vector0 = vector<>; #define DECL_VECTOR_N(n) \ template <BOOST_PP_ENUM_PARAMS(n, typename T)> \ using vector##n = vector<BOOST_PP_ENUM_PARAMS(n, T)> DECL_VECTOR_N(1); DECL_VECTOR_N(2); DECL_VECTOR_N(3); DECL_VECTOR_N(4); DECL_VECTOR_N(5); DECL_VECTOR_N(6); DECL_VECTOR_N(7); DECL_VECTOR_N(8); DECL_VECTOR_N(9); DECL_VECTOR_N(10); #undef DECL_VECTOR_N }}
素晴らしいですね。どうして今までこれが出来なかったんでしょうか。
論理演算
今度はmpl::and_を見てみましょう。
// boost/mpl/and.hpp # define AUX778076_OP_NAME and_ # define AUX778076_OP_VALUE1 false # define AUX778076_OP_VALUE2 true # include <boost/mpl/aux_/logical_op.hpp>
おっと、これも実体は別のヘッダですね。
// boost/mpl/aux_/logical_op.hpp namespace boost { namespace mpl { # define AUX778076_PARAMS(param, sub) \ BOOST_MPL_PP_PARAMS( \ BOOST_MPL_PP_SUB(BOOST_MPL_LIMIT_METAFUNCTION_ARITY, sub) \ , param \ ) \ /**/ # define AUX778076_SHIFTED_PARAMS(param, sub) \ BOOST_MPL_PP_EXT_PARAMS( \ 2, BOOST_MPL_PP_SUB(BOOST_PP_INC(BOOST_MPL_LIMIT_METAFUNCTION_ARITY), sub) \ , param \ ) \ /**/ # define AUX778076_SPEC_PARAMS(param) \ BOOST_MPL_PP_ENUM( \ BOOST_PP_DEC(BOOST_MPL_LIMIT_METAFUNCTION_ARITY) \ , param \ ) \ /**/ namespace aux { template< bool C_, AUX778076_PARAMS(typename T, 1) > struct BOOST_PP_CAT(AUX778076_OP_NAME,impl) : BOOST_PP_CAT(AUX778076_OP_VALUE1,_) { }; template< AUX778076_PARAMS(typename T, 1) > struct BOOST_PP_CAT(AUX778076_OP_NAME,impl)< AUX778076_OP_VALUE2,AUX778076_PARAMS(T, 1) > : BOOST_PP_CAT(AUX778076_OP_NAME,impl)< BOOST_MPL_AUX_NESTED_TYPE_WKND(T1)::value , AUX778076_SHIFTED_PARAMS(T, 1) , BOOST_PP_CAT(AUX778076_OP_VALUE2,_) > { }; template<> struct BOOST_PP_CAT(AUX778076_OP_NAME,impl)< AUX778076_OP_VALUE2 , AUX778076_SPEC_PARAMS(BOOST_PP_CAT(AUX778076_OP_VALUE2,_)) > : BOOST_PP_CAT(AUX778076_OP_VALUE2,_) { }; } // namespace aux template< typename BOOST_MPL_AUX_NA_PARAM(T1) , typename BOOST_MPL_AUX_NA_PARAM(T2) BOOST_MPL_PP_DEF_PARAMS_TAIL(2, typename T, BOOST_PP_CAT(AUX778076_OP_VALUE2,_)) > struct AUX778076_OP_NAME : aux::BOOST_PP_CAT(AUX778076_OP_NAME,impl)< BOOST_MPL_AUX_NESTED_TYPE_WKND(T1)::value , AUX778076_SHIFTED_PARAMS(T,0) > { BOOST_MPL_AUX_LAMBDA_SUPPORT( BOOST_MPL_LIMIT_METAFUNCTION_ARITY , AUX778076_OP_NAME , (AUX778076_PARAMS(T, 0)) ) }; BOOST_MPL_AUX_NA_SPEC2( 2 , BOOST_MPL_LIMIT_METAFUNCTION_ARITY , AUX778076_OP_NAME ) }} #undef AUX778076_SPEC_PARAMS #undef AUX778076_SHIFTED_PARAMS #undef AUX778076_PARAMS #undef AUX778076_OP_NAME #undef AUX778076_OP_VALUE1 #undef AUX778076_OP_VALUE2
こんなん読めるかああああああああ!!! 幸い、これもプリプロセストヘッダがあるので、そっちを見てみましょう。
// boost/mpl/aux_/preprocessed/gcc/and.hpp namespace boost { namespace mpl { namespace aux { template< bool C_, typename T1, typename T2, typename T3, typename T4 > struct and_impl : false_ { }; template< typename T1, typename T2, typename T3, typename T4 > struct and_impl< true,T1,T2,T3,T4 > : and_impl< BOOST_MPL_AUX_NESTED_TYPE_WKND(T1)::value , T2, T3, T4 , true_ > { }; template<> struct and_impl< true , true_, true_, true_, true_ > : true_ { }; } // namespace aux template< typename BOOST_MPL_AUX_NA_PARAM(T1) , typename BOOST_MPL_AUX_NA_PARAM(T2) , typename T3 = true_, typename T4 = true_, typename T5 = true_ > struct and_ : aux::and_impl< BOOST_MPL_AUX_NESTED_TYPE_WKND(T1)::value , T2, T3, T4, T5 > { BOOST_MPL_AUX_LAMBDA_SUPPORT( 5 , and_ , ( T1, T2, T3, T4, T5) ) }; BOOST_MPL_AUX_NA_SPEC2( 2 , 5 , and_ ) }}
(´・_・`)
まあ、さっきよりはマシ、ですね。。。これをC++11で書き直してみましょう。
namespace boost { namespace mpl { namespace detail { template <bool ...C> struct and_impl: false_ { }; template <> struct and_impl<true>: true_ { }; template <bool C0, bool ...C> struct and_impl<true, C0, C...>: and_impl<C0, C...> { }; } template <typename ...T> struct and_: detail::and_impl<T::value...> { }; }}
C++11は素晴らしいですね。何よりも魔クロが消えたのが素晴らしいです。
バインダ
最後にもう一つ、mpl::bindを見てみましょう。これもプリプロセストヘッダがあります。
// boost/mpl/aux_/preprocessed/gcc/bind.hpp namespace boost { namespace mpl { namespace aux { template< typename T, typename U1, typename U2, typename U3, typename U4 , typename U5 > struct resolve_bind_arg { typedef T type; }; template< typename T , typename Arg > struct replace_unnamed_arg { typedef Arg next; typedef T type; }; template< typename Arg > struct replace_unnamed_arg< arg< -1 >, Arg > { typedef typename Arg::next next; typedef Arg type; }; template< int N, typename U1, typename U2, typename U3, typename U4, typename U5 > struct resolve_bind_arg< arg<N>, U1, U2, U3, U4, U5 > { typedef typename apply_wrap5<mpl::arg<N>, U1, U2, U3, U4, U5>::type type; }; template< typename F, typename T1, typename T2, typename T3, typename T4 , typename T5, typename U1, typename U2, typename U3, typename U4 , typename U5 > struct resolve_bind_arg< bind< F,T1,T2,T3,T4,T5 >, U1, U2, U3, U4, U5 > { typedef bind< F,T1,T2,T3,T4,T5 > f_; typedef typename apply_wrap5< f_,U1,U2,U3,U4,U5 >::type type; }; } // namespace aux template< typename F > struct bind0 { template< typename U1 = na, typename U2 = na, typename U3 = na , typename U4 = na, typename U5 = na > struct apply { private: typedef aux::replace_unnamed_arg< F, mpl::arg<1> > r0; typedef typename r0::type a0; typedef typename r0::next n1; typedef typename aux::resolve_bind_arg< a0,U1,U2,U3,U4,U5 >::type f_; /// public: typedef typename apply_wrap0< f_ >::type type; }; }; namespace aux { template< typename F, typename U1, typename U2, typename U3, typename U4 , typename U5 > struct resolve_bind_arg< bind0<F>, U1, U2, U3, U4, U5 > { typedef bind0<F> f_; typedef typename apply_wrap5< f_,U1,U2,U3,U4,U5 >::type type; }; } // namespace aux BOOST_MPL_AUX_ARITY_SPEC(1, bind0) BOOST_MPL_AUX_TEMPLATE_ARITY_SPEC(1, bind0) template< typename F > struct bind< F,na,na,na,na,na > : bind0<F> { }; template< typename F, typename T1 > struct bind1 { template< typename U1 = na, typename U2 = na, typename U3 = na , typename U4 = na, typename U5 = na > struct apply { private: typedef aux::replace_unnamed_arg< F, mpl::arg<1> > r0; typedef typename r0::type a0; typedef typename r0::next n1; typedef typename aux::resolve_bind_arg< a0,U1,U2,U3,U4,U5 >::type f_; /// typedef aux::replace_unnamed_arg< T1,n1 > r1; typedef typename r1::type a1; typedef typename r1::next n2; typedef aux::resolve_bind_arg< a1,U1,U2,U3,U4,U5 > t1; /// public: typedef typename apply_wrap1< f_ , typename t1::type >::type type; }; }; namespace aux { template< typename F, typename T1, typename U1, typename U2, typename U3 , typename U4, typename U5 > struct resolve_bind_arg< bind1< F,T1 >, U1, U2, U3, U4, U5 > { typedef bind1< F,T1 > f_; typedef typename apply_wrap5< f_,U1,U2,U3,U4,U5 >::type type; }; } // namespace aux BOOST_MPL_AUX_ARITY_SPEC(2, bind1) BOOST_MPL_AUX_TEMPLATE_ARITY_SPEC(2, bind1) template< typename F, typename T1 > struct bind< F,T1,na,na,na,na > : bind1< F,T1 > { }; template< typename F, typename T1, typename T2 > struct bind2 { template< typename U1 = na, typename U2 = na, typename U3 = na , typename U4 = na, typename U5 = na > struct apply { private: typedef aux::replace_unnamed_arg< F, mpl::arg<1> > r0; typedef typename r0::type a0; typedef typename r0::next n1; typedef typename aux::resolve_bind_arg< a0,U1,U2,U3,U4,U5 >::type f_; /// typedef aux::replace_unnamed_arg< T1,n1 > r1; typedef typename r1::type a1; typedef typename r1::next n2; typedef aux::resolve_bind_arg< a1,U1,U2,U3,U4,U5 > t1; /// typedef aux::replace_unnamed_arg< T2,n2 > r2; typedef typename r2::type a2; typedef typename r2::next n3; typedef aux::resolve_bind_arg< a2,U1,U2,U3,U4,U5 > t2; /// public: typedef typename apply_wrap2< f_ , typename t1::type, typename t2::type >::type type; }; }; namespace aux { template< typename F, typename T1, typename T2, typename U1, typename U2 , typename U3, typename U4, typename U5 > struct resolve_bind_arg< bind2< F,T1,T2 >, U1, U2, U3, U4, U5 > { typedef bind2< F,T1,T2 > f_; typedef typename apply_wrap5< f_,U1,U2,U3,U4,U5 >::type type; }; } // namespace aux BOOST_MPL_AUX_ARITY_SPEC(3, bind2) BOOST_MPL_AUX_TEMPLATE_ARITY_SPEC(3, bind2) template< typename F, typename T1, typename T2 > struct bind< F,T1,T2,na,na,na > : bind2< F,T1,T2 > { }; template< typename F, typename T1, typename T2, typename T3 > struct bind3 { template< typename U1 = na, typename U2 = na, typename U3 = na , typename U4 = na, typename U5 = na > struct apply { private: typedef aux::replace_unnamed_arg< F, mpl::arg<1> > r0; typedef typename r0::type a0; typedef typename r0::next n1; typedef typename aux::resolve_bind_arg< a0,U1,U2,U3,U4,U5 >::type f_; /// typedef aux::replace_unnamed_arg< T1,n1 > r1; typedef typename r1::type a1; typedef typename r1::next n2; typedef aux::resolve_bind_arg< a1,U1,U2,U3,U4,U5 > t1; /// typedef aux::replace_unnamed_arg< T2,n2 > r2; typedef typename r2::type a2; typedef typename r2::next n3; typedef aux::resolve_bind_arg< a2,U1,U2,U3,U4,U5 > t2; /// typedef aux::replace_unnamed_arg< T3,n3 > r3; typedef typename r3::type a3; typedef typename r3::next n4; typedef aux::resolve_bind_arg< a3,U1,U2,U3,U4,U5 > t3; /// public: typedef typename apply_wrap3< f_ , typename t1::type, typename t2::type, typename t3::type >::type type; }; }; namespace aux { template< typename F, typename T1, typename T2, typename T3, typename U1 , typename U2, typename U3, typename U4, typename U5 > struct resolve_bind_arg< bind3< F,T1,T2,T3 >, U1, U2, U3, U4, U5 > { typedef bind3< F,T1,T2,T3 > f_; typedef typename apply_wrap5< f_,U1,U2,U3,U4,U5 >::type type; }; } // namespace aux BOOST_MPL_AUX_ARITY_SPEC(4, bind3) BOOST_MPL_AUX_TEMPLATE_ARITY_SPEC(4, bind3) template< typename F, typename T1, typename T2, typename T3 > struct bind< F,T1,T2,T3,na,na > : bind3< F,T1,T2,T3 > { }; template< typename F, typename T1, typename T2, typename T3, typename T4 > struct bind4 { template< typename U1 = na, typename U2 = na, typename U3 = na , typename U4 = na, typename U5 = na > struct apply { private: typedef aux::replace_unnamed_arg< F, mpl::arg<1> > r0; typedef typename r0::type a0; typedef typename r0::next n1; typedef typename aux::resolve_bind_arg< a0,U1,U2,U3,U4,U5 >::type f_; /// typedef aux::replace_unnamed_arg< T1,n1 > r1; typedef typename r1::type a1; typedef typename r1::next n2; typedef aux::resolve_bind_arg< a1,U1,U2,U3,U4,U5 > t1; /// typedef aux::replace_unnamed_arg< T2,n2 > r2; typedef typename r2::type a2; typedef typename r2::next n3; typedef aux::resolve_bind_arg< a2,U1,U2,U3,U4,U5 > t2; /// typedef aux::replace_unnamed_arg< T3,n3 > r3; typedef typename r3::type a3; typedef typename r3::next n4; typedef aux::resolve_bind_arg< a3,U1,U2,U3,U4,U5 > t3; /// typedef aux::replace_unnamed_arg< T4,n4 > r4; typedef typename r4::type a4; typedef typename r4::next n5; typedef aux::resolve_bind_arg< a4,U1,U2,U3,U4,U5 > t4; /// public: typedef typename apply_wrap4< f_ , typename t1::type, typename t2::type, typename t3::type , typename t4::type >::type type; }; }; namespace aux { template< typename F, typename T1, typename T2, typename T3, typename T4 , typename U1, typename U2, typename U3, typename U4, typename U5 > struct resolve_bind_arg< bind4< F,T1,T2,T3,T4 >, U1, U2, U3, U4, U5 > { typedef bind4< F,T1,T2,T3,T4 > f_; typedef typename apply_wrap5< f_,U1,U2,U3,U4,U5 >::type type; }; } // namespace aux BOOST_MPL_AUX_ARITY_SPEC(5, bind4) BOOST_MPL_AUX_TEMPLATE_ARITY_SPEC(5, bind4) template< typename F, typename T1, typename T2, typename T3, typename T4 > struct bind< F,T1,T2,T3,T4,na > : bind4< F,T1,T2,T3,T4 > { }; template< typename F, typename T1, typename T2, typename T3, typename T4 , typename T5 > struct bind5 { template< typename U1 = na, typename U2 = na, typename U3 = na , typename U4 = na, typename U5 = na > struct apply { private: typedef aux::replace_unnamed_arg< F, mpl::arg<1> > r0; typedef typename r0::type a0; typedef typename r0::next n1; typedef typename aux::resolve_bind_arg< a0,U1,U2,U3,U4,U5 >::type f_; /// typedef aux::replace_unnamed_arg< T1,n1 > r1; typedef typename r1::type a1; typedef typename r1::next n2; typedef aux::resolve_bind_arg< a1,U1,U2,U3,U4,U5 > t1; /// typedef aux::replace_unnamed_arg< T2,n2 > r2; typedef typename r2::type a2; typedef typename r2::next n3; typedef aux::resolve_bind_arg< a2,U1,U2,U3,U4,U5 > t2; /// typedef aux::replace_unnamed_arg< T3,n3 > r3; typedef typename r3::type a3; typedef typename r3::next n4; typedef aux::resolve_bind_arg< a3,U1,U2,U3,U4,U5 > t3; /// typedef aux::replace_unnamed_arg< T4,n4 > r4; typedef typename r4::type a4; typedef typename r4::next n5; typedef aux::resolve_bind_arg< a4,U1,U2,U3,U4,U5 > t4; /// typedef aux::replace_unnamed_arg< T5,n5 > r5; typedef typename r5::type a5; typedef typename r5::next n6; typedef aux::resolve_bind_arg< a5,U1,U2,U3,U4,U5 > t5; /// public: typedef typename apply_wrap5< f_ , typename t1::type, typename t2::type, typename t3::type , typename t4::type, typename t5::type >::type type; }; }; namespace aux { template< typename F, typename T1, typename T2, typename T3, typename T4 , typename T5, typename U1, typename U2, typename U3, typename U4 , typename U5 > struct resolve_bind_arg< bind5< F,T1,T2,T3,T4,T5 >, U1, U2, U3, U4, U5 > { typedef bind5< F,T1,T2,T3,T4,T5 > f_; typedef typename apply_wrap5< f_,U1,U2,U3,U4,U5 >::type type; }; } // namespace aux BOOST_MPL_AUX_ARITY_SPEC(6, bind5) BOOST_MPL_AUX_TEMPLATE_ARITY_SPEC(6, bind5) /// primary template (not a specialization!) template< typename F, typename T1, typename T2, typename T3, typename T4 , typename T5 > struct bind : bind5< F,T1,T2,T3,T4,T5 > { }; /// if_/eval_if specializations template< template< typename T1, typename T2, typename T3 > class F, typename Tag > struct quote3; template< typename T1, typename T2, typename T3 > struct if_; template< typename Tag, typename T1, typename T2, typename T3 > struct bind3< quote3< if_,Tag > , T1, T2, T3 > { template< typename U1 = na, typename U2 = na, typename U3 = na , typename U4 = na, typename U5 = na > struct apply { private: typedef mpl::arg<1> n1; typedef aux::replace_unnamed_arg< T1,n1 > r1; typedef typename r1::type a1; typedef typename r1::next n2; typedef aux::resolve_bind_arg< a1,U1,U2,U3,U4,U5 > t1; /// typedef aux::replace_unnamed_arg< T2,n2 > r2; typedef typename r2::type a2; typedef typename r2::next n3; typedef aux::resolve_bind_arg< a2,U1,U2,U3,U4,U5 > t2; /// typedef aux::replace_unnamed_arg< T3,n3 > r3; typedef typename r3::type a3; typedef typename r3::next n4; typedef aux::resolve_bind_arg< a3,U1,U2,U3,U4,U5 > t3; /// typedef typename if_< typename t1::type , t2, t3 >::type f_; public: typedef typename f_::type type; }; }; template< template< typename T1, typename T2, typename T3 > class F, typename Tag > struct quote3; template< typename T1, typename T2, typename T3 > struct eval_if; template< typename Tag, typename T1, typename T2, typename T3 > struct bind3< quote3< eval_if,Tag > , T1, T2, T3 > { template< typename U1 = na, typename U2 = na, typename U3 = na , typename U4 = na, typename U5 = na > struct apply { private: typedef mpl::arg<1> n1; typedef aux::replace_unnamed_arg< T1,n1 > r1; typedef typename r1::type a1; typedef typename r1::next n2; typedef aux::resolve_bind_arg< a1,U1,U2,U3,U4,U5 > t1; /// typedef aux::replace_unnamed_arg< T2,n2 > r2; typedef typename r2::type a2; typedef typename r2::next n3; typedef aux::resolve_bind_arg< a2,U1,U2,U3,U4,U5 > t2; /// typedef aux::replace_unnamed_arg< T3,n3 > r3; typedef typename r3::type a3; typedef typename r3::next n4; typedef aux::resolve_bind_arg< a3,U1,U2,U3,U4,U5 > t3; /// typedef typename eval_if< typename t1::type , t2, t3 >::type f_; public: typedef typename f_::type type; }; }; }}
(´・_・`)(´・_・`)(´・_・`)
このファイルのほかに、もう一つ mpl::apply_wrap の実装ファイルにも一部実装があります。このクソ長いコードを、C++11で書くとこうなります。
namespace boost { namespace mpl { namespace aux { template <typename B, typename U, typename R = std::tuple<>> struct replace_bind_args; template <typename T0, typename ...Tn, typename U, typename ...R> struct replace_bind_args< std::tuple<T0, Tn...>, U, std::tuple<R...> >: replace_bind_args< std::tuple<Tn...>, U, std::tuple<R..., T0> > { }; template <int N, typename ...Tn, typename U, typename ...R> struct replace_bind_args< std::tuple<boost::mpl::arg<N>, Tn...>, U, std::tuple<R...> >: replace_bind_args< std::tuple<Tn...>, U, std::tuple<R..., typename std::tuple_element<N-1, U>::type> > { }; template <typename U, typename ...R> struct replace_bind_args<std::tuple<>, U, std::tuple<R...>> { typedef std::tuple<R...> type; }; template <typename T> struct has_apply { template <typename U> static boost::mpl::true_ check(const typename U::apply *); static boost::mpl::false_ check(...); typedef decltype(check((const void *)0)) type; }; template <typename T, bool = has_apply<typename std::tuple_element<0, T>::type>::type::value> struct apply_wrap_tuple; template <typename F, typename ...T, bool B> struct apply_wrap_tuple<std::tuple<F, T...>, B>: F::template apply<T...> { }; template <typename F> struct apply_wrap_tuple<std::tuple<F>, true>: F::apply { }; } template <typename F, typename ...T> struct bind { template <typename ...U> struct apply { typedef typename aux::apply_wrap_tuple< typename aux::replace_bind_args<std::tuple<F, T...>, std::tuple<U...>>::type >::type type; }; }; }}
魔クロフリーの美しい実装ですね。これがC++11の実力です。
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)です。
Boost.勉強会 #6 札幌 で喋ってきました
移動記録
11/4
ほっかいどーでっかいどー
- 木の生え方が違う
- 千歳線速い
- トイレに暖房がある
- でっかいどー大学はリアル観光地(博物館あるし普通に家族連れとか居た)
- 789系撮るの忘れた。。。
- 寒い
- 肉も魚もウマー
本編
id:faith_and_brave先生
まさか時間ぴったりで終わるとは…
id:uskz先生
λカ娘本とか参加したらどうですかね
fadis先生
くらいお先生の狙撃怖い。。。
id:DigitalGhost先生
発表準備は遅延評価しないほうがいいですよ割と本気で。
id:heisseswasser先生
発表準備は(ry
egtra先生
VC++ェ…
id:kikairoya(自分)
前日に動くようになったからと言ってUDLのネタもねじ込んだのは失敗だった
id:redboltz先生
今度はC++ Now!でなんか喋ってほしいですね
id:wraith13先生
皆勤賞お疲れ様です。
GCCのバグを直した
GCCで8bit長・16bit長のビットフィールドが正しく扱われない(STRICT_ALGINMENTな環境でもアライン無視する、volatile付けると領域破壊を起こす)問題を修正した。
BTSには投げたけれど、多分無視されるのでここにパッチを置いておく(gcc-4_6-branch/trunkにて動作確認)。
I fixed the problem around handling bit-field (GCC generates wrong code when using 8bit or 16bit width of bit-field.)
Patch is here (also posted to BTS.)
diff --git a/gcc/expr.c b/gcc/expr.c index a4cfee0..a2823a2 100644 --- a/gcc/expr.c +++ b/gcc/expr.c @@ -4689,7 +4689,7 @@ expand_assignment (tree to, tree from, bool nontemporal) use BLKmode for it instead. */ if (MEM_P (to_rtx)) { - if (volatilep && flag_strict_volatile_bitfields > 0) + if (STRICT_ALIGNMENT || (volatilep && flag_strict_volatile_bitfields > 0)) to_rtx = adjust_address (to_rtx, mode1, 0); else if (GET_MODE (to_rtx) == VOIDmode) to_rtx = adjust_address (to_rtx, BLKmode, 0); @@ -6345,7 +6345,9 @@ store_field (rtx target, HOST_WIDE_INT bitsize, HOST_WIDE_INT bitpos, store it as a bit field. */ || (mode != BLKmode && ((((MEM_ALIGN (target) < GET_MODE_ALIGNMENT (mode)) - || bitpos % GET_MODE_ALIGNMENT (mode)) + || bitpos % GET_MODE_ALIGNMENT (mode) + || (TREE_THIS_VOLATILE (type) + && flag_strict_volatile_bitfields > 0)) && SLOW_UNALIGNED_ACCESS (mode, MEM_ALIGN (target))) || (bitpos % BITS_PER_UNIT != 0))) /* If the RHS and field are a constant size and the size of the @@ -6510,8 +6512,8 @@ get_inner_reference (tree exp, HOST_WIDE_INT *pbitsize, mode = DECL_MODE (field); else if (DECL_MODE (field) == BLKmode) blkmode_bitfield = true; - else if (TREE_THIS_VOLATILE (exp) - && flag_strict_volatile_bitfields > 0) + else if (STRICT_ALIGNMENT || (TREE_THIS_VOLATILE (exp) + && flag_strict_volatile_bitfields > 0)) /* Volatile bitfields should be accessed in the mode of the field's type, not the mode computed based on the bit size. */ @@ -9624,7 +9626,7 @@ expand_expr_real_1 (tree exp, rtx target, enum machine_mode tmode, use BLKmode for it instead. */ if (MEM_P (op0)) { - if (volatilep && flag_strict_volatile_bitfields > 0) + if (STRICT_ALIGNMENT || (volatilep && flag_strict_volatile_bitfields > 0)) op0 = adjust_address (op0, mode1, 0); else if (GET_MODE (op0) == VOIDmode) op0 = adjust_address (op0, BLKmode, 0); diff --git a/gcc/stor-layout.c b/gcc/stor-layout.c index 359541e..7ebba2f 100644 --- a/gcc/stor-layout.c +++ b/gcc/stor-layout.c @@ -626,6 +626,7 @@ layout_decl (tree decl, unsigned int known_align) if (TYPE_SIZE (type) != 0 && TREE_CODE (TYPE_SIZE (type)) == INTEGER_CST && GET_MODE_CLASS (TYPE_MODE (type)) == MODE_INT + && !STRICT_ALIGNMENT && !(TREE_THIS_VOLATILE (decl) && flag_strict_volatile_bitfields > 0)) {