Clickhouse SIMD 使用初探
ClickHouse在计算层做了非常细致的工作，竭尽所能榨干硬件能力，提升查询速度。它实现了单机多核并行、分布式计算、向量化执行与SIMD指令、代码生成等多种重要技术。
多核并行
ClickHouse将数据划分为多个partition，每个partition再进一步划分为多个index granularity，然后通过多个CPU核心分别处理其中的一部分来实现并行数据处理。
在这种设计下，单条Query就能利用整机所有CPU。极致的并行处理能力，极大的降低了查询延时。
分布式计算
除了优秀的单机并行处理能力，ClickHouse还提供了可线性拓展的分布式计算能力。ClickHouse会自动将查询拆解为多个task下发到集群中，然后进行多机并行处理，最后把结果汇聚到一起。
向量化执行与SIMD
ClickHouse不仅将数据按列存储，而且按列进行计算。传统OLTP数据库通常采用按行计算，原因是事务处理中以点查为主，SQL计算量小，实现这些技术的收益不够明显。但是在分析场景下，单个SQL所涉及计算量可能极大，将每行作为一个基本单元进行处理会带来严重的性能损耗：
1）对每一行数据都要调用相应的函数，函数调用开销占比高；
2）存储层按列存储数据，在内存中也按列组织，但是计算层按行处理，无法充分利用CPU cache的预读能力，造成CPU Cache miss严重；
3）按行处理，无法利用高效的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指令集的使用，有如下三种方式：
1）编译器优化
即使用C/C++编写程序之后，带有SIMD优化选项编译，在CPU支持的情况下，编译器按照自己的规则去优化。
2）使用intrinsic指令
参考Intel手册，针对SIMD指令，可以在编程时直接使用其内置的某些库函数，编译的时候在cpu和编译器的支持下会生成对应的SIMD指令。
比如：
double _mm_cvtsd_f64 (__m128d a)
该函数编译时就会翻译成指令：
movsd
3）嵌入式汇编
内联汇编直接在程序中嵌入对应的SIMD指令。
Intrinsics头文件与SIMD指令集、Visual Studio版本对应表
VS和GCC都支持SSE指令的Intrinsic，SSE有多个不同的版本，其对应的Intrinsic也包含在不同的头文件中，如果确定只使用某个版本的SSE指令则只包含相应的头文件即可。
例如，要使用SSE3，则
#include <tmmintrin.h>
如果不关心使用那个版本的SSE指令，则可以包含所有
#include <intrin.h>
image.png
参考资料：[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
}
};
完整代码git地址
测试结果如下：
32位输入：
root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread sse.cpp && ./a.out
new des is abcdefghabcdefghabcdefghabcdefgh
花费了6.8059秒
root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread nosse.cpp && ./a.out
new des is abcdefghabcdefghabcdefghabcdefgh
花费了9.39051秒
64位输入：
root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread sse.cpp && ./a.out
new des is abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh
花费了9.26642秒
root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread nosse.cpp && ./a.out
new des is abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh
花费了17.3588秒
128位输入：
root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread sse.cpp && ./a.out
new des is abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh
花费了10.2672秒
root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread nosse.cpp && ./a.out
new des is abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh
花费了31.7568秒
这只是其中一个简单的函数。
但，为什么Clickhouse快？
管中窥豹，可见一斑。
Clickhouse
仅短短几年在OLAP领域横空出世，
这和Clickhouse在设计和细节上追求极致密不可分。
对于俄罗斯人，开源一款产品可是大事。
但不开源还则罢了。
一旦开源，必是行业大事。
一如nginx。
