Preface
Recently, since I used some template tricks such as SFINAE in a project, I suddenly became very interested in this kind of “dragon-slaying technique.” In other words, if you have a chance to use functional-style techniques in a normal C++ project, it is hard to resist trying something more complicated. So after reading a guru's Brainfuck Compile Time Evaluator, I decided to write a few simple toys myself—like solving some classic recursive problems. Let's start with the Tower of Hanoi.
Basic Implementation
I will not repeat the normal recursive implementation here. To convert it into templates, we first define a structure to store the target result as follows:
:::C++
template <typename T, T a, T b>
struct pair {
static constexpr auto first = a;
static constexpr auto second = b;
};
Next, we define a sequence used to store results:
:::C++
template <typename... Args>
struct sequence {};
Then define a method to concatenate two sequences to produce a new sequence:
:::C++
template <typename... Args1, typename... Args2>
struct concat<sequence<Args1...>, sequence<Args2...>> {
using type = sequence<Args1..., Args2...>;
};
With basic sequence storage and concatenation, we can define the recursive solution for the Tower of Hanoi, as shown below:
:::C++
template <int, typename T, T a, T b, T c>
struct hanoi;
template <typename T, T a, T b, T c>
struct hanoi<1, T, a, b, c> {
using type = sequence<pair<T, a, c>>;
};
template <int n, typename T, T a, T b, T c>
struct hanoi {
using type = typename concat<
typename concat<typename hanoi<n - 1, T, a, c, b>::type,
sequence<pair<T, a, c>>
>::type,
typename hanoi<n - 1, T, b, a, c>::type
>::type;
};
Here we actually declare the template interface first, then define two instantiations: the normal recursive version, and the partial specialization for the recursion termination. This way the compiler can solve the problem correctly.
The last issue is how to output our results. Here we also use recursion to unpack the parameter pack:
:::C++
// here we use T for type "sequence<>"
template <typename T>
void print(T) {}
template <typename T, typename... Args>
void print(sequence<T, Args...>) {
std::cout << T::first << "->" << T::second << std::endl;
print(sequence<Args...>());
}
int main(int, const char*[]) {
print(typename hanoi<3, char, 'A', 'B', 'C'>::type());
}
Note that in the above Hanoi implementation, we only need to ensure that the template parameters a, b, c have the same type, and that this type overloads the stream output operator. This looks like a pretty good generic abstraction. The full code is here.
The compile command is: g++ hanoi.cpp -std=c++14 -O2 -o hanoi.
Optimization I
Clang has a limit on the maximum recursion depth of C++ template instantiation, so by default the number of Hanoi levels can be set to at most 8, producing 255 move operations. And after compiling the program this way, we find the binary size reaches an astonishing 216KB (Clang 8.0, macOS 10.12). However, for this kind of static compile-time derivation, ideally the size should be comparable to a program generated by directly “table-lookup” output, i.e., proportional to the length of the output. If we only encode the output, it should not be this large. Taking a look with objdump, we find 255 print functions with different parameter types. Because each function's symbol name contains the full type name sequence<...>, and because its length gradually becomes shorter as the parameter pack expands, these extremely long symbol names take up a lot of space—more precisely, the space complexity is polynomial. So I decisively used strip to remove these useless symbols and checked the size again; it shrank to 80KB. But the issue is that although the long symbol names are gone, the hundreds of generated function bodies are still there, so the space usage is still substantial.
Optimization II
Next, we try to optimize at the code level. Since recursively expanding the parameter pack causes overly long type names, we can consider another approach: what if we directly derive all results into a static string at compile time, and then print it all at once? Here we use std::integer_sequence to solve this. First define a method to prepend elements to a sequence:
:::C++
template <typename seq, typename seq::value_type...>
struct prepend;
template <typename T, T... x1, T... x2>
struct prepend<std::integer_sequence<T, x1...>, x2...> {
using type = std::integer_sequence<T, x2..., x1...>;
};
Then we can define a method to format the previous sequence into std::integer_sequence:
:::C++
template <typename T>
struct seq2str {};
template <typename T>
struct seq2str<sequence<T>> {
using type = std::integer_sequence<typename T::type,
T::first, '-', '>', T::second, '\n'>;
};
template <typename T, typename... Args>
struct seq2str<sequence<T, Args...>> {
using type = typename prepend<
typename seq2str<sequence<Args...>>::type,
T::first, '-', '>', T::second, '\n'
>::type;
};
Finally, we just need to print our std::integer_sequence:
:::C++
template <typename T, T... xs>
void print_seq(std::integer_sequence<T, xs...>) {
bool Do[] = { (std::cout << xs, true)... };
(void)Do;
}
int main(int, const char*[]) {
print_seq(typename seq2str<
typename hanoi<8, char, 'A', 'B', 'C'>
::type
>::type ());
}
The program compiled this way is only 48KB, a clear improvement. The complete code is here.
Optimization III
The code above has an obvious issue: it loses the generic abstraction. If we replace hanoi<3, char, 'A', 'B', 'C'> with hanoi<3, int, 1, 2, 3>, we will find the output becomes completely wrong: the formatting arrow and so on are also printed as type int. Also, if we inspect the generated binary, we will find it generates a print_seq function with a very long parameter type and a rather complex function body, which calls std::cout many times. More precisely, the length of the function symbol name and the number of cout calls are on the same order as the number of characters in the result string. So even though the program size is already proportional to the output length, there is still room for further optimization.
Looking again at our definition of pair, we find that it is enough to add a static print() method here:
:::C++
template <typename T, T a, T b>
struct pair {
static constexpr auto first = a;
static constexpr auto second = b;
static void print() { std::cout << first << "->" << second << std::endl; }
};
Then when printing output, there is no need to convert it into a static string in such a complicated way; we can directly expand the type pack and call its print() method:
:::C++
template <typename... Args>
void print_seq(sequence<Args...>) {
bool Do[] = { (Args::print(), true)... };
(void)Do;
}
int main(int, const char*[]) {
print_seq(typename hanoi<8, char, 'A', 'B', 'C'>::type());
}
With this, we find that this version does not lose genericity, and the compiled binary size is also well controlled, at only 16KB. The full code is here.
Summary
Why does this final version effectively control the binary size? If we bring out objdump again, we will see that its binary contains only \(A^2_3 = 6\) pair::print() methods. Obviously, during compilation all type permutations that actually appear specialize pair into only these few instances; and in the function print_seq, it contains 255 direct calls to these different pair::print() methods, where each call takes only 5 bytes. Therefore, this version is almost completely equivalent to a table lookup; you could even say it is better than a table lookup, so it is not hard to understand why the binary is so small.
Also, some people might wonder what these template tricks are mainly used for. The answer is... basically useless.