云风的 BLOG: 安全的迭代一个集合

把同质的东西放入一个容器，然后用迭代器迭代这个容器，把里面的内容逐个取出来处理。这是一个非常常见的需求。但是，这个过程往往也会滋生 bug 。因为，若将容器看成一个对象，那么对其迭代的这个操作很难实现原子性。

非原子性导致了，在迭代过程中，十分有可能对容器本身进行修改。或增加若干元素，或删除若干元素。这些都容易造成迭代过程不正常。

所以，最终我们需要根据需求设计以及实现合理的容器。比如管理消息的消息队列，严格的满足尾进头出，没有删除中间数据的需求，就不会导致 bug 。

那么，如果容器是一个集合怎么办？即，允许向其中增加新的元素，也可以移除某些元素。这种数据结构非常有用。比如向某对象注册若干回调函数，一旦满足条件则依次调用。即设计模式中的 Observer 观察者模式。回调函数就极有可能增加新的观察者或某些老的观察者退出。

简洁的解决方案是，使用一个可变长数组维持这个集合，把数组看成一个队列，永远在一端添加。而删除中间节点，仅仅只是做一个记号（标记成不必再处理的观察者）。

在集合中额外保存一个迭代状态堆栈。每次需要迭代时，从堆栈顶分配一个状态容器出来，负责迭代（里面保存迭代到的位置）。

当迭代尚未完成前，一旦回调函数触发对同一集合的新的迭代请求，状态堆栈会返回一个新的状态容器，保证和前次迭代互不干扰。

迭代完成后，如果当前状态堆栈为空，表示外层再无迭代事务。这个时候，可以一次扫描整个集合，把做过删除标记的节点删除，并压缩整个集合（去掉空巢）。

用 lua 实现以后功能非常简单：代码大约是这样的。

这段代码实现了一个集合，提供了一个安全的迭代器迭代它。使用 enter 把对象置入集合。enter 会返回一个 closure 用于把对象从集合中移除。

当然，用 C 或 C++ 实现一个也不复杂，就不列代码了。

Comments

可以使用intel的TBB库，里面提供了并行容器，对容器的各种操作都是线程安全的。不过内存耗得比较厉害就是了，而且还必须考虑维护并行操作的成本

Posted by: 阿福 | (17) April 29, 2009 10:49 AM

感觉下边讨论的有点儿超出帖子中的内容了. 我也说两句,我做游戏优化的经验: 1.消灭对象的副本.(减少内存消耗、内存中数据搬运) 2.充分运用缓存的思想。（效果不是一般的好） 3.项目的优化不是一个人的事儿.(让所有人都来做优化.)

Posted by: wg | (16) April 20, 2009 04:25 PM

你的博客真不错。值得大家学习！辛苦了

Posted by: 双色球 | (15) April 12, 2009 11:53 AM

那么跨机器的IPC呢？这总得涉及socket了吧，我感兴趣的是这些相关的事情有没有封装以及封装成什么形式。

Posted by: sjinny | (14) March 30, 2009 01:37 AM

IPC 在 Unix 下是多么容易的事情啊，不过是 fork 一下，share 个 fd 用管道通讯而已。read/write 足以。用文件也不坏，比如使用 stdin/stdout ，那就是管道了。至于在 Windows 下，多进程方案用的少一些。偶尔也用用管道，和封装好的简单的 lua 库。如果是 python 就更有现成的了。

Posted by: Cloud | (13) March 30, 2009 12:51 AM

说道以进程为模块的问题，想问一下云风，你们是各个进程自己实现网络通信，还是在各个进程内应用同一个网络库，或者把网络通信本身也作为一个进程？

Posted by: sjinny | (12) March 29, 2009 09:36 PM

gc 可以把内存资源管理和事物逻辑正交分离，是它的根本优势所在。在大多数情况下，让程序员更轻松只是从这点引出的结果之一而已。但同时，一些程序员逃脱不了的问题的解决同样存在，表面看起来是被掩盖的更深，实则不然。只不过大多数情况下，大家不以为然而已，而且的确也不是问题。以那个 timer 为例，并不说是漏写了 "delete" ，因为到了时间，该回收的还是会回收。这跟内存泄露是两回事。（带 gc 的语言中，内存泄露的 bug 一样存在，但这里不是）只是回收的晚了一点而已，只有当垃圾存留时间过长，导致峰值内存占用过大，变成性能问题后，它才是一个问题。 gc 避免了 C/C++ 的内存管理模式中悬空指针的问题。但世界上没有免费的午餐，由之不甚引起的性能问题将更隐蔽（而悬空指针会立刻导致程序崩溃，更容易排查。找到问题之所在，甚至只是确定有问题，需要程序员更高的素养。因为，性能问题往往不是传统意义上的 bug 造成的。比如你应该准确估算出的你程序应该使用的内存量，和实际情况加以核对。基于此，我主张更简洁的设计，每个模块更为专注做很少的事情。使用最合适的（而不是单一的）工具/模式。这样最容易理解系统，发现并解决问题。这里指的模块，不仅仅是软件里一个以 api 形式提供的模块，也可以是一个进程、一个服务……

Posted by: Cloud | (11) March 29, 2009 06:47 PM

同意楼下这样看来，gc的使用不当和忘记delete或不正确使用new如出一辙这是不是说明，在这个项目里，gc也好lua也好，都不是灵丹妙药。只有在对本质有了正确了解才能设计出正确的代码

Posted by: black | (10) March 29, 2009 06:08 PM

你说的那个timer的例子，是不是可以理解为gc如果使用不当，可能会使gc的代价峰值非常高？其实对于你所说的第二个问题，它只是涉及了gc本身，但是就第一个问题来说，gc在解决了一些问题的同时又引入了新的问题。其实那个timer里没有及时把引用置空的情况，也算是一种广义的泄漏——本来应该这时就释放的，偏偏还不必要地继续持有引用导致gc无法释放相关资源，这种没有置空和没有delete的性质相差不大，毕竟忘了及时置空引用也意味着可能会一直都没有置空引用。总感觉gc并没有很好地解决内存泄漏的问题，可能充其量只是解决了试图释放和实际释放的时间的分离问题。

Posted by: sjinny | (9) March 29, 2009 09:06 AM

在需要效率的前提下，内存管理总是重中之重。gc 只是一种内存管理方式而已。正如在其它内存管理方式下，我们一样需要考虑怎样使用内存，比如是在堆上分配还是在栈上分配；是预分配好，还是使用时再分配；是立刻回收还是延迟回收…… 使用 gc 去管理内存，不过是换了个角度看这些问题罢了。 gc 不是用牺牲性能的代价去换取编程的便捷，它只是以另一种方式去建立内存资源的管理模式。的确，这些问题往往是优化相关的问题，过早优化绝对是需要回避的，但前提是如何定义这个“早”。避免“过早优化”不等于不做“优化”。当一个模块是高内聚的，接口定义是完备的。优化的策略和使用的上下文不相关，即，增加优化不会改变接口复杂度，不会要求使用者具备更多的知识。那么在功能实现完毕后，做优化之考虑就不为“早”。 ps. 我这几年在公司里见了太多的工程，无论是用 lua 还是 python ，都遇到了大量的性能问题。程序员们急于找到“性能更好的语言”，但最终发现，不存在免费的午餐。不是说看到一些评测，说 lua 比 python 快换成 lua 做项目就好；或是有什么灵丹妙药，把一些所谓不正确的写法简单机械的修正过来，或是换上 jit ，整体性能就能成倍提高的。但不可否认的是，完成同样功能的 lua 代码，性能质量（空间/时间）上就可以差上数倍。而这些性能差异不是跑上几小段测试代码就可以比较出来，而是放在实际环境中体现出来的。这里面跟内存管理部分就极有关系。因为 gc 模块可以看成是跟业务模块功能正交的，在性能上产生影响，是个间接而漫长的过程。举个真实的例子：在目前我们运营的一款游戏中，服务器里使用的 timer 模块是这样注销一些不用的回调函数的：把回调函数以及相关数据绑定成一个 closure 挂在 timer 内部的一张表上。注销只是在其之上设置一个标记。等待下次触发时真正删除。但是这个方法导致了大量本可以在某个 gc 清理环节清理的数据，延迟了很久才被清除。原因是 closure 间接绑定了大量数据。解决方法也很简单，在主动注销时，不仅把 closure 的删除标记设置上，并主动将 closure 的 upvalue 设置为 nil 。再一例：我们在 C 中使用 gc ，一开始的机制是，内存使用量达到一定阀值就自动触发清理。在实际使用中，发现系统占用的内存总是估算值的两倍。这让人很不解，总以为是某处有内存泄露的 bug 。仔细排查后发现，原来是因为内存阀值得到的时刻，总是在函数调用栈的较深层次。堆栈上存在大量临时引用的对象总是清理不干净。后来将立刻清理改为设置一 gc 信号，在函数调用栈退到最外层（一般是程序主循环的出口处）根据信号做一次扫描清理，就能把垃圾回收的很干净了。

Posted by: Cloud | (8) March 29, 2009 12:02 AM

如果gc的负担需要如此顾忌，那么这里gc不仅没有简化编程，反而还增加了不必要的复杂度……而这种顾忌是不是也有过早优化之嫌……

Posted by: sjinny | (7) March 28, 2009 10:15 PM

@sjinny, 这个是因为我是在 lua 中做的特定实现，不想每次迭代都生成一个临时 table 加大 gc 的负担。如果像 C 或 C++ 这样，可以直接利用系统堆栈分配临时空间的语言，的缺没有必要。

Posted by: Cloud | (6) March 28, 2009 07:14 PM

为什么要用个额外的栈来保存迭代状态呢？迭代的当前位置一般是在数据结构的外面的吧，这样只要在数据结构里用一个变量来识别当前调用是否是最外层调用，然后迭代函数能够自动跳过无效元素就行了。

Posted by: sjinny | (5) March 28, 2009 07:10 PM

copy 数组的方法要看环境。因为迭代是时间复杂度 O(N) 的算法，而采用复制就有两倍开销，且迭代的空间复杂度从 O(1) 变成了 O(N) 。用的时候需要评估 N 的大小。所以不够通用。比如把实现做成黑盒子，就需要告诫用户，请警惕 N 的大小，不要随便用。或者用户拿不准是否真有需求时，需要考虑在原有数组上迭代还是 copy 一份出来。如果考虑这个限制，就不够 simple 了。KISS 的解决方案应该是：无论用户是否一定有需求，有何种需求，都可以简单用之。这就好比排序，冒泡比快排更 stupid ，但大多数（但不是全部）情况下，我们会直接调用 qsort ；遍历一个数组查找特定元素，比保持元素有序然后二分查找，或使用 hash map 组织数据更 stupid ，却在大部分情况下（即使 N 不是特别巨大）时，后者更有市场。

Posted by: Cloud | (4) March 28, 2009 06:10 PM

同 analyst 的做法。

Posted by: lyman | (3) March 28, 2009 09:57 AM

这个问题我的解法是迭代之前把容器的元素指针copy到一个临时数组里，然后对数组进行迭代，呵呵，这才叫KISS的解法。

Posted by: analyst | (2) March 28, 2009 09:10 AM

抢个先.. 学习咯~

Posted by: 文 | (1) March 28, 2009 03:15 AM

云风的 BLOG

思绪来得快去得也快，偶尔会在这里停留

安全的迭代一个集合

Comments

Post a comment