洛穆托的复出

“谢谢您的盛情邀请，洛穆托先生。我很快就会回到英国，所以这是非常及时的。“。

“谢谢你同意见我，…先生。…爵士。查尔斯·…。A.R.…。霍尔。这是我莫大的荣幸。我甚至不知道该怎么称呼你。你被封为爵士了吗？“。

“叫我托尼吧，如果不太麻烦的话，请允许我叫你尼科。”

从表面上看，这是一个平淡无奇的场景--两个男人在享受威士忌。然而，仔细观察就会发现一些耐人寻味的细节。对于初学者来说，这是一种你可以用刀割断的张力。

托尼·霍尔(Tony Hoare)穿着一套剪裁精美的四件套西装，神情淡然，只有英国人才能做到这一点，他就像一杯茶一样英国化。当他从杯子里啜饮时，他无可奈何的鬼脸充分说明了他对波旁威士忌与苏格兰威士忌的看法。在小桌子的另一边，尼科·洛穆托(Nico Lomuto)与众不同：他是一个穿着休闲的程序员，正享受着他的威士忌和可口可乐(这件事如此令人震惊，以至于托尼很早就决定刻意假装没有注意到，就像面对成熟的体味或攻击性纹身时一样)，看到他刚刚遇到的计算机科学巨头，他有一种放松的敬畏之情。

“听着，托尼，”尼科在闲聊结束时说，“关于那个分区算法。我从来没有想过要发表或--“。

“哦？是的，是的，分区算法。“。托尼假装惊讶地扬起眉毛，仿佛他没有想到过去五年里关于快速排序的每一篇论文和每一本书都同时提到了它们的名字。这显然是连接两个人和会面动机的唯一因素，但是托尼这个完美的绅士，如果他的谈话伙伴不提起天气，他可以在房间里用粉色的大象谈论几个小时的天气。

“是的，那个不断被提及的分区算法和你的一样，”尼科继续说。“我不是一个很好的算法理论家。我正在开发Ada，关于我的分区方案的整个事情让我分心。令人烦恼的是，“尼科用一种毫无掩饰的人的语气说，”它甚至不是一个更好的算法。我的分区方案将始终执行与您的相同数量的比较和至少相同数量的交换。在最坏的情况下，我的是n个额外的掉期-n！我不明白他们为什么一直提到这件受祝福的事。现在已经不是我能控制的了。我不能告诉他们应该教授和出版什么算法。就像泡泡酱一样。每当有人提到快速排序时，观众中就会有一些笨蛋--或者我应该说是泡泡脑袋--是的，我也听说过泡泡排序算法。让我毛骨悚然。“

尼科叹了口气。托尼点点头。共同的价值观。融洽的空气中弥漫着突如其来的、安静的、愉悦的气息，就像烤箱里传出的饼干的味道一样。几秒钟过去了。杰克和可乐喝了一口。桌子的另一边，波旁小口喝了一口，做了个无可奈何的鬼脸。

托尼讲话时用的是一位科学家精心挑选的措辞，他不想让任何假说都没有被探究过。“我明白，尼科。不过，请考虑以下几点。您的算法简单而规则，只向一个方向移动，并且每步最多进行一次交换。这可能适用于一些未来的…计算机。“。

“无论机器如何，掉期越多不可能比掉期越少。这是常识，“尼科专横地说。

“我不会那么肯定。计算机没有常识。计算机令人惊讶。理所当然，他们将继续这样做。嗯，不如我们好好享受今晚吧。没有什么比在安静的俱乐部里进行一次愉快的谈话更好的了。“。

“是的。干杯。这是个有趣的地方。我听说他们很快就会有现场的乡村音乐。“。

多年来，我一直对分类问题有一种未表白的上瘾。这并不难隐藏-在很大程度上，痴迷于研究排序是一种社会上可以容忍的混乱职业；毫无疑问，许多程序员花了几个深夜尝试另一种排序方法，它将比其他方法好得多。所以，当我在2002年写关于排序的文章时，没有人对此感到惊讶(听说过“Fit Pivot”吗？)。你当然没有)。当我编写D的std.ort时，没有组织任何干预，结果证明它有时是二次的(谢天谢地，后来得到了修复)。即使当我作为一个独立的局外人写了一篇关于选择问题的学术论文(索特的表亲)时，也没有人嘲笑我，就连会议组织者都说这是一个相当不错的把戏。当我在CppCon 2019年谈到分类时，没有引起公众的愤怒。程序员明白这一点。

所以，我设法做到了。你知道他们怎么说的-一天一次。然而，当我看到最近一篇论文的标题：“分支预测失误不会影响Mergesort时，我确实感到了一丝兴奋。”如此耐人寻味的标题。首先，分支机构的错误预测预计会影响合并排序吗？我没有太多的想法，主要是因为每个人和他们的猫都在使用快速排序，而不是Mergesort，所以后者并不是我关注的焦点。但是哎，我根本不需要担心，因为标题坚决断言，我不知道我应该担心的那个问题，我终究不需要担心。因此，在某种程度上，标题会自动抵消。然而，我确实读了这篇论文(并建议您也这样做)，在许多有趣的见解中，有一个引起了我的注意：从效率的角度讨论了Lomuto的分区方案，认为它是一个重要的竞争者(与普遍使用的Hoare分区相比)。效率！

让我们首先回顾一下这两个分区方案。在给定数组和枢轴元素的情况下，划分数组意味着排列数组的元素，使得小于或等于枢轴的所有元素都在左侧，而大于或等于枢轴的元素在右侧。轴心的最终位置将位于边界。(如果有多个等效的轴值，则最终轴位可能会有所不同，这会带来重要的实际后果；但是，对于本文的讨论，我们可以假设所有数组值都是不同的。)

Lomuto的分区方案从左到右遍历数组，保持一个“读”位置和一个“写”位置，这两个位置最初都是0。对于每个读取的元素，如果“读磁头”看到的值大于枢轴，则跳过它(读磁头移动到下一个位置)。否则，读磁头的值与写磁头的值互换，并且两个磁头都前进一个位置。当读磁头完成时，写磁头的位置定义分区。请参考下面的动画(来自维基百科用户Mastremo，在CC-by-SA3.0许可下未经修改使用)。

Lomuto分区的问题在于它可能会进行不必要的交换。考虑只有最左边的元素大于轴心的数组的极端情况。该元素将在每个迭代步骤中笨拙地向右移动一个位置，其方式与，嗯，气泡排序没有什么不同。

Hoare的分区方案巧妙地解决了这个问题，它使用两个“读/写头”从阵列的两端同时迭代。它们跳过已经适当放置的元素(小于左侧的轴心，大于右侧的轴心)，并且仅将左侧的一个较小的元素替换为右侧的一个较大的元素。当两个磁头相遇时，阵列围绕会合点进行分区。上面描述的极端情况是通过单个交换来处理的。大多数当前的快速排序实现都使用Hoare分区，原因很明显：它进行的比较次数与Lomuto分区一样多，交换更少。

考虑到Hoare分区显然比Lomuto分区做的工作少，问题是为什么要教授或使用后者。STL的创建者Alexander Stepanov写了一篇关于划分的很好的讨论，并提出了一个一般性的论点：Lomuto分区只需要前向迭代器，而Hoare分区需要双向迭代器。这是一个有价值的见解，尽管实用价值有限：是的，您可以在单链表上使用Lomuto的分区，但大多数情况下，您是为了快速排序而分区，并且您不想对单链表进行快速排序；Mergesort将是选择的算法。

然而，确实存在一个非常实用(也非常令人惊讶)的论点，这也是本文的笑点：以无分支的方式实现的Lomuto分区在随机数据上比Hoare分区快得多。考虑到快速排序将其大部分时间花在分区上，因此我们将看到快速排序的巨大改进(是的，我说的是C++和D的工业强度实现)，将其分区算法替换为真正做更多工作的算法。

要了解cookie是如何崩溃的，让我们仔细看看Hoare分区的实现。为了消除所有无关紧要的细节，本文中的代码作为元素类型编写，并使用原始指针。它的编译和运行方式与C++或D编译器相同。本文将用两种语言进行所有例程的实现，因为很多研究文献都使用C++的std：：Sort作为重要的基线来衡量算法性能。

/**以第一个和最后一个元素中的最小值作为透视的分区。返回：指向轴心最终位置的指针。*/long*HOARE_PARTITION(long*first，long*last){assert(first<；=last)；if(last-first<；2)先返回；//没有什么有趣的事情要做--last；if(*first>；*last)交换(*first，*last)；AUTO PIVOT_POS=FIRST；AUTO PIVOT=*PIVOT_POS；FOR(；){++FIRST；AUTO f=*FIRST；WHILE(f<；PIVOT)f=*++FIRST；AUTO l=*LAST；WHILE(PIVOT<；l)l=*--LAST；IF(FIRST&>；=LAST)Break；*First=l；*Last=f；--LAST；}--First；SWAP(*First，*Pivot_pos)；Return First；}。

(您可能会发现选择枢轴有点奇怪，但不用担心：通常它是一个更复杂的方案-比如3的中值-但对核心循环来说重要的是，枢轴不是数组中最大的元素。这允许核心循环省略许多限制条件，而不会超出数组界限。)

关于此实现的效率有很多好的方面(您可能会在C++或D标准库的实现中发现这一点，但细节稍有更改)。您可以看出上面的代码是由过着简朴生活的人编写的。那些保持指甲清洁的人，当他们说他们会出现的时候就会出现，并定期给妈妈打电话。他们每天早上都要练武术，不让电脑周期浪费掉。该代码毫无松懈之处。生成的英特尔程序集非常紧凑，对于C++和D几乎完全相同，它只在后端之间有所不同，与GCC(参见g++和gdc)相比，llvm的代码大小略有优势(参见clang和ldc)。

下面所示的Lomuto分区的初始实现对于展示来说工作得很好，但是从效率的角度看是草率的：

/**选择透视表作为第一个元素，然后分区。返回：指向轴心最终位置的指针。*/long*lomuto_PARTITION_NAIVE(long*first，long*last){assert(first<；=last)；if(last-first<；2)先返回；//没有任何有趣的事情要做，auto Pivot_pos=first；auto Pivot=*first；++first；for(auto read=first；read<；last；++read){if(*read<；vot){exchange(*read，*first)；++first；for(auto read=first；read<；last；++read){if(*read<；Pivot){exchange(*read，*first)；++first；交换(*First，*Pivot_pos)；返回第一个；}。

对于初学者来说，如果数组左侧的一串元素大于轴心，上面的代码将执行大量愚蠢的无操作交换(数组元素本身)。所有时间FIRST==WRITE，所以将*FIRST与*WRITE互换是不必要的，也是浪费的。让我们用一个预处理循环来解决这个问题，该循环跳过不感兴趣的初始部分：

/**以第一个和最后一个元素中的最小值作为透视的分区。返回：指向轴心最终位置的指针。*/long*lomuto_PARTITION(long*first，long*last){assert(first<；=last)；if(last-first<；2)先返回；//没有什么有趣的事情要做--last；if(*first&>；*last)exchange(*first，*last)；AUTO PIVOT_POS=FIRST；AUTO PIVOT=*FIRST；//Prelude：第一个元素上的第一个位置(写头)比枢轴大//执行{++First；}While(*First<；Pivot)；Assert(First<；=Last)；//主菜。FOR(AUTO READ=FIRST+1；READ<；LAST；++READ){AUTO x=*READ；IF(x<；PIVOT){*READ=*FIRST；*FIRST=x；++FIRST；}//将枢轴放在它所属的位置。ASSERT(*FIRST&>；=PIVOT)；--FIRST；*PIVOT_POS=*FIRST；*FIRST=PIVOT；RETURN FIRST；}。

该函数现在选择轴心作为第一个和最后一个元素中最小的元素，就像HOARE_PARTITION一样。我还做了另一个小更改-不使用交换例程，而是使用显式赋值。优化器会自动处理这个问题(注册加上WIN的寄存器分配)，但是用源代码表示它可以帮助我们看到相对昂贵的数组读取和数组写入。现在是有趣的部分。让我们将重点放在核心循环上：

FOR(AUTO READ=FIRST+1；READ<；LAST；++READ){AUTO x=*READ；IF(x<；PIVOT){*READ=*FIRST；*FIRST=x；++FIRST；}}。

让我们来考虑一下统计数据。此循环中有两个条件：read<；last和x<；vot。它们的可预测性如何？第一个是非常可预测的--你可以可靠地预测它永远是真的，而且不管数组有多大，你只会错一次。编译器编写人员和硬件设计人员都知道这一点，并在假设循环将继续的情况下设计最快路径。(送给你的英特尔工程师朋友的礼物点子：一张写着“向后的分支总是被拿走”的受气垫。)。甚至在决定循环是否应该继续之前，CPU就会推测性地开始执行循环的下一次迭代。该工作只会在循环结束时被丢弃一次。这就是投机性行刑的魔力。

第二个测试x<；Pivot的情况就不那么令人愉快了。如果你假设随机数据和随机选择的轴心，它可能以相等的概率走向任何一个方向。这意味着投机性执行根本没有效果，这对效率非常不利。有多糟？在深度管道架构中(就像今天一样)，失败的投机意味着需要丢弃几个管道阶段所做的工作，这反过来会在管道中传播一个无用的泡沫(比如花园软管中的气泡)。如果这些气泡出现得太频繁，循环只会以可获得带宽的一小部分产生结果。正如测量部分将显示的那样，一次浪费的投机会降低大约30%的潜在速度。

如何改进这个问题？这里有一个想法：我们不是做出控制执行流的决策，而是以直线方式编写代码，并将决策合并为整数，通过精心选择的数组索引来指导数据流。做好准备--这会迫使我们做傻事。例如，我们不会在每个迭代中执行两次条件写入，而是无论发生什么情况，我们都会在每个迭代中执行两次写入。如果不需要写入，我们将用它们自己的值覆盖内存中的单词。(我提到“傻事”了吗？)。要为所有这些做好代码准备，让我们按如下方式重写它：

FOR(AUTO READ=First+1；Read<；Last；++Read){auto x=*Read；If(x<；Pivot){*Read=*First；*First=x；First+=1；}Else{*Read=x；*First=*First；First+=0；}}。

现在，除了数据之外，循环的两个分支几乎完全相同。代码仍然是正确的(尽管很奇怪)，因为在Else分支上，它不必要地写*、读自己和*首先写自己。我们现在怎么把这两个分支统一起来呢？要以有效的方式做到这一点，需要进行一些思考和试验。有条件地递增First很容易，因为我们总是可以先写+=x<；Pivot。小菜一碟。这两个内存写入比较困难，但基本思想是取指针之间的差异并使用索引。这是密码。花点时间想一想：

for(；read<；last；++read){auto x=*read；auto size=-int(x<；Pivot)；auto Delta=Small&；(先读)；First[Delta]=*First；Read[-Delta]=x；First-=Smaller；}。

套用一句著名的拉丁语格言，“CODEX BREVIS EST”，“CODEX BREVIS EST”。短是暗号，长是“平地”。带有-int(x<；Pivot)的较小掩码的初始化看起来很奇怪，但却有很好的理由：较小既可以用作通常算术中使用的整数(0或-1)，也可以用作位运算中使用的掩码0或0xFFFFFFFFF(即，将所有位设置为0或全部设置为1)。我们将使用该掩码来允许或清除计算Δ的下一行中的另一个积分。如果x<；Pivot，则较小的为全一，并且增量被初始化为读取优先。随后，在First[Delta]和Read[-Delta]中使用Delta，它们实际上分别是*(First+Delta)和*(Read-Delta)的语法糖。如果我们在这些表达式中替换Delta，我们将分别获得*(first+(read-first))和*(read-(read-first))。

最后一行first-=size很普通：如果x<；轴心，则从first中减去-1，这等同于先递增。否则，从第一个减去0，实际上只留下第一个。干得漂亮。

将x<；Pivot替换为1后，在循环体中完成的计算将变为：

AUTO x=*READ；INT SIMLEER=-1；AUTO DELTA=-1&A；(先读)；*(FIRST+(先读))=*FIRST；*(READ-(READ-FIRST))=x；FIRST-=-1；

两个指针表达式魔术般地简化为*read和*first，因此两个赋值实现了交换(回想一下，x刚刚用*read初始化)。我们在最初版本的测试的True分支中所做的完全一样！

如果x<；Pivot为FALSE，则增量初始化为零，循环体的工作方式如下：

AUTO x=*READ；INT SIMLEER=0；AUTO DELTA=0&；(FIRST-FIRST)；*(FIRST+0)=*FIRST；*(READ-0)=x；FIRST-=0；

这一次事情更简单了：*先改写*Read本身，*Read也改写自己，而先不去管第一个。代码没有任何效果，这正是我们想要的。

long*lomuto_分区_分支自由(long*first，long*last){assert(first<；=last)；if(last-first<；2)先返回；//没有什么有趣的事情要做--last；if(*first&>；*last)exchange(*first，*last)；auto vot_pos=first；auto vot=*first；do{+first；assert(first<；=last)；}while(*first<；=lastFOR(AUTO READ=FIRST+1；读取最后一个；++读取){AUTO x=*READ；AUTO SIZER=-INT(x<；PIVOT)；AUTO增量=SIMPLE&A；(先读)；First[增量]=*First；Read[-Delta]=x；First-=Smaller；}Assert(*First>；=Pivot)；--First；*Pivot_pos=*First；*First=Pivot；Return First；}。

她很漂亮，不是吗？更漂亮的是生成的代码-看看clang/ldc和g++/gdc。同样，后端之间也有一些差异。

为了比较这两种分区方案，我组合了一个快速排序实现。这是因为大多数情况下，在快速排序过程中会使用分区。为简化起见，测试实现省略了工业快速排序实现中存在的一些细节，它们需要担心各种数据形状(部分预先排序的升序或降序、带有本地模式、具有许多重复项等)。库实现从通常由3-9个元素组成的样本中谨慎地选择枢轴，可能是随机化的，并且具有检测和避免病理性输入的方法，最常见的是使用Introsorte。

在我们的基准测试中，为了简单起见，我们只针对随机数据进行测试，并且选择的轴心很简单。

..