漫谈SIMD、SSE指令集与ClickHouse向量化执行

前言

ClickHouse之所以会像闪电一样快（"blazing fast"），是多方面优化的结果，包括且不限于：高效且磁盘友好的列式存储，高效的数据压缩，精心设计的各类索引，并行分布式查询，运行时代码生成等。

另外，ClickHouse为了最大限度地压榨硬件——尤其是CPU——的性能，实现了向量化查询执行（vectorized query execution）机制。这个名词相对于上面的那些可能没那么平易近人，但它毫无疑问是CK相对于传统OLAP引擎的大杀器。鉴于现有资料中讲解CK向量化执行的内容很少，本文就来试图探究一下，先从基础知识SIMD说起。

SIMD

SIMD即"single instruction, multiple data"（单指令流多数据流），是Flynn分类法对计算机的四大分类之一。它本质上是采用一个控制器来控制多个处理器，同时对一组数据中的每一条分别执行相同的操作，从而实现空间上的并行性的技术。

可见，“单指令流”指的是同时只能执行一种操作，“多数据流”则指的是在一组同构的数据（通常称为vector，即向量）上进行操作，如下图所示，PU=processing unit。

SIMD在现代计算机的应用甚广泛，最典型的则是在GPU的像素处理流水线中。举个例子，如果要更改一整幅图像的亮度，只需要取出各像素的RGB值存入向量单元（向量单元很宽，可以存储多个像素的数据），再同时将它们做相同的加减操作即可，效率很高。SIMD和MIMD流水线是GPU微架构的基础，就不再展开聊了。

话说回来，CPU是如何实现SIMD的呢？答案是扩展指令集。Intel的第一版SIMD扩展指令集称为MMX，于1997年发布。后来至今的改进版本有SSE（Streaming SIMD Extensions）、AVX（Advanced Vector Extensions），以及AMD的3DNow!等。ClickHouse的向量化执行机制主要依赖于SSE指令集，下面简要介绍之。

SSE指令集

SSE指令集是MMX的继任者，其第一版早在Pentium III时代就被引入了。随着新指令的扩充，又有了SSE2、SSE3、SSSE3、SSE4（包含4.1和4.2）等新版本。我们可以通过cpuid类软件获得处理器对SSE指令集的支持信息，下图以笔者自用MacBook Pro中的Intel Core i9-9880H为例。

并不仅有Intel的处理器才支持SSE指令集，AMD的同样也支持。下图以笔者游戏PC中的AMD Ryzen 5 3600为例。

ClickHouse提供的检查CPU是否支持SSE4.2的命令如下。

grep -q sse4_2 /proc/cpuinfo && echo "SSE 4.2 supported" || echo "SSE 4.2 not supported"

SSE指令集以8个128位寄存器为基础，命名为XMM0~XMM7。在AMD64（即64位扩展）指令集中，又新增了XMM8~XMM15。一个XMM寄存器原本只能存储一种数据类型：

  • 4个32位单精度浮点数

SSE2又扩展到能够存储以下类型：

  • 2个64位双精度浮点数
  • 2个64位/4个32位/8个16位整数
  • 16个字节或字符

SSE的指令分为两大类，一是标量（scalar）指令，二是打包（packed）指令。标量指令只对XMM寄存器中的最低位数据进行计算，打包指令则是对所有数据进行计算。下图示出SSE1中，单精度浮点数乘法的标量和打包运算。

图来自http://www.songho.ca/misc/sse/sse.html，是一篇很好的SSE入门

观察指令名称，mul表示乘法，接下来的s表示标量，p表示打包，最后一个s则表示类型为单精度浮点数（single-precision）。由图也可以发现，打包指令才是真正SIMD的，而标量指令是SISD的。

再举个小栗子，如果我们要实现两个4维向量v1和v2的加法，只需要三条SSE指令就够了。

 movaps xmm0, [v1] ;xmm0 = v1.w | v1.z | v1.y | v1.x 
 addps xmm0, [v2]  ;xmm0 = v1.w+v2.w | v1.z+v2.z | v1.y+v2.y | v1.x+v2.x
 movaps [vec_res]  ;xmm0

注意数据移动指令movaps中的a表示对齐（align）。第一条指令的意思就是通过[v1]直接寻址得到向量的起点，并分别按照0、4、8、16字节的偏移量写入XMM0寄存器的低到高四个域。在数据本身已经按照16字节对齐的情况下，调用这种指令效率非常高。从寄存器写入内存也是同理的，如下图。

那么如何利用SSE指令集呢？主要有以下3种方法：

  • 直接编写（内嵌）汇编语句；
  • 利用厂商提供的扩展库函数。Intel将这类指令和函数统称为intrinsics，官方提供的速查手册见这里；
  • 开启编译器的优化（-msse、-msse2等等），编译器会自动将符合条件的情景（如数组相加、矩阵相乘等）编译为intrinsic指令。

需要注意的是，SIMD和SSE虽然强大，但是对于那些严重依赖流程控制（flow-control-heavy）的任务，即有大量分支、跳转和条件判断的任务明显不太适用。也就是说，它们主要被用来优化可并行计算的简单场景，以及可能被频繁调用的基础逻辑。

说了这么多，可以进入ClickHouse的世界了。

ClickHouse向量化执行示例

编译器优化对笔者这种水平不高的人来说显然太难，所以还是去ClickHouse源码中寻找向量化执行的蛛丝马迹比较好。我们可以查找形如#ifdef __SSE2__的宏定义，或者根据手册查找intrinsic函数对应的头文件，如SSE4.1的头文件是<smmintrin.h>，以此类推。

为简单起见，选取两段应用了SSE2 intrinsics函数的示例来作分析。

计算Filter中1的数量

在ClickHouse的底层，过滤器（Filter）是一个预分配空间的、无符号8位整形数的数组，用于表示WHERE和HAVING子句的条件及真值，每一位的取值为0或1，即表示条件为假或真。Filter和列（IColumn）是共生的，在ColumnsCommon.cpp中，提供了通用的计算Filter中1的数量的方法，代码如下。

size_t countBytesInFilter(const IColumn::Filter & filt)
{
    size_t count = 0;

    /** NOTE: In theory, `filt` should only contain zeros and ones.
      * But, just in case, here the condition > 0 (to signed bytes) is used.
      * It would be better to use != 0, then this does not allow SSE2.
      */

    const Int8 * pos = reinterpret_cast<const Int8 *>(filt.data());
    const Int8 * end = pos + filt.size();

#if defined(__SSE2__) && defined(__POPCNT__)
    const __m128i zero16 = _mm_setzero_si128();
    const Int8 * end64 = pos + filt.size() / 64 * 64;

    for (; pos < end64; pos += 64)
        count += __builtin_popcountll(
            static_cast<UInt64>(_mm_movemask_epi8(_mm_cmpgt_epi8(
                _mm_loadu_si128(reinterpret_cast<const __m128i *>(pos)),
                zero16)))
            | (static_cast<UInt64>(_mm_movemask_epi8(_mm_cmpgt_epi8(
                _mm_loadu_si128(reinterpret_cast<const __m128i *>(pos + 16)),
                zero16))) << 16)
            | (static_cast<UInt64>(_mm_movemask_epi8(_mm_cmpgt_epi8(
                _mm_loadu_si128(reinterpret_cast<const __m128i *>(pos + 32)),
                zero16))) << 32)
            | (static_cast<UInt64>(_mm_movemask_epi8(_mm_cmpgt_epi8(
                _mm_loadu_si128(reinterpret_cast<const __m128i *>(pos + 48)),
                zero16))) << 48));

    /// TODO Add duff device for tail?
#endif

    for (; pos < end; ++pos)
        count += *pos > 0;

    return count;
}

defined(__SSE2__)说明当前环境支持SSE2指令集，而defined(__POPCNT__)说明支持硬件级位计数的POPCNT指令。下面根据手册简要介绍一下代码中涉及到的intrinsic函数：

  • _mm_setzero_si128()：初始化128位（16字节）的全0位图，即一个XMM寄存器。
  • _mm_loadu_si128(mem_addr)：从内存地址mem_addr处加载128位的整形数据。
  • _mm_cmpgt_epi8(a, b)：按8位比较a和b两个128位整形数，若a的对应8位比b的对应8位大，则填充对应位为全1，否则填充全0。
  • _mm_movemask_epi8(a)：根据128位整形数a的每个8位组的最高位创建掩码，一共16位长，返回int结果（高16位用0填充）。

最后，__builtin_popcountll()函数相当于直接调用POPCNT指令算出64位数的汉明权重。

由上可见，这个函数的每次循环都将连续64个Filter的真值数据（即Int8类型）压缩到一个UInt64中一起做位计数。其中每次调用上述指令都会处理16个Int8，正好是128位，SIMD的思想就是这样体现出来的。由于SSE指令集中没有真正的位运算指令，所以压缩的过程略显繁琐，但是仍然比笨方法（逐个遍历判断）效率高很多。

字符串大小写转换

ClickHouse的函数中也充分应用了SSE指令集，特别是字符串函数。以ASCII拉丁字符大小写转换函数（即toLower()和toUpper()）为例，其源码如下，位于LowerUpperImpl.h文件中。

template <char not_case_lower_bound, char not_case_upper_bound>
struct LowerUpperImpl
{
// 略去
private:
    static void array(const UInt8 * src, const UInt8 * src_end, UInt8 * dst)
    {
        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)
        {
            /// load 16 sequential 8-bit characters
            const auto chars = _mm_loadu_si128(reinterpret_cast<const __m128i *>(src));

            /// find which 8-bit sequences belong to range [case_lower_bound, case_upper_bound]
            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));

            /// keep `flip_case_mask` only where necessary, zero out elsewhere
            const auto xor_mask = _mm_and_si128(v_flip_case_mask, is_not_case);

            /// flip case by applying calculated mask
            const auto cased_chars = _mm_xor_si128(chars, xor_mask);

            /// store result back to destination
            _mm_storeu_si128(reinterpret_cast<__m128i *>(dst), cased_chars);
        }
#endif

        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;
    }
};

原理比较简单，就是利用flip_case_mask这个掩码来翻转字符的大小写（大小写字母的ASCII码值相差32）。not_case_lower_bound和not_case_lower_bound则用来标定转换的字符范围，比如a~z或A~Z。不过在SSE2的加持下，就可以一次性加载16个字符进行转换，同样是SIMD的思想，效率自然比普通的遍历高。由于每句话都有官方注释，就不再多废话了。

测试一下

将上面的LowerUpperImpl结构体拆出来，测试代码如下。

#include <iostream>
#include <string>
#include <vector>
#include <chrono>
using namespace std;
using namespace std::chrono;

#ifdef __SSE2__
#include <emmintrin.h>
#endif

template <char not_case_lower_bound, char not_case_upper_bound>
struct LowerUpperImpl {
  public:
  static void arraySSE(const char * src, const char * src_end, char * dst) {
    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) {
      const auto chars = _mm_loadu_si128(reinterpret_cast<const __m128i *>(src));

      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));

      const auto xor_mask = _mm_and_si128(v_flip_case_mask, is_not_case);

      const auto cased_chars = _mm_xor_si128(chars, xor_mask);

      _mm_storeu_si128(reinterpret_cast<__m128i *>(dst), cased_chars);
    }
#endif

    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;
  }

  static void arrayNoSSE(const char * src, const char * src_end, char * dst) {
    const auto flip_case_mask = 'A' ^ 'a';
    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;
  }
};

int main() {
  char src[261] = {'\0'};
  char dst[261] = {'\0'};

  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 26; j++) {
      src[i * 26 + j] = 'a' + j;
    }
  }

  LowerUpperImpl<'a', 'z'> lowerUpper;

  auto start1 = system_clock::now();
  for (int i = 0; i < 100; i++) {
    lowerUpper.arraySSE(&src[0], &src[261], &dst[0]);
  }
  auto end1 = system_clock::now();
  cout << dst << endl;
  auto duration1 = duration_cast<nanoseconds>(end1 - start1);
  cout << "Time cost: " << duration1.count() << " ns" << endl;

  auto start2 = system_clock::now();
  for (int i = 0; i < 100; i++) {
    lowerUpper.arrayNoSSE(&src[0], &src[261], &dst[0]);
  }
  auto end2 = system_clock::now();
  cout << dst << endl;
  auto duration2 = duration_cast<nanoseconds>(end2 - start2);
  cout << "Time cost: " << duration2.count() << " ns" << endl;
}

很简单，就是将a~z重复10遍作为源字符串，将其分别用SSE和普通方式转换成大写100次，结果如下。

/Users/lmagic/workspace/CLionProjects/ssetest/cmake-build-debug/ssetest
ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ
Time cost: 18000 ns
ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ
Time cost: 59000 ns

经过多次测试，不使用SSE的版本的耗时总是使用SSE的版本的3倍多。鉴于ClickHouse在很多地方都渗透了SIMD和SSE，积少成多，效率提升自然就非常可观了。

The End

笔者并非精通C++和微处理器方面，写这篇文章只是觉得很有意思而已，看官随意看看就行了。

民那晚安晚安。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,293评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,604评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,958评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,729评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,719评论 5赞 366
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,630评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,000评论 3赞 397
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,665评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,909评论 1赞 299
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,646评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,726评论 1赞 330
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,400评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,986评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,959评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,197评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 44,996评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,481评论 2赞 342