c++ 间接分支预测 分支预测和分支目标预测优化




间接分支预测 (3)

我的代码经常调用具有多个(不可预知的)分支的函数。 当我分析时,我发现它是一个小瓶颈,在有条件的JMP使用大部分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数组中的func)花费了很长时间。

第二个变体是一个更隐含的条件,因为CPU仍然不能预测将被调用的函数? 我是否正确地认为这与分支目标预测有关?

为什么会发生这种情况,还有其他解决方案吗?

编辑:

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


你可以尝试这样的事情:

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

这只涉及跳转到一个跳转表,并不需要调用指令。


现代处理器不仅具有分支预测功能,而且具有跳转预测功能。 例如,如果你调用一个虚拟函数,它可以预测实际的函数和前面的调用一样,并且在实际读取函数的指针之前开始执行 - 如果跳转预测是错误的,事情会变得很慢。

同样的事情发生在你的代码中。 您不再使用分支预测,但是处理器使用跳转预测来预测四个函数指针中的哪一个被调用,并且当函数指针是不可预知的时,这会变慢。


第二个变体是一个更隐含的条件,因为CPU仍然不能预测将被调用的函数? 我是否正确地认为这与分支目标预测有关?

是的,无条件的间接分支需要CPU的分支 - 目标 - 缓冲区命中来确定从下一个位置获取代码的位置。 现代的CPU是非常流水线的,如果他们要避免管道中没有任何东西需要做的事情,那么需要在代码执行前取得代码。 不得不等待直到计算出magic还为时过晚,以至于不能避免指令取出泡泡。 性能计数器将显示BTB错过作为分支mispredict,我想。

正如我在评论中所建议的那样,如果可以的话,你应该重构你的代码来做一个标量的介绍和清理一个向量化的循环。 介绍处理元素,直到你到达一个对齐的元素。 清理循环处理在最后一个完整向量之后剩下要处理的非零数量的元素的情况。 那么你不会因为第一个元素的大小或对齐不理想而做一个标量循环。

根据你正在处理的内容,如果可以重复工作并重叠,那么你可以做一个没有对齐块的无分区启动,然后其余的对齐。 一些图书馆可能会阻止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] *= 2sum+=a[i]需要避免两次处理相同的输入。 通常用一个标量循环直到找到一个对齐的地址。 尽管如此maxval = max(a[i], maxval) a[i] &= 0x7f ,或maxval = max(a[i], maxval)也是例外。

带有两个独立指针的函数可能会被不同的数量错位 。 你必须小心,不要用掩蔽来改变它们的相对偏移量。 memcpy是将数据从src处理到dest缓冲区的最简单的例子。 如果(src+3) %16 == 0(dest+7) %16 ==0memcpy必须工作。 除非您可以对呼叫者施加限制,否则一般情况下可以做的最好的做法是在主循环中对每个负载或每个商店进行对齐。

在x86上,未对齐的移动指令( movdqu和friends) 与地址对齐时的对齐所需版本一样快。 因此,当src和dest具有相同(错误)对齐的情况下,您不需要单独的特殊情况下的循环版本,并且可以对齐加载和存储。 IIRC,对于Intel 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.

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

如果你没有执行memcpy,那么将src对齐是一个好处,所以load可以折叠到另一个指令中作为内存操作数。 这节省了一个指令,并且在很多情况下还可以在内部节省英特尔uop。

对于src和dest具有不同对齐的情况,我还没有测试过对齐加载和未对齐的商店是否更快,反之亦然。 我选择了对齐的商店,因为潜在的商店 - >短期缓冲区的负载转发的好处。 如果dest缓冲区是对齐的,并且只有一对向量长,并且将被再次读取,那么如果负载穿过两个前面的存储之间的边界,那么来自dest的对齐的负载将停止约10个周期(Intel SnB)还是把它放到了L1缓存中。 (即存储转发失败)。 请参阅http://agner.org/optimize/以了解有关低级细节的信息(尤其是微型指南)。

如果缓冲区很小(可能高达64B?),或者如果下一个循环从缓冲区的末端开始读取(即使缓冲区仍然在缓存中),只会在下一个循环中存储从memcpy到下一个循环的加载开始已经被驱逐)。 否则,到缓冲区开始的存储将会从存储缓冲区到L1,所以存储转发不会起作用。

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





branch-prediction