fra*_*k90 9 c c++ optimization x86 branch-prediction
我的代码经常调用具有多个(不可预测的)分支的函数.当我分析时,我发现它是一个小瓶颈,在条件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仍然无法预测将被调用的函数？假设这与分支目标预测有关,我是否正确？
为什么会发生这种情况,还有其他解决方案吗？
编辑:
感谢您的想法,但我想解释为什么会发生这种情况.
第二个变体只是一个更隐式的条件,因为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处理到dest缓冲区的函数的最简单示例. memcpy必须工作,如果(src+3) %16 == 0和(dest+7) %16 ==0.除非您可以对调用者设置约束,否则您通常可以做的最好的事情是每个负载或每个存储在主循环中对齐.
在x86上,则非对齐移动指令(movdqu和朋友)都只是作为对齐要求的版本一样快,当地址是对齐的.因此,当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对齐是有利的,所以加载可以作为内存操作数折叠到另一个指令中.这样可以保存指令,并且在许多情况下还可以在内部保存Intel uop.
对于src和dest具有不同对齐的情况,我还没有测试对齐加载和未对齐存储是否更快,或者相反.我选择了对齐的商店,因为短缓冲区可能具有存储 - >负载转发优势.如果dest缓冲区是对齐的,并且只有几个向量长,并且将立即再次读取,那么如果负载越过前两个商店之间的边界,则来自dest的对齐加载将停止~10个周期(Intel SnB) t使它成为L1缓存.(即存储转发失败).有关此类低级别详细信息(尤其是微型指南)的信息,请参见http://agner.org/optimize/.
如果缓冲区很小(可能高达64B？),或者下一个循环从缓冲区的末尾开始读取(即使缓存仍然在缓存中),只会发生从memcpy到下一循环中的加载的存储转发一开始就已被驱逐了).否则,缓冲区起始处的存储将从存储缓冲区转移到L1,因此存储转发将不起作用.
对于具有不同对齐的大型缓冲区,对齐的加载和未对齐的存储可能会做得更好.我只是在这里制作东西,但如果未对齐的商店即使跨越缓存行或页面行也可以快速退出,这可能是真的.当然,在实际加载数据之前,未对齐的加载不能退出.随着飞行中的加载/存储指令越来越多,缓存未命中的可能性就越小.(您可能正在利用更多CPU的加载/存储缓冲区.)同样,纯粹的推测.我试图谷歌如果未对齐的商店比未对齐的负载更好或更差,但只是有关于如何做到这一点的命中,以及适用于两者的错位罚款.