快速搜索并替换int中的一些半字节[c; microoptimisation]

Question

这是在具有不同任务的相同偏移(C,微优化)问题下快速搜索两个整数中的一些半字节的变体:

任务是在int32中找到预定义的半字节并将其替换为其他半字节.例如,半字节搜索是0x5; 蚕食取代是0xe:

int:   0x3d542753 (input)
           ^   ^
output:0x3dE427E3 (output int)

可以有另外一对半字节搜索和半字节替换(在编译时已知).

我检查了我的程序,这部分是最热门的地方之一(gprof证明,75%的时间在功能中); 它被称为非常多次(gcov证明).实际上它是嵌套循环的第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;
}

是否可以使用一些位逻辑魔法以并行方式重写此函数和宏？魔术是类似的(t-0x11111111)&(~t)-0x88888888,可能与SSE*一起使用.检查已联系问题的已接受答案,以了解所需的魔法.

我的编译器是gcc452,cpu是32位模式(x86)的Intel Core2 Solo或64位模式(x86-64)的(不久的将来).

Answer 1

这似乎是一个有趣的问题，所以我写了一个解决方案，而没有查看其他答案。在我的系统上，速度大约是原来的 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);
    }
}

-O3使用 GCC，假设正确使用该标志，该函数将自动转换为 SSE 代码-march。您可以传递-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我注意到，通过将自动矢量化版本中的类型从 更改为 ，速度额外提高了 48% uint16_t。这使得总加速比原来提高了约 12 倍。更改为uint8_t会导致矢量化失败。我怀疑手工组装可以显着提高速度（如果它真的那么重要的话）。

编辑 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));
}