我最近问了一个关于代码审查的问题，以审查一种名为 quickmergesort 的排序算法。我不会获取详细信息，但是在某些时候，算法执行内部Mergesort：而不是使用其他内存存储数据合并，而是将元素交换以与原始序列的另一部分合并与ISN的另一部分合并否则对合并的关注。这是我关注的算法的一部分：执行合并的功能：
template<
typename InputIterator1,
typename InputIterator2,
typename OutputIterator,
typename Compare = std::less<>
>
auto half_inplace_merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare compare={})
-> void
{
for (; first1 != last1; ++result) {
if (first2 == last2) {
std::swap_ranges(first1, last1, result);
return;
}
if (compare(*first2, *first1)) {
std::iter_swap(result, first2);
++first2;
} else {
std::iter_swap(result, first1);
++first1;
}
}
// first2 through last2 are already in the right spot
}
该函数是根据std::inplace_merge的LIBC 实现中的同名函数进行了调整的；该新版本将元素与原始数组的另一部分交换，而不是从辅助数组中移动元素。
由于合并为，我意识到我实际上并不需要两个单独的输入类型： InputIterator1和 InputIterator2始终相同。然后我意识到，由于first1和first2上的操作总是相同的，因此我可以将它们存储在两元素的数组中，并使用比较的结果来索引数组，以了解要交换哪个迭代器并增加。有了这个小技巧，我摆脱了分支，获得了一种大部分无分支合并算法：
template<
typename InputIterator,
typename OutputIterator,
typename Compare = std::less<>
>
auto half_inplace_merge(InputIterator first1, InputIterator last1,
InputIterator first2, InputIterator last2,
OutputIterator result, Compare compare={})
-> void
{
InputIterator store[] = { first1, first2 };
for (; store[0] != last1; ++result) {
if (store[1] == last2) {
std::swap_ranges(store[0], last1, result);
return;
}
bool cmp = compare(*store[1], *store[0]);
std::iter_swap(result, store[cmp]);
++store[cmp];
}
// first2 through last2 are already in the right spot
}
现在，问题是：使用此新的half_inplace_merge功能，总体排序算法比原始half_inplace_merge慢1.5倍，我不知道为什么。我尝试了几个编译器优化级别，以避免潜在的混叠问题的几个技巧，但似乎问题来自无分支的技巧。
那么，是否有人能够解释为什么无分支代码较慢？
附录：对于那些想要与我相同的基准的人……好吧，这将有点困难：我使用了个人库中的基准，其中包括许多东西；您需要下载库，将此文件添加到某个地方，并在添加了所需的行后运行此基准，以调用quick_merge_sort在突出显示的部分附近（您需要将程序的标准输出重定向到一个文件中profiles子目录）。然后，您需要运行此Python脚本以查看结果，并将quick_merge_sort添加到突出显示的行中。请注意，需要安装numpy和matplotlib。
如此巨大的差异是两个条件的乘积。
第一个条件与原始代码有关。现场合并是如此有效，即使在汇编语言级别进行编码，也很难更快地设计任何内容。仿制药的应用很简单，因此编译器**在使用或不使用它的情况下产生了相同的组件。由于算法实现是有效的，因此在循环中添加的几个机器指令能够产生问题中指示的重大比例更改。
**整个答案中的汇编细节都使用G 6.2.1 20160916，默认的Fedora 24 DNF软件包，以及Linux内核4.8.8-200.FC24.x86_64。运行时是Intel I7-2600 8M缓存。也要使用AMP SAM3X8E ARM Cortex-M3，带有无臂-EABI-G 4.8.3-2014Q1。
第二条件与问题的第3句2句子2中描述的第二个技巧有关。第一个技巧是模板中类型的减少，并未在汇编语言中产生任何重大变化。第二个技巧在两个调用的编译器输出中产生了影响flop的组装级别差异。
此预编译器hack可以简化测试。
#ifdef ORIG
#define half_inplace_merge half_inplace_merge_orig
#else // ORIG
#define half_inplace_merge half_inplace_merge_slow
#endif // ORIG
...
half_inplace_merge(niInA.begin(), niInA.end(),
niInB.begin(), niInB.end(),
niOut.begin(), compare);
执行并在bash shell中使用这些命令进行比较。
g++ -DORIG -S -fverbose-asm -o /tmp/qq.orig.s /tmp/qq.cpp
g++ -DSLOW -S -fverbose-asm -o /tmp/qq.slow.s /tmp/qq.cpp
araxis.sh /tmp/qq.orig.s /tmp/qq.slow.s # to run Araxis Merge in Wine
这些说明是初始化inputiterator商店[]的结果，但这在循环之外。
leaq -48(%rbp), %rax #, _4
movq -64(%rbp), %rdx # first1, tmp104
movq %rdx, (%rax) # tmp104, *_5
leaq 8(%rax), %rdx #, _9
movq -96(%rbp), %rax # first2, tmp105
movq %rax, (%rdx) # tmp105, *_9
主要放慢速度是根据比较和交换所需的储存[]中包含的两个项目，而在循环中。如果没有第二个技巧，这些说明就不存在。
movb %al, -17(%rbp) # _27, cmp
movzbl -17(%rbp), %eax # cmp, _29
cltq
...
movzbl -17(%rbp), %edx # cmp, _31
leaq -48(%rbp), %rax #, tmp121
movslq %edx, %rdx # _31, tmp122
salq $3, %rdx #, tmp123
addq %rdx, %rax # tmp123, _32
尽管没有技巧的版本的条件下有代码重复，但仅影响代码的紧凑性，添加了两个呼叫，五个动作和一个比较指令。进行就地合并所需的CPU周期数量是相同的，因此分支之间的分支相同，并且两者都缺少上面列出的说明。
对于几个语法排列中的每一个，都尝试过，从而消除了分支中的冗余，以不可避免地提高紧凑度，从而导致沿执行路径所需的其他指令。
到目前为止讨论的各种排列的指令序列的详细信息将因编译器到编译器，优化选项选择甚至调用功能的条件而有所不同。
从理论上讲，编译器可以采用AST（抽象符号树）重构规则（或等效）来检测和减少该功能的任何一个版本的程序内存和CPU周期要求。这样的规则具有与要在代码中优化的模式相匹配的先例（搜索模式）。
用第二个技巧对代码的优化速度需要一个规则前提，该规则在循环的内部和外部都以非典型得分[]抽象匹配。在没有第二个技巧的情况下检测分支冗余是一个更合理的目标。
将两个语句集成在每个分支中，一个人可以看到AST中的两个类似模式如何简单，以使重构规则先进以匹配和执行所需的代码尺寸减少。如果有的话，这种情况的速度很小。
if (compare(*first2, *first1)) {
std::iter_swap(result, first2 ++);
} else {
std::iter_swap(result, first1 ++);
}
以下只是一个简短的直觉解释：
如果我们扩大所有内容，并假设迭代器是正常的指针，则在第一个示例中可以将所有迭代器存储在寄存器中。
在无分支代码中，由于store[cmp]和++store[cmp]，我们无法轻松地执行此操作，这意味着所有使用store[0]和store[1]的开销。
因此（在这种情况下）最大化使用寄存器比避免分支更重要。