Ion Gaztañaga wrote:

Tobias Schwinger wrote:

...

However, I've been wondering whether it would be possible to make the "hook interface" easier to use and less demanding in terms of names that are injected into client code. So I started experimenting a bit and the attachment is what I came up with. I believe that scheme might actually work (not sure, though)...

[code]

Very interesting, although I don't fully understand the goal. If the goal is to avoid name injection, I could rework hooks to group all the name definitions in a single internal structure and avoid code bloat.

Maybe because there were two goals: 1. Get rid of the syntactic bloat currently needed to make a class Intrusive-ready. 2. Reduce the probability of name clashes with arbitrary existing client code. Here is a second take of the code hopefully addressing the issues you pointed me to.

What I found interesting is the non-intrusive Intrusive version (nice definition ;-)). Using ADL, there is a way to obtain the hook from the value. However, Intrusive uses a two level architecture, where node algorithms only know about nodes (which in the singly linked list case is just an structure holding a single pointer) and containers know also about values (values hold nodes/hooks as base or members).

Well, it was a "waste product" trying to preserve flexibility, they might as well be replaced with function objects, as you suggested below.

This guarantees that template bloat is minimized, because instantiated algorithms are the same for all values using the same hook. Containers transform nodes to values and the inverse (using static_cast for base hooks or calculating the offset of the hook in the value in member hooks).

Ah, I see! So the "syntactic bloat" sorta just fell into place minimizing the "machine language bloat" some misguided compilers' code generation stages produce (not recognizing the that X<T> and X<U> are equivalent for something like template<class T> class X { T* x; T* y; public: /* ...member functions that work on x and y ... */ }; ). I noticed the two-level architecture, but didn't quite understand what it's for. Now that I know, I see my sample introduced an undesirable type dependency.

Although your example is not directly applicable to current Intrusive code, you suggest a very nice possibility: storing nodes(hooks) independently from values. The programmer could just offer a way to get the node from the value and the inverse when not using any base or member hook.

In the two-level Intrusive architecture your example would need two maps (we could just use boost::bimap) to transform independently stored nodes (slist_node_mgmt_data in your example) to values and the inverse operation.

... or extended the node structure with a back pointer like the attached code. I didn't notice boost::bimap is checked-in already, until now. <snip>

A lot of questions, but I think it's a fresh, great idea. Thanks!

Glad you like it. Regards, Tobias #include <boost/pointee.hpp> #include <boost/noncopyable.hpp> namespace intrusive { // ---- node with policies // management data for one node template< class Policies = void > class slist_node_mgmt_data { template< typename U, class Tr > friend class slist; slist_node_mgmt_data* ptr_next; public: slist_node_mgmt_data() { } }; // ADL extension points to allow Boost.Intrusive to work with custom // members or even non-intrusively (using some external, bidirectional // mapping). // The default implementations assume the hook a base of the value. template< class Policies > slist_node_mgmt_data<Policies>& value_to_hook( slist_node_mgmt_data<Policies>& value) { return value; } // Note: Raw pointers will probably be enough, here... template< typename NodePointer, class Policies > void hook_to_value( NodePointer& result, slist_node_mgmt_data<Policies>& node) { // ... (using Smart Pointer - capable implementation just in case). // If not, Smart Pointers must provide support for boost::pointee // (e.g. an 'element_type' member). result = NodePointer( static_cast< typename boost::pointee<NodePointer>::type* >(& node) ); } // ---- container // traits for customization template< typename T > struct slist_node_traits { typedef T value_type; typedef T* pointer_type; typedef T& reference; // not sure it belongs here, move elsewhere at will typedef void policies; // ... }; // single-linked list (incomplete for illustration) template< typename T, class Traits = slist_node_traits<T> > class slist : boost::noncopyable { typedef Traits traits; public: typedef typename traits::value_type value_type; typedef typename traits::pointer_type pointer_type; typedef typename traits::reference reference; typedef typename traits::policies policies; // ... slist_node_mgmt_data<policies>* ptr_first; public: // Note: Algorithms can work without depending on the value type // (except for casting or mapping for input and output, which will // always be there in some form). void push_front(reference x) { slist_node_mgmt_data<policies>& node = value_to_hook(x); node.ptr_next = this->ptr_first; this->ptr_first = & node; } void pop_front() { this->ptr_first = value_to_hook(* this->ptr_first).ptr_next; } reference front() { pointer_type result; hook_to_value(result, *this->ptr_first); return *result; } // ... }; } #include <boost/detail/lightweight_test.hpp> #include <map> class foo : public intrusive::slist_node_mgmt_data<> // Note: Base class does not insert any names { int val_data; public: foo(int data) : val_data(data) { } int data() const { return this->val_data; } // Note: No "member hook" }; void foo_test() { intrusive::slist<foo> my_list; foo foo1(1); my_list.push_front(foo1); foo foo2(2); my_list.push_front(foo2); BOOST_TEST( my_list.front().data() == 2 ); my_list.pop_front(); BOOST_TEST( my_list.front().data() == 1 ); my_list.pop_front(); } // Ok, let's try non-intrusive Intrusive ;-) class bar // Note: No base class { int val_data; public: bar(int data) : val_data(data) { } int data() const { return this->val_data; } // Note: No "member hook" }; // External management facility struct mgmt_data : intrusive::slist_node_mgmt_data<> // adds a back pointer for bidi mapping { bar* ptr_value; }; std::map<bar*,mgmt_data> bar_mgmt_map; intrusive::slist_node_mgmt_data<>& value_to_hook(bar& that) { mgmt_data& result = bar_mgmt_map[& that]; result.ptr_value = & that; // set back pointer return result; } void hook_to_value(bar*& result, intrusive::slist_node_mgmt_data<>& that) { // downcast to access the back pointer result = static_cast<mgmt_data&>(that).ptr_value; } void bar_test() { intrusive::slist<bar> my_list; bar bar1(1); my_list.push_front(bar1); bar bar2(2); my_list.push_front(bar2); BOOST_TEST( my_list.front().data() == 2 ); my_list.pop_front(); BOOST_TEST( my_list.front().data() == 1 ); my_list.pop_front(); } // Run the tests... int main() { foo_test(); bar_test(); return boost::report_errors(); }

Olaf Krzikalla wrote:

Hi Tobias,

as Ion already wrote the idea is interesting. However I have some remarks:

Tobias Schwinger wrote:

...

#include <boost/detail/lightweight_test.hpp> #include <map>

class foo : public intrusive::slist_node_mgmt_data<foo> // Note: Base class does not insert any names { int val_data; public:

foo(int data) : val_data(data) { }

int data() const { return this->val_data; }

// Note: No "member hook" }; IMHO 'ptr_next' is still injected in the name space of foo, since visiblitiy and accessibility are orthogonal concepts.

Right, it was imprecise. Let's say: "No names of accessible members are injected ..." Technically still sufficient to catch accidental name clashes, have them removed from syntax completion, etc.

...

// Management facility std::map<bar*,intrusive::slist_node_mgmt_data<bar> > bar_management;

intrusive::slist_node_mgmt_data<bar>& get_mgmt(bar& that) { return bar_management[& that]; } get_mgmt should be a functor. It's extremely difficult to pass contextual information to a free standing function. Your example shows that right off by simply operating on a global variable.

Yes, that idea was an "accidental bonbon" ;-). The original intent was to provide a straightforward extension point to access member hooks, but of course it also allows non-intrusiveness (though stateless). I probably over-advertised it in the code comments. As already admitted (in my reply to Ion), stateful function objects would be more flexible for the non-intrusive stuff. Anyway,

The question is if we can or should (ab)use the traits class for this or if we introduce another template parameter like this:

here is where we reach my primary point: Improving the interface. There are two much template parameters, already, and it seems that applying Boost.Parameter (to the template parameters of containers) would suit that library well: It allows to split the container configuration at any grain desired and to add features in future versions without breaking the interface. Positional template parameters whose meaning isn't immediately obvious (such as e.g. the non-type boolean ConstantTimeSize used by the Intrusive containers) tend make interfaces unintuitive, because readers of client code without in-depth knowledge of the library have to figure out what the arguments refer to. Named arguments OTOH lead to self-explanatory code. I'd also like to see a 'T' parameter for straightforwardness template< class T, // [...] class container; so one could just say container<T> given 'T' has appropriate hooks installed. That "nested 'value_traits' business" feels pretty clumsy (much more than having the hooks inject public names) and it was my main motivation to look for something better. Hope I haven't complained too much... The library is great; I have the impression that a lot of care went into the implementation -- its interface just /deserves/ some polishing ;-). Regards, Tobias

Ion Gaztañaga wrote:

Tobias Schwinger wrote:

...

As already admitted (in my reply to Ion), stateful function objects would be more flexible for the non-intrusive stuff.

I think a custom ValueTraits class just offers the necessary tools to build the stateless (or using global variables) non-intrusive approach. An alternative would be store a copy of ValueTraits inside the container, yielding to a stateful function object. Container constructors should take an additional ValueTraits parameter, guaranteeing that the internal ValueTraits will be copy constructor. If no ValueTraits object is provided a default constructed one might be used. If EBO is used there wouldn't be any size overhead for the default case (member or base ValueTraits).

...

There are two much template parameters, already, and it seems that applying Boost.Parameter (to the template parameters of containers) would suit that library well:

The fact is that containers could accept an arbitrary number of options For example: slist could just also store a pointer to the last element, so that more functions are now constant-time functions.

As mentioned, the bucket management could be more customizable. There is no logical requirement to have a bucket array. Buckets can be represented with a ramdom access iterator and a size, so that buckets can be implemented with a deque or any other container that might be more suitable for an application.

...

Positional template parameters whose meaning isn't immediately obvious (such as e.g. the non-type boolean ConstantTimeSize used by the Intrusive containers) tend make interfaces unintuitive, because readers of client code without in-depth knowledge of the library have to figure out what the arguments refer to. Named arguments OTOH lead to self-explanatory code.

I don't know much about Boost.Parameter but my goal is maintain Boost.Intrusive independent of heavy template-metaprogramming machinery, because the library is adequate for embedded systems and I wouldn't want the executable to grow with type-info information/increased compilation time created by meta-programming (I might absolutely wrong with this sentence, so please feel free to correct). I want to maintain the library *simple*.

Policy mixing (what is basically what named arguments is all about) is very simple to implement (just traits and inheritance) and requires no meta-programming machinery at all. I'm certain that an interface, similar to what Boost.Parameter provides for template arguments, can be implemented with zero overhead. Not sure whether that's what Boost.Parameter does, however. Type information is only emitted if 'typeid' is used or for polymorphic classes (IOW classes with virtual functions). Further, you can just globally disable RTTI with a compiler option and templates will keep working (well, unless they attempt to use 'typeid' or 'dynamic_cast', of course). The only potential problem I see is that container< a_policy, another_policy > and container< another_policy, a_policy > are distinct types and some compiler might not factor out redundant code properly. It can be dealt with in two ways: a) Add a note to the docs and leave it up to the user's self discipline to pick an order and to stick with it, or b) enforce some canonical order before instantiating functions. I think that a) is the way to go if you want to keep things simple.

But I agree that so many options might confuse users. Maybe a configuration structure might be better:

struct options { //If not present, defaults to true static const bool contant_time_size = true;

//If not present, defaults to std::size_t typedef unsigned short size_type;

//... };

list<T, options>

Yes, much better. It also allows to say: struct options : default_options { // just set one option static const bool constant_time_size = false; };

...

I'd also like to see a 'T' parameter for straightforwardness

template< class T, // [...] class container;

so one could just say

container<T>

given 'T' has appropriate hooks installed. That "nested 'value_traits' business" feels pretty clumsy (much more than having the hooks inject public names) and it was my main motivation to look for something better.

One option would be to detect if the passed value parameter is a value_traits class. If not, a base hook is supposed.

One could put the 'value_traits' template into 'options' (which is then used with 'T'). Alternatively we'd have 'options<T>'.

But note that if several base hooks are used, you *must* tell the container which hook you want to use:

struct tag1; struct tag2;

struct my_type : public list_hook<tag1> , public list_hook<tag2> {};

And the tag would go into 'options' as well...

No automatic detection will work here.

BTW: Given a typeof operator it can in some cases (not the one above, however, because deduction would be ambiguous).

T is the same for slist, but the hook to be used is different. What I could do, is to simplify the most common case (simple base hook).

And provide "'options' classes or templates" for common combinations of settings (e.g. with 'value_traits' using 'offset_ptr' or a template that sets a custom tag)... Now recognize that it's still imperfect and that what we actually want is named template arguments ;-)...

...

Hope I haven't complained too much... The library is great; I have the impression that a lot of care went into the implementation -- its interface just /deserves/ some polishing ;-).

I agree. It's just that I haven't found a better interface that preserves all the possibilities of the library. But I'm pretty sure that interface exists ;-)

...here's some code for the taste of it (plain, without using Boost.Parameter). Regards, Tobias // Defaults struct container_xyz_defaults { static bool const constant_time_size = true; typedef void tag; template<typename T> struct value_traits { typedef T* pointer_type; typedef T& reference; // ... }; // ... }; // Setters template<bool Enabled> struct constant_time_size { template<class Base> struct apply_options : Base { static bool const constant_time_size = Enabled; }; }; template<typename T> struct tag { template<class Base> struct apply_options : Base { typedef T tag; }; }; template<typename T> struct offset_ptr {}; // just pretend it's there... struct offset_ptr_storage { template<class Base> struct apply_options : Base { template<typename T> struct value_traits { typedef offset_ptr<T> pointer_type; typedef T& reference; // ... }; }; }; struct none_specified { template<class Base> struct apply_options : Base { }; }; // ... template<typename T, class Policy1 = none_specified, class Policy2 = none_specified, class Policy3 = none_specified, class Policy4 = none_specified > class container_xyz { typedef typename Policy4::template apply_options< typename Policy3::template apply_options< typename Policy2::template apply_options< typename Policy1::template apply_options< container_xyz_defaults > > > > policies; public: typedef typename policies::template value_traits<T> value_traits; typedef typename policies::tag tag; typedef typename value_traits::pointer_type pointer_type; static bool const constant_time_size = policies::constant_time_size; // ... }; // Demonstrate it #include <iostream> #include <typeinfo> template<class C> void show_config(char const * name) { std::cout << name << ":" << std::endl << " tag: " << typeid( typename C::tag ).name() << std::endl << " pointer_type: " << typeid( typename C::pointer_type ).name() << std::endl << " constant_time_size: " << C::constant_time_size << std::endl << std::endl; } int main() { show_config< container_xyz< int, constant_time_size<false> > > ("container_xyz< int, constant_time_size<false> >"); show_config< container_xyz< int, offset_ptr_storage > > ("container_xyz< int, offset_ptr_storage >"); show_config< container_xyz< int, offset_ptr_storage, tag<int> > > ("container_xyz< int, offset_ptr_storage, tag<int> >"); return 0; }

Ion Gaztañaga wrote:

Tobias Schwinger wrote:

...

The only potential problem I see is that

container< a_policy, another_policy >

and

container< another_policy, a_policy >

are distinct types and some compiler might not factor out redundant code properly. It can be dealt with in two ways:

This is quite frightening to me. There is another way to minimize bloat:

Sorry to frighten you. This is a non-issue (it didn't occur to me yesterday - must've been too late in my timezone), as we can use 'container_xyz_impl' containing the actual code and pass the information from the policy into it in a defined order (see below for details). Also, please keep in mind that we are talking about a workaround, because decent compilers should factor out redundant machine code automatically.

typedef define_container< another_policy, a_policy >::type Container;

The combination is concentrated in the auxiliary define_container but the resulting container is exactly the same. But it's not as easy to use as the straight policy approach.

Another question is that Intrusive has already received a review, and such important breaking change would need at least consensus from Boosters.

If it simplifies the usage it won't be that hard to reach. Of course it's best to make such changes before the official release with 1.35.

This option has also the problem of instantiating different containers with the same options, just because "options" will be a user type. Another approach can be:

list<T, list_options<Policy1, Policy2, Policy3>::type>

where the created type is unique type even if policies are passed in different order, because list_options does the job of creating a unique options type for the same policies.

Well, having the library do that internally would be "option b" from my previous post. But wait - it's not necessary because 'policies::a_specific_option' and 'different_type_for_same_policies::a_specific_option' are guaranteed to be identical. Those types can be used to select the code and the problem should be solved (see code). Also note that one can provide "factorization aid" at every granularity desired putting the code into several templates only dependending on the types needed (not done in the sample code).

The question is if the use of policies will simplify the life of the average programmer or if specifying "normal" (meaning raw) template parameters will be easier.

The most important one. First of all, I would avoid that buzzword (yes, I used it too) but it might easily provoke the false impression of the "Alexandrescu-inspired kill all birds there are with one stone" kind of thing ;-). "Named template arguments" probably cuts it better. Second, the current usage is quite far away from "normally specifying template arguments", isn't it? So it comes down to whether we prefer to write e.g. (variant 1) container< type::value_traits<type>, a_default, another_default, false > or (variant 2) struct my_settings : defaults { static bool const constant_time_size_operation = false; }; container< type, my_settings > or (variant 3) container< type, constant_time_size_operation<false> > Is it easier to write customize a container with variant 1, 2 or 3? With variant 1 you have to know the defaults and the position of the option to change. With variant 2 you have to know how to define the traits (which might become more complicated in practice - as mentioned in the previous post), plus the name of the option to change and how to specify it. With variant 3 you only need to know the name of the option to change and how to specify it (where it seems easier to pass something as a template argument than to define it within a traits class). Now imagine being unfamiliar with Intrusive, reading the code (and the source file uses a whole bunch of libraries -- you gotta get this one bug fixed, the author is on vacation and the customer's angrily awaiting the already-delayed deployment ;-) ). Which one is the easiest to understand (ideally without reading through the docs)? So variant 1 is certainly the least expressive: "What the heck does that 'false' say?" and the defaults might not be identifiable as such and cause similar questions. Variant 2 is self-explanatory but too verbose, thus probably making the customization of the container seem more important than it actually is - the constant time size operation might got disabled because it's not needed - just a nuance for optimization. Variant 3 doesn't have any of these drawbacks. Regards, Tobias // Defaults struct container_xyz_defaults { static bool const constant_time_size = true; typedef void tag; template<typename T> struct value_traits { typedef T* pointer_type; typedef T& reference; // ... }; // ... }; // Setters template<bool Enabled> struct constant_time_size { template<class Base> struct apply_options : Base { static bool const constant_time_size = Enabled; }; }; template<typename T> struct tag { template<class Base> struct apply_options : Base { typedef T tag; }; }; template<typename T> struct offset_ptr {}; // just pretend it's there... struct offset_ptr_storage { template<class Base> struct apply_options : Base { template<typename T> struct value_traits { typedef offset_ptr<T> pointer_type; typedef T& reference; // ... }; }; }; struct none_specified { template<class Base> struct apply_options : Base { }; }; // ... namespace detail { template<typename ValueTraits, typename Tag, bool ConstantTimeSize> class container_xyz_impl { // ... public: typedef Tag tag; typedef typename ValueTraits::pointer_type pointer_type; static bool const constant_time_size = ConstantTimeSize; // ... // <--- member functions go here }; template<typename T, class Policy1, class Policy2, class Policy3, class Policy4> class container_xyz_impl_spec { // join policies typedef typename Policy4::template apply_options< typename Policy3::template apply_options< typename Policy2::template apply_options< typename Policy1::template apply_options< container_xyz_defaults > > > > policies; // specialize value_traits and extract props typedef typename policies::template value_traits<T> value_traits; typedef typename policies::tag tag; static bool const constant_time_size = policies::constant_time_size; public: typedef container_xyz_impl<value_traits,tag,constant_time_size> type; }; } // namespace detail template<typename T, class Policy1 = none_specified, class Policy2 = none_specified, class Policy3 = none_specified, class Policy4 = none_specified > class container_xyz : public detail::container_xyz_impl_spec< T,Policy1,Policy2,Policy3,Policy4 >::type { public: // <-- dumb, forwarding inline ctor comes here // Note: If inheritance does not work to make code generation behave, // another option is to hold the implementing class by value and add // more dumb, forwarding inline functions. }; // Demonstrate it #include <iostream> #include <typeinfo> template<class C> void show_config(char const * name) { std::cout << name << ":" << std::endl << " tag: " << typeid( typename C::tag ).name() << std::endl << " pointer_type: " << typeid( typename C::pointer_type ).name() << std::endl << " constant_time_size: " << C::constant_time_size << std::endl << std::endl; } int main() { show_config< container_xyz< int, constant_time_size<false> > > ("container_xyz< int, constant_time_size<false> >"); show_config< container_xyz< int, offset_ptr_storage > > ("container_xyz< int, offset_ptr_storage >"); show_config< container_xyz< int, offset_ptr_storage, tag<int> > > ("container_xyz< int, offset_ptr_storage, tag<int> >"); return 0; }

Hi Joaquín, Joaquín Mª López Muñoz wrote:

Tobias and Ion,

I'm writing a lib for eventual submission to Boost that incidentally uses Boost.Parameter to achieve a flexible template argument specification like the one you're discussing. The thing is, you can have (2) and (3) at a time, so that both

Interesting. What's the library about in the first place? Quick summary of the discussion context: Boost.Parameter was my first suggestion. Ion was concerned that too much template instantiations would have a negative impact on the size of the executable image (due to poor code factorization with some compilers when a template gets instantiated with many distinct types, that actually mean the same), so we were discussing minimalist, custom-made, named template parameters.

If you'd like to have a look, please tell me so via private email and I'll send you the stuff.

Yes, always curious to take a look... Thanks, Tobias

Tobias Schwinger wrote:

Ion Gaztañaga wrote: Also, please keep in mind that we are talking about a workaround, because decent compilers should factor out redundant machine code automatically.

Do you have any evidence of this? I've read somewhere that Visual 8 does something like this, but I hope this is not the COMDAT folding option. This redundant machine code erasing is performed by the linker, the code is still instantiated at compile time, so we are not going to save much compilation time. In our example (list), all produced functions should be exactly the same, so the linker might have it easier (I don't know if shared libraries can also be optimized) to erase redundant functions. However, the two level architecture (node<->value ) would still be necessary, because functions are not exactly equal (the final transformation between the node and the hook is not equal, unlike the core algorithm).

Second, the current usage is quite far away from "normally specifying template arguments", isn't it?

Well, for an average C++ programmer, a template parameters list template <class ValueTraits, bool ConstantTimeSize, ...> is surely easier to understand that seeing something like template<class Policy1 = no_policy, class Policy2 = no_policy, > and having to write class_name <class T ,policy_name_a<parameter_to_policy2>, ,policy_name_a<parameter_to_policy3>...

specially when we only have 3 template parameters. I don't consider myself a novice, but I still don't easily grok this style (surely because no standard C++ utility uses this approach and I'm not used to it). Anyway the derivation approach of your attached code should minimize instantiation problems. All the instantiated code is the same for all policy combinations, and only the front-end class is different. Another question is if having different C++ types for otherwise semantically exact concepts (just that policies have been specified in another order) is a problem. Even if it's not a problem, that makes me really nervous. That's why I think something like: typedef options < void_pointer<void*> , constant_time_size<false> >::type my_options; list<T, my_options> is more straightforward and understandable, since the declaration of the class is something like: template<class T, class Options = default_list_options> class list; Any C++ programmer would instantly understand how to use the class ("Oh, a container of type T, where I can tweak some options"). I know, I'm from the old school, but you know: "One concept, one type" ;-) The specification of different hook types (base, member or maybe non-intrusive hooks) might not be homogeneous (the base hook needs a tag, the member hook needs a pointer to member, the non-intrusive hook might need... everything the user want to put in it). Also, taking out the T type might cause current hook definition cry. Anyway, I need to think about this more carefully, because the interface change *might* lead to a considerable architecture redesign (not sure it would provoke it, but I'm still trying to grok the consequences) .

So it comes down to whether we prefer to write e.g.

(variant 1)

container< type::value_traits<type>, a_default, another_default, false >

or (variant 2)

struct my_settings : defaults { static bool const constant_time_size_operation = false; };

container< type, my_settings >

or (variant 3)

container< type, constant_time_size_operation<false> >

Is it easier to write customize a container with variant 1, 2 or 3?

Depends on the programmer. The fact is that variant1 has been in use for years and programmers are used to it. The programmer that wants to know what a_default means will jump to the declaration (if using a IDE it will show you the definition automatically). Of course, code is more self-documented with options 2 and 3.

Which one is the easiest to understand (ideally without reading through the docs)?

Without reading the docs? Maybe letting the code non-understandable has its advantages.. (just kidding)

So variant 1 is certainly the least expressive: "What the heck does that 'false' say?" and the defaults might not be identifiable as such and cause similar questions.

Ok. Forget the "false" value, I know it's a bad choice, I should have defined a type called: enum SizeComplexity { ConstantTimeSize, LinearTimeSize }; template < class ValueTraits , SizeComplexity = ConstantTimeSize , class SizeType = std::size_t> class list;

Variant 2 is self-explanatory but too verbose, thus probably making the customization of the container seem more important than it actually is - the constant time size operation might got disabled because it's not needed - just a nuance for optimization.

Variant 3 doesn't have any of these drawbacks.

Variant 2 can be very similar to variant 3 (we don't need an external options type and derive from default options). Just do the argument processing outside the class so that we don't complicate the class with argument processing: typedef container < T , list_options < constant_time_size_operation<false> , void_pointer_type<offset_ptr<void> ,... // Unspecified options take default values > >::type > MyContainer; where container is: template<class T, class ListOptions = list_options<> > class container; Container is exactly the same type for the same options and my nervousness disappears ;-) Regards, Ion

Tobias Schwinger wrote:

max:~/Lab/consulting tosh$ g++ -O2 code_bloat.cpp ; ls -l a.out -rwxr-xr-x 1 tosh tosh 13928 Aug 10 19:26 a.out max:~/Lab/consulting tosh$ g++ -O2 code_bloat.cpp -DTRY_BLOAT ; ls -l a.out -rwxr-xr-x 1 tosh tosh 13928 Aug 10 19:26 a.out max:~/Lab/consulting tosh$ # here we go

I guess inlining is helping here, but you are surely right about the compiler optimizing the bloat.

The first argument to a container is usually the type, the other ones are >>gotta read into that library<<. For a set you can probably figure the second to be a compare function. For configuration options, however, positional arguments are a bad idea, IMO, because the resulting client code will not be self-explanatory. See

I agree. Having T as the first parameter would be ideal. Putting the configuration pack at the end of the expected parameters (predicate function + hash). Something like: list<T, ...> set<T, Pred, options...> unordered_set<T, Hash, Pred, options...>

Holding the implementation and using "dumb inline forwarders" (as suggested as the last resort method in the code sample) is documented to work in "C++ Templates" [Vandevoorde, Josuttis] as a technique to reduce code bloat.

Of course it will reduce the bloat. Inline forwards are optimized out and the core is common to all instantiations.

...

typedef container < T , list_options < constant_time_size_operation<false> , void_pointer_type<offset_ptr<void> ,... // Unspecified options take default values > >::type > MyContainer;

where container is:

template<class T, class ListOptions = list_options<> > class container;

Container is exactly the same type for the same options and my nervousness disappears ;-)

That would be a great improvement of the interface.

The reason why I suggested using a different approach is that 'list_options' is a non-trivial metaprogram which you said you wanted to avoid (see attached code).

I'm still not convinced it is the better solution, but hey - it's your party ;-).

..and I'll cry if I want to ;-) No seriously, you've convinced me just to the previous "configuration pack" example. Still not convinced by variant 3 but who knows. Whatever option I choose, I'll need to think about how I'll pass diverse hook information in the configuration and still support the stateful non-intrusive hooks you pointed out in this thread. Who said Intrusive was just in maintenance mode! Regards, Ion

...

Do you have any evidence of this? I've read somewhere that Visual 8 does something like this, but I hope this is not the COMDAT folding option. This redundant machine code erasing is performed by the linker, the code is still instantiated at compile time, so we are not going to save much compilation time.

No, it's not some new esoteric thing: Given some code like

template<typename T> struct X { /* code inside that only uses T* */ }

the compiler can determine that an incomplete type suffices for 'T' and that instances for any 'T' are interchangeable.

I tried with std::vector<type*> (cf joined source file) and it is the COMDAT folding which do the work: Without: 36ko With: 28ko (the others options by default, in particular Win98 optimization is on bumping the size) The COMDAT folding is on by default. I don't know how much this affect the compile time, but at least it should greatly reduce the code bloat. It could break some code: template< class T > void testFct(T t) { std::cout << t << std::endl; } ... std::cout << "ptr1: " << static_cast< void(*)(t1*)

(&testFct<t1*>) << std::endl; std::cout << "ptr2: " << static_cast< void(*)(t2*) (&testFct<t2*>) << std::endl;

with COMDAT folding the function address are the same (not without) (using VS8) Regards, -- Cédric Venet

Mathias Gaunard wrote:

Ion Gaztañaga wrote:

It's not the first time I've seen this, and I still do not understand what the belief of template meta-programming causing bloat is based on.

I suppose that depends on the template handling mechanism the compiler toolchain uses but I would expect that info to be erased at link time (shared libraries can be also. Anyway, my affirmation is based on "impressions" that might be false (the cause of the bloat might be related to the instantiation and *use* of many different classes and functions created using template techniques). What it's clear is that compilation times are much higher, and I really appreciate compilation times (more compilation time means less programmer productivity). I should definitely do some small tests to see if executable size is actually increased. Thanks for the comment. Regards, Ion

on Fri Aug 10 2007, Mathias Gaunard <mathias.gaunard-AT-etu.u-bordeaux1.fr> wrote:

Ion Gaztañaga wrote:

...

I don't know much about Boost.Parameter but my goal is maintain Boost.Intrusive independent of heavy template-metaprogramming machinery, because the library is adequate for embedded systems and I wouldn't want the executable to grow with type-info information/increased compilation time created by meta-programming (I might absolutely wrong with this sentence, so please feel free to correct).

It's not the first time I've seen this, and I still do not understand what the belief of template meta-programming causing bloat is based on.

It certainly increases compilation time, of course, since the point is to create a domain specific language for the problem domain -- using the type system -- and evaluate it at compile-time to generate the best targeted code, but it certainly doesn't make the executable needlessly grow at all. All information about types is lost once a program is compiled. (apart from debugging information, of course)

Imagine you have a function [template] f using named parameters. Then f(n = 4, s = "hello"); and f(s = "hello", n = 4); instantiate different specializations of f at the top level even though the two are functionally equivalent. Of course, everything in f that generates substantial code can be in an implementation function -- say, f_impl -- whose template parameters are identical for the two invocations, so in the end I don't think there's much to worry about. f simply gathers up and distributes references to its arguments. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com The Astoria Seminar ==> http://www.astoriaseminar.com

on Fri Aug 10 2007, Ion Gaztañaga <igaztanaga-AT-gmail.com> wrote:

David Abrahams wrote:

...

Imagine you have a function [template] f using named parameters. Then

f(n = 4, s = "hello");

and

f(s = "hello", n = 4);

instantiate different specializations of f at the top level even though the two are functionally equivalent. Of course, everything in f that generates substantial code can be in an implementation function -- say, f_impl -- whose template parameters are identical for the two invocations, so in the end I don't think there's much to worry about. f simply gathers up and distributes references to its arguments.

What I really don't know is what kind of information the compiler adds to the executable when using meta-programming.

NOne.

I don't kno if created types (either with recursive specialization or just applying metafunctions) add *some* overhead in the executable/library/shared library.

The creation of types involves zero runtime overhead in any C++ implementation I've seen. It's certainly possible to build a conforming C++ compiler where there is an runtime cost for the existence of types, but why would you?

I'm not talking about types that have some run-time instance in the program but just types that are used to calculate a new type.

Yes. Even types with a run-time instance incur no runtime cost by themselves. Only code incurs a runtime cost.

I "guess" that all those types (which are not negligible due to increased compilation time) can be avoided in the executable unless some kind of debugging information is needed.

Yes, and that's a space cost.

Anyway, my basic concern is that the type of the external function/class changes:

my_class<policy_a<param_a>, policy_b<param_b> >

is not the same type as

my_class<policy_b<param_b>, policy_a<param_a> >

That's the precise class template analogy to my function template example.

That's why I still prefer a more conservative approach:

my_class< policy_packer<policy_b<param_b>, policy_a<param_a> >::type >

so that my_class is the same type for the same policy combination. Call me conservative but I still prefer seeing a definition like this:

Bleah, if you don't mind my saying so :-) my_class<policy_b<param_b>, policy_a<param_a> >::normalized_type would be nicer. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com The Astoria Seminar ==> http://www.astoriaseminar.com

Hi,

It's not the first time I've seen this, and I still do not understand what the belief of template meta-programming causing bloat is based on.

Maybe I can help with that. For simple toys and well-contained programs, the compiler can do a lot to inline, as was kindly shown by someone. But take an application of ours as an example from somewhat more real software world. An average run pulls in several hundred shared libraries and has a memory foot print of about 500 MB. Of the 500 MB, ~100 MB is for text segments (machine code). Of the 100 MB, several tens of megabytes is redundant duplicate symbols, for example template instantiations and out-of-line versions of inline functions. There's 1 MB of code for (numerous copies of) a single template function. For a more real measure of redundancy, you'd have to add on top code that was actually inlined. Put another way, we estimate 10-25% of the entire program memory footprint is various degrees of _code_ redundancy. But it gets worse. The "useful" and "useless redundant code" interleave in the shared libraries. For each duplicated symbol the dynamic linker picks a "representative" symbol; the others will never be used. You won't know which ones the representative ones will be until at run time. The result: in memory code is like Swiss cheese, some hundred bytes of used code, some hundred bytes of unused code, used code, unused code. Not only do we have lots of memory committed to code, we make terrible use of it and have poor page locality. And surprise, some of the bigger bottlenecks plaguing our programs are L1 instruction cache pressure and ITLB misses. 40% of L2 cache accesses are for instructions -- and each and every L1 instruction cache miss stalls the CPU. Solving the code bloat is obviously making its way up on our performance optimisation priorities. Haphazard use of templates and inlining definitely make things worse. Hope this helps understand why. While we all hope compiler technology to improve, the reality check is that the impact factor of 20 years of compiler research is trivially measured: it's the difference between -O0 vs. -O3. If your program falls into the class where that makes a world of difference, good for you. Most programs in this world are not in that class, and you start engineering and making trade-offs. Lassi

Dear all, Thanks for your comments; I hope this responds to you all. I very much agree with David's words. For background, most developers in our project program purely as a means to an end; they are not software engineers and don't usually get a kick from discovering a cool new C++ or ABI feature. When they can focus on their problem at hand, and not on the language and the tools, we have done well. Programming languages, libraries or compilers prone to lead to mistakes reduce their efficiency. Our code base is some millions of lines of code, a complete built distribution is in the ballpark of 4 GB and 1000 shared libraries. We process large quantities of data, at present the code runs flat out on thousands of cores every day, soon on a much larger number of cores. So you may understand my ideas of performance consequences are rather concrete; I am aware others have different constraints. I'd posit template metaprogramming is a means to an end, another tool to get the compiler churn out code and help developers focus on problems interesting to them. It's definitely a tool I am pleased to have in my toolbox. However regardless of the languages and constructs used, I'll look at code maturity, maintainability, features and performance delivered per byte of object code, and factors such as build time or ability to debug the code. Like any tool, templates presently have some concrete strengths and weaknesses. I'll rejoice with you as compilers, linkers and run- times get more clever about templates. In the mean time we'll push for (substantial) economies by seeking a remedy to these present weaknesses. To us it is really not a question of whether there is bloat or not; it seems we can produce objective hard data with relative ease. What interests me most in the template bloat is that the awkward practical consequences are a result of fairly innocuous use of the language and the libraries, mostly in style taught in the best C++ text books and programming courses available. It is not even badly designed templates, and I would not be comfortable blaming just the tools either. Our tool chain actually does a decent job for a single shared library, about as good as any other as far as I know. I don't really know of production-quality whole program optimisers capable of processing hundreds of megabytes of machine code originating from several programming languages, or tools that give us a whole new class of liberty for physical packaging, or quality tools capable of combining C++ language level analysis and run-time feedback data. Pointers would be welcome. With the technology at hand today, it is difficult _not_ to make a lot of mistakes: bloat your code by 10+%, pass a 100'000-element map- of-vectors-of-vectors by value, accidentally instantiate the same template into hundreds of shared libraries, have a working set of 50 shared libraries for a particular "unit of work", or have orders of magnitude too many relocation entries in a shared library. Even the top programming and platform experts will sweat blood and tears to identify and analyse the issues, let alone devise practical remedies. There seems to be room for some novel thinking and tooling in this area. Of course not every project deals with such issues. Like you, we do the best we can to improve the classes and the tools, but we really need to look at the reality in the eye as we do that. Some of us spearhead the technology for tomorrow, but it takes wisdom to know what is the right technology for the hordes behind, for the numerous different project circumstances. Best regards, Lassi PS. Please understand I am not picking on templates for the fun of it. I am an engineer, a practitioner. I am as aware of the benefits of well-designed advanced templates as I am of the weaknesses. We recently introduced expression templates into a key algorithm. The change had been resisted for years; careful analysis of the performance costs of the "old-fashioned" code finally overcame the main technical and political arguments and we begun the migration. We are pretty unanimously pleased with the result. The costs associated with the templates may in due course produce similar migration advice. It could be investment into custom tooling, changes to our programming idioms, and other avenues.

Lassi Tuura wrote:

Hi,

...

It's not the first time I've seen this, and I still do not understand what the belief of template meta-programming causing bloat is based on.

Maybe I can help with that. For simple toys and well-contained programs, the compiler can do a lot to inline, as was kindly shown by someone. But take an application of ours as an example from somewhat more real software world.

An average run pulls in several hundred shared libraries and has a memory foot print of about 500 MB. Of the 500 MB, ~100 MB is for text segments (machine code). Of the 100 MB, several tens of megabytes is redundant duplicate symbols, for example template instantiations and out-of-line versions of inline functions. There's 1 MB of code for (numerous copies of) a single template function. For a more real measure of redundancy, you'd have to add on top code that was actually inlined.

Put another way, we estimate 10-25% of the entire program memory footprint is various degrees of _code_ redundancy.

Right: but here's the thing, had those shared libraries been written in C or FORTRAN or some other language without templates there would still be code redundancy, but they would have been implemented with cut-and-paste or (shudder) macros. This is far more fragile than reusing templates - especially heavily tested Boost or std ones. To give you a real world example: I recently had cause to dig into a math library written in a mixture of C and FORTRAN. In four different places the same identical code cropped up (a cut and paste job), had someone spotted a bug in that code in one of those places would they updated all of them? Maybe, maybe not. In contrast the Boost Math Toolkit implements similar functionality as a template. One definition, easier to maintain, test etc. I not trying to make a "mines better that yours" argument here, only that properly used C++ is far easier to write and maintain than languages that lack generics. Of course if that template is used with multiple distributions you get multiple instances. Is this really code bloat? Or is it simply that C/FORTAN hide their bloat better? As others have said already - template meta-programming is a different beast altogether - it generates neither code nor data - and can often be used to reduce code bloat by directing equivalent code to the same actual template instance. Of course whether this actually happens is a question of code quality.

But it gets worse. The "useful" and "useless redundant code" interleave in the shared libraries. For each duplicated symbol the dynamic linker picks a "representative" symbol; the others will never be used. You won't know which ones the representative ones will be until at run time. The result: in memory code is like Swiss cheese, some hundred bytes of used code, some hundred bytes of unused code, used code, unused code. Not only do we have lots of memory committed to code, we make terrible use of it and have poor page locality.

That's not good, especially for those of us used to the VC++ linker that discards duplicate symbols at link time :-)

And surprise, some of the bigger bottlenecks plaguing our programs are L1 instruction cache pressure and ITLB misses. 40% of L2 cache accesses are for instructions -- and each and every L1 instruction cache miss stalls the CPU. Solving the code bloat is obviously making its way up on our performance optimisation priorities. Haphazard use of templates and inlining definitely make things worse. Hope this helps understand why.

Honestly, I believe this bloat issue is true of any language. There is however, one downside to templates I'd admit to :-) They make it too easy to generate code in an ad-hoc fashion without thought of the consequences. The difference is that C++ lets you spot the duplication: for example if you discover that your application is using vector<int>, vector<unsigned>, vector<long> and vector<heaven-knows-what-else> then you should definately be asking why they can't all be using the same instantiation!

While we all hope compiler technology to improve, the reality check is that the impact factor of 20 years of compiler research is trivially measured: it's the difference between -O0 vs. -O3. If your program falls into the class where that makes a world of difference, good for you. Most programs in this world are not in that class, and you start engineering and making trade-offs.

You don't say which compiler you're using (gcc?), but there are many commercial compilers that will automatically spot genuine duplication and remove duplicates from the linked executable (shared libraries always make this harder though I admit). After that, I'm afraid it's down to good code management: taking care that your developers don't get "instantiation happy", and do coordinate which template instances they use between them. HTH, John.

John Maddock wrote:

The difference is that C++ lets you spot the duplication: for example if you discover that your application is using vector<int>, vector<unsigned>, vector<long> and vector<heaven-knows-what-else> then you should definately be asking why they can't all be using the same instantiation!

Just a curiosity, Digginig in the Freescale/MSL STL implementation we use at job I've seen an space optimization MACRO (I don't know if it's activated by default or not) where all vectors of POD types of the same size where treated with a single type type (just the same trick as vector<void*> but with ints, shorts, and similar POD types). I suppose that option was there because the compiler was not smart enough to optimize them (I don't know if that's true nowadays). Regards, Ion

Howard Hinnant wrote:

It's been awhile since I looked at the most recent Freescale STL, but last time I looked, this flag was on by default. This optimization was originally written before the Freescale linker did code folding. After the Freescale linker did code folding it appeared to me that the two optimizations worked together synergistically. I.e. sometimes the lib would catch stuff the linker missed and vice-versa.

Caught lurking again ;-)

Fwiw, it isn't an easy optimization in the lib to get right (I got it wrong first time out of the gate). But it does seem worthwhile. I had a major customer once tell me this optimization saved him 750Kb code, and this was back when a Mb of code was a lot. ;-)

This might be an interesting addition to Interprocess (apart from adding the use of memcpy/memmove for POD types). Fwiw, I've saved some KB on my executable on such systems changing uses of "once-constructed read-only" strings from std::string to hand-managed const char *. Sometimes, something similar to a unique_array<const char *> is all that you need.

-Howard

Regards, Ion