« Clash of Clans | 返回首页 | Objective-C 的对象模型 »

最近一些心得

最近特别忙, 每天写程序的时间都不够。有些东西在做完之前不想公开谈，所以只把一些笔记发在公司内部的周报里了。等这段时间过去，再贴到这里来。

不过还是有一些泛泛的心得可以写写的。

前几天遇到一个优化的问题。我想采用定期计算路图的方式优化寻路的算法。而不用每次每个单位在想查找目标的时候都去做一次运算并记录下路径结果。一切都看起来很顺利，算法的正确性很快就被验证了。可是最后实际跑的时候，发现在生成路图的地方会稍微卡一下影响流畅性。

遇到这类问题，第一反应通常是考虑如何优化。比如是不是应该换用多线程，是不是要分摊每次的计算量，是否可以简化问题减少运算的次数等等。

我在这些方面都尝试做了几个小时的努力。结果发现，如果我简单的把 O3 优化加上的话，可以直接加速 2 倍，相当于我其它方面做的努力的提升（当然其它方面的努力也是有效的）。

这不太符合我的平常遇到的情况。大部分情况下，C 语言编写的程序，编译器优化能做到 25% 的性能提升已经足够好了（通常 C++ 风格的代码可以提升更多）。或许是因为纯算法代码的因素导致这次的结果吧。

但是，采用多线程这样的方式来改进程序，不符合我的直觉。我不认为把程序结构改的复杂来获得需要的性能并不是第一选择。而且，在设计算法之初，我已经做过估算，认为在当前的硬件环境下，并太可能造成容忍不了的延迟的。

最后自己检查了自己的代码实现。发现我不小心把一个 O(n) 复杂度的算法实现成 O(n2) 了。修改正确后，速度一下就提高了 100 倍。

这次是个不多见的教训。程序结果的正确性被验证，但是依然存在 bug 。只是 bug 仅仅导致了代码运行缓慢，把一段需要 1/1000 秒应该完成的任务，减慢到了 1/10 秒的数量级。

另一点心得：

在外部条件不多变的问题上，适当的采用一些常量是很有效的。比如断定某个字符串长度不超过 64 ，数组的元素不超过 16 个等等。

对于 C 风格的代码，我们总能看到一些 MAXxxx 的宏来直接定义数组的大小。在 C++ 教科书上总是把他们当成反面教材，要求换用 std::vector 。

但实际上，如果能对目标问题做精确的评估，并在代码中做出合理的断言。固定长度的数组的好处也很明显。数据结构比较简单，程序会更加健壮。尤其是在多线程环境中更能体现出来。

即使是一些动态分配的部分，如果能估算出大致的总量，那么把内存池定义在结构中也更简洁一些。即，不额外用 malloc 分配一块新内存，再用指针去引用它。而是直接在结构中声明出内存块，让结构内的动态指针引用自身内存池中的内存。

这样，复杂的对象在内存中的数据布局依然是连续的。管理它们(生命期)的代码成本也比较低。对并发支持也更简单。不过，这同时也要求对需求的估算更明确，适合于用在严格定义好的内聚性很高的模块内部。

前段时间读过一本 Objective-C 的书。影响比较深刻的是 cocoa 框架对内存的管理方案。

虽然 cocoa 也使用引用计数。但是却不是在对象引用计数到 0 时就立刻释放内存。而是结合了 autorelease pool 。

这可以减少在当前栈帧访问无效对象的 bug ，而不需要引入 C++ 中的 RAII ，以比较清晰可显的法则定义出内存管理的方案。

云风 提交于 March 11, 2013 11:14 AM |

Comments

个人觉得直接在格子上做优化会比在其它地方事倍功半，比如用3d的导航网格代替原来2d的格子，格子的倍数可以明显的减少。3d网格获取边相邻也容易。另外还可以吧多个三角形合并成一个节点进一步减少网格寻路的格子数。

Posted by: whisper | (22) November 18, 2014 09:40 AM

除了时间和空间可能是无限的以外，还有什么具体事物是无限的呢？ 科学家做理想实验，工程师做带限制规格的可用产品。

Posted by: 赵中 | (21) May 17, 2013 04:38 PM

云风你真的会用C++吗？别一天到晚喷C++了，该学习学习C++了。 vector照样可以当作固定长度的数组使用。vector其中一个构造函数就可以指定其长度，比如： vector v（10， 0）构造一个长度为10的vector，并且将其初始化为0。 再者boost库中有固定长度boost::array,比C数组不知强多少了。 在这说vector要重新扩容影响效率这更搞笑了，我把vector当作固定长度的数组用不行吗？难道数组容量不够就不需要扩容了吗？数组扩容就不需要把原来的copy到新数组吗？

Posted by: Anonymous | (20) April 1, 2013 08:23 PM

优化多了，有时候也会少功能……

Posted by: icicle | (19) March 28, 2013 07:20 AM

1/1000秒的执行，也是巨大的性能瓶颈啊

Posted by: rex | (18) March 23, 2013 08:19 PM

博主辛苦了。

Posted by: 金山毒霸 | (17) March 23, 2013 02:55 PM

@zzl 果然现在用C++的使用者世风日下呀(沦落成Java那种级别了),首先栈上空间有一定限制的准确的来说一次性最好都不要分配4k,早年大家还在使用enter指令来分配,后来微软自己都直接sub了,至于栈有神马用自己去看看Intel汇编语言程序设计,一般来说默认也就是几十k,linux下是1M.vector说到底就是个动态数组,本身stl就很重量级,不如c写的轻量级,而且许多跨平台编译器下调试stl本身就很麻烦,最关键的一条stl没有边界性,这也就是工业界和追求稳定基本上不用C++的原因.c++程序员感觉现在就和学了几天MFC就说sdk不好的人一样让人无语

Posted by: swz | (16) March 19, 2013 07:39 AM

std::vector = std::vector allocator可以给stack allocator，这样就不存在动态分配内存问题，对象全在栈上创建。 当然不同大小的stack allocator对应的vector类型会不同，写法上会麻烦点。

Posted by: zzl | (15) March 15, 2013 03:15 PM

什么浏览器最好用 能做个友链吗

Posted by: 什么浏览器最好用 | (14) March 14, 2013 07:53 PM

在语言设计得很良好的情况下，比如说有很强的类型系统，会在编译器层面作更多的优化，同时保证安全性(越界错误等)，不能假设优化的典型就是c/c++, 难以判断可能发生的错误，难以判断运行时内存和算法开销等，这些工作就交给程序员的经验和不断的调试了

Posted by: lichking | (13) March 13, 2013 10:16 PM

其实vector在某些情况下得效率问题也是值得考虑的 当vector的size超过容量上限时为了保证内存连续性需要重新开辟新的内存，把原来数据Copy到新的内存块中，当Size比较大得时候需要考虑的

Posted by: dew | (12) March 13, 2013 01:46 PM

用C时候没有顺手拈来的vector，的确很多地方会做假设，简化很多。C++站在它的角度推荐用vector也是对的。Cloud毕竟还是有些放不下C++，剑招华丽，让人欣赏让人诟病。

Posted by: zack | (11) March 12, 2013 09:38 PM

@haohaolee std::array 和限定最大长度的 C 数组是不同的. 虽然实现本质一样,但是从语言的惯用法上讲是两个东西. 限定最大长度, 但实际长度还是可变的. 语义上最接近的是 std::vector .

Posted by: Cloud | (10) March 12, 2013 03:41 PM

这可以减少在当前栈帧访问无效对象的 bug:隐藏越久的bug越难查。最简单的还是立即crash掉，然后gdb一记。

Posted by: 3w哥 | (9) March 12, 2013 12:41 PM

现在的object-c, 在原来引用计数+autorelease pool的基础上引入了arc, 不用手动调用对象的release, retain, autorelease函数。 比如 void fun() { NSString* str = [[NSString alloc] init]; .... use str } 在出作用域的时候，编译器插入语句，[str release]; 写起来更方便了。

Posted by: HJC | (8) March 11, 2013 03:36 PM

泛泛而谈，实干兴邦，改天我试试，╮(╯▽╰)╭

Posted by: dew | (7) March 11, 2013 02:43 PM

甚至甚至： 每个路径记录可以记录一个被执行次数。然后以不同次数段（如100000至120000，1000至2000...）存放到不同的hash中 查找记录时优先从执行次数高的记录集里找。。。

Posted by: dew | (6) March 11, 2013 02:39 PM

看到寻路，突然有个小想法： 是不是可以把玩家每次寻路计算的路径以hash方式存到服务器某个寻路模块中，例如可以把起点和终点组成一个Key值（为了减少路径记录数量，可以做一个模糊Key值，具体怎么实现模糊，需要仔细商榷） 这样每次玩家请求寻路先在该模块中查找是否有类似的可用路径记录，如果没有就计算，冰将该路径数据由起始点和终点生成Key存到Hash中， 如果有就直接使用 这样做有个问题就是如果地图阻挡点发生变化可能会导致一部分路径失效，就可能产生一部分失效记录，可以记录一个上次执行该路径的时间，定时检查当前时间与上次执行时间时间长，超过一定时间(如30天)就剔除 为了减少查找基数，甚至可以按寻路方式进行分类： 1.同地图的按地图ID放到不同hash中 2.跨地图的按起始地图和到达地图ID 总之，要考虑全各种寻路方式，然后将将各种方式放到不同Hash中 是不是能减少寻路的开销？

Posted by: dew | (5) March 11, 2013 02:33 PM

看到寻路，突然有个小想法： 是不是可以把玩家每次寻路计算的路径以hash方式存到服务器某个寻路模块中，例如可以把起点和终点组成一个Key值（为了减少路径记录数量，可以做一个模糊Key值，具体怎么实现模糊，需要仔细商榷） 这样每次玩家请求寻路先在该模块中查找是否有类似的可用路径记录，如果没有就计算，冰将该路径数据由起始点和终点生成Key存到Hash中， 如果有就直接使用 这样做有个问题就是如果地图阻挡点发生变化可能会导致一部分路径失效，就可能产生一部分失效记录，可以记录一个上次执行该路径的时间，定时检查当前时间与上次执行时间时间长，超过一定时间(如30天)就剔除 为了减少查找基数，甚至可以按寻路方式进行分类： 1.同地图的按地图ID放到不同hash中 2.跨地图的按起始地图和到达地图ID 总之，要考虑全各种寻路方式，然后将将各种方式放到不同Hash中 是不是能减少寻路的开销？

Posted by: dew | (4) March 11, 2013 02:33 PM

忍不住吐槽，现代的C++可没有一味的建议用 std::vector，特别是在有 std::array 的情况

Posted by: haohaolee | (3) March 11, 2013 01:56 PM

难怪挺长一段时间没有更新BLOG...

Posted by: CoolDesert | (2) March 11, 2013 01:11 PM

赞同！读quake3的源代码也能感觉到类似思想。

Posted by: 游客2 | (1) March 11, 2013 12:39 PM

Post a comment

非这个主题相关的留言请到：留言本