Back to General and Gameplay Programming

How's your template metaprogramming ninja skills?

Cornstalks · 2013-01-14T06:26:38

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 : 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

General and Gameplay Programming Programming

Started by Cornstalks January 11, 2013 06:30 AM

16 comments, last by MJP 11 years, 3 months ago

frob

46,219

January 11, 2013 07:30 PM

[quote name='Cornstalks' timestamp='1357885855' post='5020199']

Anyone else have any cool template metaprogramming demos?

[/quote]

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.

ApochPiQ

23,138

January 11, 2013 07: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

Wielder of the Sacred Wands
[Work - ArenaNet] [Epoch Language] [Scribblings]

synulation

271

January 12, 2013 08: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.

Cornstalks

7,033

Author

January 13, 2013 12:03 AM

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.

[size=2][ 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 ]

alvaro

21,604

January 13, 2013 12:20 AM

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.

Hodgman

52,717

January 13, 2013 01:46 AM

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

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.

. 22 Racing Series .

L. Spiro

25,818

January 14, 2013 06: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

I restore Nintendo 64 video-game OST’s into HD! https://www.youtube.com/channel/UCCtX_wedtZ5BoyQBXEhnVZw/playlists?view=1&sort=lad&flow=grid

MJP

20,295

January 14, 2013 06: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.

The Blog | The Book

How's your template metaprogramming ninja skills?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

How's your template metaprogramming ninja skills?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines