分支预测与分支目标预测优化

Question

我的代码经常调用具有多个（不可预测的）分支的函数。当我分析时，我发现这是一个小瓶颈，大部分CPU时间用于条件JMP。

考虑以下两个函数，其中原始函数有多个显式分支。

void branch_example_original(void* mem, size_t s)
{
    if(!(s & 7)) {
        /* logic in _process_mem_64 inlined */
    }
    else if(!(s & 3)) {
        /* logic in _process_mem_32 inlined */
    }
    else if(!(s & 1)) {
        /* logic in _process_mem_16 inlined */
    }
    else {
        /* logic in _process_mem_8 inlined */
    }
}

这是一个新函数，我试图在其中删除导致瓶颈的分支。

void branch_example_new(void* mem, size_t s)
{
    const fprocess_mem mem_funcs[] = {_process_mem_8, _process_mem_16, _process_mem_32, _process_mem_64};
    const uint32_t magic = 3 - !!(s & 7) - !!(s & 3) - !!(s & 1);
    mem_funcs[magic](mem, size >> magic);
}

然而，当我分析新代码时，性能只提高了大约20%，而且调用本身(对mem_funcs数组中的一个func)花费了很长时间。

第二个变量仅仅是一个更隐含的条件吗，因为CPU仍然无法预测将要调用的函数？我假设这与分支目标预测有关，对吗？

为什么会发生这种情况，还有其他解决办法吗？

编辑：

感谢您的想法，但我想解释为什么也会发生这种情况。

Answer 1

现代处理器不仅有分支预测，还有跳跃预测。例如，如果你调用一个虚函数，它可能会预测实际函数与前一次调用中的函数相同，并在指向该函数的指针被实际读取之前开始执行——如果跳跃预测是错误的，事情会变得很慢。

同样的事情也会发生在您的代码中。您不再使用分支预测，但处理器使用跳转预测来预测调用四个函数指针中的哪一个，当函数指针不可预测时，这会减慢速度。

Answer 2

你可以试试这样的东西：

switch(s & 7) {
case 0:
    /* _process_mem_64 */
    break;
case 1:
case 3:
case 5:
case 7:
    /* _process_mem_8 */
    break;
case 2:
case 6:
    /* _process_mem_16 */
    break;
case 4:
    /* _process_mem_32 */
    break;
}

这只涉及跳转表的单个跳转，不需要调用指令。

Answer 3

第二个变量仅仅是一个更隐含的条件吗，因为CPU仍然无法预测将要调用的函数？我假设这与分支目标预测有关，对吗？

是的，无条件间接分支需要命中分支目标缓冲区，以便CPU确定从何处获取代码。现代CPU是高度流水线化的，如果要避免管道中的气泡，在没有任何事情可做的地方，就需要在执行之前提取代码。要等到计算出magic，已经太晚了，无法避免指令获取气泡。我认为，性能计数器将BTB未命中显示为分支预测失误。

正如我在一篇评论中所建议的，如果可以的话，你应该重组你的代码，在一个矢量化的循环中引入和清除标量。intro向上处理元素，直到到达对齐的元素。清理循环处理在最后一个完整向量之后还有非零数量的元素需要处理的情况。这样你就不会因为第一个元素的大小或排列不理想而陷入标量循环。

根据您正在处理的内容，如果重复工作和重叠是可以的，那么您可以创建一个无分支的启动程序，执行一个未对齐的块，然后将其余的对齐。有些库可能会实现类似这样的< code>memset:

// not shown: check that count >= 16
endp = dest + count;
unaligned_store_16B( dest );    // e.g. x86 movdqu
dest+=16;
dest &= ~0xf;  // align by 16, first aligned write overlaps by up to 15B
for ( ; dest < endp-15 ; dest+=16) {
    aligned_store_16B( dest );  // e.g. x86 movdqa
}
// handle the last up-to-15 bytes from dest to endp similarly.

这使得处理循环分支的未对齐开始变得无意义，因为您不在乎未对齐的开始有多少重叠。

注意，大多数单缓冲函数是不可重复的。例如，in-place a[i] *= 2或< code>sum =a[i]需要避免两次处理相同的输入。通常使用标量循环，直到到达对齐的地址。< code>a[i]

有两个独立指针的函数可能会因不同的量而错位，这就更为棘手了。你必须小心，不要用遮罩改变它们的相对偏移memcpy是将数据从src处理到dest缓冲区的函数的最简单示例<如果（src3）==0和 memcpy

在 x86 上，当地址对齐时，未对齐的移动指令（movdqu 和友方）与对齐所需的版本一样快。因此，在 src 和 dest 具有相同（错误）对齐的特殊情况下，您不需要单独的循环版本，并且负载和存储都可以对齐。IIRC，对于英特尔尼黑勒姆和更新的CPU以及最近的AMD来说都是如此。

// check count >= 16
endp = dest + count;
unaligned_copy_16B( dest, src );  // load with movdqu, store with movdqu
// src+=16; dest+=16;  // combine this with aligning dest, below

dest_misalign = dest & 0xf;  // number of bytes the first aligned iteration will overlap
src  += 16 - dest_misalign;  // src potentially still misaligned
dest += 16 - dest_misalign;  // dest aligned

for ( ; dest <= endp-16 ; src+=16, dest+=16) {
    tmpvec = unaligned_load_16B( src ); // x86 movdqu is fast if src is aligned
    aligned_store_16B( dest, tmpvec );  // x86 movdqa
}
// handle the last dest to endp bytes.

对齐的dest可能比对齐的源更有可能。当我们对齐的指针已经对齐时，不会发生重叠的重复工作。

如果你不做memcpy，让src对齐是一个优势，这样负载就可以折叠成另一条指令作为内存操作数。这节省了一条指令，在许多情况下还在内部节省了一个Intel uop。

对于src和dest具有不同对齐方式的情况，我还没有测试是对齐加载和非对齐存储更快，还是相反。我选择一致的商店是因为潜在的商店-

仅当缓冲区很小（可能高达 64B？），或者如果您的下一个循环从缓冲区的末尾开始读取（即使开始已被逐出，缓冲区仍将在缓存中），才会在下一个循环中存储转发到下一个循环中的负载。否则，存储到缓冲区的开始将使其从存储缓冲区变为 L1，因此存储转发将不起作用。

对于具有不同对齐方式的大型缓冲区，对齐负载和未对齐存储可能会做得更好。我只是在这里编造东西，但如果未对齐的商店可以快速退休，即使它们越过缓存行或页面行，这可能是真的。当然，在实际加载数据之前，未对齐的负载无法停用。随着更多的加载/存储指令在飞行中，缓存错过停滞的可能性就会降低。（您可能会利用更多 CPU 的加载/存储缓冲区。再次，纯粹的猜测。我试图谷歌未对齐的商店是否比未对齐的负载更好或更差，但只是得到了关于如何做到这一点的点击，以及适用于两者的未对齐惩罚。