C++的杂七杂八:constexpr与编译期计算

1. 编译期计算

我们先来看一段求阶乘(factorial)的算法:

很明显,这是一段运行期算法。程序运行的时候,传递一个值,它可以是一个变量,也可以是一个常量:

如果程序仅仅像这样传递常量,我们可能会希望能够让它完全在编译的时候就把结果计算出来,那么代码改成这样或许是个不错的选择:

只是用起来会稍显麻烦点,但好处是运行期没有任何时间代价:

像上面这种运用模板的做法,算是最简单的模板元编程了。对C++模板来说,类型和值是同一种东西;同时,又由于C++的模板有了“Pattern Matching”(即特化和偏特化),同时又允许模板的递归结构(见上面factorial中使用factorial的情况),于是C++的模板是图灵完全的一种独立于C++的语言。理论上来说,我们可以利用它在编译期完成所有计算——前提是这些计算的输入都是literal的。

2. C++11以后的新限定符:constexpr

从C++11开始,我们有了constexpr specifier。它可以被用于变量,及函数上,像这样:

当然了,上面更直接的用法是这样:

在C++11中,constexpr还有诸多限制,但到了C++14,它似乎有点过于强大了。比如我们可以在函数中写多行语句,定义变量,甚至是循环:

就如同我们在写的只是一个普通函数,之后在函数的最前面加上constexpr它马上就可以在编译期执行了。
constexpr同样带来了强大的类型计算能力。我们简单的来看个例子,实现一个“types_insert”(Reference:C++的杂七杂八:使用模板元编程操作类型集合):

可以看到,对于这种简单的类型计算,constexpr比模板元的实现要清晰很多。
不过,由于函数模板缺少偏特化,因此需要编译期分支判断的“types_assign”是没办法直接写出来的(在这里无法短路求值的std::conditional并没有什么用)。要知道,函数重载虽然强大,但仅能做编译期类型,而不是数值的Pattern Matching,这点是不如类模板的偏特化/特化的。不过我们可以利用类模板的偏特化来模拟函数模板的偏特化:

但是说实话,我并不喜欢这样,这种写法丧失了函数模板的简洁性。一般来说,大家也不会用constexpr做太复杂的类型计算,这里反而用模板元来做会更加清晰些。从上面可以看出来,在做类型计算的时候,return返回的数值并不是我们需要的,而类型结果一般会用decltype取出来。在这种情况下,不使用constexpr,仅用普通函数都是可以的。
真正让人眼前一亮的,应该还是上面c_count的写法。利用模板元做数值计算其实是它的短板。撰写复杂不说,还有不少的局限性。
比如c_count可以这样用:

而模板元对string literal这类数值做计算是比较麻烦的,template non-type arguments被限制为常整数(包括枚举),或指向外部链接对象的指针(严格来说不止这这些。Reference:Template parameters and template arguments)。

3. constexpr性能实测

理论上来说,如果constexpr发挥作用,运行时是没有性能损耗的。我们用一个例子来测试下实际的效果:

g++ -v:version 5.3.1 20160413 (Ubuntu 5.3.1-14ubuntu2)
编译命令行:g++ -std=c++14 -O3 -I. ./test.cpp
测试结果:

测试结果并不理想。按理来说,c_fib应该和t_fib一样不需要任何时间才对。下面我们尝试修改一下c_fib的测试case:

我们可以看到,马上,测试的结果发生了变化,耗时变为0ms。
从实测上来看,除了const之外,如果把r2改为static变量(定义时马上初始化,因此c_fib只会被调用一次。若是定义后再对static变量赋值,则结果和普通变量一样),或constexpr变量,或者不要r2,直接将r_fib(n)放在std::cout后面输出结果,在这些情况都会触发constexpr的编译期计算。
当然了,如果像这样写:

或者这样写:

是一定会触发编译期计算的。
constexpr并不会尽可能的让expressions在编译期执行,只是表示expressions *能* 在编译期执行。至于真正执行的时机是编译期还是运行期,依赖编译器自己的选择。见constexpr specifier (since C++11)

The constexpr specifier declares that it is possible to evaluate the value of the function or variable at compile time. Such variables and functions can then be used where only compile time constant expressions are allowed (provided that appropriate function arguments are given).

另外,需要注意的一点是,函数的参数不能被定义为constexpr。也就是说,我们不能在编译期使用constexpr函数的参数,哪怕我们给它传递的参数确实是一个literal:

自然,这样也是不行的:

简单来说:

  • 1. 除了语法上的必须之外(比如在模板参数上使用函数),constexpr函数是否在编译期执行,取决于编译器的选择;
  • 2. 不论该函数是否在编译期执行,constexpr函数里,参数都只是普通的变量。

C++这样设计估计是考虑到constexpr函数需要同时具备编译期和运行期执行的能力吧。如果我们需要在constexpr函数内使用编译期参数,只能使用template non-type arguments了。

4. constexpr的应用:实现一个编译期字符串split

constexpr可以用在构造函数上,这样定义的类可以用来定义constexpr对象,像这样:

于是,我们可以先尝试定义一个编译期的string:

在上面这个类里,我们实现了一些简单的字符串操作。它支持在构造的时候传递字符串字面量(string literal),之后可以在编译期对字符串做count、substr和find。
但是这样定义的string是一个类模板,其参数N确定起来比较麻烦,我们可以给它包装一层,让代码写起来更轻松:

要实现split,我们还需要一个编译期的array对象:

我们注意到,以上两个类的内部全部使用数组,而不是指针来存储内容,这是因为想要对象能够在编译期被定义出来,C++要求其不能有non-trivial destructor,因此对象自身是不能动态分配内存的。如果我们使用指针,就只能由外部预先传递一块足够大的内存块供我们使用了。实际上,由于我们只考虑对象在编译期时的初始化和计算,因此拷贝的开销不需要太在意。
接下来,我们可以实现split了:

到此为止,一个编译期的字符串split函数就完成了,输入参数为字符数组,输出为literal::string_array。我们还可以为literal::string_array添加to_array等函数,让它支持转换为std::array。
注意,以上代码仅在g++ 5.3.1上编译通过,VS2015由于不支持C++14的constexpr,因此无法编译这些代码。

5. 使用constexpr简化类型计算

上文第2节,我提到了可以使用constexpr做简单的类型计算来代替模板元。在不需要数值特化做分支判断的情况下,constexpr函数会比模板元简洁很多。接下来,我们尝试改写一下上一节的split,仅使用C++11标准下的constexpr,并通过类型计算来实现编译期的字符串分割。
想要通过类型计算,而不是数值计算来处理字符串是比较麻烦的。我们首先要尝试把字符串类型化。但是在C++中,string literal是不能作为模板参数的,所以我们可以尝试把字符串字面量转换成一个个的char,然后将这些char作为模板参数传递进去。

这里我在literal_array里直接使用了std::array,配合std::string来存储结果。自然,也可以使用普通的char数组来存储。麻烦的是,我们如何把一个字符串字面量转换成literal_string<char…>呢?
很明显,由于constexpr的参数无法被当做模板参数使用,因此我们需要利用一点宏元的小技巧,让string literal在预编译期自己展开成一个个的char。首先,我们来看看不用宏,在字符串中取出字符的写法是什么样的:

可以注意到,这里需要我们对字符串的字符计数,然后顺次将此字符串展开到模板参数上。宏元是没办法对字符串的内容做分析的;而我们可以使用编译期技巧得到字符个数,宏也没有办法利用这个编译期数值去做计算。
这里我们有一个简单而暴力的解决方法,就是始终让宏嵌套计算到最后一层,并提供一个at函数,当计数的个数超出字符串长度的时候返回’\0’:

这样,我们调用LITERAL_S(“123″),就可以得到literal_string<‘1′, ‘2’, ‘3’, ‘\0′, …>。迈出了第一步以后,后面的类型计算我们就轻车熟路了:

最后,我们实现literal_string的split,并完成LITERAL_SPLIT宏:

使用方法:

以上代码在g++ 5.3.1及VS2015上编译通过(VS2015里宏不能嵌套这么深,需要调整CAPO_PP_MAX_的值)。
这个split对比上一节实现的最大的好处是,支持运行期无损耗的把字符串字面量拆分,并放入std::string的std::array中。

第5节代码下载:An example for spliting a string literal in compile-time.


参考文章:

发表评论