RE: [boost] Issues in call_traits, arithmetic_traits and MPL

From: Aleksey Gurtovoy (alexy_at_[hidden])
Date: 2001-06-06 06:58:47

Vesa Karvonen wrote:
> > 'boost::mpl' library is indeed immature (and it's not an 
> > official boost library yet), but I wouldn't say that about 
> > the rest.
> 
> Ok. Has it been used outside the test code?

From what I know, yes, a lot. For example, a lot of generic code we write in
my company makes quite intensive use of the library. Also, some other boost
libraries (e.g. compressed_pair, iterator_adaptors) use the type_traits
library too. 

[snip]

> > 2) fact of (not) having a common for all traits implementation's
> > variability point; clearly, in case of 'iterator_traits<>' such point 
> > exists ('T' vs. 'T*' and 'T const*') and this is what makes splitting 
> > them into separate classes unfeasible; I believe that this applies to 
> > 'call_traits<>' as well.
> 
> What do you mean by unfeasible? It is quite feasible to implement the
> services of call_traits<> as separate classes. I will provide a sample
> implementation in the near future. I promise that the compile-time
> overhead of the sample implementation will be significantly smaller
> (an order of magnitude) than the current Boost call_traits.

By "unfeasible" I meant that the alternate implementation (of
'iterator_traits<>') would take more code and lead to a significant template
specializations bloat. However, looking more intently at the current
implementation of 'call_traits<>', I am not so sure that the same statement
applies here. It would be interesting to compare approaches having both
implementations handily :).

[snip]

> > > It is preferable to have simple primitive template
> > > metafunctions, because:
> > >
> > > 1. Such metafunctions can be made to use standard interfaces
> > > rather than
> > > the special case interface of call_traits.
> >
> > I am not sure I understand this one. Could you elaborate, please?
> 
> With a standard interface, I mean that a metafunction that 
> returns a type
> always contains a type of a strandardized name. For example:
> 
>     type_if<c,T,E>   ::type
>     param_type<T>    ::type
>     make_typelist<T> ::type
> 
> The standard interface is the "::type". This kind of standardization
> eliminates the glue that is otherwise necessary to flexibly 
> compose stuff out of metafunctions.
> 
> For example, it is possible to make an extension of type_if<c,T,E> 
> called type_inner_if<c,T,E> that returns type_if<c,T,E>::type::type 
> directly. type_inner_if<> is clearly more robust on current compilers 
> than type_if<>::type::type. type_inner_if<> can also be used to 
> eliminate many typenames.
> 
> The delayed metafunction call is often necessary to avoid 
> instantiation of templates in metacode.

Right, but you can't reduce everything to a 'something<>::type' form, and I
don't think you should. As for avoiding undesirable template instantiations
in metaprogramming constructs like 'mpl::select_type<>' - there are other
ways to do that, see below.

> > > 2. Primitive metafunctions are easier to use, understand and
> > > port (fact of life). For instance, should one little thing fail to 
> > > compile in call traits, you might not be able to port the whole 
> > > thing.
> >
> > Depends on (2) from the above list.
> 
> It is logically, practically and provably easier to port something 
> that is only one quarter of a particular system. It may be a little 
> bit more work to port each of the 4 functions, but the same porting 
> technique usually, but not necessarily always works.
> 
> For example, the param_type<> metafunction is in practice 
> much easier to port than the other call_traits<T> services. The 
> reason for this is that param_type<> never removes any qualifiers 
> from T.

That's an interesting point. I guess my statement that all 'call_traits<>'
members have "a common implementation's variability point" was incorrect.
Need to look more closely at the code :).

> 
> As what comes to useability and understandability, then it should be
> sufficient to point out that they are closely related. It is much easier
> to understand a metafunction such as param_type<> than call_traits<>. 

Agree, in sense that 'param_type' is so fundamental (and, among all other
call_traits, most often used?) generic programming facility (at least with
the language as it is now :), that personally I would prefer to see it as
close to the first left :: as possible :). However, 

boost::call_traits::param_type<T>::type (vs.
boost::call_traits<T>::param_type)

form does not (syntacticaly) make things any better, does it?

> Due to the standard interface, param_type<> can also be combined 
> with other metacode without glue, which clearly makes it arguably 
> easier to use.
> 
> > > 3. Primitive metafunctions scale better in large scale
> > > development (with a BLOB you need to include everything 
> > > whether or not you need it). (In fact, currently I only need 
> > > param_type.)
> >
> > True, but it's not obvious that 'call_traits<>' is an example 
> > of Blob.
> 
> Including <boost/call_traits.hpp> increased my current 
> compiling time by a factor of about 2 (from 1 to 2.8 seconds). 
> However, at this point my code is not complete, so the hit is 
> likely to become less significant (for a single test).

Yes, I wouldn't describe this slowdown using factor notation; when your
compile time come to 10 minutes, including 'call_traits.hpp' header won't
drop it further to 20, just to 21.8 :). 

> 
> For the nearly trivial services of param_type, I find an 
> additional 1.8 seconds of compile time unacceptable. 

I understand your reasoning; however I think that the main source of such
slowdown is not the 'call_traits' library itself, but the type_traits
library headers which as you might notice, almost all (or, in case of MSVC
etc., all) got included into it.

> 1.8 seconds of distributed compile-time fat can easily mean 
> several minutes of additional compile-time for projects that 
> our company currently develops. We've been previously 
> burned by long compile-times (on the order of an hour). It has
> taken considerable engineering effort to systematically reduce 
> compile times. In the light of past experiences, I have absolutely 
> no desire to write library code that has unnecessary 
> dependencies that can easily be eliminated.

That's perfectly understandable, and I do share your point of view, here. If
we can improve things - let's do it, especially if you have a strong
motivation for it :). 

[snip]

> > Of course we do trust each other experience. But examples are 
> > almost never superfluous as they help other people to develop 
> > their own understanding of the issues.
> 
> Like said earlier, the standardized interface eliminates the 
> glue that is otherwise necessary. This is especially handy in 
> conditional metacode, where you want to avoid template 
> instantiation. For example:
> 
>     typedef typename
>       type_inner_if
>       < condition
>       , param_type<T>
>       , some_template_that_should_not_be_instantiated<T>
>       >::type type;
> 
> In this particular case, the following code would be invalid:
> 
>     typedef typename
>       type_if
>       < condition
>       , typename param_type<T>::type
>       , typename 
> some_template_that_should_not_be_instantiated<T>::type
>       >::type type;
> 
> However, I wrote it so that you can see how the type_inner_if<> can be
> used to eliminate a lot of template clutter (typename XXX::type).
> 

Yes, but, as I said above, you can't possibly reduce everything to '::type'
interface; you need a more general technique to handle cases like

typedef typename mpl::select_type< 
      condition<T>::value
    , something<T>::fancy_type
    , T
    >::type type;

where 'something<T>' cannot be instantiated in case if 'condition<T>::value'
is false. My current approach to it, which is also used in 'boost::mpl', is
to write a simple 3-line 'faked_fancy_type' wrapper:

template<typename T> struct faked_fancy_type {
  typedef T fancy_type;
};

and then the troublesome construct can be rewritten as:

typedef typename mpl::select_type< 
      condition
    , something<T>
    , faked_fancy_type<T>
    >::type::fancy_type type;

 
> > > arithmetic_traits
> > > =================
> > >
> > > The boost/arithmetic_traits.hpp can be simplified by a 
> factor of ~4.
> [snip]
> > Yes, comparing the amount of code required to implement the same
> > functionality, something like that is clearly superior to "traditional"
> > approach. But on the other hand, implementing something as simple as
> > 'is_arithmetic' class template using type_lists & co. would impose a
> > _huge_ compilation time penalty on the library users, at least given
> > the current state of compiler technology,
> 
> Actually, I find that in most cases, the limiting factor in compile-time
> is preprocessing-time. It is easy to prove that compile time is at least 
> linearly proportional to the amount of preprocessed source code. 

Yes, but "preprocessing" of the code is still a relatively fast operation,
comparing to the process of templates instantiation, especially
instantiation of deeply recursive templates. On some compilers,
instantiation of one such template can easily take 2 to 5 times longer than
compilation of 1000 lines of "plain" C++ code.

[snip]

> > > MPL
> > > ===
> > >
> > > Technical Issues in Boost MPL:
> > > - The current code is not completely ported to MSVC++, so I
> > > can not use it.
> >
> > It wasn't ported, it was _written_ using MSVC :) (well, actually, using
> > all the following: MSVC6.4, Comeau 4.2.44 and Metrowerks 6.1). 
> > All the tests compile fine on my machine (you need to specify 
> > something like /Zm1000 in MSVC's project settings, though). Could 
> > you give a specific description of the problems you are having?
> 
> The ::template syntax causes a lot of problems.
> 

I am willing to help, but I need a specific example that fails to compile on
your machine. BTW, what exactly version of MSVC do you use?

> > > - The factory template uses O(N*N) tokens, which is not 
> > > optimal. It is possible to do with only O(N) tokens, which can 
> > > significantly reduce compilation times.
> >
> > I am not sure I understand. Could you give an example?
> 
> The code in mpl/list/factory.hpp:
> 
>     #define BOOST_MPL_LIST_FACTORY_SPEC(N)    \
>      [...]                                    \
>       BOOST_MPL_ENUMERATE_PARAMS(typename T)> \
>      [...]                                    \
>     BOOST_MPL_REPEAT_N(N , >::type)           \
>      [...]
> 
>     BOOST_MPL_ENUMERATE_USER_MACROS(BOOST_MPL_, LIST_FACTORY_SPEC)
> 
> Generates O(N*N) tokens. If I understand the purpose of the code
> correctly, it is used for generating lists.

Yep.

> It is possible to support convenient creation of typelists upto size N
> using the optimal O(N) tokens.

Ok, I think now I understand what you are talking about. I remember you've
mentioned this before. Probably I just need to look at your old postings for
the example.

[snip]

> I think that there is very little need for value lists, 
> because you can use a value wrapper type:
> 
>     template<int i>
>     struct value_identity
>     {
>       enum {value = i};
>     };
> 
> with pure typelists (holds only types). I've not had any 
> problems with the approach.

That's basically how 'value_list' is implemented. However, besides that it
has the "right" name, construction of it is also much more simple:

typedef mpl::value_list<1, 5, 9, 7, 0, 5> values;

instead of

typedef mpl::type_list< mpl::int_value<1>, mpl::int_value<5>,
mpl::int_value<9>, mpl::int_value<7>, mpl::int_value<0>, mpl::int_value<5> >
values;

I think this is an important convenience, and I would like to keep it.

> 
> I also think that a simulated iterator approach is more like a hindrance 
> rather than a help. 

Don't agree, but...

> In pure functional programming, such as the C++
> templates enable, the cons-interface:
> 
>     cons::type
>     cons::next
> 
> is extremely robust and flexible. If necessary, both of the ::type and
> ::next can be computed using an arbitrarily complex metacode. You
> might be interested in the following article:
> http://linux.rice.edu/~rahul/hbaker/Iterator.html

...need to read the paper before further discussion.

> > > - list_node<> doesn't check the validity of the template 
> > > arguments. At least NextNode has special requirements. This 
> > > same problem can be seen in many places.
> >
> > Right, for now boost::mpl doesn't perform any concept 
> > checking. It's on my to do list, but not in the top 10 items. If you 
> > think it's more important than that, I would be glad to accept your 
> > help :).
> 
> I'm interested in contributing to metaprogramming facilities of Boost.

Good, let's cooperate then :)

> > > - The endline layout is a bad idea. It makes maintanance more
> > > difficult. I can already pinpoint examples of broken code 
> > > layout in MPL.
> > > See Code Complete, ISBN 1-55615-484-4, for details.
> >
> > I've read the book. I don't think that the 'boost::mpl' code you're
> > referring to does have any of the "endline layout" problems. If it does,
> > I would appreciate being enlightened.
> 
> Here is code snippet taken from MPL:
> 
>     template<typename T, class NextNode>
>     struct make_node
>         {
>         typedef mpl::list_node< T
>                               , NextNode
>                               , list_sequence_tag
>                               , list_traits<Tag>
>                               > type;
>         };
> 
> As you can see, it uses the endline layout.
> 
> One of the problems with endline layout is that it is hard to apply
> consistently. 

Yep, I don't do it consistently, but not because it's hard, just because in
many cases I think it's inappropriate for a particular code fragment.

[snip]

> With endline layout, you'd end up with extremely long lines.

Well, if you don't use it throughly, it's not a problem :).

> Another problem is that endline layout breaks easily when 
> code is modified (e.g. identifiers renamed shorter or longer or 
> while adding typename or template keywords while bug-fixing). 
> Such changes can change the length of the line that controls the 
> indentation of the rest of the lines.

That's true. That's the only problem that is real IMO. Still, I can live
with such little burden in exchange to more pleasant/readable look of the
code.

> > > IMO Boost should have a guideline that says that library 
> > > authors are recommend not to use endline layout, because 
> > > it is not maintainable.
> >
> > May be. Depends on what do you mean by "endline layout".
> 
> Endline layout refers to a layout convention in which 
> indentation is not,
> in principle, invariant in respect to line length.
> 
> For example:
> 
>     if (an < expression) { do_something();
>                            continue_doing_it(); }

[snip]

IMO "endline layout" of control structures is a different (from the above)
story. 

> > > - MPL should be separated into multiple more cohesive libraries.
> >
> > Agree.
> >
> > > For example:
> > >   - type traits (is_same, is_convertible, ...)
> > >     - actually Boost already has this library and I don't see much
> > > value in duplicating the library.
> >
> > There is no duplication. 'boost::mpl' does use type traits 
> > library, and I don't know why you got the impression about 
> > duplicating of the functionality. The library has the 'mpl::same_as' 
> > predicate class (which uses the type traits 'is_same' class template 
> > as well), but that's a different story.
> 
> Yes, I was partially thinking of is_same & same_as. Also the 
> logical.hpp has functionality that is similar to (but not the same as)
ice.hpp.

Yep, they do shortcuting, so one can safely write a compile-time equivalent
to

bool value = ( itor1 != end1 && itor2 != end2 && *itor1 == *itor2 );

as

BOOST_STATIC_CONSTANT(bool, value = 
  mpl::logical_and< mpl::logical_not< boost::is_same<itor1, end1> >
                  , mpl::logical_not< boost::is_same<itor2, end2> >
                  , mpl::type_compare<itor1, itor2>
                  >::value
);

> 
> I can see now that you are using same_as<> as a predicate. Please note
> that it is possible to make metafunction binders using member 
> templates:
> 
>     template<class metafun, class bound>
>     struct bind_1_of_2
>     {
>       template<class unbound>
>       struct code
>       {
>         typedef typename
>           call_2<meta_fun,bound,unbound>::type
>             type;
>       };
>     };

I know :), but thanks for sharing, and another "thanks!" for all the
comments :).

Aleksey