邵东建设公司网站哪家好,网站扫码怎么做,网页设计与制作课程代码,工商注册服务平台俄罗斯Yandex开发的ClickHouse是一款性能黑马的OLAP数据库#xff0c;其对SIMD的灵活运用给其带来了难以置信的性能。本文我们聊聊它如何对过滤操作进行SIMD优化。 基本思想 1、有一个数组data#xff0c;即ColumnVector::data#xff0c;存放数据 2、使用uint8类型#xf… 俄罗斯Yandex开发的ClickHouse是一款性能黑马的OLAP数据库其对SIMD的灵活运用给其带来了难以置信的性能。本文我们聊聊它如何对过滤操作进行SIMD优化。 基本思想 1、有一个数组data即ColumnVector::data存放数据 2、使用uint8类型即1个字节类型的filter数组ICloumn::Filter。他的大小是data数组大小里面存放布尔值标记data数组里面哪些数据满足过滤条件应该筛选出来 3、最终生成一个新的数组res根据filter数组对data数组进行筛选满足条件的拷贝到res数组中。标量逻辑的简单伪码 let res []
for (let i 0; i data.size(); i ) {if (filter[i] ! 0) {res.append(data[i])}
} Clickhouse如何实现的呢 4、上面代码耗时因素在于循环次数非常多等于data数组的大小 5、如果可以降低循环次数同时保证单次循环耗时变化不大总体执行效率更高。要满足上面条件需要在同一个指令周期做更多运算SIMD指令可以做这样的运算。 6、SIMD指令目前最大支持512位数据而filter本身一个值为8位单词循环处理数据量为512 / 8 64个 7、每次取出来64个filter数组项64字节将其组成一个64位无符号整数值mask这样每个filter数组项占用一个比特位 8、有两种特殊情况1mask 64位比特位都是1本次循环中64个data项都应该拷贝到res中。2mask 64位比特位都是0可以直接跳过循环。当然这两种特殊情况经常出现在业务常见中 9、第三中情况是有一部分满足条件此时是否需要循环64次有没有进一步的优化方法看看clickhouse咋处理 10、有多少项需要拷贝到新数组取决于mask中比特位为1的个数通过__builtin_clzll内置函数得到入参64位二进制表示形式中开头0的个数从而得到最高比特位为1的索引继而知道哪项数据需要拷贝。 11、最高1比特位的数据项拷贝后需要将它置成0这里有2个比较高效的方法blsr函数一个是_blsr_u64指令另一个是mask (mask-1) 12、循环设置最高1的比特位直到mask中所有比特位都为0 ColumnVectorT::filter函数 过滤函数主要是filter函数。其实分为3部分AVX512VBMI2指令集、默认的操作和尾部数据处理。其中尾部数据处理是指处理数据不够64个时剩余的部分处理方式这种方式无法使用SIMD沿用标量处理方式。 先看下默认操作方式doFilterAligned即模板函数 这部分其实是对有一部分值满足条件场景的优化主要有3个方面 1前导0个数即data数组data[0]--data[i]都满足条件需要拷贝到结果中 2后导0个数即data数组data[i]--data[63]都满足条件需要拷贝到结果中 3其他场景比如0011 1100的场景即两边都有不满足条件的那就需要特殊处理了计算出最低位起0的个数index然后将data_pos[index]拷贝到结果中即该数组满足条件最后将index位置为0。 前缀和后缀拷贝的判断 蓝色框表示的意义其实是去除前导0后剩余的都是1即mask值。也就是从0的索引开始到64 - leading_zeroes都需要拷贝到结果中。蓝框计算效果以2个字节大小为例前导5个0: 后导0的处理其实可以调用__buitlin_ctzll函数 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;//需要拷贝个数
} 效果如下图所示 64字节值转换成64位掩码值的计算函数Bytes64MaskToBits64Mask实现也很有讲究 /// 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_castconst void *(bytes64));UInt64 res _mm512_testn_epi8_mask(vbytes, vbytes);
#elif defined(__AVX__) defined(__AVX2__)const __m256i zero32 _mm256_setzero_si256();UInt64 res (static_castUInt64(_mm256_movemask_epi8(_mm256_cmpeq_epi8(_mm256_loadu_si256(reinterpret_castconst __m256i *(bytes64)), zero32))) 0xffffffff)| (static_castUInt64(_mm256_movemask_epi8(_mm256_cmpeq_epi8(_mm256_loadu_si256(reinterpret_castconst __m256i *(bytes6432)), zero32))) 32);
#elif defined(__SSE2__)const __m128i zero16 _mm_setzero_si128();UInt64 res (static_castUInt64(_mm_movemask_epi8(_mm_cmpeq_epi8(_mm_loadu_si128(reinterpret_castconst __m128i *(bytes64)), zero16))) 0xffff)| ((static_castUInt64(_mm_movemask_epi8(_mm_cmpeq_epi8(_mm_loadu_si128(reinterpret_castconst __m128i *(bytes64 16)), zero16))) 16) 0xffff0000)| ((static_castUInt64(_mm_movemask_epi8(_mm_cmpeq_epi8(_mm_loadu_si128(reinterpret_castconst __m128i *(bytes64 32)), zero16))) 32) 0xffff00000000)| ((static_castUInt64(_mm_movemask_epi8(_mm_cmpeq_epi8(_mm_loadu_si128(reinterpret_castconst __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_castconst 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_castUInt64(0 bytes64[i]) i;
#endifreturn ~res;
} 我们看到按照优先级尽可能利用位数多的指令集进行计算同时在所有指令集都不可用及未64字节对齐(align)的部分进行了保底处理。其利用了以下指令集: AVX512F / AVX512BW AVX/AVX2 SSE2 其中_mm512_testn_epi8_mask函数功能计算a和b两个入参值按8位整数逐位与AND产生中间8位值如果中间值为0则在结果掩码k中设置相应位 FOR j : 0 to 63 i : j*8 k[j] : ((a[i7:i] AND b[i7:i]) 0) ? 1 : 0 ENDFOR 所以bytes64MaskToBits64Mask最终计算出的值需要取反。另外其他指令集比如AVX下_mm256_cmpeq_epi8比较32位是否等于0等于0表示不满足条件当然等于零时该函数返回0xFF所以同样最终结果需要取反。 另外一种操作方式doFilterAligned即模板函数 主要是通过_mm512_mask_compressstoreu_epi8类似函数分别对1、2、4、8字节长度类型针对掩码进行数据拷贝这里不再赘述。 参考 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
