Jump to content

  • Log In with Google      Sign In   
  • Create Account


How's your template metaprogramming ninja skills?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
17 replies to this topic

#1 Cornstalks   Crossbones+   -  Reputation: 6966

Like
1Likes
Like

Posted 11 January 2013 - 12:30 AM

I've never done too much template metaprogramming. Just a little here and there. Today, my professor talked about it briefly and I thought I'd try and do something cool. Here's my attempt at something cool.
 
It's a Fibonacci number generator. The "cool" part is that it has support for big integers, and it converts big integers to strings (char arrays, really) at compile time.
 
// I'm too lazy to comment this really well.
// If you're compiling with g++ and you hit the template instantiation limit, you
// can use -ftemplate-depth-NN to increase the maximum
// Written by Michael Bradshaw
// Some indentation my be messed up in this code paste...
 
#include <iostream>
 
// Various math functions
template <unsigned int b, unsigned int i>
struct log
{
    enum { value = !!(i / b) + log<b, i / b>::value };
};
 
template <unsigned int b>
struct log<b, 0>
{
    enum { value = 0 };
};
 
template <unsigned int i>
struct log2
{
    enum { value = log<2, i>::value };
};
 
template <unsigned int i>
struct log10
{
    enum { value = log<10, i>::value };
};
 
template <unsigned int b, unsigned int e>
struct pow
{
    enum { value = b * pow<b, e - 1>::value };
};
 
template <unsigned int b>
struct pow<b, 0>
{
    enum { value = 1 };
};
 
// I would use numeric_limits, but it's max() function isn't a constant
// expresion (in C++03)
template <typename T>
struct limits
{
    enum { max = (T)(-1) };
};
 
// Conditional epxressions
template <bool expression, typename if_true, typename if_false>
struct if_then_else
{
    typedef if_true result;
};
 
template <typename if_true, typename if_false>
struct if_then_else<false, if_true, if_false>
{
    typedef if_false result;
};
 
// A big integer struct... really it's just a linked list, but it has special rules about
// keeping each element's values within the specified base (and carrying over when needed)
template <unsigned int v, typename next_big_uint>
struct big_uint
{
    enum { base = pow<10, log10<limits<unsigned int>::max>::value / 2>::value,
  value = v % base };
 
    typedef typename if_then_else<v < base,
     next_big_uint,
     typename big_uint<next_big_uint::value + v / base,
typename next_big_uint::next>::canonical>::result next;
    typedef big_uint<v % base, typename next::canonical> canonical;
};
 
// End of the linked list
template <unsigned int v>
struct big_uint<v, void>
{
    enum { base = pow<10, log10<limits<unsigned int>::max>::value / 2>::value,
  value = v % base };
    typedef typename if_then_else<v < base,
    void,
    typename big_uint<v / base,
     void>::canonical>::result next;
    typedef big_uint<v % base, next> canonical;
};
 
 
// Having a zero case lets some canonicalization be done
template <>
struct big_uint<0, void>
{
    enum { base = pow<10, log10<limits<unsigned int>::max>::value / 2>::value,
  value = 0 };
    typedef void next;
    typedef big_uint<0, void> canonical;
};
 
// Logic for adding two big integers
template <typename a, typename b>
struct add
{
    typedef typename big_uint<a::value + b::value,
 typename add<typename a::next,
      typename b::next>::result>::canonical result;
};
 
template <unsigned int av, typename b>
struct add<big_uint<av, void>, b>
{
    typedef typename big_uint<av + b::value, typename b::next>::canonical result;
};
 
template <typename a, unsigned int bv>
struct add<a, big_uint<bv, void> >
{
    typedef typename big_uint<a::value + bv, typename a::next>::canonical result;
};
 
template <unsigned int av, unsigned int bv>
struct add<big_uint<av, void>, big_uint<bv, void> >
{
    typedef typename big_uint<av + bv, void>::canonical result;
};
 
// Fibonacci implementation detail... just keeps the public interface pretty 
template <unsigned int i, typename a, typename b>
struct detail_fib
{
    typedef typename detail_fib<i - 1, b, typename add<a, b>::result>::result result;
};
 
template <typename a, typename b>
struct detail_fib<0, a, b>
{
    typedef typename add<a, b>::result result;
};
 
// Pretty public interface for the Fibonacci sequence; given the parameter i, it
// calculates the ith number in the Fibonacci sequence
template <unsigned int i>
struct fibonacci
{
    typedef typename detail_fib<i - 2, big_uint<0, void>, big_uint<1, void> >::result result;
};
 
template <>
struct fibonacci<0>
{
    typedef big_uint<0, void> result;
};
 
template <>
struct fibonacci<1>
{
    typedef big_uint<1, void> result;
};
 
// Some math functions for taking the log10 of a big integer
template <typename v>
struct big_log10
{
    enum { value = log10<v::base>::value + big_log10<typename v::next>::value };
};
 
template <unsigned int v>
struct big_log10<big_uint<v, void> >
{
    enum { value = log10<v>::value };
};
 
// Got this idea from http://stackoverflow.com/a/3499919/1287251
// Modified it a bit; compile time strings! Yay!
template <typename v, unsigned int n = big_log10<v>::value + 1, unsigned int i = 0>
struct cstring : public cstring<v, n, i + 1>
{
    static const char dummy;
};
 
template <typename v, unsigned int n>
struct cstring<v, n, n>
{
    static const char dummy;
    static char str[n + 1];
};
 
template <typename v, unsigned int n>
const char cstring<v, n, n>::dummy =  0 * cstring<v, n, 0>::dummy;
 
template <typename v, unsigned int n>
char cstring<v, n, n>::str[n + 1] = {cstring<v, n, n>::dummy}; // fill str with all zeros
 
// Used to actually populate the string; given a big integer v and a string index i,
// it computes the corresponding character for the reversed string (the logic is
// easier if you reverse the string)
template <typename v, unsigned int i, bool use_this = i < log10<v::base>::value>
struct to_string_detail
{
    enum { value = '0' + (v::value / pow<10, i>::value) % 10 };
};
 
template <typename v, unsigned int i>
struct to_string_detail<v, i, false>
{
    enum { value = to_string_detail<typename v::next, i - log10<v::base>::value>::value };
};
 
// Use to_string_detail to extract characters and actually populate the string
template <typename v, unsigned int n, unsigned int i>
const char cstring<v, n, i>::dummy = cstring<v, n, n>::str[i] = to_string_detail<v, n - 1 - i>::value + 0 * cstring<v, n, i + 1>::dummy;
 
// Same as cstring<n>, really, but just a different name to convey meaning
template <typename n>
struct to_string : public cstring<n> 
{
};
 
 
int main()
{
    std::cout << "Fibonacci number generate (at compile time!)\n"
     << "F_N indicates the Nth Fibonacci number" << std::endl;
    std::cout << "F_0:\t" << to_string<fibonacci<0>::result>::str << std::endl;
    std::cout << "F_50:\t" << to_string<fibonacci<50>::result>::str << std::endl;
    std::cout << "F_100:\t" << to_string<fibonacci<100>::result>::str << std::endl;
    std::cout << "F_150:\t" << to_string<fibonacci<150>::result>::str << std::endl;
    std::cout << "F_200:\t" << to_string<fibonacci<200>::result>::str << std::endl;
    std::cout << "F_250:\t" << to_string<fibonacci<250>::result>::str << std::endl;
    std::cout << "F_300:\t" << to_string<fibonacci<300>::result>::str << std::endl;
    std::cout << "F_350:\t" << to_string<fibonacci<330>::result>::str << std::endl;
    std::cout << "F_400:\t" << to_string<fibonacci<400>::result>::str << std::endl;
}
 
Anyone else have any cool template metaprogramming demos?
 
Edit: Here's some output for those of you too lazy to compile this sucker wink.png:
 
Fibonacci number generate (at compile time!)
F_N indicates the Nth Fibonacci number
F_0: 0
F_50: 12586269025
F_100: 354224848179261915075
F_150: 9969216677189303386214405760200
F_200: 280571172992510140037611932413038677189525
F_250: 7896325826131730509282738943634332893686268675876375
F_300: 222232244629420445529739893461909967206666939096499764990979600
F_350: 413462646668428032346940119724892718502248750418536685577487386752440
F_400: 176023680645013966468226945392411250770384383304492191886725992896575345044216019675

Edited by Cornstalks, 23 October 2013 - 12:26 PM.

[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

Sponsor:

#2 Hodgman   Moderators   -  Reputation: 27590

Like
0Likes
Like

Posted 11 January 2013 - 12:46 AM

I haven't found much use for complex math like the fibonacci sequence wink.png

I think the only similar thing in my engine is a template to find the nearest power of 2 that's equal or smaller to the input (and another for equal or greater):

template<int V, int I> struct Pow2Down_Try;
template<bool B, int V, int I> struct Pow2Down_Select
{
	const static int value = I-1;//bust, use prev I
};
template<int V, int I> struct Pow2Down_Select<false,V,I>
{
	const static int value = Pow2Down_Try<V, I+1>::value;//valid, try next I
};
template<int V, int I> struct Pow2Down_Try
{
	const static int value = Pow2Down_Select< (1<<I > V), V, I >::value;//see if we've bust or not
};
template<int V> struct Pow2Down
{
	const static int value = Pow2Down_Try<V,1>::value;//start at 2^1 and increment the exponent until over V, then back up to previous (good) value
};


There's usually some funky C++ voodoo going on in binding systems, e.g. InfoFromSig tells me the return type and argument types of member function, and LuaTypeMapping tells me if a type should be bound to lua as an integer (or enum), float, object, or not bound (void):

template<class F> struct InfoFromSig;
template<class R, class T>                            struct InfoFromSig<R(T::*)(void )> { typedef ArgStore<R,Nil,Nil,Nil> Storage; typedef R Return; };
template<class R, class T, class A>                   struct InfoFromSig<R(T::*)(A    )> { typedef ArgStore<R,  A,Nil,Nil> Storage; typedef R Return; typedef A A; };
template<class R, class T, class A, class B>          struct InfoFromSig<R(T::*)(A,B  )> { typedef ArgStore<R,  A,  B,Nil> Storage; typedef R Return; typedef A A; typedef B B; };
template<class R, class T, class A, class B, class C> struct InfoFromSig<R(T::*)(A,B,C)> { typedef ArgStore<R,  A,  B,  C> Storage; typedef R Return; typedef A A; typedef B B; typedef C C; };

namespace LuaMapping
{
	enum Type
	{
		Object = 0,
		Integer,
		Number,
		Void,
	};
	struct ObjectTag  { char c; };
	struct IntegerTag { char c[2]; };
	struct NumberTag  { char c[3]; };
	eiSTATIC_ASSERT(Object  == (Type)(sizeof( ObjectTag)-1));
	eiSTATIC_ASSERT(Integer == (Type)(sizeof(IntegerTag)-1));
	eiSTATIC_ASSERT(Number  == (Type)(sizeof( NumberTag)-1));
	ObjectTag  Check(...);
	IntegerTag Check(s32);
	IntegerTag Check(u32);
	NumberTag  Check(float);
	NumberTag  Check(double);
	NumberTag  Check(u64);
	NumberTag  Check(s64);
}
template<class T> struct LuaTypeMapping
{
	const static LuaMapping::Type value = (LuaMapping::Type)(sizeof(LuaMapping::Check(*(T*)0))-1);
};
template<> struct LuaTypeMapping<void>
{
	const static LuaMapping::Type value = LuaMapping::Void;
};


#3 Álvaro   Crossbones+   -  Reputation: 11865

Like
0Likes
Like

Posted 11 January 2013 - 02:22 AM

I have to object to a definition of logarithm that says that the logarithm of 0 is 0. You should define the logarithm of 1 as 0, simplify your formula (no need for the funky `!!') and let the compiler complain if someone tries to evaluate the logarithm of 0.



#4 Ravyne   Crossbones+   -  Reputation: 6765

Like
0Likes
Like

Posted 11 January 2013 - 04:53 AM

I don't have it on me, but as an exercise I wrote a template meta-program which generated code to do arbitrary RGB/RGBA pixel format conversions, and it did so by taking in a type_traits structure for the source and destination format. This meant that I could add new formats just by defining the appropriate structure to describe it. It also maintained properly-scaled integers on up-conversions, and the compiler's constant-folding and other optimizations resulted in really tight assembly when I looked at it.



#5 Cornstalks   Crossbones+   -  Reputation: 6966

Like
0Likes
Like

Posted 11 January 2013 - 08:43 AM

I have to object to a definition of logarithm that says that the logarithm of 0 is 0. You should define the logarithm of 1 as 0, simplify your formula (no need for the funky `!!') and let the compiler complain if someone tries to evaluate the logarithm of 0.

I did that to keep things really simple. How's the following?

 // b = base, n = number, r = recursion depth level
template <unsigned int b, unsigned int n, unsigned int r = 0, bool recurse = n >= b, bool valid = (n > 0) && (b > 1)>
struct log;
 
template <unsigned int b, unsigned int n, unsigned int r, bool recurse>
struct log<b, n, r, recurse, true>
{
    enum { value = log<b, n / b, r + 1>::value };
};
 
template <unsigned int b, unsigned int n, unsigned int r>
struct log<b, n, r, false, true>
{
    enum { value = r };
};
 
I'm not sure how much I like the above. Is there a better way to do it?

Edited by Cornstalks, 11 January 2013 - 08:44 AM.

[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#6 Álvaro   Crossbones+   -  Reputation: 11865

Like
0Likes
Like

Posted 11 January 2013 - 09:52 AM

How's this?
 
 
template <unsigned int b, unsigned int n>
struct log
{
  enum { value = log<b, n / b>::value + 1 };
};

template <unsigned int b>
struct log<b, 1>
{
  enum { value = 0 };
};

Edited by Álvaro, 11 January 2013 - 09:52 AM.


#7 Cornstalks   Crossbones+   -  Reputation: 6966

Like
0Likes
Like

Posted 11 January 2013 - 09:59 AM

How's this?
 
*snip*
Try log<10, 2>::value, or log<10, 20>::value, etc.

Edited by Cornstalks, 11 January 2013 - 10:06 AM.

[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#8 Álvaro   Crossbones+   -  Reputation: 11865

Like
0Likes
Like

Posted 11 January 2013 - 11:39 AM


How's this?
 
*snip*

Try log<10, 2>::value, or log<10, 20>::value, etc.
 


Hmmm... Good point. I'll give it some more thought. In the meantime, I believe this works (but it still does something funky with log(0), so I don't love it):
 
template <unsigned int b, unsigned int n>
struct log
{
  enum { value = log<b, n / b>::value + 1 };
};
 
template <unsigned int b>
struct log<b, 0>
{
  enum { value = -1 };
};


#9 ApochPiQ   Moderators   -  Reputation: 14277

Like
0Likes
Like

Posted 11 January 2013 - 12:51 PM

I do a little metaninja stuff every now and then. I think the only one I really thought was worth explaining lives here.

#10 Álvaro   Crossbones+   -  Reputation: 11865

Like
0Likes
Like

Posted 11 January 2013 - 01:09 PM

I once tested my metaninja skills by challenging myself to write a C++ program that would solve the game of tic-tac-toe at compile time, but I failed. sad.png I tried for about 3 hours before I decided it wasn't worth my time and I would rather do things at runtime than writing code that is really hard to understand.

However, I am still curious of what a solution might look like. Any takers?

#11 frob   Moderators   -  Reputation: 18837

Like
0Likes
Like

Posted 11 January 2013 - 01:30 PM

Anyone else have any cool template metaprogramming demos?

 

Template metaprogramming is cool when it works...

 

... The problem is when it doesn't compile out.

 

... Or when someone has to maintain it.

 

... Or when the code must be supported on multiple compilers.

 

If the compiler isn't able to discover and take the optimization it will just embed the function calls.  These are often deeply-recursive.  They also often use algorithms that perform poorly relative to other implementations.

 

 

 

They're great if you're computing a Fibonacci or logarithm of a known constant at compile time.  But seriously, how often is that?  Even if I did need a logarithm, I'd need to compute it on variables rather than constants.  

 

 

In code reviews, I am one of many people who routinely reject TMP solutions.  Yes they are cool when they work, but they are far too fragile for general case development.


Check out my personal indie blog at bryanwagstaff.com.

#12 ApochPiQ   Moderators   -  Reputation: 14277

Like
0Likes
Like

Posted 11 January 2013 - 01:33 PM

TMP is certainly a tool best applied sparingly. I don't think I've checked in more than a handful of templates in my entire time at my current job, for example.

Even the Epoch compiler is relatively light on template metamagic. I use it in a couple places to decouple things and promote some nifty code reuse tricks, but I try to stay away from it... usage of boost::spirit notwithstanding :-D

#13 synulation   Members   -  Reputation: 271

Like
1Likes
Like

Posted 12 January 2013 - 02:16 PM

I spent some time on a tmp raytracer a while back:  https://github.com/lentinic/TemplateTrace

Fun project for bending the mind a bit.



#14 Cornstalks   Crossbones+   -  Reputation: 6966

Like
0Likes
Like

Posted 12 January 2013 - 06:03 PM

Pretty cool stuff, people!

 

As for why my professor was talking about template metaprogramming (and why I'm experimenting with it): some researchers want to write C++ code to run on some super computers, and they're looking into using template metaprogramming to allow them to still write C++ code, but then transform that code at compile time to target the desired super computer (with its millions of CPUs and GPUs). I was just curious of other uses of TMP, even if they're just fun demos and not really useful.


[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#15 Álvaro   Crossbones+   -  Reputation: 11865

Like
0Likes
Like

Posted 12 January 2013 - 06:20 PM

We had a situation at work about 4 years ago, where a coworker and I wanter to reimplement an old piece of code using signals and slots. I wanted to explicitly plug all the signals to the slots at runtime, but my coworker wanted to do it at compile time using some heavy TMP techniques. Unfortunately our boss agreed to do it the "modern way" (his words, not mine) and we now have a large piece of important code that only a couple of people understand, in a company with dozens of programmers.

My advice: Stay away from TMP. It might be cool, but you should optimize your code for readability, not coolness.

#16 Hodgman   Moderators   -  Reputation: 27590

Like
0Likes
Like

Posted 12 January 2013 - 07:46 PM

As for why my professor was talking about template metaprogramming (and why I'm experimenting with it): some researchers want to write C++ code to run on some super computers, and they're looking into using template metaprogramming to allow them to still write C++ code, but then transform that code at compile time to target the desired super computer (with its millions of CPUs and GPUs). I was just curious of other uses of TMP, even if they're just fun demos and not really useful.
Interesting, I did a similar thing on the Wii biggrin.png
The Wii doesn't support HLSL for pixel shaders like the 360/etc do, which makes it a real pain to work with. So, I wanted to write my own shader language for it. I didn't really have time to implement a whole language, but I was on a TMP-kick at the time, so I instead hijacked C++ as my shader language! I wrote a TMP library which converted HLSL-looking C++ code into the necessary structures to perform pixel operations on the Wii's GPU.
e.g.
PixelShader shader;
{
 TexCoord<0> uv;
 Texture<0> diffuseMap;
 Register<0> output;
 Uniform<0> multiplier;
 
 output = diffuseMap(uv);
 output.rgb *= multiplier.rgb;
} return shader;
The same problem that others have expressed applies though -- I was the only one that understood the TMP code, and now, years later, the workings of it are even foreign to me.

Edited by Hodgman, 12 January 2013 - 08:01 PM.


#17 L. Spiro   Crossbones+   -  Reputation: 12223

Like
1Likes
Like

Posted 14 January 2013 - 12:16 AM

The only useful/practical use I have ever had for this type of template metaprogramming was to calculate the size of a quad-tree at compile-time depending on how many levels I want there to be.

For 8 levels you would have 21,845 cells and it is best to keep them in 1 contiguous memory block made via 1 allocation. Not only does this improve cache performance but it allows for instant insertion into any cell in the tree. I plan to explain this method for creating a quad-tree in an upcoming tutorial as it is extremely efficient.

I don’t need to post code for such a simple thing but this is an example of a real-world situation where these tricks that allow compile-time Fibonacci sequences can be usefully employed.


L. Spiro

Edited by L. Spiro, 14 January 2013 - 12:17 AM.

It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

#18 MJP   Moderators   -  Reputation: 10226

Like
0Likes
Like

Posted 14 January 2013 - 12:26 AM

The only thing I've written that made really heavy use of template shenanigans was for a home project where I wrote a really flexible mesh baking system for baking out various forms of lighting and AO so that I could test them out. I would never check in anything like that at work, since it's a nightmare for other people to understand and maintain. I have no problem with typing out a little more code if it's easier to understand and/or less bug-prone.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS