// this software is distributed under the MIT License (http://www.opensource.org/licenses/MIT): // // Copyright 2018-2020, CWI, TU Munich, FSU Jena // // Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files // (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, // merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is // furnished to do so, subject to the following conditions: // // - The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. // // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES // OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR // IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. // // You can contact the authors via the FSST source repository : https://github.com/cwida/fsst #include "libfsst.hpp" #if defined(__x86_64__) || defined(_M_X64) #include #ifdef _WIN32 bool fsst_hasAVX512() { int info[4]; __cpuidex(info, 0x00000007, 0); return (info[1]>>16)&1; } #else #include bool fsst_hasAVX512() { int info[4]; __cpuid_count(0x00000007, 0, info[0], info[1], info[2], info[3]); return (info[1]>>16)&1; } #endif #else bool fsst_hasAVX512() { return false; } #endif // BULK COMPRESSION OF STRINGS // // In one call of this function, we can compress 512 strings, each of maximum length 511 bytes. // strings can be shorter than 511 bytes, no problem, but if they are longer we need to cut them up. // // In each iteration of the while loop, we find one code in each of the unroll*8 strings, i.e. (8,16,24 or 32) for resp. unroll=1,2,3,4 // unroll3 performs best on my hardware // // In the worst case, each final encoded string occupies 512KB bytes (512*1024; with 1024=512xexception, exception = 2 bytes). // - hence codeBase is a buffer of 512KB (needs 19 bits jobs), symbolBase of 256KB (needs 18 bits jobs). // // 'jobX' controls the encoding of each string and is therefore a u64 with format [out:19][pos:9][end:18][cur:18] (low-to-high bits) // The field 'pos' tells which string we are processing (0..511). We need this info as strings will complete compressing out-of-order. // // Strings will have different lengths, and when a string is finished, we reload from the buffer of 512 input strings. // This continues until we have less than (8,16,24 or 32; depending on unroll) strings left to process. // - so 'processed' is the amount of strings we started processing and it is between [480,512]. // Note that when we quit, there will still be some (<32) strings that we started to process but which are unfinished. // - so 'unfinished' is that amount. These unfinished strings will be encoded further using the scalar method. // // Apart from the coded strings, we return in a output[] array of size 'processed' the job values of the 'finished' strings. // In the following 'unfinished' slots (processed=finished+unfinished) we output the 'job' values of the unfinished strings. // // For the finished strings, we need [out:19] to see the compressed size and [pos:9] to see which string we refer to. // For the unfinished strings, we need all fields of 'job' to continue the compression with scalar code (see SIMD code in compressBatch). // // THIS IS A SEPARATE CODE FILE NOT BECAUSE OF MY LOVE FOR MODULARIZED CODE BUT BECAUSE IT ALLOWS TO COMPILE IT WITH DIFFERENT FLAGS // in particular, unrolling is crucial for gather/scatter performance, but requires registers. the #define all_* expressions however, // will be detected to be constants by g++ -O2 and will be precomputed and placed into AVX512 registers - spoiling 9 of them. // This reduces the effectiveness of unrolling, hence -O2 makes the loop perform worse than -O1 which skips this optimization. // Assembly inspection confirmed that 3-way unroll with -O1 avoids needless load/stores. size_t fsst_compressAVX512(SymbolTable &symbolTable, u8* codeBase, u8* symbolBase, SIMDjob *input, SIMDjob *output, size_t n, size_t unroll) { size_t processed = 0; // define some constants (all_x means that all 8 lanes contain 64-bits value X) #ifdef __AVX512F__ //__m512i all_suffixLim= _mm512_broadcastq_epi64(_mm_set1_epi64((__m64) (u64) symbolTable->suffixLim)); -- for variants b,c __m512i all_MASK = _mm512_broadcastq_epi64(_mm_set1_epi64((__m64) (u64) -1)); __m512i all_PRIME = _mm512_broadcastq_epi64(_mm_set1_epi64((__m64) (u64) FSST_HASH_PRIME)); __m512i all_ICL_FREE = _mm512_broadcastq_epi64(_mm_set1_epi64((__m64) (u64) FSST_ICL_FREE)); #define all_HASH _mm512_srli_epi64(all_MASK, 64-FSST_HASH_LOG2SIZE) #define all_ONE _mm512_srli_epi64(all_MASK, 63) #define all_M19 _mm512_srli_epi64(all_MASK, 45) #define all_M18 _mm512_srli_epi64(all_MASK, 46) #define all_M28 _mm512_srli_epi64(all_MASK, 36) #define all_FFFFFF _mm512_srli_epi64(all_MASK, 40) #define all_FFFF _mm512_srli_epi64(all_MASK, 48) #define all_FF _mm512_srli_epi64(all_MASK, 56) SIMDjob *inputEnd = input+n; assert(n >= unroll*8 && n <= 512); // should be close to 512 __m512i job1, job2, job3, job4; // will contain current jobs, for each unroll 1,2,3,4 __mmask8 loadmask1 = 255, loadmask2 = 255*(unroll>1), loadmask3 = 255*(unroll>2), loadmask4 = 255*(unroll>3); // 2b loaded new strings bitmask per unroll u32 delta1 = 8, delta2 = 8*(unroll>1), delta3 = 8*(unroll>2), delta4 = 8*(unroll>3); // #new loads this SIMD iteration per unroll if (unroll >= 4) { while (input+delta1+delta2+delta3+delta4 < inputEnd) { #include "fsst_avx512_unroll4.inc" } } else if (unroll == 3) { while (input+delta1+delta2+delta3 < inputEnd) { #include "fsst_avx512_unroll3.inc" } } else if (unroll == 2) { while (input+delta1+delta2 < inputEnd) { #include "fsst_avx512_unroll2.inc" } } else { while (input+delta1 < inputEnd) { #include "fsst_avx512_unroll1.inc" } } // flush the job states of the unfinished strings at the end of output[] processed = n - (inputEnd - input); u32 unfinished = 0; if (unroll > 1) { if (unroll > 2) { if (unroll > 3) { _mm512_mask_compressstoreu_epi64(output+unfinished, loadmask4=~loadmask4, job4); unfinished += _mm_popcnt_u32((int) loadmask4); } _mm512_mask_compressstoreu_epi64(output+unfinished, loadmask3=~loadmask3, job3); unfinished += _mm_popcnt_u32((int) loadmask3); } _mm512_mask_compressstoreu_epi64(output+unfinished, loadmask2=~loadmask2, job2); unfinished += _mm_popcnt_u32((int) loadmask2); } _mm512_mask_compressstoreu_epi64(output+unfinished, loadmask1=~loadmask1, job1); #else (void) symbolTable; (void) codeBase; (void) symbolBase; (void) input; (void) output; (void) n; (void) unroll; #endif return processed; }