前言

ClickHouse之所以會(huì)像閃電一樣快（"blazing fast"）打毛，是多方面優(yōu)化的結(jié)果柿赊，包括且不限于：高效且磁盤(pán)友好的列式存儲(chǔ)，高效的數(shù)據(jù)壓縮幻枉，精心設(shè)計(jì)的各類(lèi)索引碰声，并行分布式查詢(xún)，運(yùn)行時(shí)代碼生成等熬甫。

另外胰挑，ClickHouse為了最大限度地壓榨硬件——尤其是CPU——的性能，實(shí)現(xiàn)了向量化查詢(xún)執(zhí)行（vectorized query execution）機(jī)制椿肩。這個(gè)名詞相對(duì)于上面的那些可能沒(méi)那么平易近人瞻颂，但它毫無(wú)疑問(wèn)是CK相對(duì)于傳統(tǒng)OLAP引擎的大殺器。鑒于現(xiàn)有資料中講解CK向量化執(zhí)行的內(nèi)容很少郑象，本文就來(lái)試圖探究一下贡这，先從基礎(chǔ)知識(shí)SIMD說(shuō)起。

SIMD

SIMD即"single instruction, multiple data"（單指令流多數(shù)據(jù)流）扣唱，是Flynn分類(lèi)法對(duì)計(jì)算機(jī)的四大分類(lèi)之一藕坯。它本質(zhì)上是采用一個(gè)控制器來(lái)控制多個(gè)處理器团南，同時(shí)對(duì)一組數(shù)據(jù)中的每一條分別執(zhí)行相同的操作，從而實(shí)現(xiàn)空間上的并行性的技術(shù)炼彪。

可見(jiàn)吐根，“單指令流”指的是同時(shí)只能執(zhí)行一種操作，“多數(shù)據(jù)流”則指的是在一組同構(gòu)的數(shù)據(jù)（通常稱(chēng)為vector辐马，即向量）上進(jìn)行操作拷橘，如下圖所示，PU=processing unit喜爷。

SIMD在現(xiàn)代計(jì)算機(jī)的應(yīng)用甚廣泛冗疮，最典型的則是在GPU的像素處理流水線中。舉個(gè)例子檩帐，如果要更改一整幅圖像的亮度术幔，只需要取出各像素的RGB值存入向量單元（向量單元很寬，可以存儲(chǔ)多個(gè)像素的數(shù)據(jù)）湃密，再同時(shí)將它們做相同的加減操作即可诅挑，效率很高。SIMD和MIMD流水線是GPU微架構(gòu)的基礎(chǔ)泛源，就不再展開(kāi)聊了拔妥。

話說(shuō)回來(lái)，CPU是如何實(shí)現(xiàn)SIMD的呢达箍？答案是擴(kuò)展指令集没龙。Intel的第一版SIMD擴(kuò)展指令集稱(chēng)為MMX，于1997年發(fā)布缎玫。后來(lái)至今的改進(jìn)版本有SSE（Streaming SIMD Extensions）硬纤、AVX（Advanced Vector Extensions），以及AMD的3DNow!等碘梢。ClickHouse的向量化執(zhí)行機(jī)制主要依賴(lài)于SSE指令集咬摇，下面簡(jiǎn)要介紹之伐蒂。

SSE指令集

SSE指令集是MMX的繼任者煞躬，其第一版早在Pentium III時(shí)代就被引入了。隨著新指令的擴(kuò)充逸邦，又有了SSE2恩沛、SSE3、SSSE3缕减、SSE4（包含4.1和4.2）等新版本雷客。我們可以通過(guò)cpuid類(lèi)軟件獲得處理器對(duì)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個(gè)128位寄存器為基礎(chǔ)，命名為XMM0~XMM7枣宫。在AMD64（即64位擴(kuò)展）指令集中，又新增了XMM8~XMM15徐块。一個(gè)XMM寄存器原本只能存儲(chǔ)一種數(shù)據(jù)類(lèi)型：

• 4個(gè)32位單精度浮點(diǎn)數(shù)

SSE2又?jǐn)U展到能夠存儲(chǔ)以下類(lèi)型：

• 2個(gè)64位雙精度浮點(diǎn)數(shù)
• 2個(gè)64位/4個(gè)32位/8個(gè)16位整數(shù)
• 16個(gè)字節(jié)或字符

SSE的指令分為兩大類(lèi)渐溶，一是標(biāo)量（scalar）指令，二是打包（packed）指令颅和。標(biāo)量指令只對(duì)XMM寄存器中的最低位數(shù)據(jù)進(jìn)行計(jì)算傅事，打包指令則是對(duì)所有數(shù)據(jù)進(jìn)行計(jì)算。下圖示出SSE1中峡扩，單精度浮點(diǎn)數(shù)乘法的標(biāo)量和打包運(yùn)算蹭越。

圖來(lái)自http://www.songho.ca/misc/sse/sse.html，是一篇很好的SSE入門(mén)

觀察指令名稱(chēng)教届，mul表示乘法般又，接下來(lái)的s表示標(biāo)量，p表示打包巍佑，最后一個(gè)s則表示類(lèi)型為單精度浮點(diǎn)數(shù)（single-precision）茴迁。由圖也可以發(fā)現(xiàn)，打包指令才是真正SIMD的萤衰，而標(biāo)量指令是SISD的堕义。

再舉個(gè)小栗子，如果我們要實(shí)現(xiàn)兩個(gè)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

注意數(shù)據(jù)移動(dòng)指令movaps中的a表示對(duì)齊（align）。第一條指令的意思就是通過(guò)[v1]直接尋址得到向量的起點(diǎn)椿争，并分別按照0怕膛、4、8秦踪、16字節(jié)的偏移量寫(xiě)入XMM0寄存器的低到高四個(gè)域褐捻。在數(shù)據(jù)本身已經(jīng)按照16字節(jié)對(duì)齊的情況下，調(diào)用這種指令效率非常高椅邓。從寄存器寫(xiě)入內(nèi)存也是同理的柠逞，如下圖。

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

• 直接編寫(xiě)（內(nèi)嵌）匯編語(yǔ)句板壮；
• 利用廠商提供的擴(kuò)展庫(kù)函數(shù)。Intel將這類(lèi)指令和函數(shù)統(tǒng)稱(chēng)為intrinsics合住，官方提供的速查手冊(cè)見(jiàn)這里绰精；
• 開(kāi)啟編譯器的優(yōu)化（-msse撒璧、-msse2等等），編譯器會(huì)自動(dòng)將符合條件的情景（如數(shù)組相加笨使、矩陣相乘等）編譯為intrinsic指令沪悲。

需要注意的是，SIMD和SSE雖然強(qiáng)大阱表，但是對(duì)于那些嚴(yán)重依賴(lài)流程控制（flow-control-heavy）的任務(wù)殿如，即有大量分支、跳轉(zhuǎn)和條件判斷的任務(wù)明顯不太適用最爬。也就是說(shuō)涉馁，它們主要被用來(lái)優(yōu)化可并行計(jì)算的簡(jiǎn)單場(chǎng)景，以及可能被頻繁調(diào)用的基礎(chǔ)邏輯爱致。

說(shuō)了這么多烤送，可以進(jìn)入ClickHouse的世界了。

ClickHouse向量化執(zhí)行示例

編譯器優(yōu)化對(duì)筆者這種水平不高的人來(lái)說(shuō)顯然太難糠悯，所以還是去ClickHouse源碼中尋找向量化執(zhí)行的蛛絲馬跡比較好帮坚。我們可以查找形如#ifdef __SSE2__的宏定義，或者根據(jù)手冊(cè)查找intrinsic函數(shù)對(duì)應(yīng)的頭文件互艾，如SSE4.1的頭文件是<smmintrin.h>试和，以此類(lèi)推。

為簡(jiǎn)單起見(jiàn)纫普，選取兩段應(yīng)用了SSE2 intrinsics函數(shù)的示例來(lái)作分析阅悍。

計(jì)算Filter中1的數(shù)量

在ClickHouse的底層，過(guò)濾器（Filter）是一個(gè)預(yù)分配空間的昨稼、無(wú)符號(hào)8位整形數(shù)的數(shù)組节视，用于表示W(wǎng)HERE和HAVING子句的條件及真值，每一位的取值為0或1假栓，即表示條件為假或真寻行。Filter和列（IColumn）是共生的，在ColumnsCommon.cpp中匾荆，提供了通用的計(jì)算Filter中1的數(shù)量的方法拌蜘，代碼如下。

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__)說(shuō)明當(dāng)前環(huán)境支持SSE2指令集棋凳，而defined(__POPCNT__)說(shuō)明支持硬件級(jí)位計(jì)數(shù)的POPCNT指令拦坠。下面根據(jù)手冊(cè)簡(jiǎn)要介紹一下代碼中涉及到的intrinsic函數(shù)：

• _mm_setzero_si128()：初始化128位（16字節(jié)）的全0位圖连躏，即一個(gè)XMM寄存器剩岳。
• _mm_loadu_si128(mem_addr)：從內(nèi)存地址mem_addr處加載128位的整形數(shù)據(jù)。
• _mm_cmpgt_epi8(a, b)：按8位比較a和b兩個(gè)128位整形數(shù)入热，若a的對(duì)應(yīng)8位比b的對(duì)應(yīng)8位大拍棕，則填充對(duì)應(yīng)位為全1晓铆，否則填充全0。
• _mm_movemask_epi8(a)：根據(jù)128位整形數(shù)a的每個(gè)8位組的最高位創(chuàng)建掩碼绰播，一共16位長(zhǎng)骄噪，返回int結(jié)果（高16位用0填充）。

最后蠢箩，__builtin_popcountll()函數(shù)相當(dāng)于直接調(diào)用POPCNT指令算出64位數(shù)的漢明權(quán)重链蕊。

由上可見(jiàn)，這個(gè)函數(shù)的每次循環(huán)都將連續(xù)64個(gè)Filter的真值數(shù)據(jù)（即Int8類(lèi)型）壓縮到一個(gè)UInt64中一起做位計(jì)數(shù)谬泌。其中每次調(diào)用上述指令都會(huì)處理16個(gè)Int8滔韵，正好是128位，SIMD的思想就是這樣體現(xiàn)出來(lái)的掌实。由于SSE指令集中沒(méi)有真正的位運(yùn)算指令陪蜻，所以壓縮的過(guò)程略顯繁瑣，但是仍然比笨方法（逐個(gè)遍歷判斷）效率高很多贱鼻。

字符串大小寫(xiě)轉(zhuǎn)換

ClickHouse的函數(shù)中也充分應(yīng)用了SSE指令集宴卖，特別是字符串函數(shù)。以ASCII拉丁字符大小寫(xiě)轉(zhuǎn)換函數(shù)（即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;
    }
};

原理比較簡(jiǎn)單父丰，就是利用flip_case_mask這個(gè)掩碼來(lái)翻轉(zhuǎn)字符的大小寫(xiě)（大小寫(xiě)字母的ASCII碼值相差32）齿兔。not_case_lower_bound和not_case_lower_bound則用來(lái)標(biāo)定轉(zhuǎn)換的字符范圍，比如a~z或A~Z础米。不過(guò)在SSE2的加持下分苇，就可以一次性加載16個(gè)字符進(jìn)行轉(zhuǎn)換，同樣是SIMD的思想屁桑，效率自然比普通的遍歷高医寿。由于每句話都有官方注釋?zhuān)筒辉俣鄰U話了。

測(cè)試一下

將上面的LowerUpperImpl結(jié)構(gòu)體拆出來(lái)蘑斧，測(cè)試代碼如下靖秩。

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

很簡(jiǎn)單，就是將a~z重復(fù)10遍作為源字符串竖瘾，將其分別用SSE和普通方式轉(zhuǎn)換成大寫(xiě)100次沟突，結(jié)果如下。

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

經(jīng)過(guò)多次測(cè)試捕传，不使用SSE的版本的耗時(shí)總是使用SSE的版本的3倍多惠拭。鑒于ClickHouse在很多地方都滲透了SIMD和SSE，積少成多，效率提升自然就非持案ǎ可觀了棒呛。

The End

筆者并非精通C++和微處理器方面，寫(xiě)這篇文章只是覺(jué)得很有意思而已域携，看官隨意看看就行了簇秒。

民那晚安晚安。