將8 位字符12345678視為字串。它可以轉換為每個位元組都包含一個數字的數字，如下所示：
const char* const str = "12345678";
const char* const base = "00000000";
const uint64_t unpacked = *reinterpret_cast<const uint64_t*>(str)
- *reinterpret_cast<const uint64_t*>(base);
然后unpacked將0x0807060504030201在一個小端系統上。
將數字轉換為 的最快方法是什么12345678，可能是通過將它乘以某個幻數或使用 SIMD 到 AVX2？
更新：12345678必須是存盤在 32 位或 64 位整數中的數字，而不是字串。
uj5u.com熱心網友回復：
二進制乘法只是一系列移位和加法。SWAR 方法不應該太難理解。有關詳細的演練，請參閱：
- https://johnnylee-sde.github.io/Fast-numeric-string-to-int/
- https://kholdstare.github.io/technical/2020/05/26/faster-integer-parsing.html
- https://lemire.me/blog/2022/01/21/swar-explained-parsing-eight-digits/
- http://0x80.pl/articles/simd-parsing-int-sequences.html
// http://govnokod.ru/13461
static inline
uint32_t parse_8digits_swar_classic (char* str) {
uint64_t v;
memcpy(&v, str, 8);
v = (v & 0x0F0F0F0F0F0F0F0F) * 2561 >> 8;
v = (v & 0x00FF00FF00FF00FF) * 6553601 >> 16;
v = (v & 0x0000FFFF0000FFFF) * 42949672960001 >> 32;
return v;
}
// attempt to improve the latency
static inline
uint32_t parse_8digits_swar_aqrit (char* str) {
const uint64_t mask = 0x000000FF000000FF;
uint64_t v, t;
memcpy(&v, str, 8);
v = (v * 10) (v >> 8);
t = (v & mask) * 0x000F424000000064;
v = ((v >> 16) & mask) * 0x0000271000000001;
v = (v t 0xFF0915C600000000ULL) >> 32;
return v;
}
// SSSE3 needs less `shift & mask` operations...
static inline
uint32_t parse_8digits_simd_ssse3 (char* str) {
const __m128i mul1 = _mm_set_epi32(0, 0, 0x010A0A64, 0x14C814C8);
const __m128i mul2 = _mm_set_epi32(0, 0, 0x0001000A, 0x00FA61A8);
const __m128i mask = _mm_set1_epi8(0x0F);
__m128i v;
v = _mm_loadl_epi64((__m128i*)(void*)str);
v = _mm_and_si128(v, mask);
v = _mm_madd_epi16(_mm_maddubs_epi16(mul1, v), mul2);
v = _mm_add_epi32(_mm_add_epi32(v, v), _mm_shuffle_epi32(v, 1));
return (uint32_t)_mm_cvtsi128_si32(v);
}
uj5u.com熱心網友回復：
在沒有 AVX2 的舊 x86-64 系統上，這個基于以樹方式收集數字的簡單版本非常有效，根據我的測量，性能與基于 SWAR 的簡單實作相當。然而，這需要一個具有大量指令級并行性的處理器，因為當使用完全優化編譯時，它包含的指令比基于 SWAR 的代碼多 50%。
/* convert a string of exactly eight 'char' into a 32-bit unsigned integer */
uint32_t string_to_number (const char * s)
{
uint32_t t0 = s[0] * 10 s[1];
uint32_t t1 = s[2] * 10 s[3];
uint32_t t2 = s[4] * 10 s[5];
uint32_t t3 = s[6] * 10 s[7];
uint32_t s0 = t0 * 100 t1;
uint32_t s1 = t2 * 100 t3;
uint32_t num = s0 * 10000 s1;
uint32_t corr =
'0' * 10000000
'0' * 1000000
'0' * 100000
'0' * 10000
'0' * 1000
'0' * 100
'0' * 10
'0' * 1;
return num - corr;
}
uj5u.com熱心網友回復：
如果您將輸入格式更改為廣度優先元素順序，如下所示：
Sample 9 numbers, interleaved
digit[]:
1 1 1 1 1 1 1 1 1 ... 2 2 2 2 2 2 2 2 2 ...
... 3 3 3 3 3 3 3 3 3 ....
for(int j=0; j<num_parse; j =9)
{
for(int i=0; i<9; i )
{
value[i] =
(multiplier[i]*=10)*
(digit[i j]-'0');
}
// value vector copied to output
// clear value & multiplier vectors
}
而且，如果您將不止 9 個值（例如 512 或 8192 與填充）轉換為 32 的任意倍數，編譯器應該對其進行向量化。
要準備輸入，您可以使用 8 個不同的通道，每個決議值的每個數字 1 個。
uj5u.com熱心網友回復：
我已經實作了一個小程式來測驗一些想法。AVX2 實作比 naive 快約 1.5 倍，中間是表實作：
AVX2: 12345678 in 3.42759
Naive: 12345678 in 5.12581
Table: 12345678 in 4.49478
源代碼：
#include <cstdlib>
#include <cstdint>
#include <immintrin.h>
#include <iostream>
using namespace std;
const __m256i mask = _mm256_set1_epi32(0xf);
const __m256i mul = _mm256_setr_epi32(10000000, 1000000, 100000, 10000, 1000, 100, 10, 1);
const volatile char* str = "12345678";
volatile uint32_t h;
const int64_t nIter = 1000LL * 1000LL * 1000LL;
inline void parse_avx2() {
const char* const base = "00000000";
const uint64_t unpacked = *reinterpret_cast<const volatile uint64_t*>(str)
- *reinterpret_cast<const uint64_t*>(base);
const __m128i a = _mm_set1_epi64x(unpacked);
const __m256i b = _mm256_cvtepu8_epi32(a);
const __m256i d = _mm256_mullo_epi32(b, mul);
const __m128i e = _mm_add_epi32(_mm256_extractf128_si256(d, 0), _mm256_extractf128_si256(d, 1));
const uint64_t f0 = _mm_extract_epi64(e, 0);
const uint64_t f1 = _mm_extract_epi64(e, 1);
const uint64_t g = f0 f1;
h = (g>>32) (g&0xffffffff);
}
inline void parse_naive() {
const char* const base = "00000000";
const uint64_t unpacked = *reinterpret_cast<const volatile uint64_t*>(str)
- *reinterpret_cast<const uint64_t*>(base);
const uint8_t* a = reinterpret_cast<const uint8_t*>(&unpacked);
h = a[7] a[6]*10 a[5]*100 a[4]*1000 a[3]*10000 a[2]*100000 a[1]*1000000 a[0]*10000000;
}
uint32_t summands[8][10];
inline void parse_table() {
const char* const base = "00000000";
const uint64_t unpacked = *reinterpret_cast<const volatile uint64_t*>(str)
- *reinterpret_cast<const uint64_t*>(base);
const uint8_t* a = reinterpret_cast<const uint8_t*>(&unpacked);
h = summands[7][a[0]] summands[6][a[1]] summands[5][a[2]] summands[4][a[3]]
summands[3][a[4]] summands[2][a[5]] summands[1][a[6]] summands[0][a[7]];
}
int main() {
clock_t start = clock();
for(int64_t i=0; i<nIter; i ) {
parse_avx2();
}
clock_t end = clock();
cout << "AVX2: " << h << " in " << double(end-start)/CLOCKS_PER_SEC << endl;
start = clock();
for(int64_t i=0; i<nIter; i ) {
parse_naive();
}
end = clock();
cout << "Naive: " << h << " in " << double(end-start)/CLOCKS_PER_SEC << endl;
uint32_t mul=1;
for(int i=0; i<8; i , mul*=10) {
for(int j=0; j<9; j ) {
summands[i][j] = j*mul;
}
}
start = clock();
for(int64_t i=0; i<nIter; i ) {
parse_table();
}
end = clock();
cout << "Table: " << h << " in " << double(end-start)/CLOCKS_PER_SEC << endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/452164.html