Hi all,
I was just playing around with some ideas about optimizing a core piece of my library: the run-time type identification system (RTTI). What does that have to do with compile-time string concatenation? Well, the whole point of the RTTI is to provide information on the type of objects, and a string representation of that name is a pretty central part of that (as well as a hash value). Type names are made of identifiers, which are names that are known at compile-time, and could thus be compile-time string literals (that means things like "Hello world!"). The problem is, for complex types, like templates, many compile-time strings need to be assembled or concatenated to form the complete type names. At that point, I had to switch over to run-time code (e.g., using std::string or C-style functions) to form those compound strings. Why? Because there is no way to concatenate strings at compile-time, or so I thought...
What makes this difficult is that normally, when you concatenate strings, you just create a new chunk of memory big enough for the two original strings and then copy the two strings one after the other. Easy right? Well, there are two problems. First, you cannot "create a chunk of memory" at compile-time because there is no concept of memory at this point. Second, you cannot copy data because that would imply changing things, and you cannot change compile-time constants. So, clearly, the traditional method won't work.
Welcome to the world of pure functional programming!
Pure functional programming works on two fundamental principles: there are only values, and values can never change. "Only values" means no variables. You don't assign values to variables, like you do in imperative programming (i.e., the "normal" way), you simply have to keep generating new values that generate others and so on until you get to the final value (or desired result).
Pure functional programming is a big part of C++, because there are two additional programming languages hidden in the C++ language, and they are pure functional languages. The first is very well known to most seasoned C++ programmers, it's called template meta-programming (TMP) and it can be used to compute anything you want at compile-time, but it is mainly used to generate secondary or derived types when doing generic programming. The other language is that of constexpr expressions, a relatively new feature added to the standard in 2011 (C++11). The rules of the game with constexpr is pretty much the same as for TMP, because they are both compile-time meta-programming languages, but const-expressions are made to create compile-time values, as opposed to types (in TMP). Although TMP can be used to compute values (i.e., as static members of types), it's very inefficient to do so because of the overhead in compilation times and code-bloat (e.g., symbols, useless code, etc.), and dealing with string values in TMP is even worse, which is why the lesser-evil solution to my problem (before C++11) was to use run-time string values. But now, it looks like constexpr is the right tool for the job!
However, I could not find any practical, lean-and-mean implementation of string concatenation using constexpr. So, I wrote my own, and here it is. I thought I would post it here, for its educational value. Mind you, this is still just a draft.
(WARNING: If you're not ready for it, reading what follows could blow your mind!)
If you are not familiar with constexpr, here is a quick overview. Const-expressions allow you to write some "normal" functions that will be evaluated at compile-time (by the compiler, as it is parsing the code) if certain conditions are met; specifically, all its inputs must be const-expressions (or compile-time constants) and it cannot have intermediate variables (i.e. local variables). For example, you could have this:
constexpr int add(int a, int b) { return a + b; };
which means that if the inputs a and b happen to be compile-time constants, the compile will evaluate the function (addition) at compile-time to produce a result which is itself a compile-time constant (e.g., could be used as the size value for a static array, or as a template argument). This means that you could write something like this:
std::array<double, add(5, 10)> arr;
because both 5 and 10 are compile-time constants, and therefore, the result of add(5,10) is too.
So, back to the problem at hand, how does one go about putting together two strings if one cannot copy or change anything? Well, even though this sounds like a difficult restriction, it does grant a side benefit: if nothing can change, things are persistent, i.e., they will always be there, unmodified. The reason you want to copy or assign data in general is because the source of that data is not persistent, i.e., it could disappear or change some time in the future. So, we don't need to make a copy if we can rely on the persistence and immutability of the source.
This principle is well explained by this simple class that "stores" a compile-time string:
class literal_str {
const char* const text_ptr;
unsigned int text_size;
public:
template <unsigned int N>
constexpr literal_str(const char(&aStr)[N]) :
text_ptr(aStr), text_size(N-1) {
static_assert(N >= 1, "Invalid string literal! Length is zero!");
};
};
This is what is called a literal class because it fulfills a number of basic requirements, and it has a constructor marked with constexpr, meaning that if its inputs are compile-time constants, then the object created will be itself a compile-time constant (yes, you heard that right, the compiler will create the object at compile-time!).
The point here is that a string literal, such as "Hello world!", is a static array, which is what the constructor of literal_str takes in. Because a string literal is a compile-time constant (managed by the compiler, and usually stored in read-only data section of the final executable, if needed at run-time), it will always be there and remain unchanged, and therefore, to "store" it, we can simply store a pointer to it (yes, a compile-time constant pointer!).
So, now we can look at the problem of concatenation. If we want to "store" two strings onto a single one, then we simply need to "store" one string, and "store" another. Here we go, down the rabbit hole:
class literal_str_list {
const char* const text_ptr;
unsigned int text_size;
const literal_str_list* const head;
public:
template <unsigned int N>
constexpr literal_str_list(const char(&aStr)[N],
const literal_str_list* aHead = nullptr) :
text_ptr(aStr), text_size(N-1), head(aHead) {
static_assert(N >= 1, "Invalid string literal! Length is zero!");
};
};
What happened here is that one string is "stored" as before, but there is also a pointer to another compile-time object that "stores" a string. It is not a coincidence that the class is now called "list" and has a pointer called "head". This is indeed a single linked-list, that is, a compile-time single linked-list. And as you probably know, this can, in principle, store a long list of strings all concatenated together.
So, we can do a few things with this literal string class, such as getting its size and retrieving an individual character from it, all at compile-time:
class literal_str_list {
//... as above ..
constexpr unsigned int size() const {
return text_size + (head != nullptr ? head->size() : 0);
};
constexpr char get_char_from_head(unsigned int i, unsigned int hd_size) const {
return (i < hd_size ?
(*head)[i] :
(i < (hd_size + text_size) ? text_ptr[i - hd_size] : '\0'));
};
constexpr char operator[](unsigned int i) const {
return (head != nullptr ?
get_char_from_head(i, head->size()) :
(i < text_size ? text_ptr[i] : '\0'));
};
};
As you can notice, everything is done recursively. If you've been following my posts here on Daniweb, you might find this odd, because I generally discourage recursion vehemently. However, in pure functional programming, recursion is the only option. Any form of iteration will require that you modify some kind of a variable (e.g., loop counter, termination condition, etc.), which is completely impossible in pure functional programming. So, everything has to be turned into a recursion (which is always possible, if you didn't know that already). So, here, the size() function simply does a recursive traversal of the linked-list to accumulate the sizes of the individual strings. The operator[] function is a bit more tricky because it has to locate the individual string into which the index i falls.
One might point out that things would be a lot simpler if I had used forward links (with "next" pointers). However, there is a reason why it had to be backwards links, and it will become clear as we look at a concatenation operator:
class literal_str_list {
//... as above ..
template <unsigned int N>
constexpr literal_str_list operator+(const char(&aHead)[N]) const {
return literal_str_list(aHead, this);
};
};
The problem here is that when we construct the new literal_str_list object, we need two things: a string literal and an existing literal_str_list object. But we have an additional quirky problem to deal with, which is the fact that the "this" object in the above operator can be recognized as a const-expression, but not if it was a parameter to the function (it is really hard to explain why). This means that we must define the operator+ as a member function if we want the "this" object to be recognized as a const-expression (again, breaking another one of my rules, prefer defining operators as free-functions or friends). This implies that the literal_str_list object involved in the concatenation (passed to the constructor) is always going to be the left operand of the concatenation, and that is why the linked-list needs to be using backward pointers.
That is pretty much it. There are a couple more fancy little things in the code (like a compile-time FNV-1a hashing function), but that was the important part. Here is a test program:
#include "literal_string_list.hpp"
#include <iostream>
#include <iomanip>
#include <string>
#include <type_traits>
std::string convert_to_string(const literal_str_list& lit) {
std::string result(lit.size(), ' ');
lit.copy_to(result.begin(), result.end());
return result;
};
// Note, the following are all compile-time constants:
constexpr literal_str_list hello = "Hello ";
constexpr literal_str_list world = "World!";
constexpr literal_str_list lit_str = hello + "World!";
constexpr literal_str_list lit_str2 = hello + world;
constexpr char c1 = lit_str[5];
constexpr std::size_t h1 = lit_str.hash();
int main() {
std::cout << "Got string: " << convert_to_string(lit_str) << std::endl;
std::cout << "Got string: " << convert_to_string(lit_str2) << std::endl;
std::cout << "Sixth character is '" << c1 << "'." << std::endl;
std::cout << "Hash value is " << std::hex << h1 << std::endl;
if(std::is_literal_type< literal_str_list >::value)
std::cout << "The literal_str_list class is considered as a literal type!" << std::endl;
else
std::cout << "The literal_str_list class is NOT considered as a literal type!" << std::endl;
};
The resulting code, after compilation, is simply a linked-list being formed in the read-only data section of the executable, as seen in these assembly listings:
.LC5: // LC5 is the 'pointer' to the "World!" string
.string "World!" // this is the "World!" string entry
.section .rodata // in read-only data section
.align 16
.type _ZL7lit_str, @object
.size _ZL7lit_str, 24
_ZL7lit_str: // this is the 'pointer' to the 'lit_str' object
.quad .LC5 // points to the "World!" string
.long 6
.zero 4
.quad _ZL5hello // has a 'head' pointer to the 'hello' object
.section .rodata.str1.1 // again, in read-only data section
.LC6: // LC6 is the 'pointer' to the "Hello " string
.string "Hello " // this is the "Hello " string entry
.section .rodata // in read-only data section
.align 16
.type _ZL5hello, @object
.size _ZL5hello, 24
_ZL5hello: // this is the 'pointer' to the 'hello' object
.quad .LC6 // points to the "Hello " string
.long 6
.zero 4
.quad 0 // has a null 'head' pointer (end of list)
There is definitely some overhead to this scheme (as with any use of a linked-list), but the important part here is that there is no initialization code needed, the strings can simply be read off from read-only memory. If one were to use "normal" string concatenation code to create some global string objects (instead of the constexpr constants in the test code above), there would be a much larger amount of overhead to account for the initialization code that needs to run in order to construct those global objects. And when my intended application (RTTI) is to construct such a string for every type (or template instantiation) in a library, this initialization code becomes a very measurable burden on the overall code.
