由于这个学期没有返校，我变懒了不少。明明有不少可以写的东西，却没有去写。等学期结束了有时间了我会好好补写一些博客。
这几天，我在赶一个高性能计算的大作业。题目要求优化一段代码，使程序的运行时间尽可能短。大作业本来是一个令人烦躁忧虑，头皮发麻的事物，但在deadline的紧逼之下，我仿佛按下了大脑的启动按钮，火力全开地应对起这个大作业来。于是，我的漫长的编程时间就开始了。——看到这里，如何你对编程不是非常了解，可能完全没有读下去的兴致。但我保证我会用外行人也能看懂的方式，来描述我这次有趣的写大作业经历。
再具体地讲一下我的大作业要求。我的大作业题目是代码优化，跑代码花费的时间是评价成绩的唯一指标。当然，代码的正确性不能受到影响，你不能让程序刚进去就关掉。代码跑得越快，分数越高。如果代码速度是原来的2倍，则可以拿到60分及格。如果达到原来的2.5，3，3.5，4倍，则可以分别拿到80，90， 95， 100分。成绩评判标准唯一且清晰。
我是作业截止的最后4天开始看这个大作业的。看完这个评分标准，我心里先是一乐：“哈哈，终于有一个评分透明的大作业了，写论文什么的成绩太容易受老师主观评价影响了。”接着，我又发现事情有些不太对：“既然老师敢给这么高的分数，说明代码想优化到3倍或者4倍是很困难的。我的时间这么少，恐怕只能拿个80分吧。”我也没再想下去，反正代码能优化多少就优化多少，也没有那种先定目标再开始干活的必要。
我的编程任务正式开始了。准确来说，我做的不是编程，是合理而优雅地修改老师给的代码，让这个代码运行速度更快一些，而不改变程序本身的意思。要打比方的话，我是一个拿着手术刀的医生，我需要精准地切掉病变部位，还病人一个更好的身体。比较幸运的是，我的工作可以反复调试，代码出了问题可以重新修改，而不需要担心造成什么破坏性的后果。
代码的功能是计算化学反应的一些参数。这段代码产生的程序不会产生任何花哨的网页、按钮，只会在默默地运行数十秒中后，冷冰冰地在控制台上输出一行数学计算的结果。运行这段代码就好像把一个优等生关进一个房间，让他把数学卷子全做出来再离开一样。只不过程序在输入的参数完全相同的情况下，每次都会执行一模一样的操作，最终得到完全相同，完全正确的结果。
这段代码可谓是又臭又长。丝毫没有注释，一个文件里的代码（代码分布在多个文件中）全是看不懂的化学常量，另一个文件的代码全是看似毫无逻辑的计算步骤。在浏览过代码，手足无措数秒钟后，我迅速转换了思维：“化学反应的代码归根结底就是计算一个很长的公式。我没有必要看懂为什么这么做，我只需要知道哪些加减乘除运算可以被我优化就行了。”我的这种冷静能力与思维跳转能力非常惊人。
在这个大作业中，我学到了查看代码性能瓶颈的方法。经过检测，代码最耗时的部分竟然是一个exp()自然指数运算。自然指数本身是一个很容易理解的函数，高中数学就讲过这个函数的性质。这个函数在数学上很好表达，在程序中计算起来却非常麻烦。因为这个函数的值往往是一个无限不循环数，而程序只能进行有限的计算。程序只能通过多次的加法、乘法来得到一个十分近似的结果。程序总计进行了3亿次自然指数运算，代码性能瓶颈出现在这确实也情有可原。
程序中的指数运算，需要调用标准库。标准库是高级程序员们反复锤炼，被无数人反复验证的代码。这个自然指数运算对我来说是根本不可能修改的。看到这个情况，我心都凉了半截。
虽然一上来就碰到如此困难的情况，但我再次调整了心态。指数运算耗费了三成的时间，还有七成的运行时间可以被优化。我把目光又放到了其他运算速度较慢的代码上。凭借多年的高级语言（比较抽象、接近自然语言的程序语言）编程经验，我意气风发，大刀阔斧地对代码进行优化。我主要对代码进行了预处理、循环合并这两类优化。预处理就是把一些程序中不会变动的常量提前算好，避免每次重新计算。就好像你提前买一箱抽纸，这样几个月都不用再去买纸一样。循环合并就是把条件一样，需要反复做的事情，再每个“反复”中一起做掉。比如让你去测全校同学的身高体重，量身高和量体重的仪器摆在一起，这里假设两台仪器不能同时工作。你不能让同学挨个测完身高，回教室休息一下，再一个一个回来量体重。每个人量身高体重的时间虽然没变，但来回教室、排队等待的时间浪费了。最好的方法是每个人先量身高，再量体重。如果你懂编程，你或许能理解，这里的来回教室时间就是CPU从内存中读数据的时间，排队时间可以看成循环变量、控制流耗费的时间，在一个循环里做尽可能多的事能减小时间开销。
以上两类优化是非常基础的优化。经过优化后，程序运行时间从26秒到了17秒。很可惜，速度还没有达到2倍，我的成绩连及格也没有。我反复查看了其他部分的代码，绞尽脑汁也没有想出哪里可以优化。于是，我只好把目光再次放到了开始的指数运算上。
经过观察，我发现指数运算是一批一批做的，也就是一次会对多个数据依次执行步骤相同的指数运算，而标准库只能每次对一个数据进行指数运算。这里面有没有可以利用的空间呢？我凭借着十多年与搜索引擎打交道的经验，总算找到了一个比较厉害的数学运算库。里面有一种对批量数据进行指数运算的函数。我满怀期望地用这种”高级“函数替换了原来的函数。结果非常令人惊喜：程序的执行时间从17秒降到了12~13秒，速度整体变成了原来的2倍，我总算及格了。
开心之余，我总感觉自己忘了些什么事。仔细回忆了一下，代码优化不仅要快，原来程序的输出结果还不能被更改。我还没有验证新代码的正确性呢！我赶快把新代码和旧代码的结果进行了比较，发现新代码的输出结果发生了变化！
我改动了那么多处，究竟是哪一步出错了啊？！为了找出代码中的BUG，我采用了古老而有效的控制变量法。我把旧代码粘贴了回去，一段一段地把代码更新成新代码。如果某一次更新后运行结果有问题，就说明这段代码有问题。我顺利地找出了不少的低级错误。可是，我最不想碰到的情况发生了——
我发现指数运算的那整段代码中存在问题。我尝试地把指数运算的那一行改回了旧版本的代码，输出结果就正常了。也就是说，这种优化的指数运算会导致结果不正确。
我又慌了，心想指数运算这道坎可能就是过不去了。但我内心中突然涌现出的自信告诉我，我的新代码没有错误。这个新的指数运算函数是intel公司写的，如果有问题，只可能是他们有问题。代码的运行结果虽然改变了，但是代码不一定有错——这两句话并不是矛盾的。在精度较高的数学计算中，如果小数点后面好多位出现了偏差，只能算是结果有误差，不能说结果错误。况且原来的代码也只是对数学计算结果的一种近似，你怎么能保证原来的代码就离正确的结果更近呢？给你两块手表，两者差了几秒，你能知道哪块手表是正确的时间吗？保证这样的心理，我对新代码输出结果的误差进行了计算。
经检验，新代码和源代码的相对误差在小数点后6位，也就是0.0001%这个数量级。老师可没有强调结果要完全相同，或者误差保持在什么范围内。从道理上来看，只要保证代码整体的正确性就行。在强烈的自我暗示下，我接受了代码输出结果不完全相同，但我却是正确的这一事实。
如前面所述，我已经尽可能地在其他地方优化代码，就目前而言，这份代码对我来说是最优的。第一天天色已晚，我选择偃旗息鼓，明日再战。
第二天十点，烈日当空，天朗气清。我再次开始着手优化代码。经过缜密的分析，我觉得我缺少部分的知识，我需要从别的角度入手，用一些我不太熟悉的方法优化代码。
程序的运行可以分成串行和并行。串行的概念非常简单，我们人的大脑就是串行的。你不能说我左半边脑子在浏览选项题，右边的大脑跑去想填空题去了。并行就是多个串行，可以理解成多个人合作做一件事。写论文时，你写正文，我写摘要，我们同时开始写，这就是一种并行。显然，N个人干活，必然不能让事情的快N倍。因为人与人之间的交流存在着极大的效率浪费。如若不然，为什么每个企业要设置那么复杂的管理体系呢？并行程序也是如此，在硬件支持的情况下，程序并行可以提高速度，但也有一定的资源损耗。
我学过并行的知识，了解并行的概念，但没有并行编程的经验。于是，我只好以”C++ 并行编程”为搜索词去搜索有关信息。很快，我就搜到了一个满意的答案：有一种叫OpenMP的并行编程API，只需要在程序里加一些代码，就能把串行的程序变成并行的程序。但是，要是只加少量代码的话，只能并行执行循环结构，且只有对重复次数较多的循环起到优化作用。比如搬1000个箱子，让10个人来搬来搬肯定比1个搬快，而且大家只需要在搬完后交换一次信息，确认一下所有箱子都搬完了。想把更复杂的代码并行执行并达到优化效果，就要学更多的知识了。考虑到我所剩的时间不多，我打算只用OpenMP来并行优化循环。
我写了个算加法的循环，并用OpenMP并行优化。经过实验后，这个简单循环的运算确实变快了，优化成功了。看来，并行加速并不是很难啊。现在大作业代码的性能瓶颈还是那个指数运算。指数运算是作用在一个数组上的，目前的实现方式是循环对数组的每一个元素做指数运算。如果能把这个循环并行化，但代码的运算速度肯定能快上很多。于是，我把OpenMP的并行代码运用到了指数运算循环上。
可是，并行化后，代码不仅没有变快，反而变慢了。甚至随着并行线程数（可以理解为同时有多少个人在做同一个工作）增加，代码会运行得越来越慢。
做为一个自信的程序员，碰到问题时，我的第一反应肯定不是觉得我自己写错了，而是这个OpenMP调用得用问题。可能我使用这个工具的方法不太对。既然这样，也没时间去学新的东西了，没有轮子就自己造轮子，我只好自己来写一个多线程的并行程序了。于是，我删掉了OpenMP的代码，手写了创造线程、用线程做指数运算、同步线程的代码。我自己写的代码，肯定没问题了吧？
结果，用我自己的并行代码运行程序后，程序的运行速度也变慢了。做为一个正常的程序员，在代码全是自己写的情况下还发现了运行上的问题，第一反应就是出bug了。于是，我把那段并行的代码拎了出来，单独测试了好久。可是，无论怎么调试，都没有发现问题。第二天就在无聊而令人烦恼的调试中度过了。
晚上，躺在床上，苦恼地思索着代码里的问题。突然，我想到：是不是我的代码一直没有问题，而是并行这个方案有问题？做循环的次数只有10多次，如果用多线程的话，线程之间沟通的时间，就远远多于并行运算本身减少的时间。正所谓“三个和尚没水喝啊”。没办法，第二天就这么浪费了。我及时止损，准备使用新的方法优化程序。
经过昨晚的计划后，第三天，我早早地打开电脑查询一个新的技术。我顺着并行编程这一条线索，想到了另一个并行技术——SIMD（单指令多数据流）。这个技术就好比之前是一个人搬一箱货物，现在这个人可以拿手推车，一次搬几箱货物。在SIMD中，唯一增加的成本，就是货物得提前按组打包，这样才能够一组一组地搬运。这一项成本远远小于之前多线程之间沟通的成本。我去网上查了什么AVX指令集，学会了如何一次对4个数据进行计算。这样，不仅是那个指数运算，还有一些相邻的乘除法运算也可以顺便用并行
这次程序运算时间在8、9秒左右浮动。严格来说，程序并没有优化到三倍。但是，要是精心挑选一组比较看得过去的测试时间的话，应该能在报告里声称我把程序优化了3倍。这下，80分才算勉勉强强拿到。
代码真的就不能再优化了吗？既然老师敢说把速度优化4倍就能拿到满分，说明这份代码肯定还是有优化空间的。我把这份代码从头到尾读了一遍又一遍，在我的知识范围内，能用的优化小伎俩都用上了。但是，程序的运算时间几乎没有减少。我感觉自己已经弹尽粮绝了。
经过多次优化后，指数运算的用时占比已经不算很多了。一些对一个常量数组的遍历、取值、运算的用时占比逐渐高了起来。就好像一个邮递员要挨家挨户上门取件，再把货物送到另一个地方一样。这一部分的时间完全耗费在了跑到每个人家门口，敲门等人开门上，跑腿的时间反倒是可以忽略不计。这部分循环操作数组的代码是不能用之前的并行来优化的。这部分的代码没有什么过多的操作，自然也几乎没有改动的空间。我通读代码，看到这一团改不了的代码时，总会无可奈何地快速跳过。
我对代码优化已经绝望了。走神时，我想起了计算机体系结构课里的知识：现在CPU采用了流水线的设计，跳转指令（比如循环）会导致流水线的断流。为了让代码更快运行，某些时候能不用分支、循环就不要用。
我突然产生了一个奇怪的念头：循环吗……如果我把从常量数组取值的循环全部拆掉如何？这个可以理解成快递员上门取一层楼的货品时，可以用循环表示：取这个房间的货，往前走；去这个房间的货，往前走；……；如果这一层没有住户了，就上一层楼。但是，这是一个常量数组，即我可以提前知道这栋楼有几层，每层有哪几个房间。这样，快递员的指令就变成了：去101取件；去102取件……去606取件这样确切的命令。快递员不用动脑筋去观察什么时候把这层楼走完，可以上一层楼了。抛弃掉回产生跳转指令的循环后，按理说代码能变快很多。
但是，我们初学编程认识循环时，就知道循环是用来简化代码的。现在，我却要反常识地把循环拆掉，把要执行的代码展开来，一行一行写出来。这太反常识了。当然，循环拆掉代码展开后，代码会变得特别长，其中会包含很多重复的代码。与其我手动写，不如写个脚本自动把这些代码生成出来。于是，我写了一段生成代码的Python代码，把原来的循环拆掉了。
我持着怀疑的态度，一边苦笑地看着那些丑陋的代码，一边等待着程序运行结束。没想到，程序的运算时间竟然大幅度变少了！这次运行时间之间减少到了6秒多，程序的速度基本上是最开始的4倍了。我还没来得及烦恼怎么跨过优化3.5倍这道分数砍，程序一下就优化到满分了。
这太有趣了！违反常理地拆掉循环竟然能让代码加速。我关掉了再也不想多看一眼的代码，开开心心地把优化四倍的结果写进实验报告里。然后，我开始着手写这篇文章，记录一下这段过程紧张，结局却是Happy Ending的代码优化之旅。
噢，对了，源代码我是有的，但我一定不会开源。我能想象到，老师肯定会把同一份大作业用好几年。为了让这门课公平一点，我是不会上传代码的。当然了，稍微有一点编程水平的人，看完这篇文章后，都知道了该怎么优化程序了。这篇文章也算是给和我一样初学代码优化的人一些学习上的启发吧。
这是2020年6月份的文章，我当时写到一半搁笔没写了。趁现在有时间，赶快填一个坑。
现在重温这段经历，当时提笔时的激动已经没了，只剩下了怀念。两年前，我肯定想不到这四天不到的代码优化经历，竟然是我本科期间学代码优化技术学得最多、学习效率最高的一段时间，也想不到几年后的现在的几天后我即将开始新的工作，会把之前学到的这些代码优化技术全部用出来。
对了，最近我在写很多文章。今天不认真的文字写了3000~4000，之前比较认真的写得话一天3000字都不到。我本来以为这个速度很慢，上网一看，这才是正常速度。把写东西单纯当一个爱好也挺不错嘛。虽然既没有编程有趣，也没有编程挣钱就是了。