【IT168 技术】

　　注：本文为IT168&NVIDIA联合举办的“如何并行化我的应用”方案征集活动参赛作品。本次方案征集活动详情见：http://cuda.itpub.net/thread-1299715-1-1.html。近期活动的大部分方案，将会逐步与大家分享，不可错过哦!

　　CUDA ZONE专区：http://cuda.it168.com

　　CUDA技术论坛：http://cuda.itpub.net

　　比赛是公司搞的，要求在20天时间内完成一程序，求三维空间内所有射线同所有三角平面的交点。射线和三角平面都通过文件方式输入，结果以文件输出，程序最后测试的平台有8核，8G的内存。算法，语言，线程库都不做限制，任意发挥，最后以结果正确，速度最快者获胜。我大概搞了七八天(由于放了长假还要上班，实际没有20天，不过这个大家都一样，公平)，从对图形学零知识，学习向量、点乘、叉乘等等这些基础知识开始，到运用空间划分、光线行进算法，加上多线程，最后也能跑出相对满意的结果，虽然最后由于程序局部设计上的一点缺陷，导致公测的时候未跑出正确结果，但依然感触良多，故在博客中开个处女贴，一是作为纪念，二是希望能跟更多的技术爱好者共同交流，共同进步。

　　一：先说一下自己的整个比赛过程：

　　当刚拿到题目的时候，除了需要先学习基本点图形学基础外，还在网上找了射线跟三角面求交的算法(也就几十行代码)，然后很简单的认为只要每条射线跟每个三角面求一下交，所有的交点就能获得了，在算法上还能做啥优化不成?这种想当然使我很快实现了整个程序，包括读文件，写文件以及求交。拿比赛委员会给的最大的测试数据一测，跑了十几秒(由于本机是双核，于是用了两个线程来求交)，然后想再做些优化，发现小小的程序已无太多优化的余地，遂心中起疑虑，这种算法是个选手都能想到，线程的效用也都能发挥到最大，那最后比成绩岂不是在拼运气，于是觉得应该没那么简单，但对于此前从未涉足过图形学的我来说，也实在不知该从何处下手优化。此状态持续了有三天左右，一直在一些小地方做优化，提高成绩也很有限。

　　之后跟一个同事聊起此比赛，由于他研究生读的就是图形学，大概跟我提了一下空间划分、八叉数这些概念，突然感觉这里面有戏，于是开始在网上搜索这些概念，找相关的资料、论文，果然，发现了一片大天地，于是花了一两天时间好好研究了一把这些知识，并结合自身的需求，设计了出了一套算法。再马不停蹄的用代码实现，经过漫长的调试后一跑，时间降到了两三秒，我的天呀，这种成就感太让人兴奋了，不过兴奋之后并没有忘乎所以，开始分功能模块单独测试运行时间，哪一块所占时间大就先优化哪一块，时间在一点点缩短，令人感叹的地方也越来越多，最后优化到600多毫秒的时候，离最后提交时间就差一小时了，于是匆忙提交。哎，说到这里，有个教训需要提一下，那就是疏忽了测试数据，误以为最后公测的数据也应该跟委员会提供的最大数据量差不多，可实际根本就不是一个数量级的，导致了程序在初始化的时候发生错误，从而前功尽弃。虽然说比赛以参与为主，但既然参加了比赛，自然就希望能打败对手，所以最后失败也略感不爽。当然，这也算是个不大不小的经验教训，对自己今后还是会有帮助的。

　　二：下面主要从算法，数据结构，语言，多线程三个方面来总结优化的过程：

　　(1) 算法、数据结构永远是计算机的核心，语言只是表达它们的一种工具，而多线程多核只能算是一道诱人的小菜。

　　从我参与的整个过程看，算法在这里起到了决定性的作用，提高的性能绝不是多几个核能解决的，而数据结构设计的好坏，不仅对算法的性能提高有很大帮助，而且对多线程发挥效用也起到了决定性作用，因为好的数据结构能减少线程访问公共数据的冲突，从而让线程跑的更加畅通无阻。至于语言，我用的是C++，当然，是面向对象还是面向过程对这个比赛影响不大，主要是在使用C++库上面需要好好考察一番，尤其是STL，当整个运行时间降到1s以下时，你会发现无论它的map类还是hash类都是那么的慢，能占个几百毫秒，这时如果你消耗点内存，开个全散列的读写缓存，几百毫秒一下就没了，当然，这里是以空间换时间。还有碰到的一个情况是，如果你要初始化几百万个对象，而这个对象里包含了一个vector，此vector的功能仅仅是插入一些数据，那你还是老老实实自己写个列表吧，因为它的初始化也是几百毫秒，当然，这里的情况比较特殊，一是有几百万个对象，二是程序性能优化是在毫秒级别的。你要是碰不到这种情况，用了也无所谓。这里就引出第二个结论。

　　(2) 不要轻易对性能瓶颈做出结论，一切都要在精确测量之后再确定。

　　直观判断的结论往往是不准确的，很多时候也很难做直观的判断，所以尽可能的插入一些统计数据，包括时间，循环执行次数等等有利于你做判断的数据。

　　(3) 性能瓶颈是在不断转化的，当不起眼的部分在你优化了其它部分后，它就是你下一步要攻克的对象了。

　　当我把求交的模块优化好之后，发现从得到交点到写出文件耗费了很长时间，一开始以为是从缓存把数据写到文件时慢了，但一测其实速度是很快的，于是就往上找，最后定位在sprintf_s这个函数上面(需要把double转换成char)，一统计时间，乖乖，又是个几百毫秒的家伙，于是考虑自己写double转换成char的函数，哈，很多人可能会直观觉得这会比较复杂，自己写出错风险较大，我一开始也这么觉得，可没办法，此处不优化，我夜不能寐啊，于是开始分析所有double可能的值，如何设计特殊情况，大概60行左右代码就完成功能，而sprintf_s据说有一千多行代码，故性能提升也很明显。

　　(4) 扩展你的知识面，最好对它们都有一定的了解，这能让你在最短时间内做出最合适的选择。

　　由于我对图形学知识的匮乏，使得在前面浪费了很多宝贵时间;另外不了解OpenMP, TBB等这些线程库，不仅缩小了我的选择范围，也增加了自己学习的时间。在这样的比赛中，谁能更好的利用时间，谁就赢得了一半比赛。

　　(5) 先从大处着手优化，然后再优化小处，否则顺序颠倒，就算你在小处优化的再好，也只能是个甜头。所谓大处小处，请通过第2条来确定。

　　在时间有限的前提下，用最宝贵的时间来做最有利的事，往往这件事难度也会比较大，但不要任性去做自己喜欢或觉得简单的事，否则只能是在浪费时间，对结果却帮助不大。

　　(6) 模块化设计程序，让你有更方便的优化空间。

　　这点跟平时的编码功底很有关系，混乱的设计虽然最后功能也实现了，但会让你在优化的时候痛苦不堪，令结果也错误百出，最后不得不为了保证正确性而不做优化。而清晰的程序设计，尤其是数据和执行逻辑的耦合性低，会让你优化起来事半功倍。

　　(7) 记住，你程序的瓶颈也会因输入数据的差异而转变，所以不要忽略测试，并自己准备好最合理的测试数据。

　　关于这一点，也有不少感触，用一开始提供的样本数据，同最后公测的数据测试一比，发现瓶颈完全转变了，所以记得多用不同的数据测测，并按重要程度做优化。

　　(8) 当你需要频繁申请、释放内存的时候，可以考虑开辟一个内存池统一申请和释放内存，因为频繁的new,delete也会花你很多时间，当然，前提还是你的程序是在ms级别上的优化。

　　三：其它感悟

　　(1) 公司能多举办这类比赛，确实能激发员工的活力，像我以前对图形学，空间划分，OpenMP这些知识一无所知，在短短数十天时间就接触了大量相关知识并做优化，可以说能很大激发一个人的潜力，这让我感觉特别刺激：)。

　　(2) 从应用OpenMP这个线程库来看，其优点很明显，结构化特性很强，但缺点也明显，不适合开发大型程序，只能做局部优化，后面我会再去研究一下TBB怎么用，待研究过几套已有的线程库之后，我想用ACE和Loki两个C++库来实现一个类似于OpenMP功能的线程库，需要让它能适应大规模程序开发。