Re: [Boost-users] Meta Template Programming with MPL - Compiler B ug or is the code really so evil slow?

From: Vinzenz 'evilissimo' Feenstra (evilissimo_at_[hidden])
Date: 2006-02-13 10:12:26

Hi James,

I've already attached the code to the post but here it is as quotation:
[SNIP]
#include <boost/mpl/long.hpp>
#include <boost/mpl/range_c.hpp>
#include <boost/mpl/vector_c.hpp>
#include <boost/mpl/arithmetic.hpp>
#include <boost/mpl/accumulate.hpp>
#include <boost/mpl/back_inserter.hpp>
#include <boost/mpl/equal.hpp>
#include <boost/mpl/copy_if.hpp>
#include <boost/mpl/at.hpp>
#include <boost/mpl/size.hpp>
#include <iostream>

namespace mpl = boost::mpl;

template < typename Sum , typename Div , typename Num >
struct perf_num_plus_if :
     mpl::if_<
     mpl::equal_to<
     mpl::modulus< Num,Div > ,
     mpl::long_<0>
     >,
     typename mpl::plus<Sum,Div>::type,
     Sum
     >::type
{};

template< typename Num >
struct perf_num_impl :
     mpl::accumulate<
     mpl::range_c<
     long,
     1,
     Num::value/2+1
     >,
     mpl::long_<0>,
     perf_num_plus_if<
     mpl::_,
     mpl::_,
     Num
     >
     >::type
{};

template< long Start , long End >
struct  perfect_number :
     mpl::copy_if<
     mpl::range_c<long,Start,End>,
     mpl::equal_to< mpl::_1 , perf_num_impl<mpl::_1> >,
     mpl::back_inserter< mpl::vector_c<long> >
     >::type
{};

template< typename Seq , size_t Pos , size_t Max >
struct Output
{
     Output()
     {
         std::cout << mpl::at_c<Seq, Pos >::type::value << std::endl; 

         Output< Seq , Pos+1 , Max >();
     }
};
template< typename Seq , size_t N >
struct Output< Seq , N , N >
{
     Output(){}
};

int main()
{
     typedef perfect_number< 1 ,30 > vec;
     Output< vec , 0 , mpl::size< vec >::value >();
}
[/SNIP]

James Hughes schrieb:
> 
>> -----Original Message-----
>> From: Vinzenz 'evilissimo' Feenstra [mailto:evilissimo_at_[hidden]]
>> Sent: 13 February 2006 12:40
>> To: boost-users_at_[hidden]
>> Subject: [Boost-users] Meta Template Programming with MPL - 
>> Compiler Bug
>> or is the code really so evil slow?
>>
>>
>>
>> Hi,
>>
>> I've written a little Meta Template Program which should 
>> calculate the 
>> first 3 perfect numbers. ( range 1 - 500 )
>>
>> The code is compilable if you use the range 1 - 30 really 
>> fast and works 
>> correctly. But I've tried to compile the code but I can't get 
>> it finished.
>>
>> Someone tried it on a Machine with 40 GB RAM and it now compiles for 
>> more than 12 hours and uses more than 7.1 GB RAM ( the compilation )
>>
>> I've tried it by myself with g++ 3.4.x and g++ 4.0.x and with VC++ 7.1
>>
>> The code works on all tested compilers if the range would be 
>> 1 - 30 but
>>
>> If the range is 1 - 500 VC++ says:
>>
>> d:\boost\vc71\include\boost-1_33_1\boost\mpl\aux_\preprocessed
>> \plain\apply_wrap.hpp(48): 
>> fatal error C1204: compiler limit: internal structure overflow.
>>
>> ( This seems to be a known bug in VC++ 
>> http://support.microsoft.com/default.aspx?scid=kb;en-us;883655 )
>>
>> and g++ compiles and compiles and uses more and more RAM.
>>
>>
>> Is the code really so evil slow or is it a compiler Bug in g++?
>>
>> Maybe anyone has an answer.
>>
>> BR
>> evilissimo
>>
>>
> 
> Without the code its difficult to tell, but this meta programming 
> uses recursive definitions of templates, and with a lot of information 
> required per template per iteration, you are running out of memory, as 
> the error messages indicate. Not a compiler bug I don't expect - you are 
> just asking too much. Templates require quite a bit of memory for a single 
> instance - multiply that by the 500 you are asking for and things rapidly 
> go downhill, which is why 30 works - you haven't hit the point at which you
> run out of memory (and hence require swapping  which is a very slow process
> in
> comparison to memory access). In fact the multiplication factor is probably 
> more than 500, it may go up as exponential or perhaps even factorial
> depending 
> on the code
> 
> James