无分支内部合并比带分支的内部合并慢

Question

我最近在 Code Review 上要求 a question 审查名为 QuickMergeSort 的排序算法。我不会详细介绍，但在某些时候算法会执行内部合并排序：它不会使用额外的内存来存储要合并的数据，而是交换元素以与原始序列另一部分的元素合并，这是'否则与合并有关。这是我关心的算法部分：执行合并的函数：

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++ 实现中的 eponym 函数；这个新版本将元素与原始数组的另一部分交换，而不是从辅助数组中移动元素。

由于合并是内部，我意识到我实际上并不需要有两个单独的输入类型：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 倍，我不知道为什么。我已经尝试了几种编译器优化级别，几种避免潜在别名问题的技巧，但问题似乎来自无分支技巧本身。

那么，有人能解释为什么无分支代码速度较慢吗？

附录： 对于那些想要运行与我一样的基准的人...好吧，这会有点困难：我使用了来自个人图书馆，里面有很多东西；您需要下载 the library, to add this file somewhere, and to run this benchmark after having added the required line to invoke quick_merge_sort near the highlighted section (you will need to redirect the standard output of the program to a file in a profiles subdirectory). Then you'll need to run this Python script 才能查看结果，将 quick_merge_sort 添加到突出显示的行。注意需要安装NumPy和matplotlib

Answer 1

如此大的差异是两个条件的产物。

第一个条件与原代码有关。就地合并非常高效，即使在汇编语言级别手动编码，也很难设计出更快的东西。泛型的应用很简单，因此编译器无论是否使用泛型都产生相同的程序集。因为算法实现是高效的，所以只需要在循环中添加几条机器指令就能够产生问题中指示的显着比例变化。

** 此答案中的编译细节使用的是 g++ 6.2.1 20160916，默认的 Fedora 24 dnf 包，以及 LINUX 内核 4.8.8-200.fc24.x86_64。运行时是 Intel i7-2600 8M 缓存。也适用于带有 arm-none-eabi-g++ 4.8.3-2014q1.

的 Atmel SAM3X8E ARM Cortex-M3

第二个条件与问题第3段第2句中描述的第二个技巧的编译有关。第一个技巧，即模板中类型的减少，并未对汇编语言产生任何重大变化。第二个技巧在两个调用的编译器输出中产生了影响触发器的汇编级别差异。

这个预编译器 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 中使用这些命令执行和比较会利用预编译器 hack。

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    , %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 ++);
}

Answer 2

以下只是一个简短的直观解释：

如果我们缩小所有内容并假设迭代器是普通指针，我们可以在第一个示例中将所有迭代器存储在寄存器中。

在无分支代码中，由于 store[cmp] 和 ++store[cmp]，我们不能轻易做到这一点 - 这意味着所有使用 store[0] 和 [=] 的开销13=]。

因此（在这种情况下）最大限度地使用寄存器比避免分支更重要。

无分支内部合并比带分支的内部合并慢

Branchless internal merge slower than internal merge with branch

c++

sorting

performance

branch-prediction