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]) 生成的依赖关系实际上与顺序无关(假定不需要增量评估 Ram_i)，并且依赖关系链可以折叠到二叉树。

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