ACM通信
实践
你做错了
资料来源:123RF Ltd.
如果我声称，一个被Knuth这样的天才以令人痛苦的细节进行分析、并在世界上所有计算机科学课程中教授的算法，可以被优化到运行速度的10倍，你会相信我吗?
几年前，我加入了一家有趣的公司，成为了一个名为Varnish的开源HTTP加速器的作者，它基本上是一个放在慢速Web服务器前面的HTTP缓存。如今，各种各样的网站都在使用Varnish，从Facebook、Wikia和Slashdot到你肯定从未听说过的鲜为人知的网站。
作为FreeBSD内核的首席开发人员，我花了15年的时间，在进入用户领域时，我对系统调用下发生的事情有详细的了解。我接受Varnish方案的一个主要原因是展示如何编写高性能服务器程序。
因为，坦率地说，你们大多数人都做错了。
错误不仅在于不完美，而且在于浪费一半甚至更多的表现。
Varnish的第一个用户，挪威大型报纸VG，用3台运行Varnish的机器替换了12台运行Squid的机器。Squid机器是100%的忙碌，而Varnish机器有90%的CPU可用来摆弄它们的数字拇指。一个
简而言之，Varnish知道它不是在裸金属上运行，而是在一个提供基于虚拟内存的抽象机器的操作系统下运行。例如，Varnish并没有忽略内存是虚拟的这一事实;它积极地利用它。300GB的后备存储(内存映射到内存不超过16GB的机器上)是相当典型的。用户购买了64位的地址空间，我并不害怕使用它。
Varnish内部的一个特殊任务是，当对象的虚拟生命计时器用完沙子时，将对象从缓存中过期。这需要一个数据结构，它可以有效地从总集合中交付最小的键控对象。
快速浏览一下心理目录，翻出了二进制堆卡片，它不仅有一个O (log2 (n))事务性能，但也有元数据开销，只有一个指针指向每个对象，这是重要的，如果你有超过1000万个对象。
仔细重读《Knuth》后，我发现这是一个明智的选择，执行起来很琐碎:“Ponto facto, Cæsar transit，”等等。
在最近一次乘坐夜间火车去阿姆斯特丹的旅行中，我的思绪走神了，我突然想到Knuth可能在二进制堆的性能上有严重的误导，甚至可能有一个数量级。在回家的路上，也是在火车上，我写了一个模拟程序来证明我的预感是正确的。
在任何原教旨主义CS理论家被咖啡呛到之前:不要惊慌!的P与NP情况没有改变，我没有在Knuth等人的推理质量中发现系统性的缺陷。正如我们所知，CS的发现仍然是正确的。它们只是没有你想象的那么相关和有用，至少在性能方面是这样。
我在计算机环境中找到的对二进制堆最古老的引用是J.W.J. Williams在1964年6月出版的ACM通信，标题为“算法编号232堆排序”。2，b问题是，威廉姆斯已经脱离了现实，他的算法分析在发表之前就已经过时了。
在1961年4月的一篇文章中通信， J. Fotheringham记录了曼彻斯特大学的Atlas计算机如何将地址的概念从内存位置中分离出来，这标志着虚拟内存(VM)的发明。1VM使用了相当长的时间，但是现在所有通用的、大多数嵌入式的和许多专业操作系统都使用VM向它们所管理的进程呈现一个标准化的虚拟机模型(如POSIX)。
当然，指责威廉姆斯没有意识到阿特拉斯已经使他的算法中的一个默认假设无效是不公平和不合理的:只有后见之明才使这种观察成为可能。然而，事实是，46年过去了，大多数接受cs教育的专业人士仍然将VM视为一种例行公事。这对计算机科学作为一门学科和专业来说是一种尴尬，更不用说浪费大量的硬件和电力了。
性能仿真
足够的讨论。让我把一些模拟的事实摆在桌面上。的情节图1显示了二进制堆和我的新b堆版本在64位机器上的100万个项目的运行时。c(我尊敬的FreeBSD同事Colin Percival很有帮助地指出，我对二叉堆所做的更改与从二叉树到b -树的更改非常相似，所以我采纳了他的建议，并将我的新变体命名为b -堆。d）
的x-axis是VM压力，用不驻留在主内存中的地址空间量来衡量，因为内核将其分页到辅助存储。左边y-axis是以秒为单位的运行时(对数刻度)，右边Y-axis显示两个运行时的比率:(二进制堆/ b堆)。
让我们先把我的“数量级”说法放一边。当我们把左边放大图2，我们看到两种算法在几乎全部VM压力下运行的时间确实有10倍的差异:分配的1954个页面中，只有8到10个页面同时在主内存中。
你刚刚判定我的数量级索赔是假的吗因为它只是基于一个极端的极端情况?如果是这样，那么您就做错了，因为这几乎是我们在现实世界中看到的行为。
在清漆中创建和过期对象是相对不常见的操作。一旦创建了对象，对象通常会被缓存几周，如果不是几个月，因此二进制堆可能甚至不会每分钟更新一次;有些网站甚至一小时一次。
同时，我们向客户机的浏览器交付了千兆字节的对象，由于所有这些对象都在主内存中争夺空间，因此包含未被访问的binheap的VM页面将被换出。在只有9个页面驻留的最坏情况下，二进制堆平均每个操作需要11.5个页面传输，而b堆只需要1.14个页面传输。如果您的服务器有固态驱动器(SSD)，则每次操作需要11毫秒或1.1毫秒。如果你仍然有旋转的盘子，这是110和11毫秒之间的差异。
在这一点上，是否有这样的想法:“如果它每分钟只运行一次，谁在乎呢，即使它需要整整一秒钟。”
我们之所以关心这个问题，是因为每分钟需要一次的10个额外的页面会在RAM中停留一段时间，什么都不做，直到内核页面再次将它们取出，这时它们会堆积在已经非常繁忙的磁盘活动之上，通常在VM压力很大的系统中会出现这种情况。e
接下来，让我们放大图的另一端(图3)．如果没有VM压力，b堆算法需要比二进制排序更多的比较，而且简单的父到子/子到父索引计算需要更多的工作量:因此，它需要5.92秒，而不是4.55秒的运行时，速度慢了30%;每次操作要慢350纳秒。
所以，是的，Knuth和其他CS的伙计们把他们的数学算对了。
然而，如果我们在曲线上向左移动，那么我们会发现，在VM缺少4个页面的压力下(= 0.2%)，b堆会赶上来，因为VM页面错误较少;它逐渐变得越来越好，直到我们之前看到的，它以10倍的速度达到峰值。
这是假设你使用的是SSD，它可以在1毫秒内完成一个页面操作，这是相当乐观的，特别是对于写操作。如果我们模拟一个机械磁盘，将I/O时间设置为仍然乐观的10毫秒(图4)，那么当内核从1954页的工作集中截取一页时，b堆的速度就会提高10%，当缺少4页时，b堆的速度就会提高37%。
那么到底什么是b堆呢?
二进制堆和b堆之间的唯一区别是从子堆中查找父堆的公式，反之亦然。
传统的N -> {2n, 2n+1}公式留给我们的是一堆虚拟页面，一个又一个地堆叠在一起，这导致(几乎)所有垂直遍历在树中的每一步向上或向下都要碰到不同的VM页面，如图所示图5，每页八项。(数字显示对象分配的顺序，而不是键值。)
b堆通过垂直填充页面来构建树，以匹配遍历堆的方向(图6)．这种重新排列增加了保持树不变为真所需的比较/交换操作的平均数量，但确保大多数操作发生在单个VM页面内，从而减少VM占用空间，从而减少VM页面错误。
有两个细节值得注意:
- 当我们从底部离开VM页面时，两个子节点位于同一个VM页面中对于性能非常重要，因为我们将把它们与它们的父节点进行比较。
- 因此，为了有效地使用页面中的前两个元素，每次进入一个新的VM页面时，树都不能扩展一代。
在我们的模拟示例中，如果不这样做，将需要5页以上的页面。
如果这对您来说不重要，那么您的操作是错误的:尝试将b堆行向内右移20KB图2而且3.，并思考其中的含义。
我所选择的模拟参数代表在Varnish中实际发生的情况，我没有尝试全面地描述或分析b堆的所有可能参数的性能。同样，我不排除有更聪明的方法将VM-clue添加到二进制堆中，但我不倾向于为了找时间解决它而买一张西伯利亚大铁路的车票。
差异的数量级显然源于每个VM页面内堆的级别数，因此最终的加速将在指针大小较小而页面大小较大的机器上实现。这是一个相关的观察，因为操作系统内核开始使用超页来跟上不断增加的I/O吞吐量。
那么为什么你和我还在做错呢?
一场著名的辩论，“快速排序与堆排序”，集中在一个事实上，即前者的最坏情况行为是可怕的，而后者的平均性能更差，但没有这样的“坏点”。根据您的应用程序，这可能是一个非常重要的区别。
面对由虚拟内存、CPU缓存、写缓冲区和现代硬件的其他事实造成的各向异性内存访问延迟，我们缺乏对算法选择的类似研究。
无论你从哪本书中学习编程，它可能在前五页就有一个图，图中的计算机与书中所示的很像图7．这就是它变成梨形的原因:这种模式在今天完全是虚假的。
令人惊讶的是，它是计算机教育中使用的唯一概念模型，尽管它与现代计算机上的执行环境几乎没有任何关系。郑重声明:这里的现代指的是VAX 11/780或更晚的版本。
在过去的三四十年间，硬件和操作系统的发展似乎只对计算机科学学院的算法分析部分的议程产生了微小的影响，而且就我的传闻来看，它完全没有在计算机科学学院提供的教育中得到体现。
阿特拉斯计算机主存储器和次存储器之间的速度差距约为1:1 000。Atlas鼓发送一个扇区需要两毫秒;执行指令大约需要两微秒。对于每个VM页面错误，您将丢失大约1000条指令。
在一个现代的多问题CPU上，运行在一些千兆赫时钟频率上，最坏情况下的损失是每个VM页面错误将近1000万条指令。如果使用旋转磁盘运行，则这个数字更接近1亿个指令。f
大多数接受过cs教育的专业人士仍然将VM视为一种例行公事。这对计算机科学作为一门学科和专业来说是一种尴尬，更不用说浪费大量的硬件和电力了。
有什么用呢?O (log2 (n))如果这些操作导致页面错误和磁盘操作变慢，该如何处理?对于大多数相关的数据集O (n)甚至是O (n2）避免页面错误的算法会绕着它转一圈。
算法的性能分析将永远是计算机科学的基石成就，像你们所有人一样，我真的很珍惜的折叠图表与磁带分类在第3卷计算机编程的艺术。但是CS部门的研究结果如果能应用到真正的计算机上，而不仅仅是像ZX81、C64和TRS-80这样的玩具上，将会更加有趣和有用。
相关文章
在queue.acm.org
FreeBSD 5.2中的线程调度
马歇尔·柯克·麦库西克和乔治五世·内维尔-尼尔
http://queue.acm.org/detail.cfm?id=1035622
今天的Flash存储
亚当·利文斯
http://queue.acm.org/detail.cfm?id=1413262
高性能网站
Steve Souders
http://queue.acm.org/detail.cfm?id=1466450f
参考文献
1.阿特拉斯计算机中的动态存储分配，包括自动使用后备存储。Commun。ACM 4， 19(1961年4月)，435436。
2.Williams, j.w. J.算法232堆排序。Commun。ACM 7， 6(1964年6月)，347348。
脚注
a.这个双关语是专门用来启发Stan Kelly-Bootle的。
b.当世界上所有的算法都可以用一个8位字节来列举的时候，生活和编程该是多么美妙啊。
c.页面大小为4KB，每个页面包含512个64位指针。仿真了虚拟机系统的脏跟踪和完善的LRU页面替换。分页操作设置为1毫秒。对象键值是随机产生的(3)。测试插入一百万个对象，然后交替删除和插入对象一百万次，最后从堆中删除剩下的一百万个对象。源代码载于http://phk.freebsd.dk/B-Heap．
e.请不要相信我的话:把排队理论应用到这种情况是一个非常有教育意义的经验。
f.在吃水线以下是管道的刷新，现在已经没用了，而且是缓存内容、页表更新、备用缓冲区失效、页表加载等等。在CPU数据手册的“针对操作系统程序员”部分中找到指示并不少见，这些指示需要数百甚至数千个时钟周期，才能完成所有操作。
DOI: http://doi.acm.org/10.1145/1785414.1785434
©2010 acm 0001-0782/10/0700 $10.00
允许为个人或课堂使用本作品的全部或部分制作数字或硬拷贝，但不得为盈利或商业利益而复制或分发，且副本在首页上附有本通知和完整的引用。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定的许可和/或付费。
数字图书馆是由计算机协会出版的。版权所有©2010 ACM, Inc。
评论
CACM管理员
以下这封信发表在2010年9月出版的《致编辑的信》(//www.eqigeno.com/magazines/2010/9/98018)上。
——CACM管理员
波尔-亨宁·坎普(poull - henning Kamp)的文章《你做错了》(2010年7月)如果写得更专业，更重要的是，避免粗枝大雅的夸张，可能会更有价值、更有效。例如，Kamp说他在图7中描述的计算机架构“在今天是完全伪造的”。错了。虽然简单，但它完全适合作为初学的学生的初级体系结构，因为大多数学生甚至无法提供像“输入”和“输出”这样的词的精确定义。同样，Kamp所说的“这是计算机教育中使用的唯一概念模型”也不可能是正确的。
亚历克斯Simonelis
Montral
------------------------------------------
作者的回应
针对这篇文章，CS学者们表示了不满，抗议所谓的教育缺陷，而实践者也证实了这些缺陷。我只看到两种反应说:“我们已经知道了。”学生们显然没有学到计算机学界认为他们教的东西。但检验在布丁里;如果毕业生在阅读这篇文章时说“这对我来说是新闻”，那么计算机科学的学者就做错了。
Poul-Henning坎普
Slagelse、丹麦
显示1评论