前言

ClickHouse之所以會像閃電一樣快（"blazing fast"），是多方面優(yōu)化的結(jié)果，包括且不限于：高效且磁盤友好的列式存儲，高效的數(shù)據(jù)壓縮，精心設計的各類索引，并行分布式查詢，運行時代碼生成等。

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

SIMD

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

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

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

話說回來，CPU是如何實現(xiàn)SIMD的呢？答案是擴展指令集。Intel的第一版SIMD擴展指令集稱為MMX，于1997年發(fā)布。后來至今的改進版本有SSE（Streaming SIMD Extensions）、AVX（Advanced Vector Extensions），以及AMD的3DNow!等。ClickHouse的向量化執(zhí)行機制主要依賴于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位寄存器為基礎(chǔ)，命名為XMM0~XMM7。在AMD64（即64位擴展）指令集中，又新增了XMM8~XMM15。一個XMM寄存器原本只能存儲一種數(shù)據(jù)類型：

• 4個32位單精度浮點數(shù)

SSE2又擴展到能夠存儲以下類型：

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

SSE的指令分為兩大類，一是標量（scalar）指令，二是打包（packed）指令。標量指令只對XMM寄存器中的最低位數(shù)據(jù)進行計算，打包指令則是對所有數(shù)據(jù)進行計算。下圖示出SSE1中，單精度浮點數(shù)乘法的標量和打包運算。

圖來自http://www.songho.ca/misc/sse/sse.html，是一篇很好的SSE入門

觀察指令名稱，mul表示乘法，接下來的s表示標量，p表示打包，最后一個s則表示類型為單精度浮點數(shù)（single-precision）。由圖也可以發(fā)現(xiàn)，打包指令才是真正SIMD的，而標量指令是SISD的。

再舉個小栗子，如果我們要實現(xiàn)兩個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ù)移動指令movaps中的a表示對齊（align）。第一條指令的意思就是通過[v1]直接尋址得到向量的起點，并分別按照0、4、8、16字節(jié)的偏移量寫入XMM0寄存器的低到高四個域。在數(shù)據(jù)本身已經(jīng)按照16字節(jié)對齊的情況下，調(diào)用這種指令效率非常高。從寄存器寫入內(nèi)存也是同理的，如下圖。

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

• 直接編寫（內(nèi)嵌）匯編語句；
• 利用廠商提供的擴展庫函數(shù)。Intel將這類指令和函數(shù)統(tǒng)稱為intrinsics，官方提供的速查手冊見這里；
• 開啟編譯器的優(yōu)化（-msse、-msse2等等），編譯器會自動將符合條件的情景（如數(shù)組相加、矩陣相乘等）編譯為intrinsic指令。

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

說了這么多，可以進入ClickHouse的世界了。

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

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

為簡單起見，選取兩段應用了SSE2 intrinsics函數(shù)的示例來作分析。

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

在ClickHouse的底層，過濾器（Filter）是一個預分配空間的、無符號8位整形數(shù)的數(shù)組，用于表示W(wǎng)HERE和HAVING子句的條件及真值，每一位的取值為0或1，即表示條件為假或真。Filter和列（IColumn）是共生的，在ColumnsCommon.cpp中，提供了通用的計算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__)說明當前環(huán)境支持SSE2指令集，而defined(__POPCNT__)說明支持硬件級位計數(shù)的POPCNT指令。下面根據(jù)手冊簡要介紹一下代碼中涉及到的intrinsic函數(shù)：

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

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

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

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

ClickHouse的函數(shù)中也充分應用了SSE指令集，特別是字符串函數(shù)。以ASCII拉丁字符大小寫轉(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;
    }
};

原理比較簡單，就是利用flip_case_mask這個掩碼來翻轉(zhuǎn)字符的大小寫（大小寫字母的ASCII碼值相差32）。not_case_lower_bound和not_case_lower_bound則用來標定轉(zhuǎn)換的字符范圍，比如a~z或A~Z。不過在SSE2的加持下，就可以一次性加載16個字符進行轉(zhuǎn)換，同樣是SIMD的思想，效率自然比普通的遍歷高。由于每句話都有官方注釋，就不再多廢話了。

測試一下

將上面的LowerUpperImpl結(jié)構(gòu)體拆出來，測試代碼如下。

#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和普通方式轉(zhuǎn)換成大寫100次，結(jié)果如下。

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

經(jīng)過多次測試，不使用SSE的版本的耗時總是使用SSE的版本的3倍多。鑒于ClickHouse在很多地方都滲透了SIMD和SSE，積少成多，效率提升自然就非?？捎^了。

The End

筆者并非精通C++和微處理器方面，寫這篇文章只是覺得很有意思而已，看官隨意看看就行了。

民那晚安晚安。