俄羅斯Yandex開發(fā)的ClickHouse是一款性能黑馬的OLAP數(shù)據(jù)庫，其對SIMD的靈活運用給其帶來了難以置信的性能。本文我們聊聊它如何對過濾操作進行SIMD優(yōu)化。

基本思想

1、有一個數(shù)組data，即ColumnVector::data，存放數(shù)據(jù)

2、使用uint8類型，即1個字節(jié)類型的filter數(shù)組：ICloumn::Filter。他的大小是data數(shù)組大小，里面存放布爾值，標記data數(shù)組里面哪些數(shù)據(jù)滿足過濾條件，應該篩選出來

3、最終生成一個新的數(shù)組res，根據(jù)filter數(shù)組，對data數(shù)組進行篩選，滿足條件的拷貝到res數(shù)組中。標量邏輯的簡單偽碼：

let res = []
for (let i = 0; i < data.size(); i ++) {if (filter[i] != 0) {res.append(data[i])}
}

Clickhouse如何實現(xiàn)的呢？

4、上面代碼耗時因素在于循環(huán)次數(shù)非常多，等于data數(shù)組的大小

5、如果可以降低循環(huán)次數(shù)，同時保證單次循環(huán)耗時變化不大，總體執(zhí)行效率更高。要滿足上面條件，需要在同一個指令周期做更多運算，SIMD指令可以做這樣的運算。

6、SIMD指令目前最大支持512位數(shù)據(jù)，而filter本身一個值為8位，單詞循環(huán)處理數(shù)據(jù)量為512 / 8 = 64個

7、每次取出來64個filter數(shù)組項（64字節(jié)），將其組成一個64位無符號整數(shù)值mask，這樣每個filter數(shù)組項占用一個比特位

8、有兩種特殊情況：1）mask 64位比特位都是1，本次循環(huán)中，64個data項都應該拷貝到res中。2）mask 64位比特位都是0，可以直接跳過循環(huán)。當然，這兩種特殊情況經(jīng)常出現(xiàn)在業(yè)務常見中

9、第三中情況是有一部分滿足條件，此時是否需要循環(huán)64次？有沒有進一步的優(yōu)化方法？看看clickhouse咋處理

10、有多少項需要拷貝到新數(shù)組，取決于mask中比特位為1的個數(shù)，通過__builtin_clzll內(nèi)置函數(shù)得到入?yún)?#xff08;64位）二進制表示形式中開頭0的個數(shù)，從而得到最高比特位為1的索引，繼而知道哪項數(shù)據(jù)需要拷貝。

11、最高1比特位的數(shù)據(jù)項拷貝后，需要將它置成0，這里有2個比較高效的方法blsr函數(shù)：一個是_blsr_u64指令，另一個是mask & (mask-1)

12、循環(huán)設置最高1的比特位，直到mask中所有比特位都為0

ColumnVector<T>::filter函數(shù)

過濾函數(shù)主要是filter函數(shù)。其實分為3部分，AVX512VBMI2指令集、默認的操作和尾部數(shù)據(jù)處理。其中尾部數(shù)據(jù)處理是指處理數(shù)據(jù)不夠64個時，剩余的部分處理方式，這種方式無法使用SIMD，沿用標量處理方式。

先看下默認操作方式：doFilterAligned即：模板函數(shù)

?

這部分其實是對有一部分值滿足條件場景的優(yōu)化，主要有3個方面：

1）前導0個數(shù)，即data數(shù)組data[0]--data[i]都滿足條件，需要拷貝到結(jié)果中

2）后導0個數(shù)，即data數(shù)組data[i]--data[63]都滿足條件，需要拷貝到結(jié)果中

3）其他場景，比如0011 1100的場景，即兩邊都有不滿足條件的，那就需要特殊處理了：計算出最低位起0的個數(shù)index，然后將data_pos[index]拷貝到結(jié)果中，即該數(shù)組滿足條件，最后將index位置為0。

前綴和后綴拷貝的判斷：

藍色框表示的意義：其實是去除前導0后，剩余的都是1，即mask值。也就是從0的索引開始，到64 - leading_zeroes都需要拷貝到結(jié)果中。藍框計算效果，以2個字節(jié)大小為例，前導5個0:

后導0的處理：其實可以調(diào)用__buitlin_ctzll函數(shù)

uint8_t suffixToCopy(UInt64 mask)
{const auto prefix_to_copy = prefixToCopy(~mask);//mask值取反return prefix_to_copy >= 64 ? prefix_to_copy : 64 - prefix_to_copy;//需要拷貝個數(shù)
}

效果如下圖所示：

64字節(jié)值轉(zhuǎn)換成64位掩碼值的計算函數(shù)Bytes64MaskToBits64Mask實現(xiàn)也很有講究：

/// Transform 64-byte mask to 64-bit mask
inline UInt64 bytes64MaskToBits64Mask(const UInt8 * bytes64)
{
#if defined(__AVX512F__) && defined(__AVX512BW__)const __m512i vbytes = _mm512_loadu_si512(reinterpret_cast<const void *>(bytes64));UInt64 res = _mm512_testn_epi8_mask(vbytes, vbytes);
#elif defined(__AVX__) && defined(__AVX2__)const __m256i zero32 = _mm256_setzero_si256();UInt64 res =(static_cast<UInt64>(_mm256_movemask_epi8(_mm256_cmpeq_epi8(_mm256_loadu_si256(reinterpret_cast<const __m256i *>(bytes64)), zero32))) & 0xffffffff)| (static_cast<UInt64>(_mm256_movemask_epi8(_mm256_cmpeq_epi8(_mm256_loadu_si256(reinterpret_cast<const __m256i *>(bytes64+32)), zero32))) << 32);
#elif defined(__SSE2__)const __m128i zero16 = _mm_setzero_si128();UInt64 res =(static_cast<UInt64>(_mm_movemask_epi8(_mm_cmpeq_epi8(_mm_loadu_si128(reinterpret_cast<const __m128i *>(bytes64)), zero16))) & 0xffff)| ((static_cast<UInt64>(_mm_movemask_epi8(_mm_cmpeq_epi8(_mm_loadu_si128(reinterpret_cast<const __m128i *>(bytes64 + 16)), zero16))) << 16) & 0xffff0000)| ((static_cast<UInt64>(_mm_movemask_epi8(_mm_cmpeq_epi8(_mm_loadu_si128(reinterpret_cast<const __m128i *>(bytes64 + 32)), zero16))) << 32) & 0xffff00000000)| ((static_cast<UInt64>(_mm_movemask_epi8(_mm_cmpeq_epi8(_mm_loadu_si128(reinterpret_cast<const __m128i *>(bytes64 + 48)), zero16))) << 48) & 0xffff000000000000);
#elif defined(__aarch64__) && defined(__ARM_NEON)const uint8x16_t bitmask = {0x01, 0x02, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80, 0x01, 0x02, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};const auto * src = reinterpret_cast<const unsigned char *>(bytes64);const uint8x16_t p0 = vceqzq_u8(vld1q_u8(src));const uint8x16_t p1 = vceqzq_u8(vld1q_u8(src + 16));const uint8x16_t p2 = vceqzq_u8(vld1q_u8(src + 32));const uint8x16_t p3 = vceqzq_u8(vld1q_u8(src + 48));uint8x16_t t0 = vandq_u8(p0, bitmask);uint8x16_t t1 = vandq_u8(p1, bitmask);uint8x16_t t2 = vandq_u8(p2, bitmask);uint8x16_t t3 = vandq_u8(p3, bitmask);uint8x16_t sum0 = vpaddq_u8(t0, t1);uint8x16_t sum1 = vpaddq_u8(t2, t3);sum0 = vpaddq_u8(sum0, sum1);sum0 = vpaddq_u8(sum0, sum0);UInt64 res = vgetq_lane_u64(vreinterpretq_u64_u8(sum0), 0);
#elseUInt64 res = 0;for (size_t i = 0; i < 64; ++i)res |= static_cast<UInt64>(0 == bytes64[i]) << i;
#endifreturn ~res;
}

我們看到，按照優(yōu)先級盡可能利用位數(shù)多的指令集進行計算，同時在所有指令集都不可用及未64字節(jié)對齊(align)的部分進行了保底處理。其利用了以下指令集:

????AVX512F / AVX512BW

????AVX/AVX2

????SSE2

其中，_mm512_testn_epi8_mask函數(shù)功能：計算a和b兩個入?yún)⒅蛋?位整數(shù)逐位與（AND），產(chǎn)生中間8位值，如果中間值為0，則在結(jié)果掩碼k中設置相應位：

FOR j := 0 to 63

? i := j*8

? k[j] := ((a[i+7:i] AND b[i+7:i]) == 0) ? 1 : 0

ENDFOR

所以，bytes64MaskToBits64Mask最終計算出的值需要取反。另外，其他指令集，比如AVX下，_mm256_cmpeq_epi8比較32位是否等于0，等于0表示不滿足條件，當然等于零時該函數(shù)返回0xFF，所以同樣最終結(jié)果需要取反。

另外一種操作方式：doFilterAligned即：模板函數(shù)

主要是通過_mm512_mask_compressstoreu_epi8類似函數(shù)分別對1、2、4、8字節(jié)長度類型針對掩碼進行數(shù)據(jù)拷貝，這里不再贅述。

參考

https://zhuanlan.zhihu.com/p/454657709

https://blog.csdn.net/u010002184/article/details/113977586

https://blog.51cto.com/u_15103025/2643507

https://zhuanlan.zhihu.com/p/449154820

https://www.zhihu.com/question/450069375/answer/1813516193

https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html