Re: c++ function templates and memory hogging

[me22 <me22 dot ca at gmail dot com>]

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