编程与软件工程queue.acm.org
你做错了：现实世界中的计算机科学
You're Doing It Wrong: CS in the real world
2010 — 2018，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这是 Poul-Henning Kamp（Varnish 作者）发表在 ACM Queue 上的文章，讲述他在 Varnish 缓存过期任务中发现教科书上的二叉堆在真实硬件上性能不佳，于是把数据结构改造成对磁盘页/缓存友好的 B-heap，获得数量级的性能提升。文章批评计算机系教育只讲抽象的 O() 复杂度，忽视了虚拟内存、多级缓存等真实硬件特性。
为什么经久不衰：它揭示了大 O 分析与真实硬件（缓存层次、虚拟内存）之间的鸿沟，这一教训跨越硬件变迁依然适用，因此多年反复登上 HN。
HN 评论精选
树结构在现代缓存层次下天然吃亏，哈希表更符合硬件现实；作者的思路有价值但并非首创。
Knuth 写作时面向的 MIX 机器和所有同时代机器一样，只有平坦的内存层次。如果你疑惑为什么文献里满是树、而实践中集合和关联存储常用哈希实现，想想现代硬件一次缓存未命中要 300 个周期。在树中查找需要 log N 次缓存未命中（指针指向随机位置，几乎必然 miss），远比哈希合理长度的键、在哈希表里只付出一次缓存未命中更昂贵。作者的贡献不错，把链接式数据结构改造成块友好形式有很长的历史，但他大肆宣扬自己重新发现了块设备按块操作这一事实，令人遗憾。
kmavm查看英文原文
Knuth was writing for MIX. This machine, like all its contemporaries, had a flat memory hierarchy. If you've ever wondered why the CS literature seems full of trees, but in 2010 practice, sets, associative memories, etc., are often implemented with hashing, consider that a cache miss on much modern hardware is 300 cycles. The equivalent of for (register int i = 0; i < 299; i++) ; can pay for itself by saving a cache miss. The log N cache misses to find something in a tree (the pointers all point somewhere random, and you should expect them to miss) is much more expensive than hashing reasonable-length keys and taking a single cache miss in a hash table, for almost any value of N > 1. The author has made a nice contribution; as Colivas probably was trying to hint to him, there is a long history of converting linked data structures to block-friendly form by an analogous transformation. A straight write-up of his work, without all the chest-pounding over his rediscovery of the fact that block devices operate on blocks, would have been a pleasure to read. Pity.
内存感知算法早有学术研究，但文章很好地说明了性能必须实测而非推测。
这是篇好文章，尽管对学术界来说并不新鲜。计算机科学中有一整个分支专门研究内存层次下的复杂度，还有 Architecture Cognizant 和 Cache Oblivious 等不同框架。不过这确实是个好例子，说明真实机器上的性能往往需要实测而非纸上推演，因为架构复杂性会带来有趣的性能特征。
kenjackson查看英文原文
It's a good article, although certainly not new, even to academics. There is a whole branch of CS that is dedicated to understanding complexity with respect to the memory hierarchy. For example, see: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.587 And there are different frameworks for building algorithms that perform well in the memory hierarchy, such as Architecture Cognizant and Cache Oblivious algorithms (although, as you can tell by the name, they have somewhat opposing ideological beliefs). Nevertheless, this is a good example as to why performance on real machines often needs to be implemented, rather than speculated, as the the architectural complexity can lead to some interesting peformance characteristics (of course, some good ground in complexity and experience will help prioritize which algorithms are even in the ballpark).
作者澄清：文章的核心论点是 CS 教育割裂了算法理论与真实硬件，而非 B-heap 本身。
（作者本人回复）第二，我感到不少自尊心受了伤。很好，这通常说明成功戳到了痛处。第三，用户 gaius 说到了点子上：算法课和硬件课完全分开教，两位教授从没想过交叉融合。如果我能让这两位教授对话，这篇文章就值了。重点不是 B-heap 本身——那我只花了一小时就想出来——而是大多数 CS 教育根本不提真实计算机有虚拟内存、写缓冲、多级缓存，更不提 O() 依赖其中 13 个以上的随机变量。
phkamp查看英文原文
Ohh, dear, another forum to keep an eye on :-) First: congratulations, the level of discussion here is a fair bit above what I have seen so far on reddit and slashdot. Second: A sense a number of bruised egos. Good. That is often a sound indication that a sore point successfully poked. Third: user "gaius" hits the problem spot on: "In mine, we learnt about the hardware, the cache hierarchy and so on, completely separately from the algorithms and complexity theory. Two different classes, two professors. Probably they both knew it themselves, but it never occurred to them to cross-pollinate their course materials." If I can get those two professors to talk to each other, my article will have been worth the effort. Hopefully the HW-prof will tease the algorithm-prof with my article and some fruitfull cooperation ensue. The important point in my article is not the B-heap, that took me all of an hour to figure out and I'm sure most of you could have done the same thing, had your thoughts been wandering in that direction. No, the important point is that most CS educations don't even mention that actual computers have Virtual Memory, Write buffers, multilevel caches and so on, and if they do, the certainly don't mention that the O() function depends on 13+ more or less stochastic variables extracted therefrom. Several people here, and elsewhere, seem to make the sign of the cross at there mere mention of virtual memory and RAM overcommit. That is understandable, in particular if nobody ever taught them how to properly use those facilities. Getting into a fight with the kernels VM bits is a sure-fire recipe for lousy performance, and after one or two such experiences, becoming a bit sceptical is fair. But the facts are, that by intelligently using the those VM bits you save a lot of complex code, and get as good performance as you can hope for. But you have to know what you are doing, and for most of us, that means that the professor should have told us. Poul-Henning
B 树的流行正是同一原理：统一访存假设在真实硬件上不成立。
这和数据库用 B 树而不是二叉树是同一个道理——当你必须考虑存储访问的非均匀延迟时，假设任意内存地址访问时间相同的传统算法分析就变得极具误导性。
userbinator查看英文原文
It's pretty much the same reason why databases use B-trees and not binary trees --- when you have to consider the nonuniform latency of storage access, traditional algorithmic analysis that assumes every memory address is accessible in the same time as any other becomes extremely misleading.
质疑其方案未必最优，且新硬件可能让传统分析重新成立。
我同意他对 CS 系算法分析不覆盖真实硬件问题的抱怨，我 1997 年在圣安德鲁斯大学的本科课程也是如此。但我不明白他找最近使用项为什么不用链表——每次访问把对象移到一端，淘汰时从另一端删除，O(1) 且几乎不产生缺页。另外 NVMe 或大页、NUMA 绑定也能解决他的问题，或许 CS 系教的东西又变对了。
abainbridge查看英文原文
I agree with his rant about "CS departments' algorithmic analysis" failing to cover these real-world hardware issue. That was certainly true of my ~1997 undergrad CS course at the University of St Andrews, that was otherwise exemplary. The only thing I don't understand is why his data structure for finding the least-recently-used item wasn't just a linked list - where each time you touch an object you move it to one end of the list, and when you want to discard an object you remove from the other end. That'd be o(1) and would cause, at most, one page fault per update and none for the add and remove cases (since the two ends would surely be paged "in"). And it'd be a lot easier than his fancy thing. I guess I missed something. It might be worth pointing out that NVMe or Intel Optane would solve his problem (1) without his fancy data structure too. Some might go as far as to say that while his fancy data structure is out dated now, the stuff that the CS departments teach became correct again. Maybe St Andrews had the right idea all along. 1) Or huge-pages or NUMA node pinning, to some extent.
核心教训是性能不能想当然，但文章的傲慢语气与其贡献不匹配。
很好地提醒了空间局部性对性能至关重要。但这其实广为人知，更重要的教训或许是：不要把性能视为理所当然，即使是成熟语言的标准库或经典算法，针对你的使用场景也可能有很大改进空间。不过文章显得相当傲慢，这个优化的思想并不新鲜，只是把基本概念应用得好，做得不错但不足以支撑那种语气。
slx26查看英文原文
A great reminder that spatial locality can be critical to performance. But that's actually quite well-known, and maybe a more important lesson would be: don't take performance for granted, even in standard libraries of well stablished languages or algorithms, there might be much room for improvement for your use case (if you need it). This said, the article feels quite arrogant. As other commenters say, the idea behind the optimization is nothing new, just some basic concepts well applied. Which is a job well done, but probably doesn't justify the tone (that at least I perceive) from the article.
历次讨论
同类还值得读
开源应用架构
The Architecture of Open Source Applications
《开源软件架构》（AOSA）是一本在线免费书，邀请知名开源项目的作者亲自剖析其内部设计，涵盖 SQLAlchemy、LLVM、Audacity、Apache、Bash 等系统。
编程与软件工程上首页 9 次 · 2011–2024aosabook.org编辑精选编程语言简史：简短、不完整且多半错误
A Brief, Incomplete, and Mostly Wrong History of Programming Languages
一篇以戏谑、故意不准确的方式回顾编程语言史的博客文章，用夸张轶事和讽刺定义串起 Lisp、C、C++、Java、JavaScript、PHP 等语言。
编程与软件工程上首页 8 次 · 2009–2021james-iry.blogspot.comSQLite 是如何测试的
How SQLite is tested
SQLite 官方文档页，系统介绍 SQLite 的测试体系：多种测试方法（TCL 测试、模糊测试、回归测试、静态分析等）和海量测试用例，展示了这个小型开源项目如何靠极致测试获得…
编程与软件工程上首页 8 次 · 2009–2025sqlite.org编辑精选高级编程语言（2009）
Advanced programming languages (2009)
Matt Might 的经典文章，按用途推荐“高级编程语言”：如果追求就业就选主流语言，如果追求表达力、学术研究或创业，则推荐 Haskell、OCaml、Scala 等函数式语…
编程与软件工程上首页 8 次 · 2009–2022matt.might.net我的 Forth 与栈机器经历
Yosefk - My history with Forth & stack machines
作者以亲身经历回顾了使用 Forth 语言和栈式机器的历程：既赞叹其简洁优雅、代码量小、可自举的优点，也坦率指出栈操作在实际编程中的痛苦，以及 Forth 社区文化中的问题。
编程与软件工程上首页 8 次 · 2010–2024yosefk.com编辑精选