分支预测和分支目标预测优化
Branch prediction and branch target prediction optimization
我的代码频繁调用具有多个（不可预测的）分支的函数。当我分析时，我发现这是一个小瓶颈，大部分 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%，并且 CALL 本身（对 mem_funcs 数组中的函数）花费了很长时间。
第二个变体是否只是一个更隐含的条件，因为 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;
}
这只涉及一次跳转table，不需要调用指令。
Is the second variation simply a more implicit conditional, as the CPU
still cannot predict the function that will be called? Am I correct in
assuming that this has to do with branch target prediction?
是的，无条件间接分支需要 CPU 的分支目标缓冲区命中以确定下一步从何处获取代码。现代 CPUs 是大量流水线化的，如果它们要避免管道中无事可做的气泡，就需要在它们执行之前就获取代码。必须等到 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 缓冲区的数据的函数的最简单示例。如果 (src+3) %16 == 0 和 (dest+7) %16 ==0，memcpy 必须工作。除非您可以对调用者施加约束，否则您通常可以做的最好的事情就是让每个加载或每个存储在主循环中对齐。
在 x86 上，未对齐的移动指令（movdqu 和朋友）在地址对齐 时与需要对齐的版本一样快。因此，当 src 和 dest 具有相同（错误）对齐并且加载和存储都可以对齐时，您不需要针对特殊情况的单独版本的循环。 IIRC，对于 Intel Nehalem 和更新的 CPUs，以及最近的 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 缓冲区已对齐，并且只有几个向量长，并且将立即再次读取，那么如果负载跨越两个先前存储之间的边界，来自 dest 的对齐加载将停止约 10 个周期（Intel SnB）尚未进入 L1 缓存。 （即存储转发失败）。有关此类低级详细信息的信息，请参阅 http://agner.org/optimize/（尤其是微架构指南。）
只有当缓冲区很小（可能高达 64B？），或者如果你的下一个循环从缓冲区的末尾开始读取（它仍然会即使开头已经被驱逐，也要在缓存中）。否则，缓冲区开头的存储将从存储缓冲区到 L1，因此存储转发不会起作用。
对于具有不同对齐方式的大型缓冲区，对齐的加载和未对齐的存储可能会做得更好。我只是在这里胡编乱造，但如果未对齐的存储即使跨越缓存行或页面行也可以快速退出，这可能是正确的。当然，在实际加载数据之前，未对齐的加载不会退出。随着更多 load/store 指令的运行，缓存未命中的可能性就会降低。 （您可能会利用更多 CPU 的 load/store 缓冲区。）同样，纯粹的猜测。我尝试 google 判断未对齐的存储是否比未对齐的加载更好或更差，但只是得到了关于如何做它们的命中，以及适用于两者的未对齐惩罚。
现代处理器不仅有分支预测，还有跳转预测。例如，如果你调用一个虚函数，它可能会预测实际函数与之前的调用相同，并在实际读取函数指针之前开始执行——如果跳转预测错误，事情就会变慢。
同样的事情发生在你的代码中。您不再使用分支预测，但处理器使用跳转预测来预测调用四个函数指针中的哪一个，当函数指针不可预测时，这会减慢速度。
我的代码频繁调用具有多个（不可预测的）分支的函数。当我分析时，我发现这是一个小瓶颈，大部分 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%，并且 CALL 本身（对 mem_funcs 数组中的函数）花费了很长时间。
第二个变体是否只是一个更隐含的条件，因为 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;
}
这只涉及一次跳转table，不需要调用指令。
Is the second variation simply a more implicit conditional, as the CPU still cannot predict the function that will be called? Am I correct in assuming that this has to do with branch target prediction?
是的，无条件间接分支需要 CPU 的分支目标缓冲区命中以确定下一步从何处获取代码。现代 CPUs 是大量流水线化的，如果它们要避免管道中无事可做的气泡，就需要在它们执行之前就获取代码。必须等到 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 缓冲区的数据的函数的最简单示例。如果 (src+3) %16 == 0 和 (dest+7) %16 ==0，memcpy 必须工作。除非您可以对调用者施加约束，否则您通常可以做的最好的事情就是让每个加载或每个存储在主循环中对齐。
在 x86 上，未对齐的移动指令（movdqu 和朋友）在地址对齐 时与需要对齐的版本一样快。因此，当 src 和 dest 具有相同（错误）对齐并且加载和存储都可以对齐时，您不需要针对特殊情况的单独版本的循环。 IIRC，对于 Intel Nehalem 和更新的 CPUs，以及最近的 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 缓冲区已对齐，并且只有几个向量长，并且将立即再次读取，那么如果负载跨越两个先前存储之间的边界，来自 dest 的对齐加载将停止约 10 个周期（Intel SnB）尚未进入 L1 缓存。 （即存储转发失败）。有关此类低级详细信息的信息，请参阅 http://agner.org/optimize/（尤其是微架构指南。）
只有当缓冲区很小（可能高达 64B？），或者如果你的下一个循环从缓冲区的末尾开始读取（它仍然会即使开头已经被驱逐，也要在缓存中）。否则，缓冲区开头的存储将从存储缓冲区到 L1，因此存储转发不会起作用。
对于具有不同对齐方式的大型缓冲区，对齐的加载和未对齐的存储可能会做得更好。我只是在这里胡编乱造，但如果未对齐的存储即使跨越缓存行或页面行也可以快速退出，这可能是正确的。当然，在实际加载数据之前，未对齐的加载不会退出。随着更多 load/store 指令的运行，缓存未命中的可能性就会降低。 （您可能会利用更多 CPU 的 load/store 缓冲区。）同样，纯粹的猜测。我尝试 google 判断未对齐的存储是否比未对齐的加载更好或更差，但只是得到了关于如何做它们的命中，以及适用于两者的未对齐惩罚。
现代处理器不仅有分支预测，还有跳转预测。例如，如果你调用一个虚函数，它可能会预测实际函数与之前的调用相同，并在实际读取函数指针之前开始执行——如果跳转预测错误，事情就会变慢。
同样的事情发生在你的代码中。您不再使用分支预测，但处理器使用跳转预测来预测调用四个函数指针中的哪一个，当函数指针不可预测时，这会减慢速度。