在Qsort上跳动（2019）
最近，Daniel Lemire解决了随机选择N个不同数字的主题。在我们要对输出进行排序的情况下，一种很明显的解决方案是：对随机选择的值进行排序并对列表进行重复数据删除，这很容易，因为现在相同的值是相邻的。 1个
尽管Daniel建议了一种聪明的方法来完全避免排序2，但我也对它们为何对sort方法的基本性能感兴趣：每个元素花费100 ns以上的时间，这意味着100多个CPU时钟周期，通常甚至更多指令比那（在超标量处理器上）好！作为健全性检查，快速基准测试（性能记录./bench＆amp;＆amp;性能报告）显示，这种方法花费的时间中有90％以上是在排序例程qsort中进行的-因此，我们专注于此步骤，而不是说重复数据删除步骤或初始随机数生成。这自然会引起一个问题：在对整数排序时qsort有多快，我们能做得更好吗？
这篇文章的所有代码都可以在GitHub上找到，因此，如果您想遵循在编辑器中打开的代码，请继续进行操作（警告：如果您先仔细研究一下代码，显然会破坏代码）。
首先，让我们看一下qsort在做什么，看看是否有任何低调的性能成果。我们使用perf record ./bench qsort捕获性能分析数据，并使用perf report --stdio打印摘要3：
＃样本：101K事件＆＃39;周期：ppp＆＃39;＃事件计数（大约）：65312285835 ##开销命令共享对象符号＃........ ....... .. .................................................................... ..... ## 64.90％Bench libc-2.23.so [。] msort_with_tmp.part.0 21.45％Bench Bench [。] compare_uint64_t 8.65％Bench libc-2.23.so [。] __memcpy_sse2 0.87％板凳libc-2.23.so [。] __memcpy_avx_unaligned 0.83％板凳[。]主0.41％板凳[kernel.kallsyms] [k] clear_page_erms 0.34％板凳[kernel.kallsyms] [k] native_irq_return_iret 0.31％板凳[。] bench_one
百分比地址拆卸 - - - - - - - - - - - - - - - - - - - - - - - - - -30.55：39200：mov rax，QWORD PTR [r15] 0.61：39203：sub rbp，0x1 0.52：39207：添加r15,0x8 7.30：3920b：mov QWORD PTR [rbx]，rax 0.39：3920e：添加rbx，0x8 0.07 ：39212：测试r12，r12 0.09：39215：je 390e0;合并完成1.11：3921b：测试rbp，rbp 0.01：3921e：je 390e0;合并完成5.24：39224：mov rdx，QWORD PTR [rsp + 0x8] 0.42：39229：mov rsi，r15 0.19：3922c：mov rdi，r13 6.08：3922f：调用r14 0.59：39232：测试eax，eax 3.52：39234： jg 39200 32.69：39236：mov rax，QWORD PTR [r13 + 0x0] 1.31：3923a：sub r12,0x1 1.01：3923e：add r13,0x8 1.09：39242：jmp 3920b＆lt; bsearch @@ GLIBC_2.2.5 + 0x205b＆gt;
取决于您的汇编阅读技能水平，可能并不明显，但这基本上是经典的合并例程：它通过比较每个列表的顶部元素（由r13和r15指向）来合并两个列表，然后存储较小的元素（行QWORD PTR [rbx]，rax），并从该列表中加载下一个元素。还有两个终止检查（测试r12，r12和测试rbp，rbp）。此热循环直接对应于glibc的以下代码（来自文件msort.c 5）：
而（n1＆gt; 0＆amp;＆amp; n2＆gt; 0）{if（（（* cmp）（b1，b2，arg）＆lt; = 0）{*（uint64_t *）tmp = *（uint64_t *）b1; b1 + = sizeof（uint64_t）; -n1; } else {*（uint64_t *）tmp = *（uint64_t *）b2; b2 + = sizeof（uint64_t）; -n2; } tmp + = sizeof（uint64_t）; }
由于“哪个元素更大”分支是高度不可预测的（至少对于看起来随机的输入数据而言），此循环会严重遭受分支错误预测的折磨。实际上，我们在排序约1100万个元素时看到大约1.28亿个错误预测：每个元素接近12个错误预测。
我们还注意到在呼叫r14线路上存在间接呼叫。这对应于源代码中的（* cmp）（b1，b2，arg）表达式：它通过函数指针调用用户提供的比较器函数。由于qsort（）代码是提前编译的，并且可以在共享的libc二进制文件中找到，因此没有任何机会可以内联作为函数指针传递的比较器。
int compare_uint64_t（const void * l_，const void * r_）{uint64_t l = *（const uint64_t *）l_; uint64_t r = *（const uint64_t *）r_;如果（l＆lt; r）返回-1;如果（l> r）返回1;返回0; }
请注意，比较器必须从内存中冗余加载两个位置以进行比较，这是合并循环已完成的操作（合并循环会读取它们，因为它负责移动元素）。
如果将比较器内联到合并循环中，情况会变得更好吗？这就是我们在qsort-inlined 6中所做的，这是现在包含比较器功能7的主循环：
0.07：401dc8：测试rbp，rbp 0.66：401dcb：je 401e0c＆lt; void msort_with_tmp＆lt; CompareU64＆gt;（msort_param const *，void *，unsigned long，CompareU64）+ 0xbc> 3.51：401dcd：mov rax，QWORD PTR [r9] 5.00：401dd0：lea rdx，[rbx + 0x8] 1.62：401dd4：mov rcx，QWORD PTR [rbx] 0.24：401dd7：lea r8，[r9 + 0x8] 6.96： 401ddb：cmp rax，rcx20.83：401dde：cmovbe r9，r8 8.88：401de2：cmova rbx，rdx 0.27：401de6：cmp rcx，rax 6.23：401de9：sbb r8，r8 0.74：401dec：cmp rcx，rax 4.93： ：sbb rdx，rdx 0.24：401df2：不是r8 6.69：401df5：添加rbp，rdx 0.44：401df8：cmp rax，rcx 5.34：401dfb：cmova rax，rcx 5.96：401dff：添加rdi，0x8 7.48：401e03：mov QWORD [rdi-0x8]，rax 0.00：401e07：添加r15，r8 0.71：401e0a：jne 401dc8＆lt; void msort_with_tmp＆lt; CompareU64＆gt;（msort_param const *，void *，unsigned long，CompareU64）+ 0x78＆gt;
一个关键的区别是循环的核心现在是无分支的。是的，仍然有两个条件跳转，但是它们都只是在检查终止条件（要合并的列表之一已用尽），因此我们希望此循环除了最终迭代之外不会出现分支错误预测。确实，我们用性能统计数据来衡量，错误预测率已经从每个元素接近12个错误预测下降到每个元素0.75个左右。该循环只有两个负载和一个存储，因此消除了合并代码和比较器之间的内存访问冗余8。最后，比较器进行三向比较（返回＆lt;，＆gt;和==的离散结果），但合并代码仅需要进行两次比较（＆lt; =或＆gt;）-内联比较器设法删除与区分＆lt;和==案件。
加速速度徘徊在1.77倍左右。请注意，这比简单地消除所有花费在原始版本中的单独比较器功能上的时间要大得多（大约17％的时间意味着如果所有功能时间都消失了，则意味着加速1.2倍）。这是一个很好的例子，它说明了内联不仅可以消除函数调用的开销，而且可以实现进一步的优化，与不仅仅消除与函数调用相关的开销相比，效果更显着。
只需复制现有的glibc（已获得LGPL许可）排序代码以允许内联，我们还能做些什么来加快处理速度？我是用C ++写的，所以＆lt; algorithm＆gt;中可用的C ++排序函数如何？标头？与C的qsort不同，后者通过获取函数指针和有关对象大小的信息而变得通用，而C ++排序函数使用模板来实现通用性，因此直接在头文件中实现。由于排序代码和比较器正在一起编译，因此我们希望比较器易于内联，并且可能还会发生其他优化。
事不宜迟，让我们将std :: sort，std :: stable_sort和std :: partial_sort放入混合中：
除了std :: partial_sort 9之外，C ++的排序功能也很不错。有趣的是std :: stable_sort的实现要比std :: sort严格得多（即，任何稳定的sort也适合std :: sort）以更快的速度结束。我多次重写了此参数，因为有时在重新启动后stable_sort会变慢，有时会更快（如上所示）。当它是“快速”时，它有不到2％的分支错误预测，而当它是缓慢时，它是15％。因此，不确定分支预测器中是否存在某种类型的别名问题，具体取决于分配的物理地址，我不确定这会因运行而异。有关std :: stable_sort较慢时的旧注释，请参见10。
这样就可以了，对吗？我想如果不付出很大的努力，我们就不会击败std :: sort或std :: stable_sort？毕竟，这些大概是由标准库实现者编写的高度优化的排序例程。当然，我们可能希望能够胜过qsort（），但这主要是因为qsort具有内在的劣势，缺乏内联比较器的能力等。
好吧，我们可以尝试的一件事是非比较类。我们知道我们有整数键，所以为什么要坚持成对比较数字-也许我们可以使用基数排序之类的方法将数字直接固定在其最终位置。
我们几乎可以将维基百科文章中的描述复制到如下所示的C ++代码中：
const size_t RADIX_BITS = 8; const size_t RADIX_SIZE =（size_t）1＆lt;＆lt; RADIX_BITS; const size_t RADIX_LEVELS =（63 / RADIX_BITS）+ 1; const uint64_t RADIX_MASK = RADIX_SIZE-1;使用queuetype = std :: vector＆lt; uint64_t＆gt; ; void radix_sort1（uint64_t * a，size_t count）{for（size_t pass = 0; pass＆lt; RADIX_LEVELS; pass ++）{uint64_t shift = pass * RADIX_BITS; std ::数组＆lt;队列类型，RADIX_SIZE＆gt;队列; //根据当前RADIX_BITS大小将每个元素复制到适当的队列中// //＆＃34; digit＆＃34;其中（for size_t i = 0; i 就这么简单。我们决定使用一个字节（即radix-256）作为我们“数字”的大小（尽管很容易通过调整RADIX_BITS常数进行更改），因此我们对uint64_t数组进行了8次遍历，从最小字节到最高字节。每次通过时，我们都基于当前字节的值将当前值分配给256个“队列”（在此情况下为向量）之一，一旦处理完所有元素，我们便将每个队列依次复制回原始数组。完成-列表已排序。 嗯，这并不可怕，虽然它在元素数量较少时肯定会遇到一些问题，但它确实以1,000,000个元素挤到了第一位，在100,000和10,000,000个方面具有竞争力。十几行代码还不错。[^ rewrite] 我们在内核中花费的时间（用户系统时间）与在用户空间中花费的时间大致相同。其他算法在内核中只花费了很少的一部分，几乎全部花费在了安装代码中，而不是实际的排序中。 ＃样本：事件的4K＆＃39; cycles：ppp＆＃39;＃事件计数（大约）：2858148287 ##开销命令共享对象符号＃........ ....... .. .................................................. ......＃29.02％替补席替补席[。] radix_sort1 26.16％替补席libc-2.23.so [。] __memmove_avx_unaligned 4.93％替补席[kernel.kallsyms] [k] clear_page_erms 4.46％基准[kernel.kallsyms] [k]本机_irq_return_iret 3.61％基准[kernel.kallsyms] [k] error_entry 3.04％基准[kernel.kallsyms] [k] swapgs_restore_regs_and_return_to_usermode 2.99％基准[kernel.kallsyms] 1。 [。]主要1.91％基准[kernel.kallsyms] [k] get_page_from_freelist 1.64％基准libc-2.23.so [。] __memcpy_avx_unaligned 1.59％基准[kernel.kallsyms] [k] release_pages 1.40％基准[kernel.kallsyms] [k ] __handle_mm_fault 1.37％基准[kernel.kallsyms] [k] _raw_spin_lock 1.01％基准[kernel.kallsyms] [k] __pagevec_lru_add_fn 0.88％基准[kernel.kallsyms] [k] handle_mm_fault 0.86％基准[kernel.kalls] c_pages_nodemask 0.83％基准[kernel.kallsyms] [k] unmap_page_range 0.75％基准[kernel.kallsyms] [k] try_charge 0.74％基准[kernel.kallsyms] [k] get_mem_cgroup_from_mm 0.70％基准[[] bench_one 0.63％基准[kernel] .kallsyms] [k] __do_page_fault 0.63％基准[kernel.kallsyms] [k] __mod_zone_page_state 0.49％基准[kernel.kallsyms] [k] free_pcppages_bulk 0.45％基准[kernel.kallsyms] [k] page_add_new_all_anon_rmap 0.4。 ] [k] up_read 0.40％基准[kernel.kallsyms] [k] page_remove_rmap 0.36％基准[kernel.kallsyms] [k] __mod_node_page_state 我什至不打算解释__pagevec_lru_add_fn的作用，但这里的基本思想是我们在内核上花费了大量时间，而这样做是因为我们正在分配和释放大量内存。每次通过，我们都会将每个元素推回256个向量中的一个，该向量将不断增长以容纳新元素，然后最终在所有分配的末尾释放所有当前巨型向量。这对内核11中的内存分配路径造成了很大的压力。 让我们尝试一下向量涉及和性能问题时要做的第一件事；也就是说，在开始添加元素之前，让我们为每个向量保留（）内存。只需在每次通过时将其抛出： 这里1.2是一个任意的软化系数，用于说明某些向量将获得比平均元素数更多的事实。确切的值并不重要，只要它不太小即可（0.9是一个差值，几乎evey的矢量都需要最后加倍）。这可以使用radix_sort2，直接进入结果（我删除了一些不太有趣的排序，以减少混乱）： 我想会好一点吗？对于较小的数组，它的性能更好，这可能是因为在此不断调整小向量的大小的开销在那儿更为显着，但对于中等大小的数组，实际上却要慢一些。系统时间较低，但仍然很高： 我们真正想要的是停止丢弃每次通过分配的内存。让我们将队列移出循环，然后在每次迭代中清除它们： void radix_sort3（uint64_t * a，size_t count）{使用queuetype = std :: vector＆lt; uint64_t＆gt; ; std ::数组＆lt;队列类型，RADIX_SIZE＆gt;队列; //我们保留了保留代码（现在不在循环中），//尽管现在不再重要了，因为调整大小通常只在（auto＆amp; queue：queues）{queue的第一次迭代中发生。保留（count / RADIX_SIZE * 1.2）; } for（size_t pass = 0; pass＆lt; RADIX_LEVELS; pass ++）{// ...和以前一样//将所有队列复制回原始数组的顶部，顺序为uint64_t * aptr = a; for（自动＆amp;队列：队列）{aptr = std ::复制（队列。begin（），队列。end（），aptr）;排队。清除（）; //＆lt; ---这是新的，请清除队列}}} 看起来好多了！这种基数排序总是比我们之前的尝试更快，并且对于10,000及以上的大小，总体上最快。它仍然落后于std ::算法，可用于1,000个元素的大小，其中O（n）与O（n * log（n））的差异所起的作用不大。尽管取得了这一小小的胜利，并且在减少系统数量的同时，我们仍将30％的时间用于内核： 排序应该是关于我的代码的，而不是内核的-因此，让我们永远摆脱内核的时间。 为此，我们将完全摆脱std :: vector，仅为所有队列分配一个大的临时区域。尽管我们知道所有队列的最终总大小（与输入数组的大小相同），但我们不知道任何特定队列的大小。这意味着我们不知道如何划分区域。解决此问题的一种众所周知的方法是首先计算将落入每个队列的值的数量，以便可以适当地调整它们的大小（也称为获取数据的直方图）。另外，我们可以计算一次数据中所有基数遍的频率，因此我们希望这部分比需要为每个“数字”分别遍历的基数排序便宜得多。 知道每个队列的大小后，我们就可以将所有值精确地打包在一个临时区域内。每个阶段末尾的副本只是一个线性副本。现在的代码更长了，因为我们需要实现频率计数，从而使我们有了radix_sort4。结果： 与Radix 3相比，它具有明显的提速，尤其是在小尺寸（提速约3倍）下，但在大尺寸（每10m元素约1.3倍）上仍然不错。较差的qsort的加速范围是3.7倍至5.45倍，在较大尺寸时会增加。即使与标准库std :: stable_sort中满足程度最高的内容相比，平均提速也约为2倍。 一个小技巧是要注意，临时“队列区域”和原始数组现在具有相同的大小和类型，因此与其总是执行从原始数组到临时区域的基数传递（这需要将副本复制回原始数组）。每次使用原始数组），我们可以在这两个区域之间来回复制，每次都交替使用“ from”和“ to”区域。每次通过都会保存一份副本。 同样有趣的是改进有多小。这种变化实际上将算法的内存带宽需求几乎切成两半：而不是在每个遍次中对每个元素读写两次（在排序期间一次，在最终副本中一次），我们只读取一次（不完全是一半）因为单次直方图传递会添加另一次读取）。然而，整体加速很小，范围在1.05倍至1.2倍之间。由此可以得出结论，我们没有达到基数遍中的内存带宽限制。 这里有一个问题：在排序的最后，如果我们完成了奇数次的传递，则最终排序的结果将在临时区域中，而不是在原始数组中，因此我们需要复制回原始数组-但是多出1份比8份好！无论如何，如果我们选择的RADIX_BITS == 8，则副本数是偶数，因此该代码永远不会在我们的基准测试中执行。 我们可以得出的另一种观察结果是，对于此输入（以及现实世界中的许多输入），许多基数传递不起作用。所有输入值均小于40,000,000,000。在看起来像0x00000009502F9000的64位十六进制中，前28位始终为零。任何使用这些全零位的基数传递都是毫无意义的：每个元素都将一个一个地复制到第一个队列条目中：本质上这是一个缓慢而复杂的记忆。 我们可以通过检查频率计数来简单地跳过这些“琐碎”的过程：如果除单个条目外所有计数均为零，则过程不执行任何操作。这使我们有了radix_sort6，最终切掉了8个基数遍中的3个，从而获得了这样的性能（我改变了比例，以强调更快的算法，因为它们被排在了最底端）： 相对而言，与radix_sort5相比，这可提供1.2倍至1.5倍的显着加速。跳过8个通行证中的3个的理论速度为1.6倍，但我们之所以无法实现，是因为核心通行证之外还有工作（例如，计算频率），并且这3个平凡的通行证实际上比非平凡的，因为更好的缓存行为。 那么，我们可以从这种性能橙中榨取多少果汁呢？这篇文章会结束吗？到目前为止，有没有人做到？ 事实证明，我们还没有完成，下一个更改也许是迄今为止最简单的更改，即一次更改。首先，让我们观察到核心基数排序循环对元素进行了线性读取（非常预取和缓存行 ......