c++ - 优化 uint8 的递减最大值

Question

我发现我的程序大部分时间都在类似这样的循环中度过:

uint8_t (&c) [17] = ...
for (int x = 0; x < 16; x++) {
    if (c[x + 1] < c[x] - 1) {
        c[x + 1] = c[x] - 1;
    }
}

它将字段值计算为当前值和前一个字段值减 1 的最大值。

有什么办法可以加快速度吗？

c 是几个 SSE 操作的结果，所以它可能已经在 xmm 中了。但是，我们也欢迎任何其他类型的改进。

Answer 1

可以通过注意结果是 16 个独立内核的最大值来打破依赖关系，每个内核的形式为 0 0 0 0 N N-1 N-2 N-3 N-3。

__m128i d = _mm_loadu_si128((__m128i*)&c);  // get 16 bytes
__m128i ramp = _mm_set_epi8(15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0);
static __m128i bcast[16]; // shuffles item at i to i+1, i+2, ... 15
// e.g. bcast[3] = _mm_set_epi8(3,3,3,3,3,3,3,3,3,3,3,3,3,0xff,0xff,0xff);

for (i = 0; i < 16; i++)
    __m128i tmp = _mm_shuffle_epi8(d, bcast[i]);
    tmp = _mm_subs_epu8(tmp, ramp);  // saturated subtraction
    ramp = _mm_srli_si128(ramp, 1);        // Shift the ramp
    d = _mm_max_epu8(d, tmp);
}

d = max(d, x[i]) 的结果依赖实际上与顺序无关(假设 ramp_i 不必增量评估)并且依赖链可以折叠到二叉树。

但我们可以做得比 16 次迭代更好——分而治之的技术会将任务分成下半部分和上半部分，每个需要 8 次迭代(并且可以并行进行)。然后需要一个合并的最后阶段，其中必须合并上面的结果 d[8..15] 和 d[0..7] 的递减尾部。