mpl::begin<mpl::vector<...> > performance problem
Hi all, I am having a huge compile performance problem trying to use mpl::begin for an mpl::vector of a large size -- the complexity seems to be far from constant (or even linear) time. The following example demonstrates it (I am using GCC 3.3.3 or 3.4.2) ---------- #define BOOST_TYPEOF_LIMIT_SIZE 200 #include "boost/mpl/vector.hpp" #include "boost/mpl/size_t.hpp" #include "boost/mpl/begin_end.hpp" #include "boost/mpl/aux_/config/ctps.hpp" #include "boost/preprocessor/iterate.hpp" #include "boost/preprocessor/if.hpp" #include "boost/preprocessor/repetition/enum.hpp" #include "boost/config.hpp" #if (BOOST_TYPEOF_LIMIT_SIZE > BOOST_MPL_LIMIT_VECTOR_SIZE) #warning started generating namespace boost { namespace mpl { #define BOOST_PP_ITERATION_PARAMS_1 (3,( \ BOOST_PP_INC(BOOST_MPL_LIMIT_VECTOR_SIZE), \ BOOST_TYPEOF_LIMIT_SIZE, \ "boost/mpl/vector/aux_/numbered.hpp")) #include BOOST_PP_ITERATE() } } #warning done generating #endif//BOOST_TYPEOF_LIMIT_SIZE > BOOST_MPL_LIMIT_VECTOR_SIZE #define MACRO(z, n, _)\ boost::mpl::size_t<n> #warning started getting begin typedef boost::mpl::begin<BOOST_PP_CAT(boost::mpl::vector, BOOST_TYPEOF_LIMIT_SIZE)< BOOST_PP_ENUM(BOOST_TYPEOF_LIMIT_SIZE, MACRO, ~)
::type it; #warning done getting begin
main() {} --------------- Thanks in advance for any help. Regards, Arkadiy
"Arkadiy Vertleyb" <vertleyb@hotmail.com> writes:
Hi all,
I am having a huge compile performance problem trying to use mpl::begin for an mpl::vector of a large size -- the complexity seems to be far from constant (or even linear) time. The following example demonstrates it (I am using GCC 3.3.3 or 3.4.2)
Are you sure you're not seeing preprocessor slowness? -- Dave Abrahams Boost Consulting www.boost-consulting.com
"David Abrahams" <dave@boost-consulting.com> wrote
"Arkadiy Vertleyb" <vertleyb@hotmail.com> writes:
I am having a huge compile performance problem trying to use mpl::begin for an mpl::vector of a large size -- the complexity seems to be far from constant (or even linear) time. The following example demonstrates it (I am using GCC 3.3.3 or 3.4.2)
Are you sure you're not seeing preprocessor slowness?
Almost :-) It takes almost nothing to generate 200 vector definitions. And then it takes about 10 seconds to do the begin (including preprocessor code that again generates 200 repetitions) But I can only verify it with the pre-processed code in a few hours... Regards, Arkadiy
"David Abrahams" <dave@boost-consulting.com> wrote in message
"Arkadiy Vertleyb" <vertleyb@hotmail.com> writes:
Hi all,
I am having a huge compile performance problem trying to use mpl::begin for an mpl::vector of a large size -- the complexity seems to be far from constant (or even linear) time. The following example demonstrates it (I am using GCC 3.3.3 or 3.4.2)
Are you sure you're not seeing preprocessor slowness?
I modified the example to get the PP code out: typedef BOOST_PP_CAT(boost::mpl::vector, BOOST_TYPEOF_LIMIT_SIZE)< BOOST_PP_ENUM(BOOST_TYPEOF_LIMIT_SIZE, MACRO, ~)
v;
#warning started getting begin typedef boost::mpl::begin<v>::type it; #warning done getting begin It takes about 35 seconds between two warnings.... The similar problem seems to exist for at<>. It takes forever to compile at<v, int_<0> > in the same context. Regards, Arkadiy
"Arkadiy Vertleyb" <vertleyb@hotmail.com> writes:
"David Abrahams" <dave@boost-consulting.com> wrote in message
"Arkadiy Vertleyb" <vertleyb@hotmail.com> writes:
Hi all,
I am having a huge compile performance problem trying to use mpl::begin for an mpl::vector of a large size -- the complexity seems to be far from constant (or even linear) time. The following example demonstrates it (I am using GCC 3.3.3 or 3.4.2)
Are you sure you're not seeing preprocessor slowness?
I modified the example to get the PP code out:
typedef BOOST_PP_CAT(boost::mpl::vector, BOOST_TYPEOF_LIMIT_SIZE)< BOOST_PP_ENUM(BOOST_TYPEOF_LIMIT_SIZE, MACRO, ~)
v;
#warning started getting begin typedef boost::mpl::begin<v>::type it; #warning done getting begin
It takes about 35 seconds between two warnings....
The similar problem seems to exist for at<>. It takes forever to compile at<v, int_<0> > in the same context.
Well, we need to hear from Aleksey on this one, I guess. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams writes:
"Arkadiy Vertleyb" <vertleyb@hotmail.com> writes:
"David Abrahams" <dave@boost-consulting.com> wrote in message
"Arkadiy Vertleyb" <vertleyb@hotmail.com> writes:
Hi all,
I am having a huge compile performance problem trying to use mpl::begin for an mpl::vector of a large size -- the complexity seems to be far from constant (or even linear) time. The following example demonstrates it (I am using GCC 3.3.3 or 3.4.2)
Are you sure you're not seeing preprocessor slowness?
I modified the example to get the PP code out:
typedef BOOST_PP_CAT(boost::mpl::vector, BOOST_TYPEOF_LIMIT_SIZE)< BOOST_PP_ENUM(BOOST_TYPEOF_LIMIT_SIZE, MACRO, ~)
v;
#warning started getting begin typedef boost::mpl::begin<v>::type it; #warning done getting begin
It takes about 35 seconds between two warnings....
The similar problem seems to exist for at<>. It takes forever to compile at<v, int_<0> > in the same context.
Well, we need to hear from Aleksey on this one, I guess.
I haven't had a chance to look at it in detail yet, but I'm pretty sure that the penatly comes from simply _instantiating_ the vector type with a huge number of elements. 'begin' just happened to be the first metafunction that causes that in Arkadiy's code. Of course that doesn't mean that it's not an issue, especially since we guarantee that "predefined" content specification has amortized constant time complexity. At the very least, if we find out that there is nothing we can do, the docs would need to be fixed. -- Aleksey Gurtovoy MetaCommunications Engineering
Aleksey Gurtovoy <agurtovoy@meta-comm.com> writes:
I haven't had a chance to look at it in detail yet, but I'm pretty sure that the penatly comes from simply _instantiating_ the vector type with a huge number of elements. 'begin' just happened to be the first metafunction that causes that in Arkadiy's code. Of course that doesn't mean that it's not an issue, especially since we guarantee that "predefined" content specification has amortized constant time complexity. At the very least, if we find out that there is nothing we can do, the docs would need to be fixed.
According to the tests we did for "C++ Template Metaprogramming," there is no cost associated with argument arity except on GCC and Comeau, where the cost rises linearly with N So, on those compilers, expect that first instantiation of a long vector template will be expensive. That said, I see no reason why we need to be causing any instantiation. Everything *could* be done by partial specialization matching, though it might be verbose to account for the numbered and unnumbered forms. -- Dave Abrahams Boost Consulting www.boost-consulting.com
"David Abrahams" <dave@boost-consulting.com> wrote
vector template will be expensive. That said, I see no reason why we need to be causing any instantiation. Everything *could* be done by partial specialization matching, though it might be verbose to account for the numbered and unnumbered forms.
Just speculating: Wouldn't implementing at<> exclusively by partial specialization matching involve defining n * n / 2 specializations? at<v1<>, 0>, at<v2<>, 0>, at<v3<>, 0>, ..., at(Vn<>, 0) at<v2<>, 1>, at<v3<>, 1>, ..., at(Vn<>, 1) at<v3<>, 2>, ..., at(Vn<>, 2) In my case, where n = 255, this would result in ~30,000 specializations of at (or at_impl). Maybe this is where the actual problem is? Regards, Arkadiy
participants (3)
-
Aleksey Gurtovoy -
Arkadiy Vertleyb -
David Abrahams