Disclaimer

此项目仅供学习与交流使用，请遵循MIT协议，如果您在任何项目中使用相关代码，请保留此项目的LICENSE文件。

SIMD Vectorization Demo

This demo is made by Wang Lipeng and CHE Yulin from Hong Kong University of Science and Technology. Feel free to give this repo a star if you like it.

intel intrinsics guide: see https://software.intel.com/sites/landingpage/IntrinsicsGuide/

bechmarking CPU info: see src/playground, using single-thread

Tokenizing

/ | type --- | --- input | form body output | dubbo package

algorithms | elapsed time --- | --- serial transform time | 380 ms sse4 transform time | 240 ms avx2 transform time | 90 ms

• workaround for __tzcnt_u32 (requiring bmi) in sse4 (handle 16bits currently, else modify zero if-sentence)

inline int __tzcnt_u32_using_popcnt_cmpeq(unsigned int x) {
    int ret_cnt = 0;
    int half_bits = x & (0xff);
    if (half_bits == 0) {
        half_bits = (x >> 8) & (0xff);
        ret_cnt = 8;
    }

    __m128i pivot_u = _mm_set1_epi16(half_bits);
    __m128i inspected_ele = _mm_set_epi16(
            0xff, 0x7f, 0x3f, 0x1f, 0xf, 0x7, 0x3, 0x1);
    __m128i trunc_pivot_u = _mm_and_si128(pivot_u, inspected_ele);

    __m128i pivot_new = _mm_set1_epi16(0);
    __m128i cmp_res = _mm_cmpeq_epi16(trunc_pivot_u, pivot_new);

    int mask = _mm_movemask_epi8(cmp_res); // 16 bits
    ret_cnt += _mm_popcnt_u32(mask) >> 1;
    return ret_cnt;
}

• idea: advance with simd cmp and tzcnt

        // 1st: advance fo find first '='
        while (true) {
            __m128i pivot_u = _mm_set1_epi8('=');
            __m128i inspected_ele = _mm_loadu_si128((__m128i *) (str + i));
            __m128i cmp_res = _mm_cmpeq_epi8(pivot_u, inspected_ele);
            int mask = _mm_movemask_epi8(cmp_res); // 16 bits

            int advance = (mask == 0 ?
                           16 : __tzcnt_u32_using_popcnt_cmpeq(mask));
            i += advance;
            if (advance < 16) { break; }
        }
        off[next] = i;
        next++;

• details: see src/fast_tokenizer/tokenizer.cpp, src/playground/test_split.cpp

Base64 Decoding/Encoding (i.e, Serialization/Deserialization)

• base64 encoding includes 1) unpacking and 2) ascii translation (to)

• base64 decoding includes 1) ascii translation (from) and 2) packing

• the translation table

base64 | ascii-dec | ascii-hex | offset (diff) --- | --- | --- | --- 0-25 | 65-90 | 0x41-0x5a | 65 26-51 | 97-122 | 0x61-0x7a | 71 52-61 | 48-57 | 0x30-0x39 | -4 62 | 43, i.e., '+' | 0x2b | -19 63 | 47, i.e., '/' | 0x2f | -16 others | invalid | invalid | invalid

Base64 Decoding Vectorization

ascii code to base64 translation vectorization (simplified)

        // attention: each SIMD lane is 128-bits
        const __m256i lut_roll = _mm256_setr_epi8(
            0,   16,  19,   4, -65, -65, -71, -71,
            0,   0,   0,   0,   0,   0,   0,   0,
            0,   16,  19,   4, -65, -65, -71, -71,
            0,   0,   0,   0,   0,   0,   0,   0
        );
        const __m256i mask_2F = _mm256_set1_epi8(0x2f);

        // 1st: shift right for 4 32bit-wise-elements in each SIMD lane
        // shift to get high 4bits
        __m256i hi_nibbles  = _mm256_srli_epi32(str, 4);
        
        // 2nd: cmpeq to distinguish 0x2f ('/') from 0x2b ('+') 
        // when the byte is 0x2f, the result byte in eq_2F is 0xff (-1)  
        const __m256i eq_2F = _mm256_cmpeq_epi8(str, mask_2F);

        // 3rd: add -1 when the byte is 0x2f, 
        // lookup lut_roll for offsets to add, shuffling in each SIMD Lane
        // shuffling using the previous high 4-bits in the byte (see 1st step)
        const __m256i roll  = _mm256_shuffle_epi8(lut_roll, 
                                _mm256_add_epi8(eq_2F, hi_nibbles));
        
        // 4th: add offsets
        str = _mm256_add_epi8(str, roll);

Benchmark

• implementations

benchmark main file: src/playground/test_serialization.cpp

algorithms | link --- | --- naive-comp | src/naive_base64/naive_base64.cpp naive-lookup | src/naive_base64/naive_base64.cpp chromium | src/fast_base64/chromiumbase64.c fast-avx2 | src/fast_base64/fastavxbase64.c

• measure: we report TPS (throughput including both serialization and deserialization time)

algorithms | idea --- | --- naive-comp | ascii-base64 translation using computations naive-lookup | ascii-base64 translation using two look-up tables chromium | use separate lookup tables for saving some computations fast-avx2 | apply avx2, and serial fallback using chromium

• message len 200

algorithms | TPS-total | TPS-serializtion | TPS-deserializtion --- | --- | --- | --- naive_comp | 201.448 MB/s | 467.150 MB/s | 354.179 MB/s naive_lookup | 490.444 MB/s | 1080.221 MB/s | 898.286 MB/s chromium | 493.397 MB/s | 1039.237 MB/s | 939.390 MB/s avx2_chromium | 887.260 MB/s | 1838.769 MB/s | 1714.608 MB/s

• message len 80

algorithms | TPS-total | TPS-serializtion | TPS-deserializtion --- | --- | --- | --- naive_comp | 149.235 MB/s | 288.609 MB/s | 309.029 MB/s naive_lookup | 394.224 MB/s | 740.423 MB/s | 843.135 MB/s chromium | 409.404 MB/s | 725.954 MB/s | 938.900 MB/s avx2_chromium | 556.984 MB/s | 974.215 MB/s | 1300.531 MB/s

• message len 50

algorithms | TPS-total | TPS-serializtion | TPS-deserializtion --- | --- | --- | --- naive_comp | 115.787 MB/s | 218.357 MB/s | 246.493 MB/s naive_lookup | 330.488 MB/s | 598.695 MB/s | 737.719 MB/s chromium | 335.035 MB/s | 595.675 MB/s | 765.698 MB/s avx2_chromium | 385.963 MB/s | 656.360 MB/s | 936.887 MB/s