c++11+模板元编程：现代化计算引擎的速度秘诀
大数据计算引擎编程语言的迭代
伴随着Hadoop和Mapreduce的出现，引发了大数据时代。在大数据时代，计算引擎及其附加组价通常以java来实现，一方面java语言的开发难度比较低，另一方面原因是基础的组件是java开发，那么附加的生态以及拓展不得不以java开发，以实现协同效应。
Hadoop系统解决了分布式计算的问题，这是原来的数据库系统所解决不了的，因而在web风行的年代，Hadoop成为了大数据系统的不二选择。
反应过来的数据库圈子，借助于Mapreduce的理念，在原有数据库系统架构基础上，完成了数据库的分布式执行的改造。
而MapReduce系统，随着市场的推广，也遇到了他的难题：
- 编写分析程序的代价比较高。这也导致受众有限。而数据库凭借着半个世纪的积累，以及SQL这种门槛非常低的语言，成功的挽回了半壁江山。
- 执行的延时比较高，分析一个程序可能需要几个小时。对于快速迭代的互联网来说是不可接受的。
因此又出现了一些替代品，使用内存计算来加速，例如Presto。再后来，为了更加深挖性能，出现了Clickhouse这种性能怪物。那么像Clickhouse的这种速度极致的计算引擎，原因有很多种，本文关注在语言层面的原因。
Clickhouse，Velox等基础现代化的计算引擎，普遍采用c++17+的编程语法。以往大数据引擎通常java实现，生态丰富，开发代价比较小，而Clickhouse的成功布道了基于c++的计算引擎也是可以的，不仅可以完成，而且速度更快。
C++11+：一种全新设计理念的语言
每一种编程语言都有自己特定的编程风格：
c : 过程式
c++ ：面向对象
java: 异步回调
c++11+ : 什么风格？
c++11版本的发布距离上一个版本过去了c++03过去了8年的时间。更新了大量重量级的feature，以及全新的编程理念。
虽然都是以c++命名，但是c++的语言在c++11之后发生非常大的变化。这种变化，即使让我们称呼c++11以后的语言是一种全新的语言，也不为过。这种关系就像c和c++的关系：虽然c中也有结构体，但是c是一种过程式的语言，而c++则是一种面向对象的语言。而c++和c++11+也一样，虽然c++中也有模板，但是这种模板跟宏替换没太大区别；而在c++11+中，模板被提升到了新的高度，灵活的语法让我们具备了在编译期编程的能力，在c++11以后，是对于c++11的修补。基于c++11+ ，我们有能力告诉编译器，编译期应该怎么做。这种编译期的编程行为，称为是“元编程”。例如类型计算、编译器常量计算、生成代码控制。在本章节中，我们将介绍c++11+中模板元编程的核心方法。
c++11+ 的新的技术诞生了新的编程理念。关于template知识点比较零碎，但是我们可以聚焦于借助于template的新的技能，我们如何完成更高效的程序。在本文的最后，我们给出模板元编程的通用范式。
模板元编程的定义
模板元编程是什么？按照Wikipedia的定义：
1 | metaprogramming is a computer programming technique in which computer programs have the ability to treat other programs as their data. It means that a program can be designed to read, generate, analyse, or transform other programs, and even modify itself, while running. |
因此我们可以这样说，模板元编程就是在编译阶段，通过指令操纵编译器生成目标程序的过程，也就是操作程序的程序。
哪些系统在使用
模板元编程在现代化的计算引擎中得到了广泛应用。
- Clickhouse
- Velox
- Processila
- Makes extensive use of C++ template metaprogram- ming for compile time code generation. This allows utilizing many optimization techniques, such as partial application, to be applied to a single function imple- mentation automatically, while avoiding large virtual call overheads.
模板元编程解决什么问题：
通过编译器行为，控制编译生成的代码，在编译器生成所有的可能的代码，避免运行时的多态、分支跳转。
虚函数是比较众所周知的降低性能的点。虚函数降低性能的的原因：
- 动态寻址，打破流水线
- 如果预测准确，可以实现预加载
- 阻碍编译优化，如函数内联
- 这一点才是最主要因素，我们看一个样例
1 |
|
虚函数版本屏蔽了函数内联，导致每次都要重复计算。而非虚函数可以在静态阶段就计算出各个值，甚至可以复用重复的计算结果。
虚函数版本:29761.8 ms
非虚函数版本：0.00038ms
模板元编程核心技术
接下里介绍几个模板元编程的核心技术：类型萃取、模板特化、SFINAE、不定长参数。这些核心技术构成了模板元编程的主要概念。
类型萃取
类型萃取是 C++ 中的一项模板编程技术，它允许在编译时查询和操作类型的属性。类型萃取广泛用于模板元编程和泛型编程，特别是在实现编译时决策、条件编译、类型检查和类型转换时非常有用。说人话就是，类型萃取以类型作为变量，在编译时进行一些判断逻辑
类型萃取通常通过使用特殊的模板结构来实现，这些模板结构称为类型特征（type traits）。C++ 标准库 <type_traits> 头文件中提供了一组丰富的类型特征，用于对类型进行各种检查和转换。
类型特征可以返回关于类型的信息，如是否是整数类型、是否是指针类型、是否具有某个成员函数等。这些信息通常以编译时常量（如 true 或 false）或者类型（如 T::value_type）的形式提供。
以下是一些常见类型特征的类别和示例：
基本类型特征
std::is_integral<T>：检查T是否是整数类型。std::is_floating_point<T>：检查T是否是浮点类型。std::is_array<T>：检查T是否是数组类型。std::is_pointer<T>：检查T是否是指针类型。std::is_reference<T>：检查T是否是引用类型。std::is_const<T>：检查T是否有const限定符。std::is_function<T>：检查T是否是函数类型。
1 |
|
上边中，std::is_integral
模板特化和SFINAE
模板特化是 C++ 模板编程中的一个强大特性，允许程序员为特定的模板参数提供特殊的实现。模板是代码的通用实现，而模板特化是特殊性实现。模板特化分为全特化和偏特化，它们可以应用于函数模板和类模板。
全特化（Full Specialization）
全特化是针对所有模板参数提供一个特定实现的过程。当模板实例化时，如果实际参数与特化参数完全匹配，编译器会使用特化版本的模板。
类模板全特化示例：
1 | template <typename T> |
在这个例子中，当实例化 MyArray<int> 时，编译器会使用全特化版本，而其他类型比如 MyArray<double> 会使用通用模板。
函数模板全特化示例：
1 | template <typename T> |
当调用 print(10)（T 为 int 类型）时，会使用全特化版本。调用 print(3.14) 时，则会使用通用模板。
偏特化（Partial Specialization）
偏特化是针对一部分模板参数提供特定实现的过程，它只适用于类模板。在偏特化中，一部分模板参数被固定，其他保持通用。
类模板偏特化示例：
1 | template <typename T1, typename T2> |
在这个例子中，无论 T1 是什么类型，只要 T2 是 int 类型，就会使用偏特化版本。
特化的规则和用途
- 当特化的实例与通用模板实例冲突时，编译器会选择最特殊化（最具体）的版本。
- 模板特化可以用于优化特定类型的性能，提供特殊行为，或处理特定类型的限制。
- 特化不改变原始模板的接口，但提供了不同的实现细节。
- 特化必须在原始模板已定义的情况下进行。
- 模板特化必须在全局或命名空间作用域进行，不能在类或函数作用域内。
- 模板特化应该谨慎使用，因为过多的特化可能导致代码维护困难，而且可能会破坏模板的泛型性。
- 函数模板不支持偏特化，但可以通过重载或者模板参数的默认值来模拟偏特化行为。
模板特化是 C++ 模板编程中用来根据特定情况定制或优化代码的一个强大工具。通过模板特化，开发者可以针对特定类型或条件提供高效的算法实现，同时保持代码的通用性和可重用性。
分支特化constexpr
模板特化是类级别或者函数级别的。而代码块级别需要使用constexpr。
在模板函数中，经常会在一个函数体内生成针对多种类型的计算逻辑。当模板实例化后，部分逻辑就不需要了，只需要走实例化类型对应的逻辑就行。为了减少这种多余的代码，可以采用constexpr关键字来声明。constexpr 是 C++11 引入的关键字，其目的是指示编译器在编译时计算表达式的值，前提是所有表达式中的参数值在编译时均可知。使用 constexpr 可以创建编译时常量表达式，这对嵌入式系统和性能敏感的代码尤其有用，因为它可以消除运行时的计算成本并节省内存。
const关键字代表对象在运行期间值不变；而constexpr关键字代表从编译时就确认了对应的值，可以在编译时做更多优化。constexpr可以用于：
constexpr变量当你声明一个
constexpr变量时，编译器会尝试在编译时计算其值。这要求变量的初始化表达式必须是一个常量表达式。1
2
3
4
5
6constexpr int factorial(int n) {
return n <= 1 ? 1 : (n * factorial(n - 1));
}
constexpr int val = factorial(5); // val 在编译时计算为 120constexpr函数constexpr函数是指能在编译时产生常量表达式的函数。对于constexpr函数，编译器会在编译时进行函数调用，前提是提供给函数的所有参数也都是常量表达式。在 C++11 中，
constexpr函数的限制比较严格，要求函数体只能包含一条返回语句。但是在 C++14 和 C++17 中，对constexpr函数的限制放宽了，允许它们包含更丰富的语句，如循环和多个返回语句。1
2
3
4
5
6
7
8
9
10// C++14 开始，允许使用循环和多条语句
constexpr int factorial(int n) { //如果函数没有声明成constexpr，则后边定义const变量会报错。
int result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
constexpr int val = factorial(5); // val 仍然在编译时计算为 120constexpr构造函数类的构造函数也可以是
constexpr的。constexpr构造函数允许在编译时创建和初始化类或结构体的对象。1
2
3
4
5
6struct Point {
constexpr Point(double xVal, double yVal) : x(xVal), y(yVal) {}
double x, y;
};
constexpr Point p(1.0, 2.0); // 在编译时创建和初始化 Point 对象constexpr用于限制代码区块：
C++17 引入了所谓的
constexpr if语句，它允许在编译时根据常量表达式的值选择执行不同的代码路径。这是一个在编译时进行条件分支的强大特性，它可以用来移除非活动分支的代码，从而减少编译后程序的大小，并且可以减少模板元编程中的模板实例化。使用
constexpr if时，如果条件为true，编译器只会编译if分支内的代码；如果条件为false，则只会编译else分支内的代码（如果存在）。非活动的代码分支甚至不需要是合法的代码，因为它会在编译时被丢弃。这对于模板编程尤其有用，因为它允许根据模板参数的特性条件性地启用或禁用代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <typename T>
void process(const T& value) {
if constexpr (std::is_integral<T>::value) {
// 对整数类型的处理
std::cout << "Integer: " << value << std::endl;
} else if constexpr (std::is_floating_point<T>::value) {
// 对浮点类型的处理
std::cout << "Floating point: " << value << std::endl;
} else {
// 对其他类型的处理
std::cout << "Other type" << std::endl;
}
}
int main() {
process(10); // 输出 "Integer: 10"
process(3.14); // 输出 "Floating point: 3.14"
process("hello"); // 输出 "Other type"
}
SFINAE
SFINAE 是 C++ 模板编程中的一个基本原则，全称是 “Substitution Failure Is Not An Error”，意为“替换失败不是错误”。这个原则是指在模板参数替换的过程中，如果某个候选函数由于替换导致编译错误，这个错误将不会导致编译失败，而只是导致该候选函数被编译器丢弃，不参与后续的重载决议过程。
SFINAE 主要用于三个方面：
- 函数模板的重载决议：在函数模板重载决议中，如果一个候选函数模板在替换过程中失败（例如，由于类型不匹配或表达式不合法），编译器会简单地忽略该函数模板，继续尝试其他重载或模板。值得注意的是，只有函数模板才会有SFINAE的特性。也就是说函数必须声明成模板。一个模板类的成员函数，即便使用了类的模板变量，也不是一个模板函数，不具备SFINAE特性。
- 模板特化的选择：在类模板或函数模板的特化选择中，如果特化在替换过程中失败，那么它不会被选择。
- 类型萃取：利用 SFINAE 检测类型是否具有某些属性，如成员函数、嵌套类型等。
SFINAE 常通过以下方式实现：
- 类型萃取和
std::enable_if：利用std::enable_if在编译时基于类型特征条件启用或禁用某些模板。enable_if的机制是在满足特定条件时，才会特化出特定类型。当替换失败时，类型萃取无法获得完整的类型或者数据，例如没有type。
1 |
|
- 表达式 SFINAE：通过尝试解析特定的表达式来触发 SFINAE。
1 |
|
- 尾置返回类型：使用尾置返回类型的 SFINAE 来检测表达式的合法性。
1 | template <typename T> |
- 无效指针：将类型检查的结果映射到指针类型（例如
nullptr），只有在检查为真时才产生合法的类型。
1 | template <typename T> |
SFINAE 和编译错误
- 在使用 SFINAE 时，只有在模板参数替换阶段出现的错误才会被忽略，如果错误发生在替换之后（例如，函数体中的语义错误），那么它仍然会导致编译失败。
- 在众多的可选项中，至少要有一个替换成功。或者会报错。
不定长模板参数（Variadic Templates）
在 C++11 中引入的不定长模板参数列表（或称为可变参数模板）是一种高级的模板特性，它允许你定义接受任意数量模板参数的模板函数或模板类。这些参数可以是类型参数，也可以是非类型参数，或两者的混合。不定长模板参数列表提供了极大的灵活性，可以用来编写泛化的算法和数据结构。
不定长模板参数列表通常使用省略号 ... 来表示。
函数模板的不定长参数
当定义一个函数模板，你可以允许它接受任意数目的参数，这些参数可以是不同的类型。
例如：
1 | template <typename... Args> |
在这个例子中，Args... 表示一个可变数量的类型参数。
类模板的不定长参数
同样地，类模板也可以定义为接受任意数目的模板参数：
1 | template <typename... Elements> |
在这个例子中，Tuple 可以持有任意数目和类型的元素。
展开不定长模板参数列表
展开不定长模板参数列表意味着在编译时对参数列表中的每个参数执行操作。有几种不同的方法可以展开参数列表：
- 递归模板函数
可以通过递归模板函数的方式来展开参数列表。每个递归调用处理参数列表中的一个参数，然后将剩下的参数传递给下一个递归调用，直到参数列表为空。递归的终止条件：只有一个参数的场景，也就是可变参数列表为空的场景。
例如：
1 | template <typename T> |
- 初始化列表展开
这种技术涉及到创建一个初始化列表，它会在编译时展开参数列表，并且可以应用于任意表达式。
1 | template <typename... Args> |
这里，每个参数 args 都被插入到初始化列表中，并且通过逗号运算符，每个参数对应的表达式都会被执行。在这里等同于是展开为逗号表达式。
- 折叠表达式（C++17）
C++17 引入了折叠表达式，这是展开参数包的一个更简单和直接的方法。
1 | template <typename... Args> |
在这个例子中，<< 运算符被折叠应用于参数包 args 的每个元素，从左到右。
不定长模板参数列表和参数包的展开技术，大大增强了 C++ 模板的能力，使得编写能够处理任意数量和类型参数的泛型代码成为可能。这些技术在实现复杂的库功能如类型安全的变参函数、元组和函数对象绑定等时非常有用。
折叠表达式有两种形式：
二元右折叠（Binary Right Fold）：
(pack op ... op init)，其中op是二元运算符，pack是参数包，init是初始值。右折叠的含义是从右向左对参数包的元素进行折叠。例如
(args + ...);(1, 2, 3, 4)展开成(1 + (2 + (3 + 4)))。二元左折叠（Binary Left Fold）：
(init op ... op pack)，其中运算符和参数与右折叠相同。左折叠是从左向右对参数包的元素进行折叠。例如
(... + args);(1, 2, 3, 4)展开成((1 + 2) + 3) + 4。
Clickhouse 变参展开
1 | static bool castType(const IDataType * type, F && f) |
如何去虚
变参展开去虚
在动态运行时，由于不知道参数的实际类型，必须会产生一次动态类型解析。在普通的虚函数调用时，每次调用子类的函数都需要调用虚函数，而调用虚函数的过程就涉及到一次动态类型解析，引发访问虚表的开销。
基于模板的实现是怎么做的呢？由于运行时不知道实际类型，必然产生至少一次类型解析。那么我们可以使用一次类型解析，把变量转换为实际的类型。然后之后的运行调用类型中的函数，无论调用多少次，都不会产生虚函数调用的开销。而模板要做的，就是为每一个子类的每一个函数调用生成执行代码。
1 | //定义类型 |
在processColumn中，调用castType。而castType在编译时为多种类型生成执行代码。并且在运行时通过typeid_cast动态识别类型，把类型转换为实际的类型后，在lambda函数中调用真正的处理函数processColumnImpl。而processColumnImpl是一个模板函数，为每一种类型都生成了代码。在运行时批量处理大量的数据。也就是说实现了一次类型转换，在实际类型中批量处理大量数据。避免了每处理一次数据就调用一次虚函数的开销。
CRTP去虚
CRTP可以用于消除虚函数调用，我们以Clickhouse中的使用样例为例：
1 | class IAggregateFunction |
add是一个虚函数，如果每一行调用一次add函数，必然产生比较大的虚函数开销。但是在子类中，我们可以把子类作为函数模板传入中间的基类中，然后在中间的基类中强制转换成模板类的类型来实现虚函数的调用。
Variant
std::variant
std::variant 是一个模板类，它可以容纳给定类型列表中的任何一个类型的值。在任何时刻，std::variant 只包含这些类型中的一个。如果你熟悉 C 的联合体（union），std::variant 可以被看作是联合体的类型安全版本。std::variant 可以保证存储的值始终是有效的，而且可以在运行时检查当前保存了哪种类型的值。
1 |
|
std::variant 提供成员函数 index() 来查询当前存储的类型的索引值，std::get 可以根据类型或索引来访问存储的值。如果使用错误的类型或索引，std::get 将抛出异常。
std::variant提供了除虚函数以外的另外一种方法去实现动态多态。为了访问variant中的内容，需要使用std::visit。
std::visit
std::visit 是一个函数模板，用于访问存储在一个或多个 std::variant 对象中的值。它接收一个可调用对象和一个或多个 std::variant 对象作为参数。可调用对象的形参类型必须能够接受 std::variant 所有可能值的类型。
使用 std::visit 的主要好处是它允许你编写一个泛型的访问者，它可以处理 std::variant 包含的任意类型的值，你不需要手动检查 std::variant 当前包含的是哪种类型。
1 | #include <variant> |
在这个例子中，我们定义了一个 std::variant，它可以存储 int、float 或 std::string 类型的值。使用 std::visit 和一个泛型 lambda 表达式，我们可以访问并打印存储在 std::variant 中的值，而不需要关心它当前包含的具体类型。
std::visit 和 std::variant 配合使用，提供了一个强大的模式匹配机制，非常适合用于那些需要根据运行时确定的类型来执行不同行为的场景。这种类型安全和灵活性在 C++ 中是非常有价值的，尤其是在处理复杂的数据结构和算法时。
基于variant和visit的方法，相比基于虚函数的方法，性能可以提升20%左右。
Velox variant
velox中使用variant容纳不同的类型。
1 | template <TypeKind KIND> |
一些坑
模板元编程是编译期行为，要区分清楚运行时行为。一个简单的例子：
1 | class ColumnWriter |
在编译阶段，是找不到基类的函数的，只能看到本类内的函数签名。
模板元编程的一个终极案例：
1 |
|
模板元编程加速计算的范式
模板元编程解决分支和虚函数问题的原理大概如此，就是想办法把提前解析动态类型，把动态类型转换为实际的类型。然后执行实际类型的函数。然后通过模板为每一种可能的模板参数组合写出所有的实现。下图是模板元编程和虚函数风格的不同。当我们理解了这种风格之后，再去看代码，就会有一种豁然开朗的感觉，也就不存在代码可读性的问题了。
，对应的SIMD指令是
对应的SIMD指令是
