快速搜索并替换int [c;微优化]

| 这是在具有不同任务的相同偏移量（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）或（不久以后）64位模式（x86-64）的Intel Core2 Solo。

已邀请:

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代码。您可以将ѭ7传递给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倍。更改为“ 11”会导致矢量化失败。我怀疑手动组装会发现一些重要的额外速度，如果它是如此重要的话。编辑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));
}

要回复问题请先登录或注册

快速搜索并替换int [c;微优化]

1 个回复

发起人

c

optimization

micro_optimization

问题状态

快速搜索并替换int [c;微优化]

与内容相关的链接

1 个回复

发起人

c

optimization

micro_optimization

问题状态