logo标签列表

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

c++coptimizationx86branch-prediction
10

我的代码频繁调用一个有多个（不可预测的）分支的函数。当我进行性能分析时，发现这是一个轻微的瓶颈，大部分CPU时间用于条件跳转操作。

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

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％，而CALL本身（调用mem_funcs数组中的函数）花费了很长时间。
第二个变体是否只是更隐式的条件语句，因为CPU仍然无法预测将要调用的函数？我是否正确地认为这与分支目标预测有关？
为什么会发生这种情况，还有其他解决方案吗？
编辑：感谢您提供的想法，但我也想知道为什么会出现这种情况的解释。
2
这看起来像是一个处理对齐/不对齐内存地址的函数。你能做些什么来保证对齐吗？你知道哪个路径被最频繁地执行吗？你能预测调用点的对齐方式吗（例如，如果你知道你的内存块是64字节对齐的）？ - nneonneo
它确实涉及对齐/非对齐的内存，但在这种情况下我无法保证大小或对齐。 - frank90
2
@nneonneo：即使您无法保证对齐或大小，通常也可以进行逐字节介绍，直到您对齐，然后使用向量，直到距离结尾不足15B，然后再进行逐字节清理。因此，大部分时间您都在处理大的对齐块，并进行标量设置/清理。 - Peter Cordes
达夫设备？或其衍生物。 - too honest for this site
3个回答
7
第二个变量只是更加隐晦的条件语句吗，因为CPU仍然无法预测将要调用的函数？我猜想这与分支目标预测有关吗？
是的，无条件间接分支需要分支目标缓冲器命中，以便CPU确定从哪里获取代码。现代CPU具有高度流水线化，如果它们要避免管道中没有任何任务可执行的气泡，就需要提前获取代码。等到计算出“magic”时已经太晚了，无法避免指令获取气泡。我认为性能计数器将BTB未命中显示为分支预测错误。
正如我在评论中建议的那样，如果可以的话，您应该重构代码，在向量化循环周围进行标量介绍和清理。介绍处理元素，直到达到对齐的元素。清理循环处理最后一个完整向量之后还剩余一定数量元素的情况。然后，您不必因为第一个元素的大小或对齐方式不理想而陷入做标量循环的困境。

根据您正在处理的内容，如果重复工作和重叠是可以接受的，则可以创建一个无分支启动程序，执行不对齐的块，然后执行其余对齐的部分。一些库可能实现了类似于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.

这使得处理循环分支的非对齐起点变得无需分支，因为您不需要关心非对齐起点重叠了多少。
请注意，大多数单缓冲函数都不能重复执行。例如，就地执行 a[i] *= 2 或 sum+=a[i] 需要避免重复处理相同的输入。通常使用标量循环直到达到对齐地址。但是，a[i] &= 0x7f 或 maxval = max(a[i], maxval) 是例外。
具有两个独立指针的函数，可以由不同数量的偏移量使其错位。您必须小心，不要通过掩码改变它们的相对偏移量。 memcpy 是一个从源缓冲区到目标缓冲区处理数据的最简单示例。如果(src+3)%16==0和(dest+7)%16==0，则memcpy必须工作。除非您可以对调用者施加约束，否则通常情况下，您所能做的最好的事情就是在主循环中对每个加载或每个存储进行对齐。
在x86上，不需要对齐的移动指令（movdqu等）与要求对齐的版本一样快，当地址对齐时。因此，当src和dest具有相同的（错位）对齐方式时，不需要为特殊情况创建单独的循环，并且负载和存储都可以对齐。据我所知，这适用于英特尔Nehalem和更新的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.
一个对齐的目标指针比对齐的源指针更可能。当我们要对齐的指针已经对齐时，不会发生重复工作的重叠。
如果你没有进行memcpy，那么让src对齐可能是有优势的，因为加载可以折叠到另一个指令中作为内存操作数。这节省了一条指令，在许多情况下也节省了Intel uop的内部开销。
对于src和dest具有不同对齐方式的情况，我还没有测试过做对齐的加载和未对齐的存储哪种更快。我选择了对齐存储，因为短缓冲区可能会有存储->加载转发的好处。如果目标缓冲区是对齐的，并且只有几个向量长，并且将立即再次读取，则从dest进行对齐加载将停顿约10个周期（Intel SnB），如果加载跨越两个前置存储之间的边界，这些存储尚未进入L1高速缓存。（即存储转发失败）。请参见http://agner.org/optimize/以获取此类低级细节的信息（特别是微架构指南）。

如果缓冲区很小（可能最多达到64B），或者下一个循环从缓冲区的末尾开始读取（即使开头已经被驱逐出缓存），那么从memcpy到下一个循环中的负载的存储转发只会发生。否则，对于缓冲区开头的存储将从存储缓冲区传输到L1，因此存储转发不会起作用。

对于具有不同对齐方式的大缓冲区，对齐的负载和不对齐的存储可能更好。我只是在这里编造东西，但是如果不对齐的存储可以快速退役，即使它们跨越缓存线或页面线，也可能是真实的。当然，直到实际加载数据，不对齐的负载才能退役。随着更多的load / store指令在飞行中，缓存未命中导致停顿的机会就会减少。（您潜在地利用了CPU的更多load / store缓冲区）。再次纯属猜测。我试图搜索不对齐的存储是否比不对齐的负载更好或更差，但只获得了有关如何执行它们以及适用于两者的不对齐惩罚的命中。

1
谢谢您的解释！我也尝试着实现了您的解决方案（不包括循环，因为我没有进行复制），即使有初始化的开销，对于小块来说它也加快了速度。 - frank90
如果你需要使用memcpy，那么在许多系统中调用memcpy是最快的方法。例如，MacOS X会在启动时设置针对计算机中特定处理器进行优化的memcpy代码，并且执行你甚至无法理解的优化。 - gnasher729
@gnasher729：我使用memcpy作为一个易于理解的可重复操作的例子，而不是你实际上想要自己实现的东西。 - Peter Cordes
使用 +=15 会更好吗？ - user3528438
@user3528438: 你的意思是在非对齐复制后使用 dest+=15，而不是使用 +=16 和掩码吗？不，你不能避免掩码，因为你需要从任何16种可能的输入对齐中取出对齐指针，包括实际上一开始就对齐的情况。如果你使用 +=15 然后再使用掩码，那么在输入已经对齐的（希望这是常见情况）情况下会重新复制前16B。 - Peter Cordes
1
@user3528438：思考这个问题让我意识到当源和目标具有不同的对齐方式时，我会出现一个错误。现在已经修复了。我添加了memset作为一个简单的例子，它是一个可以重新处理字节的单缓冲函数。（大多数原地函数都不可重复执行，但是memset可以）。 - Peter Cordes
4
你可以尝试这样做：

你可以尝试类似以下的方法：

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;
}

这仅涉及一次跳转到跳转表中，并不需要调用指令。

谢谢，但是是代码引起了分支，而不是调用指令。在我的情况下，删除它解决了问题。 - frank90
3
现代处理器不仅具有分支预测，还具有跳转预测。例如，如果你调用了一个虚函数，它可能会预测实际函数与上次调用相同，并在读取函数指针之前开始执行 - 如果跳转预测是错误的，那么速度会变慢。
在你的代码中也会出现这种情况。虽然你不再使用分支预测，但处理器会使用跳转预测来预测将调用哪个四个函数指针，当函数指针是不可预测时，就会导致速度减慢。
这与我在第一段中所说的相同。分支目标缓冲器必须正确预测间接分支将跳转到哪个位置，否则会出现停顿。在CPU术语中，无条件跳转仍被称为分支，因为它们会破坏指令字节进入流水线的顺序流程。 - Peter Cordes
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接