比条件语句和指针增量更快的Blit？

Question

这是我的简单粗暴的blitting函数：

static void blit8(unsigned char* dest, unsigned char* src)
{
    byte i;
    for (i = 0; i < 8; ++i) {
        if (*src != 0) {
            *dest = *src;
        }
        ++dest;
        ++src;
    }
}

我已经使用了-O3，并且blit8被内联了。在这里使用restrict(gcc)没有效果，在指针中使用不同的递增方式、使用另一个数字作为透明度或使用其他类型代替i也无法改善情况……我甚至尝试传递一个1字节的位掩码并检查其是否比解引用src更快。将i的限制提高到16似乎可以提供一个非常小的速度提升(~4-6%)，但我处理的是8字节而不是16字节的块。

我的瓶颈？实际上我不知道，我认为这不是缓存行问题，因为我的miss率很低(?)，而当改变一些东西时，64(我的cache line大小)没有特殊意义。但我也不认为这是内存速度的问题(因为memcpy更快，稍后会详细介绍)。

cg_annotate关于blit8(未内联)的报告如下:

Ir    I1mr   ILmr            Dr      D1mr   DLmr          Dw       D1mw    DLmw  file:function
3,747,585,536      62      1 1,252,173,824 2,097,653      0 674,067,968          0       0  ppu.c:blit8.constprop.0

常规的cachegrind输出（包含内联函数）：

I   refs:      6,446,979,546
I1  misses:          184,752
LLi misses:           22,549
I1  miss rate:          0.00%
LLi miss rate:          0.00%

D   refs:      2,150,502,425  (1,497,875,135 rd   + 652,627,290 wr)
D1  misses:       17,121,968  (    2,761,307 rd   +  14,360,661 wr)
LLd misses:          253,685  (       70,802 rd   +     182,883 wr)
D1  miss rate:           0.8% (          0.2%     +         2.2%  )
LLd miss rate:           0.0% (          0.0%     +         0.0%  )

LL refs:          17,306,720  (    2,946,059 rd   +  14,360,661 wr)
LL misses:           276,234  (       93,351 rd   +     182,883 wr)
LL miss rate:            0.0% (          0.0%     +         0.0%  )

0.8% 的D1缺失率？听起来对我来说相当低。

但是最有趣的是，删除0-check（变得与memcpy功能上相同）可以提供小于1%的加速，尽管：

memcpy快约25%。我希望尽可能接近原始memcpy的速度，同时保留颜色0为透明。

问题在于，据我所知，没有矢量指令支持条件语句，但我需要保留src为0时的dest。有什么[快速]可以像按字节级别的OR一样工作的东西吗？

我之前看过一个扩展或者CPU不缓存某些数据的东西，但我现在找不到它了。我的想法是不直接从src读取，只从中写入dest，并确保它不被缓存。然后只需从位掩码中读取以检查透明度。 我不知道如何实际操作。那是否可能快速完成？我也不知道，因此我才会问这个问题。

我更喜欢用C做得更快的提示，也许使用一些gcc扩展，但如果x86汇编是唯一的方法，那就这样吧。帮助我理解我的真正瓶颈（因为我对结果感到困惑）也会有所帮助。

- Accumulator

---

为什么不使用memcpy？它是超级优化的，如果在您的体系结构上可用，则会被一些低级汇编操作替换。 - Jazzwave06

@sturcotte06 这段代码不会用零覆盖，因此与memcpy不同。 - interjay

@sturcotte06 OP已经提到了memcpy函数。 - Weather Vane

那么我认为你无法匹配memcpy的性能，因为你无法利用x86指令。 - Jazzwave06

它非常适用于掩码。例如，可以看看 pblendvb 指令，似乎很适合这里。 - interjay

Answer 1

你没有提到是否使用GCC编译器，但我们假设你是使用的。

GCC对循环内部的条件非常挑剔，这就是为什么你的示例无法进行向量化处理的原因。

所以这段代码：

void blit8(unsigned char* dest, unsigned char* src)
{
    char i;
    for (i = 0; i < 8; ++i) {
        if (*src != 0) {
            *dest = *src;
        }
        ++dest;
        ++src;
    }
}

最终结果为：

blit8:
        movzx   eax, BYTE PTR [rsi]
        test    al, al
        je      .L5
        mov     BYTE PTR [rdi], al
.L5:
        movzx   eax, BYTE PTR [rsi+1]
        test    al, al
        je      .L6
        mov     BYTE PTR [rdi+1], al
.L6:
        movzx   eax, BYTE PTR [rsi+2]
        test    al, al
        je      .L7
        mov     BYTE PTR [rdi+2], al
.L7:
        movzx   eax, BYTE PTR [rsi+3]
        test    al, al
        je      .L8
        mov     BYTE PTR [rdi+3], al
.L8:
        movzx   eax, BYTE PTR [rsi+4]
        test    al, al
        je      .L9
        mov     BYTE PTR [rdi+4], al
.L9:
        movzx   eax, BYTE PTR [rsi+5]
        test    al, al
        je      .L10
        mov     BYTE PTR [rdi+5], al
.L10:
        movzx   eax, BYTE PTR [rsi+6]
        test    al, al
        je      .L11
        mov     BYTE PTR [rdi+6], al
.L11:
        movzx   eax, BYTE PTR [rsi+7]
        test    al, al
        je      .L37
        mov     BYTE PTR [rdi+7], al
.L37:
        ret

这段代码虽然被编译器展开，但仍然逐字节工作。

在这种情况下，有一个技巧经常有效 - 使用三目运算符而不是if（cond）。这将解决一个问题。但还有另一个问题 - GCC拒绝对短小的块进行向量化处理 - 例如，在此示例中为8个字节。因此，让我们使用另一个技巧 - 在更大的块上进行计算，但忽略其中的一部分。

以下是我的示例：

void blit8(unsigned char* dest, unsigned char* src)
{
    int i;
    unsigned char temp_dest[16];
    unsigned char temp_src[16];

    for (i = 0; i < 8; ++i) temp_dest[i] = dest[i];
    for (i = 0; i < 8; ++i) temp_src[i] = src[i];

    for (i = 0; i < 16; ++i) 
    {
        temp_dest[i] = (temp_src[i] != 0) ? temp_src[i] : temp_dest[i];
    }

    for (i = 0; i < 8; ++i) dest[i] = temp_dest[i];
}

以及相应的汇编代码：

blit8:
        mov     rax, QWORD PTR [rdi]
        vpxor   xmm0, xmm0, xmm0
        mov     QWORD PTR [rsp-40], rax
        mov     rax, QWORD PTR [rsi]
        mov     QWORD PTR [rsp-24], rax
        vmovdqa xmm1, XMMWORD PTR [rsp-24]
        vpcmpeqb        xmm0, xmm0, XMMWORD PTR [rsp-24]
        vpblendvb       xmm0, xmm1, XMMWORD PTR [rsp-40], xmm0
        vmovq   QWORD PTR [rdi], xmm0
        ret

注意： 我没有对其进行基准测试 - 这只是证明采用适当的编码规则和技巧可以生成SIMD代码 ;)

- Anty

---

使用这么多晦涩的编译器技巧来让编译器满意，可能更好（更稳定、更易于维护）的方法是使用内置函数。 - Brendan

如果他使用16字节而不是8字节，那么只需要用? :替换if()。手动使用指令时，这一步也必须完成（8->16），正如您所看到的，这种转换非常便宜。并且不 - 指令并不更容易维护，更不用说代码已经不可移植了。 自动向量化器运行良好 - 只需遵循文档中列出的限制即可。 - Anty

你的意思是，对于一个特定编译器版本、一个特定架构和一组特定参数，如果你修改代码以适应这个特定编译器版本、特定架构和特定参数集，那么自动向量化就会表现不佳（没有预取、没有缓存行刷新）？ - Brendan

如果你将最流行的编译器称为“特定的”，并指代几年前的“当前”版本，以及遵循自动向量化规则的“混淆”和“特定参数”，那么我就没有更多问题了。 - Anty

Answer 2

如果你的编译器/架构支持矢量扩展（例如clang和gcc），你可以使用类似以下的代码：

//This may compile to awful code on x86_64 b/c mmx is slow (its fine on arm64)
void blit8(void* dest, void* src){
typedef __UINT8_TYPE__ u8x8  __attribute__ ((__vector_size__ (8), __may_alias__));
    u8x8 *dp = dest, d = *dp, *sp = src, s = *sp, cmp;
    cmp = s == (u8x8){0};
    d &= cmp;
    *dp = s|d;
}

//This may compile to better code on x86_64 - worse on arm64
void blit8v(void* dest, void* src){
typedef __UINT8_TYPE__ u8x16  __attribute__ ((__vector_size__ (16), __may_alias__));
typedef __UINT64_TYPE__ u64, u64x2  __attribute__ ((__vector_size__ (16), __may_alias__));
    u8x16 *dp = dest, d = *dp, *sp = src, s = *sp, cmp;
    cmp = s == (u8x16){0};
    d &= cmp;
    d |= s;
    *(u64*)dest = ((u64x2)d)[0];
}

//This one is fine on both arm and x86, but 16 bytes vs. 8
void blit16(void* dest, void* src){
typedef __UINT8_TYPE__ u8x16  __attribute__ ((__vector_size__ (16), __may_alias__));
    u8x16 *dp = dest, *sp = src, d = *dp, s = *sp, cmp;
    cmp = s == (u8x16){0};
    *dp = s|(d & cmp);
}

在 ARM 上编译为：

blit8:
        ldr     d1, [x1]
        ldr     d2, [x0]
        cmeq    v0.8b, v1.8b, #0
        and     v0.8b, v0.8b, v2.8b
        orr     v0.8b, v0.8b, v1.8b
        str     d0, [x0]
        ret
blit16:
        ldr     q1, [x1]
        ldr     q2, [x0]
        cmeq    v0.16b, v1.16b, #0
        and     v0.16b, v0.16b, v2.16b
        orr     v0.16b, v0.16b, v1.16b
        str     q0, [x0]
        ret

在 x86_64 上：

blit8v:                                 # @blit8v
        movdqa  xmm0, xmmword ptr [rsi]
        pxor    xmm1, xmm1
        pcmpeqb xmm1, xmm0
        pand    xmm1, xmmword ptr [rdi]
        por     xmm1, xmm0
        movq    qword ptr [rdi], xmm1
        ret
blit16:                                 # @blit16
        movdqa  xmm0, xmmword ptr [rsi]
        pxor    xmm1, xmm1
        pcmpeqb xmm1, xmm0
        pand    xmm1, xmmword ptr [rdi]
        por     xmm1, xmm0
        movdqa  xmmword ptr [rdi], xmm1
        ret

- technosaurus