Re: [boost] [MPL][vector] Is there interest in mpl::vector using variadic templates?

Subject: Re: [boost] [MPL][vector] Is there interest in mpl::vector using variadic templates?
From: Larry Evans (cppljevans_at_[hidden])
Date: 2017-03-04 20:01:58

On 03/03/2017 11:21 AM, Bruno Dutra via Boost wrote:
 > On Mar 3, 2017 17:58, "Peter Dimov via Boost" <boost_at_[hidden]> 
wrote:
 >
 > Bruno Dutra wrote:
 >
 > OTOH the void* trick requires that a pack of M void pointers be
 >> instantiated when the element at position M is retrieved from a 
list, so,
 >> for a list of N elements, the compiler must instantiate N *distinct* 
packs
 >> of void pointers, because each of these packs have a different size 
and is
 >> thus a distinct type.
 >>
 >
 > Not just that, but the helper function that is required to obtain the Mth
 > element is a template instantiation as well.
 >
 > Saying that we shouldn't use map_from_list because it consumes memory for
 > the instantiation is misleading; the alternatives consume memory for
 > instantiations as well. Except for __type_pack_element, of course.
 >

I see your point. It seems obvious now that you mention the
helper function. Thanks Peter.

More explicitly, the helper functions (would metafunction be
more accurate?) for the:

   // mp_repeat_c

method from:

   simple_cxx11_metaprogramming_2.html

are:

   struct mp_repeat_c_impl
   struct mp_at_c_impl

OTOH, for the:

   // mp_map_from_list

method, the metafunctions are:

   struct mp_map_from_list_impl
   struct mp_at_c_impl

in addition, there's the:

   class integer_sequence

Hence, just based on the number of class template's used,
mp_repeat_c wins (although, since the cost of instantiating
integer_sequence can be amortized, it may not be by much).
A more difficult but accurate analysis would, somehow,
calculate the number of distinct class template
instantiations.  Anyone care to try that?

OOPS.  Bruno did that, sortof, when he said (in the Date:
Fri, 3 Mar 2017 17:51:26 +0100 post):

   OTOH the void* trick requires that a pack of M void
   pointers be instantiated when the element at position M is
   retrieved from a list, so, for a list of N elements, the
   compiler must instantiate N *distinct* packs of void
   pointers, because each of these packs have a different
   size and is thus a distinct type. This means the
   compiler does not benefit from memoization at all.

So, I guess to retrieve N elements, something of the order
of N^2 instantiations are needed?  That because, for each of
the N elements, a different instantiation of N elements( M
void* and N-M other elements) is needed?  OOPS.  Looking at
the times in the table, it appears almost linear, not
quadratic.  Attached is a libreoffice spreadsheet with the
graph of times vs. number of elements.  It does clearly show
the void* method does show some non-linearity, but it's not
very pronounced.

 >
 > Right, the trick is usually to figure out what consumes less memory, i.e.
 > what leads to the least amount of distinct template
 > instantiations.

Which is more expensive, function template instantiations
and class template instantiations? (I'd assumed class
templates were more expensive).

Thanks to you both for helping me understand the code
complexity.

-regards,
Larry