template recursion depth

[Ingo Nolden]

Hi,

I want to write a template class that holds another class that uses the
same template. This recursion should stop after a predefined number. I
think it's either impossible or easy, but I have no idea right now :-(

A simplified version is here:

template< unsigned Depth >
class Foo
{
public:
list<int> GetList( const char* word )
{
return foo[*word].GetList( word + sizeof( char ) );
}
private:
Foo< Depth - 1 > foo[27];
};

template<>
class Foo<0>
{
public:
list<int> GetList( const char* word )
{
return _list[*word];
}
private:
list<int> _list[27];
};

The compiler runs through, but I get a stack overflow before main( ) is
reached. It is like a multidimensional lookup table and the number of
dimensions should be determined by a template parameter. The compiler
should be able to inline as much as possible, therefore I don't use
inheritance, virtual functions etc.

I think the point is, how can I prevent the compiler to include Foo<-1>
in Foo<0> ? I bet there is a special trick.

thanks for any help

Ingo

 

[Victor Bazarov]

I want to write a template class that holds another class that uses the
same template. This recursion should stop after a predefined number. I
think it's either impossible or easy, but I have no idea right now :-(

A simplified version is here:

template< unsigned Depth >
class Foo
{
public:
list<int> GetList( const char* word )
{
return foo[*word].GetList( word + sizeof( char ) );

'sizeof(char)' is always 1. There is no sense to spell it out. Just
write 1.

}
private:
Foo< Depth - 1 > foo[27];
};

template<>
class Foo<0>
{
public:
list<int> GetList( const char* word )
{
return _list[*word];
}
private:
list<int> _list[27];
};

The compiler runs through, but I get a stack overflow before main( ) is
reached.

How many instantiations are you trying to create? Where is the code
that *uses* your Foo template?

Remember that the size of Foo<N> grows exponentially. The Foo<0> has
27 objects of type 'list<int>'. Even if 'list<int>' is only 4 bytes
long, it's 108 bytes. Foo<1> has 27 Foo<0>'s, that's about 3K. Next

It is like a multidimensional lookup table and the number of dimensions
should be determined by a template parameter. The compiler should be able
to inline as much as possible, therefore I don't use inheritance, virtual
functions etc.

I think the point is, how can I prevent the compiler to include Foo<-1> in
Foo<0> ? I bet there is a special trick.

You already are using that "trick". It's called "specialization".

V

 

[Ingo Nolden]

'sizeof(char)' is always 1. There is no sense to spell it out. Just
write 1.

ok, in the real 'not simplified' code it is sizeof( CharT ) and it may
be parameterized to be something else.
I actually expected if I write 1 someone would tell me that it may be a
problem when switching to a different char type.
But you're right, since I spelled it char and not CharT...

}
private:
Foo< Depth - 1 > foo[27];
};

template<>
class Foo<0>
{
public:
list<int> GetList( const char* word )
{
return _list[*word];
}
private:
list<int> _list[27];
};

The compiler runs through, but I get a stack overflow before main( ) is
reached.

How many instantiations are you trying to create? Where is the code
that *uses* your Foo template?

ok, this is important of course

it was:

WordStore<CharUse, 5> store;

and I didn't think 5 is much

Remember that the size of Foo<N> grows exponentially. The Foo<0> has
27 objects of type 'list<int>'. Even if 'list<int>' is only 4 bytes
long, it's 108 bytes. Foo<1> has 27 Foo<0>'s, that's about 3K. Next
level (Foo<2>) is 78K, next is 2M, next is 55M. Foo<5> is about 1.5G.
Shall I continue or can you do it yourself?

but I had to reduce it to Foo<2> to make it >not crash<. I have to admit
that I am a little ashamed not to have tried Foo<2>.
Also I have to admit that I didn't really use int but a
list<WordCounteryCharT> > where WordCounter is holding an unsigned and a
CharT*

How much memory can I expect an empty list to consume? If it is 40
bytes, Foo<3> should use about 20M. Is that too much for a static
memory? Any if it is, should it cause a stack overflow?

You already are using that "trick". It's called "specialization".

I know I am using specialization. However I didn't expect it to work,
since it seems 'magic' to me and I have not much experience using it
this way.
So, if one could tell me by what rule the compiler did not include the
foo[] for instanciations of Depth = 0, that would take me a good step
forward along the way to understand c++ and meta programming ( it is
meta programming right? )

On the other hand, I would like to have one level more. 20MB is not soo
much memory, I have 1Gb on a WinXP system. Is there a limitation for
static allocetions independant from the hardware and averything else?

And does anybody know, how much memory an empty std::list needs and how
much it uses for any item additionally to the memory for the item
itself? Ok, that may be implementation dependant but any hints are
welcome. I use VC7.1

cheers
Ingo

 

[Victor Bazarov]

[...]
I think the point is, how can I prevent the compiler to include Foo<-1>
in Foo<0> ? I bet there is a special trick.

You already are using that "trick". It's called "specialization".

I know I am using specialization. However I didn't expect it to work,
since it seems 'magic' to me and I have not much experience using it this
way.

No magic. The process of instantiation has to check whether there are
specialisations and if there are, use them instead of generating the
type from the original template.

So, if one could tell me by what rule the compiler did not include the
foo[] for instanciations of Depth = 0, that would take me a good step
forward along the way to understand c++ and meta programming ( it is meta
programming right? )

On the other hand, I would like to have one level more. 20MB is not soo
much memory, I have 1Gb on a WinXP system. Is there a limitation for
static allocetions independant from the hardware and averything else?

If your compiler reports stack overflow during the creation of your
template "chain", it's a limitation of the compiler (the compiler is
just another program with its own memory allocations and algorithms).
You can find more information in a newsgroup dedicated to that compiler.
Try microsoft.public.vc.language.

And does anybody know, how much memory an empty std::list needs

#include <list>
#include <iostream>
int main() {
std::list<int> emptylist;
std::cout << "Empty: " << sizeof emptylist << std::endl;
}

and how much it uses for any item additionally to the memory for the item
itself?

#include <list>
#include <iostream>
int main() {
std::list<int> mylist;
std::cout << "Empty: " << sizeof mylist << std::endl;
mylist.push_back(42);
std::cout << "After one insertion: " << sizeof mylist << std::endl;
}

although I bet you the size of the object doesn't change since all
elements of a list are kept outside of the object itself, and you
will need some other methods to find out how much additional memory
such allocation requires.

Ok, that may be implementation dependant but any hints are welcome. I use
VC7.1

microsoft.public.vc.language

V

 

[Ingo Nolden]

Since you defined what Foo<Depth == 0> should look like, why should the
compiler "include" anything not in your definition of it?

Ok, thats clear. I think I got it now. Indeed its not so magic

If your compiler reports stack overflow during the creation of your
template "chain", it's a limitation of the compiler (the compiler is
just another program with its own memory allocations and algorithms).
You can find more information in a newsgroup dedicated to that compiler.
Try microsoft.public.vc.language.

My compiler never reported anything. This is what I meant by 'compiler
runs through'. It is when I started the program I got stack overflow
before main( ) has been reached. But anyway, you may be right that this
is compiler related.

#include <list>
#include <iostream>
int main() {
std::list<int> emptylist;
std::cout << "Empty: " << sizeof emptylist << std::endl;
}

Thank you for that hint. But that is clear. I expected the list to use
additional dynamic memory outside of what I could measure with sizeof.

#include <list>
#include <iostream>
int main() {
std::list<int> mylist;
std::cout << "Empty: " << sizeof mylist << std::endl;
mylist.push_back(42);
std::cout << "After one insertion: " << sizeof mylist << std::endl;
}

although I bet you the size of the object doesn't change since all
elements of a list are kept outside of the object itself, and you
will need some other methods to find out how much additional memory
such allocation requires.

That's what I mean. I think sizeof is always resolved at compile time.

thank you anyway

Ingo