转载

让我印象深刻并很喜欢的一个bug

【51CTO.com快译】那是在2013年11月初，我和朋友在准备参加一年一度的美国计算机协会（ACM）主办的国际大学生程序设计竞赛（ICPC）区域赛，选择的项目是各种算法和数据结构。据我了解，跳表并不经常用于编程比赛，但是它是一种用户维护有序元素的数据结构。我们认为将跳表添加到自己的库也许是个好主意。（注意：我们选择的编程语言C++已经通过其标准库，提供了平衡二进制搜索树，但是不支持扩增（augmentation），编程比赛中经常需要用到扩增。）

于是，我们晚上就开始行动，将跳表添加到自己的库。我的朋友找到了旧的实现方法，将低级C编写的程序转换成更易使用的高级C++。完成后就开始测试它，首先我们做了几个小小的手动测试，没有发现问题。然后进行更全面测试，开始生成大量的随机性测试用例（test case），将跳表的结果与C++的set进行比较。看了看一些旧的Github提交代码后，我发现这个程序看起来基本上是这样：

让我印象深刻并很喜欢的一个bug

因代码中某个地方有错误（bug），引起了这个内存损坏。我们花了好长时间分析代码，查找可能解释得通的原因，但是结果一无所获。后来想到也许是转换过程中犯了错误，我们就回过头去检查原始的实现方法，修改了测试生成器，然后使用低级接口再次运行程序。这回运行起来很顺畅，没有错误！我们更加确定是转换过程中犯了某个错误，接着我们回到转换后的代码，更细致地分析代码，但由于毫无进展。最后我们决定掏出大家伙用GDB调试器（https://en.wikipedia.org/wiki/GNU_Debugger）来运行程序。

我的朋友在GDB方面比较有经验，就让他来带路。我的记忆有点模糊，但这大约发生了什么。我们观察到的第一件事情是错误出现在一个节点的析构函数中，接着在那里释放一些内存。遗憾的是，并没有查出为何会出现这样的情况。在反复的调试器中，我们得到了一个大突破。跳表的析构函数似乎被调用了不止一次。这就可以解释我们看到节点的析构函数出现奇怪的行为以及内存错误。在修改了代码输出一些调试信息后，我们证实了情况就是这样，但是那也很奇怪。我们没有显式调用析构函数，所以它唯一被（隐式）调用的地方是在程序末尾。

于是从头查阅代码，终于明白了析构函数为什么莫名其妙地被调用了多次。我还记得，我和朋友同时发现了这点，我们互相对视一秒钟之后哈哈大笑，意识到我们有多可笑。

根源就出在size()函数上。不是跳跃表的size()函数，而是我在代码开头定义的那个size()函数，如下所示：

让我印象深刻并很喜欢的一个bug

我之前定义这个便利函数是为了消除关于带符号整数和无符号整数之间的比较的一些警示信息，在测试代码中用了它几次。比如说，确保跳跃表中的元素数量 (t1)等于set中的元素数量（t2）时，我们是这么做的：

让我印象深刻并很喜欢的一个bug

那么，这个函数到底错在哪里呢？问题在于，参数x由值传递（这是C++中的默认模式），而不是由引用传递。这意味着每当我们调用函数，给它传递某个对象（这里是跳跃表），就会发生下列情况：

1. 对象被拷贝

2. 副本被传递给函数。

3. 函数使用对象的这个副本来执行；当函数终结时，

4. 副本（通过调用析构函数）被销毁。

所以，每当测试代码调用size(t1)，它就会使用拷贝构造函数，对跳跃表作一份拷贝，然后调用副本的析构函数。

未实现拷贝构造函数或析构函数函数时，C++会提供一个健全的默认实现。实际上，如果我们刚使用了默认的实现，就不会有这个错误。然而，当对象分配内存（使用跳跃板就是这样），用户通常想自定义实现拷贝构造函数，以便拷贝已分配内存的实际值（而不是默认的实现那样仅仅拷贝指针）。但是我们刚实现了析构函数，而不是拷贝构造函数。于是当跳跃表的副本被拷贝后（为了size()函数），默认的拷贝构造函数只是将指针拷贝过去。然后，副本的析构函数被调用后，它释放指针的内存。而由于这是跳跃板的原始副本使用的内存，现在它不可以被使用。但测试代码继续下去，因而遇到许多内存错误，最终崩溃。

但是这不是size()函数引起的唯一不良反应。不妨考虑下面这段代码：

让我印象深刻并很喜欢的一个bug

它创建了100万个整数的向量，然后迭代处理这个向量，将每个值设为42。这通常会在你的普通计算机上运行几毫秒（我的计算机上实际用了4毫秒）。然而，由于ize()的参数由值传递，100万个元素的向量拷贝到循环的每次迭代。又由于有100万次迭代，这要花很长的时间。实际上，这在我的计算机上耗时13分钟38秒。

不管怎样，不妨回到我和朋友认识到什么引起内存错误的那一刻。我不仅认识到当前编写的size()函数可能有什么影响，我还明白：由于这个函数实际上来自默认C++模板（我将编辑器配置成这样每当创建一个新的C++文件，自动导入该模板），这个错误就会出现在我长期以来编写的基本上所有C++代码里面。至少几个月来是这样！

当然，这解决起来轻而易举，从提交的这段代码（https://github.com/SuprDewd/CompetitiveProgramming/commit/a72e4ec132d595beb7614c11e41bebf76e12f937）可以看出，我们的测试程序在解决了这个问题后运行起来毫无问题。

后记

很高兴发现了这个问题，这是一次很好的学习过程。自那以后，我对于如何声明函数很谨慎。但愿这是好事。

不过，我对这件事做了反思。

为何这个错误会出现？正如前所述，我开始使用这个size()函数的原因是为了消除编译器警告信息。在C++的标准库中，大多数容器的size()函数返回类型size_t的整数，这是无符号整数。所以，如果你编译下面这样的一段代码：

for (int i = 0; i < v.size(); i++) { 
 
}

编译器就会给出关于带符号整数和无符号整数之间的比较的警告信息。看到大量这样的警告信息很快会让人乏味。另一个相关问题如下。比如说你想迭代处理除容器最后一个元素之外的所有部分。你可能这样来实现这个部分：

for (int i = 0; i < v.size() - 1; i++) { 
 
}

但是容器为空时，这段代码无法正确运行。由于v.size()返回的是无符号整数（这里值为零），减1会下溢，给出size_t的最大表示值，而不是预期的-1。这反过来会导致无限循环。

要解决上述两个问题，一个明显的简单办法就是将结果转换为整数，如下所示：

for (int i = 0; i < (int)v.size() - 1; i++) { 
 
}

但是由于经常为循环编写这种代码，每次编写会很烦人。我认为在编程比赛界很常见的另一个办法是，定义诸如下列宏命令之类的命令：

#define SZ(c) (int)(c).size()

然而像下面这样使用它：

for (int i = 0; i < SZ(v) - 1; i++) { 
 
}

当我开始参加编程比赛时，可能见过这个宏命令好几次；有时我决定编写自己的版本。我觉得SZ不好看，更习惯于键入size，于是我想继续这么做。但是用名称size创建宏命令会有点危险，因为size是个常见的变量名称，这会引起麻烦。于是，我走另一条路，创建了下列函数，而不是宏命令：

template <class T> int size(T x) { return x.size(); }

我不确信为什么没有让参数由引用传递，但是确信在我开始参加编程比赛之前（因而在我编写这个函数之前）知道区别所在。但是很容易犯这个错误，哪怕是经验丰富的编程人员，要是他在实现这种看似微不足道的函数时没有高度集中注意力的话。

我还想知道为什么之前没有遇到问题。一个原因可能是，我缺乏经验，不知道这种循环会运行多快。另一个因素也是这个事实，参加编程比赛的程序员通常没必要为编写拷贝构造函数和析构函数而操心。进程终结时，通常我们就让C++运行时环境释放所有的内存。至少我确信我在发现这个错误时，我在库中的数据结构没有一个实现这些构造函数。

我试着准确查明何时开始使用这个函数。我查看了在TopCoder和Codeforces上的提交历史。在TopCoder上，我发现没有在2011年10月26日的比赛中使用这个函数（遗憾的是，你不得不登录到TopCoder才能访问链接）。然而，我在2011年11月12日的比赛中使用了那个函数。发觉这一点让我崩溃。这个错误出现在了我从2011年11月12日直到2013年11月3日的所有编程比赛解决方案当中。那可是我参加编程比赛的头两年！

举例说，我发现了提交的这个代码（http://codeforces.com/contest/134/submission/914840），当时是为了解决参与Codeforces的第二场比赛的第一个问题。我试图解决头两个问题，但结果证明我的两个解决方法都速度太慢了。然而，就我提交的解决第一个问题的方案而言，我只是增添了那个字母（&），让size()函数由引用传递，提交的内容通过了。我为自己过去的愚蠢而感到可笑。

最近我又分析了几年前解决不了的一个问题，不过试着实现一种解决办法。我仔细阅读了问题，提出了解决办法。我还记得，那是我第一次想到的同一个解决方法。由于有点懒，我找到了原来的代码，而不是从头开始实现一切。我分析了代码，似乎很正常。于是我提交了，但结果运行速度太慢了。我花了好长时间来检查代码，但是不明白为何这么慢。但突然之间，我发现了问题之所在。那个旧的、坏的size()函数，我添加了&，重新提交了，通过了！

尽管我以为自己在多年前解决了这个错误，但直到今天它仍在为我敲警钟！

原文标题：My favorite bug

作者：Bjarki Ágúst Guðmundsson

【51CTO译稿，合作站点转载请注明原文译者和出处为51CTO.com】

【责任编辑：张书情 TEL：（010）68476606】

原文 http://developer.51cto.com/art/201612/524940.htm

正文到此结束