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

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
16 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
Dear community,

I've recently started contributing to boost::variant. To speed up variant's
compilation I'm implementing mpl::vector on variadic templates. For now
status of new vector implementation is:
 1) it passes all mpl/test tests on gcc 4.9 and 6.3
 2) it is decoupled from mpl::vectorN, simultaneously making mpl::vectorN
visible, so libs like Boost.Geometry, which rely on mpl::vectorN compile
nicely
 3) There are several compilation errors during full build on gcc 4.9 and
6.3
 4) I fix problems on mpl/tests stage for clang 3.4 and latest MSVS2017
compiler

Bruno's introduction of new shiny Metal library and Sergey's comment in the
same thread:

> The biggest and most useful feature of "new" TMP libraries is variadic
> templates that increase performance by a really huge factor. The problem
> with MPL is that vector type sequence must derive from vectorN-s, which are
> documented and can be used in template specialization. So it is impossible
> or pointless to remplement mpl::vector in terms of variadic parameters
> because of that. The other problem that I can quickly recall is recursive
> iterator-based approach, which also kills performance.


made me wonder, is there interest in variadic templates implementation? Are
there limitations for it's usefulness, which I did not see?

Regards,
Mike Maximov

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
On Tue, Feb 21, 2017 at 11:52 AM, Михаил Максимов via Boost <
[hidden email]> wrote:

> Dear community,
>
> I've recently started contributing to boost::variant. To speed up variant's
> compilation I'm implementing mpl::vector on variadic templates. For now
> status of new vector implementation is:
>  1) it passes all mpl/test tests on gcc 4.9 and 6.3
>  2) it is decoupled from mpl::vectorN, simultaneously making mpl::vectorN
> visible, so libs like Boost.Geometry, which rely on mpl::vectorN compile
> nicely
>  3) There are several compilation errors during full build on gcc 4.9 and
> 6.3
>  4) I fix problems on mpl/tests stage for clang 3.4 and latest MSVS2017
> compiler
>
> Bruno's introduction of new shiny Metal library and Sergey's comment in the
> same thread:
>
> > The biggest and most useful feature of "new" TMP libraries is variadic
> > templates that increase performance by a really huge factor. The problem
> > with MPL is that vector type sequence must derive from vectorN-s, which
> are
> > documented and can be used in template specialization. So it is
> impossible
> > or pointless to remplement mpl::vector in terms of variadic parameters
> > because of that. The other problem that I can quickly recall is recursive
> > iterator-based approach, which also kills performance.
>
>
> made me wonder, is there interest in variadic templates implementation? Are
> there limitations for it's usefulness, which I did not see?


I'll give you my opinio as someone who has contributed bugfixes to MPL in
the past, fiddled with the idea of modernizing it and eventually end up
with a "new shiny Metal" (I appreciate the compliment).

By now you have certainly realized that under the hood MPL is a very
complex piece of software full of quirks and tricks that magically fit
together to provide a clean and very well designed interface to the user.
Half of those were workarounds for broken compilers that probably aren't
used by anyone for a decade now, the other half consisting in the emulation
of language features made obsolete by C++11. If you take these out, not
much is left but tag dispatching and the public API. In an attempt to
modernize MPL, it would probably be much easier to rewrite it from scratch,
but then why not taking full advantage of modern features and adapting the
public API accordingly, while at the same time fine tuning for performance
and ease of use?

My two cents.

Regards,
Bruno

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
2017-02-21 13:52 GMT+03:00 Михаил Максимов via Boost <[hidden email]>:
> Dear community,
>
> I've recently started contributing to boost::variant. To speed up variant's
> compilation I'm implementing mpl::vector on variadic templates. For now
> status of new vector implementation is:
<...>
> made me wonder, is there interest in variadic templates implementation? Are
> there limitations for it's usefulness, which I did not see?

I'm very interested in patching MPL to be able to use variadic templates.

There are many C++ libraries and code that use MPL. Those libraries
can not switch from MPL to Metal or Hana because:
* they have to be usable in C++98/C++03 and C++11
* they have a huge code base that can not be simply migrated to new library
* they depend on third party libraries that use MPL and need the
ability to interact with those libraries

Moreover, making MPL variadic will not just speed up compilation, but also will:
* reduce executable size and improve startup times if MPL structure is
part of an exported entity
* improve runtime speed if MPL structure is part of an entity that is
used in operations involving typeid()

So please, continue the work and make a pull request.

--
Best regards,
Antony Polukhin

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
>
>
> I'm very interested in patching MPL to be able to use variadic templates.
>
> There are many C++ libraries and code that use MPL. Those libraries
> can not switch from MPL to Metal or Hana because:
> * they have to be usable in C++98/C++03 and C++11
> * they have a huge code base that can not be simply migrated to new library
> * they depend on third party libraries that use MPL and need the
> ability to interact with those libraries
>
> Moreover, making MPL variadic will not just speed up compilation, but also
> will:
> * reduce executable size and improve startup times if MPL structure is
> part of an exported entity
> * improve runtime speed if MPL structure is part of an entity that is
> used in operations involving typeid()
>
> So please, continue the work and make a pull request.
>
> --
> Best regards,
> Antony Polukhin
>

For what it's worth, I very much agree with all of the above.

-- chris

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On 03/01/2017 12:56 PM, Antony Polukhin via Boost wrote:

> 2017-02-21 13:52 GMT+03:00 Михаил Максимов via Boost <[hidden email]>:
>> Dear community,
>>
>> I've recently started contributing to boost::variant. To speed up variant's
>> compilation I'm implementing mpl::vector on variadic templates. For now
>> status of new vector implementation is:
> <...>
>> made me wonder, is there interest in variadic templates implementation? Are
>> there limitations for it's usefulness, which I did not see?
>
> I'm very interested in patching MPL to be able to use variadic templates.
>
There was a variadic template mpl try from 7 years ago:

https://github.com/cppljevans/variadic_templates/tree/master/boost/mpl

Maybe it could give you some ideas.  OTOH, maybe it's *too* old :(

HTH.

-regards,
Larry






_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
On 03/01/2017 05:07 PM, Larry Evans via Boost wrote:

> On 03/01/2017 12:56 PM, Antony Polukhin via Boost wrote:
>> 2017-02-21 13:52 GMT+03:00 Михаил Максимов via Boost
>> <[hidden email]>:
>>> Dear community,
>>>
>>> I've recently started contributing to boost::variant. To speed up
>>> variant's
>>> compilation I'm implementing mpl::vector on variadic templates. For now
>>> status of new vector implementation is:
>> <...>
>>> made me wonder, is there interest in variadic templates
>>> implementation? Are
>>> there limitations for it's usefulness, which I did not see?
>>
>> I'm very interested in patching MPL to be able to use variadic templates.
>>
> There was a variadic template mpl try from 7 years ago:
>
> https://github.com/cppljevans/variadic_templates/tree/master/boost/mpl
>
> Maybe it could give you some ideas.  OTOH, maybe it's *too* old :(
>
One problem with the above cppljevans mpl is there's no at.hpp.
Instead, the non-variadic boost/mpl/at.hpp was used.
The reason no variadic at was created was because, AFAICT, there was no
non-recursive method for picking the I-th element from T... , and, IIUC,
recursive templates cause compile-time slow downs.

Since then, I've stumbled across other methods as shown in the attached
(where, type_at is used instead of at).

In addition there have been language proposals to do essentially the
same:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0535r0.html#parameter-pack-slicing

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4235.htm

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0327r1.pdf

I don't know of any compiler's that implement those "tuple slicing"
operations; however, if someone does know of some, I'd like
to see their use as an alternative to the existing mpl::at.

Mike, if you find such an tuple-slicing compiler, maybe in your
variadic mpl implementation you could provide a flag which uses
that or one of the methods in the type_at.hpp attachment.
Then, you could profile them to demonstrate which is best :)

-regards,
Larry





_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

type_at.hpp (5K) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
Larry Evans wrote:

> One problem with the above cppljevans mpl is there's no at.hpp.
> Instead, the non-variadic boost/mpl/at.hpp was used.
> The reason no variadic at was created was because, AFAICT, there was no
> non-recursive method for picking the I-th element from T... , and, IIUC,
> recursive templates cause compile-time slow downs.

Have you read

http://pdimov.com/cpp2/simple_cxx11_metaprogramming_2.html

?

Search for mp_at.


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
On 03/02/2017 11:27 AM, Peter Dimov via Boost wrote:

> Larry Evans wrote:
>
>> One problem with the above cppljevans mpl is there's no at.hpp.
>> Instead, the non-variadic boost/mpl/at.hpp was used.
>> The reason no variadic at was created was because, AFAICT, there was
>> no non-recursive method for picking the I-th element from T... , and,
>> IIUC, recursive templates cause compile-time slow downs.
>
> Have you read
>
> http://pdimov.com/cpp2/simple_cxx11_metaprogramming_2.html
>
> ?

Nope.  Thanks *very much* for the link.  I'm impressed (especially
with the way you actually cited the parts of the standard to guide
your search for the best method!).

>
> Search for mp_at.
>
Thanks for that tip.

I'm a bit surprised that the mp_map_from_list was fastest.
I would have thought that large template classes mean slow
compile times, but I guess not.

Thanks again, Peter.

-regards,
Larry




_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
On 03/02/2017 11:54 AM, Larry Evans via Boost wrote:

> On 03/02/2017 11:27 AM, Peter Dimov via Boost wrote:
>> Larry Evans wrote:
>>
>>> One problem with the above cppljevans mpl is there's no at.hpp.
>>> Instead, the non-variadic boost/mpl/at.hpp was used.
>>> The reason no variadic at was created was because, AFAICT, there was
>>> no non-recursive method for picking the I-th element from T... , and,
>>> IIUC, recursive templates cause compile-time slow downs.
>>
>> Have you read
>>
>> http://pdimov.com/cpp2/simple_cxx11_metaprogramming_2.html
>>
>> ?
>
> Nope.  Thanks *very much* for the link.  I'm impressed (especially
> with the way you actually cited the parts of the standard to guide
> your search for the best method!).
>
>>
>> Search for mp_at.
>>
> Thanks for that tip.
>
> I'm a bit surprised that the mp_map_from_list was fastest.
> I would have thought that large template classes mean slow
> compile times, but I guess not.

This:

   http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4235.htm

claims:

   template instantiations use memory that is never freed during the
   compilation process

so, maybe mp_map_from_list should be used with caution.  If many
mp_map_from_list instantiations are used, I'm guessing the compiler
might become pressed for memory. Maybe a benchmark showing
compile time vs number of instantiations would show this.
For example, instead of N=800, see what happens when 2
instantiations with N=400 happen, and compare with a similar
test for mp_repeat_c.

-regards,
Larry



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
On Thu, Mar 2, 2017 at 7:42 PM, Larry Evans via Boost <[hidden email]
> wrote:

> On 03/02/2017 11:54 AM, Larry Evans via Boost wrote:
>
>> On 03/02/2017 11:27 AM, Peter Dimov via Boost wrote:
>>
>>> Larry Evans wrote:
>>>
>>> One problem with the above cppljevans mpl is there's no at.hpp.
>>>> Instead, the non-variadic boost/mpl/at.hpp was used.
>>>> The reason no variadic at was created was because, AFAICT, there was
>>>> no non-recursive method for picking the I-th element from T... , and,
>>>> IIUC, recursive templates cause compile-time slow downs.
>>>>
>>>
>>> Have you read
>>>
>>> http://pdimov.com/cpp2/simple_cxx11_metaprogramming_2.html
>>>
>>> ?
>>>
>>
>> Nope.  Thanks *very much* for the link.  I'm impressed (especially
>> with the way you actually cited the parts of the standard to guide
>> your search for the best method!).
>>
>>
>>> Search for mp_at.
>>>
>>> Thanks for that tip.
>>
>> I'm a bit surprised that the mp_map_from_list was fastest.
>> I would have thought that large template classes mean slow
>> compile times, but I guess not.
>>
>
Since you seem to be interested on benchmarking compilation times, check
out http://metaben.ch.


> This:
>
>   http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4235.htm
>
> claims:
>
>   template instantiations use memory that is never freed during the
>   compilation process
>
> so, maybe mp_map_from_list should be used with caution.  If many
> mp_map_from_list instantiations are used, I'm guessing the compiler
> might become pressed for memory. Maybe a benchmark showing
> compile time vs number of instantiations would show this.
> For example, instead of N=800, see what happens when 2
> instantiations with N=400 happen, and compare with a similar
> test for mp_repeat_c.


This is actually not the case, in fact the exact opposite is true. It turns
out mp_map_from_list is actually very cheap to the compiler in terms of
memory allocation, because it takes advantage of template memoization, so
if you retrieve every single element of a list using this trick, the
compiler needs to instantiate it only once. On the other hand, the trick
employing void pointers can't be expressed in a way that take advantage of
memoization, which means that, for every element retrieved from the list,
the entire pack of void pointers must be instantiated again.

I'm not just guessing here, in fact, benchmarks for the algorithm `at` on
metaben.ch prove it by plotting the time it takes to compile a metaprogram
that retrieves every element in a list as a function of its size, from 0 up
to 500 elements. Brigand and Meta (and likely also Hana, but I'm not sure)
rely on the void pointers trick, as you can verify in their source codes,
and as you can see on metaben.ch their benchmarks appear to vary with the
square of the list size. This is precisely because the entire variadic pack
of void pointers must be generated for each of the N elements retrieved. On
the other hand, the fastest implementation on all compilers(*) is that of
Metal, which seems to vary approximately linearly with the list size. That
is because it relies on a variant of the trick to retrieve an element from
a map and was carefully designed to take advantage of memoization, as you
can verify here
https://github.com/brunocodutra/metal/blob/master/include/metal/detail/lookup.hpp

(*) Specifically on Clang, Metal actually relies on a compiler intrinsic
called __type_pack_element to get the N-th type in a variadic pack. This is
arguably as fast as `at` can possibly get and still it is only slightly
faster than the implementation on GCC, which does not rely on any compiler
intrinsic.

Bruno

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On Wed, 2017-03-01 at 21:56 +0300, Antony Polukhin via Boost wrote:

> 2017-02-21 13:52 GMT+03:00 Михаил Максимов via Boost <[hidden email]
> st.org>:
> >
> > Dear community,
> >
> > I've recently started contributing to boost::variant. To speed up
> > variant's
> > compilation I'm implementing mpl::vector on variadic templates. For
> > now
> > status of new vector implementation is:
> <...>
> >
> > made me wonder, is there interest in variadic templates
> > implementation? Are
> > there limitations for it's usefulness, which I did not see?
> I'm very interested in patching MPL to be able to use variadic
> templates.
>
> There are many C++ libraries and code that use MPL. Those libraries
> can not switch from MPL to Metal or Hana because:
> * they have to be usable in C++98/C++03 and C++11
> * they have a huge code base that can not be simply migrated to new
> library
> * they depend on third party libraries that use MPL and need the
> ability to interact with those libraries
>
> Moreover, making MPL variadic will not just speed up compilation, but
> also will:
> * reduce executable size and improve startup times if MPL structure
> is
> part of an exported entity
> * improve runtime speed if MPL structure is part of an entity that is
> used in operations involving typeid()
>
> So please, continue the work and make a pull request.

I wonder if instead an MPL implementation could be written with a Metal
backend for newer compilers and use the legacy MPL for C++03 compiler.
I thought Bruno was developing something like that at one point. So
building off of that could be useful. Although, Metal is not in boost
yet, hopefully it will be soon.

Paul


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
On Thu, Mar 2, 2017 at 9:55 PM, paul via Boost <[hidden email]>
wrote:

> On Wed, 2017-03-01 at 21:56 +0300, Antony Polukhin via Boost wrote:
> > 2017-02-21 13:52 GMT+03:00 Михаил Максимов via Boost <[hidden email]
> > st.org>:
> > >
> > > Dear community,
> > >
> > > I've recently started contributing to boost::variant. To speed up
> > > variant's
> > > compilation I'm implementing mpl::vector on variadic templates. For
> > > now
> > > status of new vector implementation is:
> > <...>
> > >
> > > made me wonder, is there interest in variadic templates
> > > implementation? Are
> > > there limitations for it's usefulness, which I did not see?
> > I'm very interested in patching MPL to be able to use variadic
> > templates.
> >
> > There are many C++ libraries and code that use MPL. Those libraries
> > can not switch from MPL to Metal or Hana because:
> > * they have to be usable in C++98/C++03 and C++11
> > * they have a huge code base that can not be simply migrated to new
> > library
> > * they depend on third party libraries that use MPL and need the
> > ability to interact with those libraries
> >
> > Moreover, making MPL variadic will not just speed up compilation, but
> > also will:
> > * reduce executable size and improve startup times if MPL structure
> > is
> > part of an exported entity
> > * improve runtime speed if MPL structure is part of an entity that is
> > used in operations involving typeid()
> >
> > So please, continue the work and make a pull request.
>
> I wonder if instead an MPL implementation could be written with a Metal
> backend for newer compilers and use the legacy MPL for C++03 compiler.
> I thought Bruno was developing something like that at one point. So
> building off of that could be useful. Although, Metal is not in boost
> yet, hopefully it will be soon.


Indeed I proposed this idea on the mailing list about a year ago, when
Metal was very similar to MPL in terms of design, such that I wasn't sure
whether it made sense to propose Metal as a separate library, but even back
then some expressed concerns about reworking MPL internally and argued
Metal should be proposed as an independent library instead. The truth is,
it is very hard to achieve consensus in this community regarding big and
potentially breaking changes to MPL, since it is one of the cornerstones of
the Boost libraries, so I decided to take a step back and tackle the
problem at a different angle. My idea is to provide an independent
implementation of MPL based on Metal on a separate repository, such that
users could seamlessly replace MPL on legacy code [1]. Should it prove
successful, would it probably be easier to gather support in the community
for its integration in MPL proper.

Now, implementing MPL from the ground up while making sure it can be used
to compile all other Boost libraries and pass all MPL unit tests is a huge
undertaking no matter what and I warmly welcome any help.

[1]: https://github.com/brunocodutra/metal/projects

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On 03/02/2017 01:54 PM, Bruno Dutra via Boost wrote:

> On Thu, Mar 2, 2017 at 7:42 PM, Larry Evans via Boost <[hidden email]
>> wrote:
>
>> On 03/02/2017 11:54 AM, Larry Evans via Boost wrote:
>>
>>> On 03/02/2017 11:27 AM, Peter Dimov via Boost wrote:
>>>
>>>> Larry Evans wrote:
>>>>
>>>> One problem with the above cppljevans mpl is there's no at.hpp.
>>>>> Instead, the non-variadic boost/mpl/at.hpp was used.
>>>>> The reason no variadic at was created was because, AFAICT, there was
>>>>> no non-recursive method for picking the I-th element from T... , and,
>>>>> IIUC, recursive templates cause compile-time slow downs.
>>>>>
>>>>
>>>> Have you read
>>>>
>>>> http://pdimov.com/cpp2/simple_cxx11_metaprogramming_2.html
>>>>
>>>> ?
>>>>
>>>
>>> Nope.  Thanks *very much* for the link.  I'm impressed (especially
>>> with the way you actually cited the parts of the standard to guide
>>> your search for the best method!).
>>>
>>>
>>>> Search for mp_at.
>>>>
>>>> Thanks for that tip.
>>>
>>> I'm a bit surprised that the mp_map_from_list was fastest.
>>> I would have thought that large template classes mean slow
>>> compile times, but I guess not.
>>>
>>
> Since you seem to be interested on benchmarking compilation times, check
> out http://metaben.ch.
>
The at benchmark there indicates mpl.vector is the fastest
in the, I guess you'd call it, the "performance at given
number_of_elements pop-up list", when the cursor is moved
over to the rhs at number_of_elements=500.  Hmmm. Now I see
there's actually no mpl.vector graph at that
number_of_elements. OOPS.  I see that that's because
mpl.vector was not run for number_of_elements > 50, but
that's only obvious when the subtract_baseline radio button
is turned-off.  To avoid this confusion, the graph should
give some indication, in the "performance at given
number_of_elements pop-up list", which methods were actually
run at the given number_of_elements.

>
>> This:
>>
>>   http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4235.htm
>>
>> claims:
>>
>>   template instantiations use memory that is never freed during the
>>   compilation process
>>
>> so, maybe mp_map_from_list should be used with caution.  If many
>> mp_map_from_list instantiations are used, I'm guessing the compiler
>> might become pressed for memory. Maybe a benchmark showing
>> compile time vs number of instantiations would show this.
>> For example, instead of N=800, see what happens when 2
>> instantiations with N=400 happen, and compare with a similar
>> test for mp_repeat_c.
>
>
> This is actually not the case, in fact the exact opposite is true.

So n4235.htm was wrong or maybe I've misinterpreted it?

> It turns
> out mp_map_from_list is actually very cheap to the compiler in terms of
> memory allocation, because it takes advantage of template memoization, so
> if you retrieve every single element of a list using this trick, the
> compiler needs to instantiate it only once. On the other hand, the trick
> employing void pointers can't be expressed in a way that take advantage of
> memoization, which means that, for every element retrieved from the list,
> the entire pack of void pointers must be instantiated again.

So how do you resolve what n4235 is saying and what you say above?

I'm guessing that 4235 was actually referring to this
memoization when it said:

   template instantiations use memory that is never freed

The memoizations do use memory which, IIUC, is never freed
until the compiler is finished.  OTOH, when you say:

 > for every element retrieved from the list, the entire pack
 > of void pointers must be instantiated again.

That means more compile time is needed for the repeated
instantiations; however, no memory is *permanently* used as
is the case for memoization.  IOW, this is a classic case of
trading memory for speed:

   https://en.wikipedia.org/wiki/Space%E2%80%93time_tradeoff

OTOH, my point was that as these memoization's increase, the
compiler has less memory to use; hence, might slow down;
whereas, since, the memory used by the vec_of_void* method
is reused, memory pressure is less, and, although it's
slower for 1 instance of a pack, it might become faster as
many packs are used.

I hope that makes more sense ;)

-regards,
Larry


[snip]


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
On Fri, Mar 3, 2017 at 2:46 PM, Larry Evans via Boost <[hidden email]
> wrote:

> On 03/02/2017 01:54 PM, Bruno Dutra via Boost wrote:
>
>> On Thu, Mar 2, 2017 at 7:42 PM, Larry Evans via Boost <
>> [hidden email]
>>
>>> wrote:
>>>
>>
>> On 03/02/2017 11:54 AM, Larry Evans via Boost wrote:
>>>
>>> On 03/02/2017 11:27 AM, Peter Dimov via Boost wrote:
>>>>
>>>> Larry Evans wrote:
>>>>>
>>>>> One problem with the above cppljevans mpl is there's no at.hpp.
>>>>>
>>>>>> Instead, the non-variadic boost/mpl/at.hpp was used.
>>>>>> The reason no variadic at was created was because, AFAICT, there was
>>>>>> no non-recursive method for picking the I-th element from T... , and,
>>>>>> IIUC, recursive templates cause compile-time slow downs.
>>>>>>
>>>>>>
>>>>> Have you read
>>>>>
>>>>> http://pdimov.com/cpp2/simple_cxx11_metaprogramming_2.html
>>>>>
>>>>> ?
>>>>>
>>>>>
>>>> Nope.  Thanks *very much* for the link.  I'm impressed (especially
>>>> with the way you actually cited the parts of the standard to guide
>>>> your search for the best method!).
>>>>
>>>>
>>>> Search for mp_at.
>>>>>
>>>>> Thanks for that tip.
>>>>>
>>>>
>>>> I'm a bit surprised that the mp_map_from_list was fastest.
>>>> I would have thought that large template classes mean slow
>>>> compile times, but I guess not.
>>>>
>>>>
>>> Since you seem to be interested on benchmarking compilation times, check
>> out http://metaben.ch.
>>
>> The at benchmark there indicates mpl.vector is the fastest
> in the, I guess you'd call it, the "performance at given
> number_of_elements pop-up list", when the cursor is moved
> over to the rhs at number_of_elements=500.  Hmmm. Now I see
> there's actually no mpl.vector graph at that
> number_of_elements. OOPS.  I see that that's because
> mpl.vector was not run for number_of_elements > 50, but
> that's only obvious when the subtract_baseline radio button
> is turned-off.  To avoid this confusion, the graph should
> give some indication, in the "performance at given
> number_of_elements pop-up list", which methods were actually
> run at the given number_of_elements.


This is actually a known feature of NVD3, which is the tool we use to plot
data, see: https://github.com/ldionne/metabench/issues/158

I agree it is not very intuitive the way it is, but it is not obvious how
to fix it without hacking NVD3. I appreciate thoughts on that.


> This:
>>>
>>>   http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4235.htm
>>>
>>> claims:
>>>
>>>   template instantiations use memory that is never freed during the
>>>   compilation process
>>>
>>> so, maybe mp_map_from_list should be used with caution.  If many
>>> mp_map_from_list instantiations are used, I'm guessing the compiler
>>> might become pressed for memory. Maybe a benchmark showing
>>> compile time vs number of instantiations would show this.
>>> For example, instead of N=800, see what happens when 2
>>> instantiations with N=400 happen, and compare with a similar
>>> test for mp_repeat_c.
>>>
>>
>>
>> This is actually not the case, in fact the exact opposite is true.
>>
>
> So n4235.htm was wrong or maybe I've misinterpreted it?


>
> It turns
>> out mp_map_from_list is actually very cheap to the compiler in terms of
>> memory allocation, because it takes advantage of template memoization, so
>> if you retrieve every single element of a list using this trick, the
>> compiler needs to instantiate it only once. On the other hand, the trick
>> employing void pointers can't be expressed in a way that take advantage of
>> memoization, which means that, for every element retrieved from the list,
>> the entire pack of void pointers must be instantiated again.
>>
>
> So how do you resolve what n4235 is saying and what you say above?
>
> I'm guessing that 4235 was actually referring to this
> memoization when it said:
>
>   template instantiations use memory that is never freed
>
> The memoizations do use memory which, IIUC, is never freed
> until the compiler is finished.  OTOH, when you say:
>
> > for every element retrieved from the list, the entire pack
> > of void pointers must be instantiated again.
>
> That means more compile time is needed for the repeated
> instantiations; however, no memory is *permanently* used as
> is the case for memoization.  IOW, this is a classic case of
> trading memory for speed:
>
>   https://en.wikipedia.org/wiki/Space%E2%80%93time_tradeoff
>
> OTOH, my point was that as these memoization's increase, the
> compiler has less memory to use; hence, might slow down;
> whereas, since, the memory used by the vec_of_void* method
> is reused, memory pressure is less, and, although it's
> slower for 1 instance of a pack, it might become faster as
> many packs are used.
> <http://lists.boost.org/mailman/listinfo.cgi/boost>
>


I believe you've misinterpreted n4235 and/or what I was trying to say.

Memoization is not something the programmer can tell the compiler to do or
not, compilers just do it, because that is what they are made for:
instantiate templates and record information about them so that they can be
used elsewhere in the program where they happen to be visible, so it is
true that memory is never freed once a template is instantiated, because in
general it must not.

Now let us take a look at the problem at hand from this point of view.
Using the type-map idea, for a given list of N elements, the compiler
instantiates the *same* type-map of N key-value pairs whenever any element
from this list is retrieved. Since information about this type is memoized,
the compiler doesn't need to repeatedly instantiate it, it can simply look
it up. This means a single extra template instantiation is needed to
retrieve all N elements of a list. 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. Also remember that a
bunch of intermediary instantiations are required in order to generate a
pack of void pointers, even if we use the logarithmic trick, so we end up
forcing the compiler to store a bunch of useless information about all
these dummy types. That is what compromises compilation times when using
the void pointer trick.

Bruno

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
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.


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
On Mar 3, 2017 17:58, "Peter Dimov via Boost" <[hidden email]> 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.


Right, the trick is usually to figure out what consumes less memory, i.e.
what leads to the least amount of distinct template instantiations. Alias
templates help a lot with that, since they are not actually instantiated,
but there is only so much one can do with alias templates alone.

Bruno

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Loading...