快速搜索并替换int中的一些半字节
这是在具有不同任务的相同偏移（C，微优化）问题的两个整数中快速搜索一些半字节的变体：
任务是在int32中找到预定义的半字节并将其替换为其他半字节。 例如，半字节搜索是0x5; 蚕食取代是0xe：
int: 0x3d542753 (input) ^ ^ output:0x3dE427E3 (output int) 可以有另外一对半字节搜索和半字节替换（在编译时已知）。
我检查了我的程序，这部分是最热门的地方之一（gprofcertificate，75％的时间在function中）; 它被称为非常多次（gcovcertificate）。 实际上它是嵌套循环的第3或第4循环，运行计数估计为（n ^ 3）*（2 ^ n） ，n = 18..24。
我当前的代码很慢（我将其重写为函数，但它是来自循环的代码）：
static inline uint32_t nibble_replace (uint32_t A) __attribute__((always_inline)) { int i; uint32_t mask = 0xf; uint32_t search = 0x5; uint32_t replace = 0xe; for(i=0;i<8;i++) { if( (A&mask) == search ) A = (A & (~mask) ) // clean i-th nibble | replace; // and replace mask <<= 4; search <<= 4; replace <<= 4; } return A; }
是否可以使用一些位逻辑魔法以并行方式重写此函数和宏？ Magic类似于(t-0x11111111)&(~t)-0x88888888 ，可能与SSE *一起使用。 检查已联系问题的已接受答案，以了解所需的魔法。
我的编译器是gcc452，cpu是32位模式（x86）的Intel Core2 Solo或64位模式（x86-64）的（不久的将来）。
这似乎是一个有趣的问题，所以我写了一个解决方案而没有看其他答案。 这在我的系统上似乎快了4.9倍。 在我的系统上，它也比DigitalRoss的解决方案稍快（大约快25％）。
static inline uint32_t nibble_replace_2(uint32_t x) { uint32_t SEARCH = 0x5, REPLACE = 0xE, ONES = 0x11111111; uint32_t y = (~(ONES * SEARCH)) ^ x; y &= y >> 2; y &= y >> 1; y &= ONES; y *= 15; /* This is faster than y |= y << 1; y |= y << 2; */ return x ^ (((SEARCH ^ REPLACE) * ONES) & y); }
我会解释它是如何工作的，但是......我认为解释它会破坏它的乐趣。
关于SIMD的注意事项：这种东西非常非常容易矢量化。 您甚至不必知道如何使用SSE或MMX。 这是我如何矢量化它：
static void nibble_replace_n(uint32_t *restrict p, uint32_t n) { uint32_t i; for (i = 0; i < n; ++i) { uint32_t x = p[i]; uint32_t SEARCH = 0x5, REPLACE = 0xE, ONES = 0x11111111; uint32_t y = (~(ONES * SEARCH)) ^ x; y &= y >> 2; y &= y >> 1; y &= ONES; y *= 15; p[i] = x ^ (((SEARCH ^ REPLACE) * ONES) & y); } }
假设正确使用-march标志，使用GCC，此函数将自动转换为-O3处的SSE代码。 您可以将-ftree-vectorizer-verbose=2传递给GCC，要求它打印出哪些循环被矢量化，例如：
$ gcc -std=gnu99 -march=native -O3 -Wall -Wextra -o opt opt.c opt.c:66: note: LOOP VECTORIZED.
自动矢量化给了我额外的速度增益约64％，我甚至没有达到处理器手册。
编辑：我注意到通过将自动矢量化版本中的类型从uint32_t更改为uint16_t ， uint32_t额外48％的加速。 这使总加速比原始加速大约12倍。 更改为uint8_t会导致矢量化失败。 我怀疑手部assembly有一些显着的额外速度，如果这很重要的话。
编辑2：将*= 7更改为*= 15 ，这使速度测试无效。
编辑3：这是一个回顾中显而易见的变化：
static inline uint32_t nibble_replace_2(uint32_t x) { uint32_t SEARCH = 0x5, REPLACE = 0xE, ONES = 0x11111111; uint32_t y = (~(ONES * SEARCH)) ^ x; y &= y >> 2; y &= y >> 1; y &= ONES; return x ^ (y * (SEARCH ^ REPLACE)); }