12月 | 2009 | 技术奇异点

Archive for 2009年12月

Snow Leopard 的修正准则

2009/12/22

只要应用程序够复杂，每次操作系统升级都会弄坏几个本来工作得好好的功能，有些是应用程序本身代码的问题，只是在系统升级时才突然现身。这些 bug 在旧的操作系统上深藏不露，系统一升级才兴风作浪，大多因为操作系统的 API 行为变得更『正确』了。

升级到 Mac OS X Snow Leopard 之后我们的应用程序就出现了两个这样的 bug。第一个是应用程序 fork 之后立刻在子进程里调用 File Manager 的函数。跑了几年都没问题的代码，一到 Snow Leopard 上就僵死。第二个是 MPEG 的播放代码，同样是用户使用了很多年都没有问题，一到 Snow Leopard 上播放的视频就不停的闪烁。原因都是应用程序调用 API 的时机不对：File Manager 必须在 exec*() 函数调用之后才能使用；用 Core Video 配合 Quick Time 播放视频，必须在取出后一帧之后才能销毁前一帧。这些限制在 Leopard 版的文档上就有说明，幸运的不幸的是，系统『恰好』缓存了某些数据让不恰当的 API 调用『碰巧』能工作，掩饰了旧代码中的错误。显然，我们可以猜到，程序在 Snow Leopard 上才初次显露问题是因为新的操作系统去掉了那些缓存。

这样看来，OS X 岂不是自寻烦恼？旧的 API 行为在原来的应用程序里工作得好好的，何苦修改呢？大致猜想有这些原因：一是缓存让 API 的实现复杂化了。加上一个缓存，就得再加上一套代码保证缓存和真实数据的同步（或者在无法同步时清空缓存）。二来，因为缓存不能完全替代获取或者计算真实数据的代码，所以缓存、维护缓存同步的代码、计算真实数据的代码要同时占用内存。应用程序的活跃部分的体积会增大，原来能适合 CPU cache 的部分可能必须在主存和 cache 之间换进换出，本来为了提高效率的缓存却适得其反。最后一点，缓存让 API 行为变得不可预测。一段『碰巧』能工作的代码意味着当它碰巧不工作的时候更难被监测到和修正。

这些 bug，或者更广泛的说，所有系统升级中暴露的遗留代码的问题都说明了软件（特别是 API ）设计的一个陷阱 —— 性能和 API 的确定性行为哪个更重要。结论是，确定性行为不仅更重要，而且往往带来更简洁的设计和更好的性能。

这是『修正准则』（Rule of Repair）的变形实例。Leopard 里的 API 不完美的修正了应用程序的错误输入（这里的输入是调用时机），引入了更复杂的实现和不确定的行为。Snow Leopard 去掉了缓存，消除了 silent success，但是 failure 不够 noisy。结果是功能被搞坏，新出现的 bug 诊断起来也很困难。所以，不要只在文档里说明你的 API 需要什么样的 precondition。如果在你的 API 文档里出现这样的文字 —— 在某某条件不满足的情况下调用某个 API 的行为是不确定的，那你就得三思。应用程序的作者不可能有时间细细品味文档，他们只会在出问题的时候（或者更窄的范围，程序崩溃或者挂起的时候；甚至没有人会注意你的 API 会有内存泄露，即使瞥一眼 Activity Monitor 就能看到疯狂的增长）才匆匆翻阅一下。所以，你的那些告诫会被人忽视数年。直到有一天你决定清理一下你的 API 实现，让它变得更简洁。这个时候那些告诫才会出来咬人。那么，亡羊补牢的方法是用一个 crash 来表达你的告诫（那样会在 debugger 里清晰的显露出出错点），而不是听任程序出现任何可能的行为（比如僵死和闪烁）。

不论如何，Snow Leopard 毕竟简化了实现，尽管做得不完美，起码比打着向后兼容的口号，为了让几个 killer-app 的 buggy code 正常工作而保留丑陋的实现然后把文档变成让人无法理解的技术诉讼书（或者辩护书）更好。

发表在软件开发, Mac OS X | 2 Comments »

链表迷魂阵

2009/12/15

只要粗粗看过数据结构，对链表的印象一定是插入、删除操作都很快。不过对 C++ 标准库里的 list（也就是 std::list ）就得多加小心。比如下面的代码：

std::list node_list; ... NodeData a = node_list.front(); ... node_list.remove(a);

熟悉 STL 的人可能一眼发现其中的陷阱：node_list.remove(a) 可不是一个 O(1) 的操作（虽然经典链表的删除操作是）。这是因为 std::list<T>::remove(const T&) 实际是一个经典链表的查找操作加上一个经典删除操作。虽然能看出这个问题的人也许不在少数，但是犯下这个错误的人也不在少数。而且，当前者遇到后者编写的代码时，修改起来往往很头疼。因为虽然 NodeData 是从链表中取出的，但是它并没有存储前后节点的信息。所以要想把上面的有缺陷的代码改正，必须把所有涉及到 NodeData 参数传递和临时存储的地方都加以修改。所以说，使用 std::list::front() 这样的拷贝语义函数的行为本身看起来就是个错误。

这里先插上两句说说所谓『经典』链表（因为后文会拿来比较）。很多数据结构的书里的链表就是把 NodeData 这个对象本身加上一个 prev 指针和一个 next 指针，用来分别指向前一个和后一个节点。所以『经典』链表的数据结构和节点数据本身由一个对象表示。经典链表对 NodeData 的定义是侵入式的 —— 如果你希望把一个原来和链表操作完全没有联系的对象或者 struct 加入链表，就必须修改它本身的结构。相对的，std::list 的方式是把链表看成一种『容器』，包容原有的对象而无需修改其结构。

所以你的第一反应也许是应该永远用 std::list::begin() 或者 --std::list::end() 之类的操作返回 iterator，相比 NodeData，iterator 更像经典链表的节点，带有前后节点的联系。但是 C++ 永远不会给你简单的方案。这个方案的问题在当在代码的多处拥有指向同一个 NodeData 的 iterator 时，调用任何一个 iterator 或者 list 本身的 erase() 方法都会导致其它 iterator 失效。而且，C++ 标准库仅仅告诉你唯一的以定义行为是其它 iterator 会『失效』。你甚至没有一个 valid() 方法来检验一个 iterator 是否失效。C++ 标准期待的是你无论如何知道这一状态并且决不能再对那些 iterator 做任何操作。

所以 std::list 相比『经典』链表有两个致命问题。第一是直接取出 NodeData 的操作丢失了和 list 本身的联系，让后续操作承受性能损失。第二，『经典』链表可以通过设置 prev/next 让任何拥有 NodeData 指针的代码轻易的判断一个节点数据是否还在链表中，而 std::list 对 iterator 行为的粗略定义让这一点变得不可行。

接下来我们把问题搞得更全面（也更复杂）一些，考虑 NodeData 的生命周期。C++ 标准库一贯的拷贝语义让这个问题得到了（幼稚地）解决。但是对于 std::list 来说，我们已经看到拷贝语义的操作会让取出的节点丢失和 list 的联系，而总是取出 iterator 又会带来失效的问题。

当然，经典链表虽然没有 iterator 失效问题，但是仍然要面对何时销毁节点数据本身的问题。不过，讽刺的是并非所有的数据都是可复制（copiable）的，所以 std::list 里面存储的也经常并非数据本身，而是数据的指针。因此，在同样面对 std::list<NodeData> 的『联系切断』和『iterator 失效』两难之际，std::list<NodeData*> 还必须面对经典链表的销毁节点数据的时机问题。更遗憾的是，C++ 的内存管理法宝 shared_ptr 在这个问题上完全无能为力。一个 std::list< shared_ptr<NodeData> > 同样拥有『联系切断』和『iterator 失效』的矛盾。这时只有经典链表，加上在 NodeData 中实现手工引用计数才算一个比较完美的方案。

链表是 C++ 的好几个设计理念走麦城的地方。链表重在『链』，它的灵活性就在于『链』。把链表作为『容器』，特别是和 STL 其它容器一样保持拷贝语义操作就毁了链表。而且基于拷贝构造和自动析构的共享指针和手工的引用计数相比也并非处处领先。

如果一开始能抛开 STL 那种容器的概念和对数据节点不侵入的要求，C++ 的链表设计不会这么差。比如 Linux 内核的链表设计，把链表节点作为链表数据的一部分，让链表数据包含节点，而不是反之。这样的设计用 C++ 模版也完全可以作到。（当然我更喜欢 Linux 内核的基于宏的设计，而且 Linux 的设计通过一个可被优化的 forced cast 同样保证了类型安全。）

后记：

写这篇 blog 的时候又重温了一下 Java 的 LinkedList 文档，发现 C++ 还不是最差的。LinkedList 的文档是，至少 6.0 还如此 —— 对 LinkedList 做的任何结构更改（什么意思？删除节点算吗？）都会导致所有已经获取的 iterator 失效。什么玩艺，这样的话我还用链表干什么？