c - 快速搜索并替换 int [c; 中的一些半字节微优化]

Question

这是 Fast search of some nibbles in two ints at same offset (C, microoptimisation) 的变体不同任务的问题:

任务是在 int32 中找到一个预定义的半字节并将其替换为其他半字节。例如查找半字节为0x5；替换为 0xe 的半字节:

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

可以有其他一对半字节来搜索和半字节替换(在编译时已知)。

我检查了我的程序，这部分是 HitTest 门的地方之一(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;
}

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

我的编译器是 gcc452，cpu 是 Intel Core2 Solo，32 位模式 (x86) 或(在不久的将来)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);
    }
}

使用 GCC，假设正确使用 -march 标志，此函数将自动转换为 -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，速度提高了 48%。这使总加速比原来提高了大约 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));
}