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

Question

我最近询问了有关Code Review 的问题,以检查名为QuickMergeSort的排序算法.我不会详细介绍,但在某些时候算法执行内部mergesort:它不是使用额外的内存来存储要合并的数据,而是交换元素以与原始序列的另一部分中的元素合并,这不是否则就合并而言.这是我关注的算法的一部分:执行合并的函数:

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
}

该函数改编自libc ++实现中的eponym函数std::inplace_merge; 这个新版本将元素与原始数组的另一部分交换,而不是从辅助数组中移动元素.

由于合并是内部的,我意识到我实际上并不需要有两种不同的输入类型:InputIterator1并且InputIterator2总是相同的.然后我开始意识到,由于on 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功能,整体排序算法比原始排序算法慢1.5倍half_inplace_merge,我不知道为什么.我已经尝试了几个编译器优化级别,以避免潜在的别名问题的几个技巧,但似乎问题来自无分支技巧本身.

那么,是否有人能够解释为什么无分支代码更慢？

---

附录:对于那些想要像我一样运行相同基准的人......好吧,这将有点困难:我使用了个人图书馆的基准测试,其中包括许多内容; 您需要下载库,在某处添加此文件,并在突出显示的部分附近添加所需的行以调用后运行此基准quick_merge_sort(您需要将程序的标准输出重定向到profiles子目录中的文件).然后,您需要运行此Python脚本以查看结果,并添加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

主要的减速来自取消引用store []中包含的两个项目,这是比较和交换所需要的,并且在循环内.没有第二个技巧的版本中不存在这些指令.

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