一文了解 ClickHouse 的向量化执行
一文了解 ClickHouse 的向量化执行
ClickHouse在计算层做了非常细致的工作，竭尽所能榨干硬件能力，提升查询速度。它实现了单机多核并行、分布式计算、向量化执行与SIMD指令、代码生成等多种重要技术。
多核并行
ClickHouse将数据划分为多个partition，每个partition再进一步划分为多个index granularity，然后通过多个CPU核心分别处理其中的一部分来实现并行数据处理。
在这种设计下，单条Query就能利用整机所有CPU。极致的并行处理能力，极大的降低了查询延时。
分布式计算
除了优秀的单机并行处理能力，ClickHouse还提供了可线性拓展的分布式计算能力。ClickHouse会自动将查询拆解为多个task下发到集群中，然后进行多机并行处理，最后把结果汇聚到一起。
向量化执行与SIMD
ClickHouse不仅将数据按列存储，而且按列进行计算。传统OLTP数据库通常采用按行计算，原因是事务处理中以点查为主，SQL计算量小，实现这些技术的收益不够明显。但是在分析场景下，单个SQL所涉及计算量可能极大，将每行作为一个基本单元进行处理会带来严重的性能损耗：
•对每一行数据都要调用相应的函数，函数调用开销占比高；
•存储层按列存储数据，在内存中也按列组织，但是计算层按行处理，无法充分利用CPU cache的预读能力，造成CPU Cache miss严重；•按行处理，无法利用高效的SIMD指令；
ClickHouse实现了向量执行引擎（Vectorized execution engine），对内存中的列式数据，一个batch调用一次SIMD指令（而非每一行调用一次），不仅减少了函数调用次数、降低了cache miss，而且可以充分发挥SIMD指令的并行能力，大幅缩短了计算耗时。向量执行引擎，通常能够带来数倍的性能提升。
What IS SIMD ?
SIMD
即 single instruction multiple data 英文首字母缩写，单指令流多数据流，也就是说一次运算指令可以执行多个数据流，一个简单的例子就是向量的加减。
SSE 与 SMID 关系
SSE（为Streaming SIMD Extensions的缩写）是由 Intel公司在1999年推出Pentium III处理器时，同时推出的新指令集。如同其名称所表示的，SSE是一种SIMD指令集。SSE有8个128位寄存器，XMM0 ~XMM7。可以用来存放四个32位的单精确度浮点数。可以看出，SSE 是一套专门为 SIMD（单指令多数据）架构设计的指令集。通过它，用户可以同时在多个数据片段上执行运算，实现数据并行（aka:矢量处理）。
SSE2是SSE指令的升级版，寄存器与指令格式都和SSE一致，不同之处在于其能够处理双精度浮点数等更多数据类。SSE3增加了13条新的指令。
参考：https://www.cnblogs.com/xidian-wws/p/11023762.html
C++使用SIMD编程的3种方法
SIMD指令集的使用，有如下三种方式：
•编译器优化 即使用C/C++编写程序之后，带有SIMD优化选项编译，在CPU支持的情况下，编译器按照自己的规则去优化。•使用intrinsic指令 参考Intel手册，针对SIMD指令，可以在编程时直接使用其内置的某些库函数，编译的时候在cpu和编译器的支持下会生成对应的SIMD指令。比如：double _mm_cvtsd_f64 (__m128d a) 该函数编译时就会翻译成指令：movsd•嵌入式汇编 内联汇编直接在程序中嵌入对应的SIMD指令。
Intrinsics头文件与SIMD指令集、Visual Studio版本对应表
VS和GCC都支持SSE指令的Intrinsic，SSE有多个不同的版本，其对应的Intrinsic也包含在不同的头文件中，如果确定只使用某个版本的SSE指令则只包含相应的头文件即可。
例如，要使用SSE3，则
#include <tmmintrin.h>如果不关心使用那个版本的SSE指令，则可以包含所有
#include <intrin.h>参考资料：https://www.cnblogs.com/huaping-audio/p/4115890.html
简单运算的Intrinsic和SSE指令对比 使用Intrinsic函数的代码：
__m128 a1, b2; __m128 c1; for (int i = 0; i < count; i++) { a1 = _mm_load_ps(a); b2 = _mm_load_ps(b); c1 = _mm_add_ps(a1, b2); }对应汇编指令代码：
for(int i = 0; i < count; i ++) _asm { movaps xmm0, [a]; movaps xmm1, [b]; addps xmm0, xmm1; }简要说明其中一种操作：
addps XMM,XMM/m128 源存储器内容按双字对齐，共4个单精度浮点数与目的寄存器相加，结果送入目的寄存器
计算机硬件支持与编译器支持
要能够使用 Intel 的 SIMD 指令集，不仅需要当前 Intel 处理器的硬件支持，还需要编译器的支持。
$ grep -q sse4_2 /proc/cpuinfo && echo "SSE 4.2 supported" || echo "SSE 4.2 not supported"如果你的机器支持SSE4.2，那么，将打印：
SSE 4.2 supported使用SIMD考量
•利用优点： 频繁调用的基础函数，大量的可并行计算•尽量避免： SSE指令集对分支处理能力非常的差，而且从128位的数据中提取某些元素数据的代价又非常的大，因此不适合有复杂逻辑的运算。
How Clickhouse USE SIMD ?
大家在搜索CLICKHOUSE为什么快的文章中，都提到了CH使用到的技术列式存储，压缩，向量引擎。
CH在所有能够提高CPU计算效率的地方，都大量的使用了SIMD。
本文以clickhouse其中的一个简单的LowerUpperImpl函数为例（这个函数完成大小写转换）。
测试产出SIMD模式与非SIMD模式下benchmark的效率对比。
code如下，关键节点已加注释:
template <char not_case_lower_bound, char not_case_upper_bound>struct LowerUpperImpl{public: static void array( char * src, char * src_end, char * dst) { //32 const auto flip_case_mask = 'A' ^ 'a';#ifdef __SSE2__ const auto bytes_sse = sizeof(__m128i); const auto src_end_sse = src_end - (src_end - src) % bytes_sse; const auto v_not_case_lower_bound = _mm_set1_epi8(not_case_lower_bound - 1); const auto v_not_case_upper_bound = _mm_set1_epi8(not_case_upper_bound + 1); const auto v_flip_case_mask = _mm_set1_epi8(flip_case_mask); for (; src < src_end_sse; src += bytes_sse, dst += bytes_sse) { //_mm_loadu_si128表示：Loads 128-bit value；即加载128位值。 //一次性加载16个连续的8-bit字符 const auto chars = _mm_loadu_si128(reinterpret_cast<const __m128i *>(src)); //_mm_and_si128(a,b)表示：将a和b进行与运算，即r=a&b //_mm_cmpgt_epi8(a,b)表示：分别比较a的每个8bits整数是否大于b的对应位置的8bits整数，若大于，则返回0xff，否则返回0x00。 //_mm_cmplt_epi8(a,b)表示：分别比较a的每个8bits整数是否小于b的对应位置的8bits整数，若小于，则返回0xff，否则返回0x00。 //下面的一行代码对这128位的寄存器并行操作了3遍，最后得到一个128位数，对应位置上是0xff的，表示 //那个8-bit数在 [case_lower_bound, case_upper_bound]范围之内的，其余的被0占据的位置，是不在操作范围内的数。 const auto is_not_case = _mm_and_si128(_mm_cmpgt_epi8(chars, v_not_case_lower_bound), _mm_cmplt_epi8(chars, v_not_case_upper_bound)); //每个0xff位置与32进行与操作，原来的oxff位置变成32，也就是说，每个在 [case_lower_bound, case_upper_bound]范围区间的数，现在变成了32，其他的位置是0 const auto xor_mask = _mm_and_si128(v_flip_case_mask, is_not_case); //将源chars内容与xor_mask进行异或，符合条件的字节可能从uppercase转为lowercase，也可能从lowercase转为uppercase，不符合区间的仍保留原样。 const auto cased_chars = _mm_xor_si128(chars, xor_mask); //将结果集存到dst中 _mm_storeu_si128(reinterpret_cast<__m128i *>(dst), cased_chars); }#endif#ifndef __SSE2__ for (; src < src_end; ++src, ++dst) if (*src >= not_case_lower_bound && *src <= not_case_upper_bound) *dst = *src ^ flip_case_mask; else *dst = *src;#endif }};完整代码参考 这里[1]
测试结果如下：
32位输入：
root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread sse.cpp && ./a.outnew des is abcdefghabcdefghabcdefghabcdefgh花费了6.8059秒root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread nosse.cpp && ./a.outnew des is abcdefghabcdefghabcdefghabcdefgh花费了9.39051秒64位输入：
root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread sse.cpp && ./a.outnew des is abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh花费了9.26642秒root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread nosse.cpp && ./a.outnew des is abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh花费了17.3588秒128位输入：
root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread sse.cpp && ./a.outnew des is abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh花费了10.2672秒root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread nosse.cpp && ./a.outnew des is abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh花费了31.7568秒这只是其中一个简单的函数。但，为什么Clickhouse快？管中窥豹，可见一斑。
Clickhouse 仅短短几年在OLAP领域横空出世，这和Clickhouse在设计和细节上追求极致密不可分。
对于俄罗斯人，开源一款产品可是大事。但不开源还则罢了。一旦开源，必是行业大事。一如nginx。
本文转载自：https://www.jianshu.com/p/fc384f18ff1a，作者：金科_
引用链接
[1] 这里: https://github.com/Johnny-Three/clickhousedive/blob/master/main.cpp