数据库计算向量化

前面我们通过一系列的CPU原理来学习了CPU的结构，以及怎么样让CPU跑得更快，那么我们有没有很好的案例来实战让CPU跑得更快呢。接下来我们通过数据库领域的向量化计算是如何利用CPU这些特性来让CPU更快地帮我们处理数据(SQL)

在做向量化之前数据库一直用的是volcano模型来处理SQL

volcano火山模型

对于如下一条SQL, 数据库会将它解析成一颗树，这棵树每个节点就是一个operator(简单理解就是一个函数，进行一次计算处理)

SELECT pv.siteId, user.nickame
FROM pv JOIN user
ON pv.siteId = user.siteId AND pv.userId = user.id
WHERE pv.siteId = 123;

可以看到火山模型实现简单，只需要根据不同的计算提供一堆算子(operator)就可以了，然后根据不同的SQL只需要将operator进行组装（类似搭积木一样），就能得到一个递归调用结构（火山模型），每行数据按照这个调用逻辑经过每个operator进行嵌套处理就得到最终结果。

火山模型不但实现简单，框架结构性也非常好容易扩展。

但是火山模型效率不高:

每个operator拆分必须到最小粒度，导致嵌套调用过多过深；
嵌套都是虚函数无法内联；
这个处理逻辑整体对CPU流水线不友好，CPU希望你不停地给我数据我按一个固定的逻辑(流程)来处理，而不是在不同的算子中间跳来跳去。

向量化加速的CPU原理

向量化加速的CPU原理:

如下图，表示的是for循环每次跳K个int，在K小于16的时候虽然循环次数逐渐减少到原来的1/16, 但是总时间没变，因为一直是访问的同一个cache里面的数据。到16个之后就会产生突变（跨了cache_line），再后面32、64、128的时间减少来源于循环次数的减少，因为如论如何每次循环都需要访问内存加载数据到cache_line中.

Cache_line大小是64，正好16个int，也就是存取1个或者16个int的代价基本是一样的。

1	for (int i = 0; i < arr.Length; i += K) arr[i] *= 3;

另外一个大家耳熟能详的案例是对一个二维数组逐行遍历和逐列遍历的时间差异，循环次数一样，但是因为二维数组按行保存，所以逐行遍历对cache line 更友好，最终按行访问效率更高:

const int row = 1024;
const int col = 512
int matrix[row][col];
//逐行遍历耗时0.081ms
int sum_row=0;
for(int _r=0; _r<row; _r++) {
    for(int _c=0; _c<col; _c++){
        sum_row += matrix[_r][_c];
    }
}
//逐列遍历耗时1.069ms
int sum_col=0;
for(int _c=0; _c<col; _c++) {
    for(int _r=0; _r<row; _r++){
        sum_col += matrix[_r][_c];
    }
}

了解了以上CPU运算的原理我们再来看向量化就很简单了

向量化

向量化执行的思想就是不再像火山模型一样调用一个算子一次处理一行数据，而是一次处理一批数据来均摊开销：这个开销很明显会因为一次处理一个数据没用利用好cache_line以及局部性原理，导致CPU在切换算子的时候要stall在取数据上，表现出来的结果就是IPC很低，cache miss、branch prediction失败都会增加。

举例来说，对于一个实现两个 int 相加的 expression，在向量化之前，其实现可能是这样的：

class ExpressionIntAdd extends Expression {
        Datum eval(Row input) {
                int left = input.getInt(leftIndex);
                int right = input.getInt(rightIndex);
                return new Datum(left+right);
        }
}

在向量化之后，其实现可能会变为这样：

class VectorExpressionIntAdd extends VectorExpression {
        int[] eval(int[] left, int[] right) {
                int[] ret = new int[input.length];
                for(int i = 0; i < input.length; i++) {
                  //利用cache局部性原理一次取多个数据和取一个代价一样
                  ret[i] = new Datum(left[i] + right[i]);
                }
                return ret;
        }
}

很明显对比向量化之前的版本，向量化之后的版本不再是每次只处理一条数据，而是每次能处理一批数据，而且这种向量化的计算模式在计算过程中也具有更好的数据局部性。

向量化–Vector、批量化（一次处理一批数据）。向量化核心是利用数据局部性原理，一次取一个和取一批的时延基本是同样的。volcanno模型每次都是取一个处理一个，跳转到别的算子；而向量化是取一批处理一批后再跳转。整个过程中最耗时是取数据（访问内存比CPU计算慢两个数量级）

如果把向量化计算改成批量化处理应该就好理解多了，但是low，向量化多玄乎啊

为了支持这种批量处理数据的需求，CPU设计厂家又搞出了SIMD这种大杀器

SIMD (Single Instruction Multiple Data，单指令多数据)

SIMD指令的作用是向量化执行(Vectorized Execution)，中文通常翻译成向量化，但是这个词并不是很好，更好的翻译是数组化执行，表示一次指令操作数组中的多个数据，而不是一次处理一个数据；向量则代表有数值和方向，显然在这里的意义用数组更能准确的表达。

在操作SIMD指令时，一次性把多条数据从内存加载到宽寄存器中，通过一条并行指令同时完成多条数据的计算。例如一个操作32字节(256位)的指令，可以同时操作8个int类型，获得8倍的加速。同时利用SIMD减少循环次数，大大减少了循环跳转指令，也能获得加速。SIMD指令可以有0个参数、1个数组参数、2个数组参数。如果有一个数组参数，指令计算完数组中的每个元素后，分别把结果写入对应位置；如果是有两个参数，则两个参数对应的位置分别完成指定操作，写入到对应位置。

如上图所示：SIMD指令同时操作A和B中4对数字，产生4个结果存放到C中

以如下代码为例，对4个float计算平方：

void squre( float* ptr )
{
    for( int i = 0; i < 4; i++ )
    {
      const float f = ptr[ i ];
      ptr[ i ] = f * f;
    }
}

上述代码转写成SIMD指令，则可以删除循环，用三条指令即可完成计算，分别是加载到寄存器，计算平方，结果写回内存:

void squre(float * ptr)
{
    __m128 f = _mm_loadu_ps( ptr ); 
    f = _mm_mul_ps( f, f ); 
    _mm_storeu_ps( ptr, f );
}

简单理解SIMD就是相对于之前一个指令(一般是一个时钟周期)操作一个数据，但现在有了SIMD就可以在一个时钟周期操作一批数据，这个批如果是64，那么性能就提升了64倍。

英特尔在1996年率先引入了MMX（Multi Media eXtensions）多媒体扩展指令集，也开创了SIMD（Single Instruction Multiple Data，单指令多数据）指令集之先河，即在一个周期内一个指令可以完成多个数据操作，MMX指令集的出现让当时的MMX Pentium处理器大出风头。

SSE（Streaming SIMD Extensions，流式单指令多数据扩展）指令集是1999年英特尔在Pentium III处理器中率先推出的，并将矢量处理能力从64位扩展到了128位。

AVX 所代表的单指令多数据（Single Instruction Multi Data，SIMD）指令集，是近年来 CPU 提升 IPC（每时钟周期指令数）上为数不多的重要革新。随着每次数据宽度的提升，CPU 的性能都会大幅提升，但同时晶体管数量和能耗也会有相应的提升。因此在对功耗有较高要求的场景，如笔记本电脑或服务器中，CPU 运行 AVX 应用时需要降低频率从而降低功耗。

向量化当然也非常希望利用SIMD(跟GPU为什么挖矿比CPU快是一样的道理)

这里可以参考为什么这20年CPU主频基本都在2G-3G附近不再提升但是性能仍然遵循摩尔定律在提升。