c++ function templates and memory hogging

c++ function templates and memory hogging

[Guido Loupias]

Hi,

Why does the following behavior occur?

I have 2 naive implementations of fibonacci through function templates.
The first one has no problem compiling fib<46>(). However the second one starts 
eating significant memory when N > 23. It's gradual (seems to be exponential 
with regard to N) but when N = 27 the compilation process consumes about a gigabyte.

This happens when compiling with -O1 or higher.

(1)
template<int N>
inline int fib() {
     static const int n = fib<N-1>() + fib<N-2>();
     return n;
}
template<>
inline int fib<0>() {
     return 0;
}
template<>
inline int fib<1>() {
     return 1;
}

(2)
template<int N>
inline int fib() {
     return fib<N-1>() + fib<N-2>();
}
template<>
inline int fib<0>() {
     return 0;
}
template<>
inline int fib<1>() {
     return 1;
}

Regards,
Guido

Re: c++ function templates and memory hogging

[Mojmir Svoboda]

* Guido Loupias <guidoloupias@gmail.com> [2008-12-10 19:51:33 +0100]:

> Why does the following behavior occur?
>
> I have 2 naive implementations of fibonacci through function templates.
> The first one has no problem compiling fib<46>(). However the second one 
> starts eating significant memory when N > 23. It's gradual (seems to be 
> exponential with regard to N) but when N = 27 the compilation process 
> consumes about a gigabyte.

i do not attempt to answer your problem, but i thought traditional way to do
compile-time computation was like:

template<int N>
struct fib {
    static int const n = fib<N-1>::n + fib<N-2>::n;
};
template<>
struct fib<0> {
    static int const n = 0;
};
template<>
struct fib<1> {
    static int const n = 1;
};

(or using enums) which behaves much better for me. local gurus will probably 
explain best why..

best regards,
mojmir

Re: c++ function templates and memory hogging

[Guido Loupias]

Mojmir Svoboda schreef:
> i do not attempt to answer your problem, but i thought traditional way to do
> compile-time computation was like:
> 
> template<int N>
> struct fib {
>     static int const n = fib<N-1>::n + fib<N-2>::n;
> };
> template<>
> struct fib<0> {
>     static int const n = 0;
> };
> template<>
> struct fib<1> {
>     static int const n = 1;
> };
> 
> (or using enums) which behaves much better for me. local gurus will probably 
> explain best why..
> 
> best regards,
> mojmir

You're right. Judging from the resulting object file it's much cleaner and it 
also works for large values of N. Still I wonder why the second function 
template version of the algorithm in my previous e-mail behaves the way it does. 
Perhaps it's doing computation on 2^N integers?

Regards,
Guido

Re: c++ function templates and memory hogging

[me22]

On Wed, Dec 10, 2008 at 15:53, Guido Loupias <guidoloupias@gmail.com> wrote:
> Mojmir Svoboda schreef:
>>
>> i do not attempt to answer your problem, but i thought traditional way to
>> do
>> compile-time computation was like:
>>
>> template<int N>
>> struct fib {
>>    static int const n = fib<N-1>::n + fib<N-2>::n;
>> };
>> template<>
>> struct fib<0> {
>>    static int const n = 0;
>> };
>> template<>
>> struct fib<1> {
>>    static int const n = 1;
>> };
>>
>> (or using enums) which behaves much better for me. local gurus will
>> probably explain best why..
>>
>> best regards,
>> mojmir
>
> You're right. Judging from the resulting object file it's much cleaner and
> it also works for large values of N. Still I wonder why the second function
> template version of the algorithm in my previous e-mail behaves the way it
> does. Perhaps it's doing computation on 2^N integers?
>

I don't know how function-scope statics are handled, but if they were
initialized separately from running them (somehow), then each function
would only ever be "return a static" in the first case, but in the
second it would likely inline all the function calls, resulting in an
addition with O(fib(n)) terms.  If the static is done inside the
function, then the inliner might just be refusing to inline it after a
certain point, as the function would be getting large quickly.

Regardless, Mojmir Svoboda's is certainly a better approach.  The
reason being that the results of the computation are also memoised,
rather than just the declarations, as they're static constants inside
the type, so there's no "call graph" built at all, which is the part
with O(fib(n)) behaviour.

HTH,
~ Scott