-
-
Notifications
You must be signed in to change notification settings - Fork 266
Commit
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Make an AVX512 inflate fast with low cost masked writes
This takes advantage of the fact that on AVX512 architectures, masked moves are incredibly cheap. There are many places where we have to fallback to the safe C implementation of chunkcopy_safe because of the assumed overwriting that occurs. We're to sidestep most of the branching needed here by simply controlling the bounds of our writes with a mask.
- Loading branch information
1 parent
94aacd8
commit 0ed5ac8
Showing
13 changed files
with
301 additions
and
62 deletions.
There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 +1,44 @@ | ||
| #ifndef _AVX2_TABLES_H | ||
| #define _AVX2_TABLES_H | ||
|
|
||
| #include "../generic/chunk_permute_table.h" | ||
|
|
||
| /* Populate don't cares so that this is a direct lookup (with some indirection into the permute table), because dist can | ||
| * never be 0 - 2, we'll start with an offset, subtracting 3 from the input */ | ||
| static const lut_rem_pair perm_idx_lut[29] = { | ||
| { 0, 2}, /* 3 */ | ||
| { 0, 0}, /* don't care */ | ||
| { 1 * 32, 2}, /* 5 */ | ||
| { 2 * 32, 2}, /* 6 */ | ||
| { 3 * 32, 4}, /* 7 */ | ||
| { 0 * 32, 0}, /* don't care */ | ||
| { 4 * 32, 5}, /* 9 */ | ||
| { 5 * 32, 22}, /* 10 */ | ||
| { 6 * 32, 21}, /* 11 */ | ||
| { 7 * 32, 20}, /* 12 */ | ||
| { 8 * 32, 6}, /* 13 */ | ||
| { 9 * 32, 4}, /* 14 */ | ||
| {10 * 32, 2}, /* 15 */ | ||
| { 0 * 32, 0}, /* don't care */ | ||
| {11 * 32, 15}, /* 17 */ | ||
| {11 * 32 + 16, 14}, /* 18 */ | ||
| {11 * 32 + 16 * 2, 13}, /* 19 */ | ||
| {11 * 32 + 16 * 3, 12}, /* 20 */ | ||
| {11 * 32 + 16 * 4, 11}, /* 21 */ | ||
| {11 * 32 + 16 * 5, 10}, /* 22 */ | ||
| {11 * 32 + 16 * 6, 9}, /* 23 */ | ||
| {11 * 32 + 16 * 7, 8}, /* 24 */ | ||
| {11 * 32 + 16 * 8, 7}, /* 25 */ | ||
| {11 * 32 + 16 * 9, 6}, /* 26 */ | ||
| {11 * 32 + 16 * 10, 5}, /* 27 */ | ||
| {11 * 32 + 16 * 11, 4}, /* 28 */ | ||
| {11 * 32 + 16 * 12, 3}, /* 29 */ | ||
| {11 * 32 + 16 * 13, 2}, /* 30 */ | ||
| {11 * 32 + 16 * 14, 1} /* 31 */ | ||
| }; | ||
|
|
||
| static const uint16_t half_rem_vals[13] = { | ||
| 1, 0, 1, 4, 2, 0, 7, 6, 5, 4, 3, 2, 1 | ||
| }; | ||
|
|
||
| #endif |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 +1,189 @@ | ||
| /* chunkset_avx512.c -- AVX512 inline functions to copy small data chunks. | ||
| * For conditions of distribution and use, see copyright notice in zlib.h | ||
| */ | ||
| #include "zbuild.h" | ||
|
|
||
| #ifdef X86_AVX512 | ||
|
|
||
| #include "avx2_tables.h" | ||
| #include <immintrin.h> | ||
| #include "x86_intrins.h" | ||
|
|
||
| typedef __m256i chunk_t; | ||
| typedef __m128i halfchunk_t; | ||
| typedef __mmask32 mask_t; | ||
| typedef __mmask16 halfmask_t; | ||
|
|
||
| #define HAVE_CHUNKMEMSET_2 | ||
| #define HAVE_CHUNKMEMSET_4 | ||
| #define HAVE_CHUNKMEMSET_8 | ||
| #define HAVE_CHUNKMEMSET_16 | ||
| #define HAVE_CHUNKMEMSET_1 | ||
| #define HAVE_CHUNK_MAG | ||
| #define HAVE_HALF_CHUNK | ||
| #define HAVE_MASKED_READWRITE | ||
| #define HAVE_CHUNKCOPY | ||
| #define HAVE_HALFCHUNKCOPY | ||
|
|
||
| static inline halfmask_t gen_half_mask(unsigned len) { | ||
| return (halfmask_t)_bzhi_u32(0xFFFF, len); | ||
| } | ||
|
|
||
| static inline mask_t gen_mask(unsigned len) { | ||
| return (mask_t)_bzhi_u32(0xFFFFFFFF, len); | ||
| } | ||
|
|
||
| static inline void chunkmemset_2(uint8_t *from, chunk_t *chunk) { | ||
| int16_t tmp; | ||
| memcpy(&tmp, from, sizeof(tmp)); | ||
| *chunk = _mm256_set1_epi16(tmp); | ||
| } | ||
|
|
||
| static inline void chunkmemset_4(uint8_t *from, chunk_t *chunk) { | ||
| int32_t tmp; | ||
| memcpy(&tmp, from, sizeof(tmp)); | ||
| *chunk = _mm256_set1_epi32(tmp); | ||
| } | ||
|
|
||
| static inline void chunkmemset_8(uint8_t *from, chunk_t *chunk) { | ||
| int64_t tmp; | ||
| memcpy(&tmp, from, sizeof(tmp)); | ||
| *chunk = _mm256_set1_epi64x(tmp); | ||
| } | ||
|
|
||
| static inline void chunkmemset_16(uint8_t *from, chunk_t *chunk) { | ||
| *chunk = _mm256_broadcastsi128_si256(_mm_loadu_si128((__m128i*)from)); | ||
| } | ||
|
|
||
| static inline void loadchunk(uint8_t const *s, chunk_t *chunk) { | ||
| *chunk = _mm256_loadu_si256((__m256i *)s); | ||
| } | ||
|
|
||
| static inline void storechunk(uint8_t *out, chunk_t *chunk) { | ||
| _mm256_storeu_si256((__m256i *)out, *chunk); | ||
| } | ||
|
|
||
| static inline void storechunk_mask(uint8_t *out, mask_t mask, chunk_t *chunk) { | ||
| _mm256_mask_storeu_epi8(out, mask, *chunk); | ||
| } | ||
|
|
||
| static inline uint8_t* CHUNKCOPY(uint8_t *out, uint8_t const *from, unsigned len) { | ||
| Assert(len > 0, "chunkcopy should never have a length 0"); | ||
|
|
||
| unsigned rem = len % sizeof(chunk_t); | ||
| mask_t rem_mask = gen_mask(rem); | ||
|
|
||
| /* Since this is only ever called if dist >= a chunk, we don't need a masked load */ | ||
| chunk_t chunk; | ||
| loadchunk(from, &chunk); | ||
| _mm256_mask_storeu_epi8(out, rem_mask, chunk); | ||
| out += rem; | ||
| from += rem; | ||
| len -= rem; | ||
|
|
||
| while (len > 0) { | ||
| loadchunk(from, &chunk); | ||
| storechunk(out, &chunk); | ||
| out += sizeof(chunk_t); | ||
| from += sizeof(chunk_t); | ||
| len -= sizeof(chunk_t); | ||
| } | ||
|
|
||
| return out; | ||
| } | ||
|
|
||
| static inline chunk_t GET_CHUNK_MAG(uint8_t *buf, uint32_t *chunk_rem, uint32_t dist) { | ||
| lut_rem_pair lut_rem = perm_idx_lut[dist - 3]; | ||
| __m256i ret_vec; | ||
| *chunk_rem = lut_rem.remval; | ||
|
|
||
| /* See the AVX2 implementation for more detailed comments. This is that + some masked | ||
| * loads to avoid an out of bounds read on the heap */ | ||
|
|
||
| if (dist < 16) { | ||
| const __m256i permute_xform = | ||
| _mm256_setr_epi8(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | ||
| 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16); | ||
| __m256i perm_vec = _mm256_load_si256((__m256i*)(permute_table+lut_rem.idx)); | ||
| halfmask_t load_mask = gen_half_mask(dist); | ||
| __m128i ret_vec0 = _mm_maskz_loadu_epi8(load_mask, buf); | ||
| perm_vec = _mm256_add_epi8(perm_vec, permute_xform); | ||
| ret_vec = _mm256_inserti128_si256(_mm256_castsi128_si256(ret_vec0), ret_vec0, 1); | ||
| ret_vec = _mm256_shuffle_epi8(ret_vec, perm_vec); | ||
| } else { | ||
| halfmask_t load_mask = gen_half_mask(dist - 16); | ||
| __m128i ret_vec0 = _mm_loadu_si128((__m128i*)buf); | ||
| __m128i ret_vec1 = _mm_maskz_loadu_epi8(load_mask, (__m128i*)(buf + 16)); | ||
| __m128i perm_vec1 = _mm_load_si128((__m128i*)(permute_table + lut_rem.idx)); | ||
| halfmask_t xlane_mask = _mm_cmp_epi8_mask(perm_vec1, _mm_set1_epi8(15), _MM_CMPINT_LE); | ||
| __m128i latter_half = _mm_mask_shuffle_epi8(ret_vec1, xlane_mask, ret_vec0, perm_vec1); | ||
| ret_vec = _mm256_inserti128_si256(_mm256_castsi128_si256(ret_vec0), latter_half, 1); | ||
| } | ||
|
|
||
| return ret_vec; | ||
| } | ||
|
|
||
| static inline void loadhalfchunk(uint8_t const *s, halfchunk_t *chunk) { | ||
| *chunk = _mm_loadu_si128((__m128i *)s); | ||
| } | ||
|
|
||
| static inline void storehalfchunk(uint8_t *out, halfchunk_t *chunk) { | ||
| _mm_storeu_si128((__m128i *)out, *chunk); | ||
| } | ||
|
|
||
| static inline chunk_t halfchunk2whole(halfchunk_t *chunk) { | ||
| /* We zero extend mostly to appease some memory sanitizers. These bytes are ultimately | ||
| * unlikely to be actually written or read from */ | ||
| return _mm256_zextsi128_si256(*chunk); | ||
| } | ||
|
|
||
| static inline halfchunk_t GET_HALFCHUNK_MAG(uint8_t *buf, uint32_t *chunk_rem, uint32_t dist) { | ||
| lut_rem_pair lut_rem = perm_idx_lut[dist - 3]; | ||
| __m128i perm_vec, ret_vec; | ||
| halfmask_t load_mask = gen_half_mask(dist); | ||
| ret_vec = _mm_maskz_loadu_epi8(load_mask, buf); | ||
| *chunk_rem = half_rem_vals[dist - 3]; | ||
|
|
||
| perm_vec = _mm_load_si128((__m128i*)(permute_table + lut_rem.idx)); | ||
| ret_vec = _mm_shuffle_epi8(ret_vec, perm_vec); | ||
|
|
||
| return ret_vec; | ||
| } | ||
|
|
||
| static inline uint8_t* HALFCHUNKCOPY(uint8_t *out, uint8_t const *from, unsigned len) { | ||
| Assert(len > 0, "chunkcopy should never have a length 0"); | ||
|
|
||
| unsigned rem = len % sizeof(halfchunk_t); | ||
| halfmask_t rem_mask = gen_half_mask(rem); | ||
|
|
||
| /* Since this is only ever called if dist >= a chunk, we don't need a masked load */ | ||
| halfchunk_t chunk; | ||
| loadhalfchunk(from, &chunk); | ||
| _mm_mask_storeu_epi8(out, rem_mask, chunk); | ||
| out += rem; | ||
| from += rem; | ||
| len -= rem; | ||
|
|
||
| while (len > 0) { | ||
| loadhalfchunk(from, &chunk); | ||
| storehalfchunk(out, &chunk); | ||
| out += sizeof(halfchunk_t); | ||
| from += sizeof(halfchunk_t); | ||
| len -= sizeof(halfchunk_t); | ||
| } | ||
|
|
||
| return out; | ||
| } | ||
|
|
||
| #define CHUNKSIZE chunksize_avx512 | ||
| #define CHUNKUNROLL chunkunroll_avx512 | ||
| #define CHUNKMEMSET chunkmemset_avx512 | ||
| #define CHUNKMEMSET_SAFE chunkmemset_safe_avx512 | ||
|
|
||
| #include "chunkset_tpl.h" | ||
|
|
||
| #define INFLATE_FAST inflate_fast_avx512 | ||
|
|
||
| #include "inffast_tpl.h" | ||
|
|
||
| #endif |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Oops, something went wrong.