梦想风暴

经过周末的休息，重新回到工作之中，而我面对的依然是那个需要优化的发布过程。正如我在之前提到过的，在上周末结束工作之前，我为这周的工作留下了一个尾巴：需要算分的企业。

回顾一下我在之前列出的公式：
    需要算分的企业 * (真正算分的时间 + 保存历史的时间)

从这个公式中，我们可以清晰的看到，需要算分企业的多少将直接决定循环次数的多少。但需要算分的企业真的能减少，会不会破坏业务逻辑，我们还不是特别清楚。所以，我们先要与我们可爱的BA（业务分析师）进行讨论，因为他们是项目组里面最了解业务的人。目前的逻辑是，只要有新的发布，那就会把与发布相关品牌的所有企业拿出来算分，按照我们的分析，其实没有这个必要，因为这次发布的内容可能并不会影响到有些企业。经过与BA的讨论，BA认同了我们的观点，接下来，要做的就是用实际数据测试一下，如果真的这么做了，会不会有改变。测试的数据，比较让人兴奋，我们随机的做了一次发布，涉及到的企业数就下降到原来的一半，这意味着，运行时间接近缩减到原来的一半。虽然我们需要增加一些逻辑判断企业是否需要算分，但对比于能够削减的时间而言，简直就是微不足道。那个让我们吃了午饭还有空闲的程序，已经大幅度的缩减了，至少现在我们已经敢把所有的程序都跑完了。

继续分析日志，我们又找到一些算分时间特别长的企业，之所以这些企业之前没有发现，主要还是归功于运行时间太长，我们没有勇气运行完所有的程序，或者说，不想偷懒到那种地步。把一个企业单独拿出来算分，运行时间在25秒中以上，其中保存历史大约10秒种，也就是纯粹算分时间在15秒左右。这可是经过之前的优化，否则时间会更长。

我们打开代码继续分析，我和Pair突然发现了一个问题，还是与分类相关。之前提到过，我们一次计算需要算6类的分数，但是，对于我们计算的目标而言，它只可能属于一个分类，所以，其它5类的结果必然没有任何意义。之所以之前计算了所有类别，主要是考虑到它可能会涉及到多个类别，但目前的需求已经统一到一个类别，也就是需求已经变了，但代码没有变，虽然代码很成功的覆盖了目前的情况，但也为之付出了代价。理解了这一点，我们又一次修改了代码，真正算分的操作降到了10秒左右。

从需要算分的企业优化尝到甜头的我们，看到削减大规模计算次数的好处。所以，我们继续试图从目前的代码中发现一些可以削减计算的目标。果不其然，我们还是有机会的。

我们每次发布其实可能只有几个需要算分的目标，但这里的计算却把这个企业所涉及的所有目标全部拿出来算分，这显然是一个非常浪费时间的操作。我们用来测试的企业，之所以被我们找了出来，原因就是它有113个需要算分的目标，而事实上，我们的发布只有1个。不过，之前一直没有保留其它算分目标的计算结果，因为，每次都重新计算，所以，倒也不必保留。不过，现在要想提高性能，我们就不得不采用空间换时间的策略，把计算过的结果保存下来，只有这次发布涉及到的目标才重新计算。我们的选择是在数据库表中增加一个字段保存计算结果，不过，考虑到之前一直没有采用这种方法，我们就在程序中加以处理，当这个字段为空的时候，就重新计算这个字段的结果。第一次跑这个程序的时候，我们并没有明显感觉到程序运行加快，因为数据库表中这个字段都是空，所有的数据都需要重新计算，但第二次计算时，速度明显加快了需要，1秒以内就可以完成。当然这个数字取决于一次发布包含的目标个数，显然，比起10秒好了很多。

我们用这段代码对产品数据进行测试，第一次依然是一个漫长的过程，不过，第二次发布明显快了很多，大约在20分钟左右，所有的操作就宣告完成，对，就是那个曾经耗时几个小时的过程。

我想，这次优化至此就要告一段落了。现在的这段程序优化到已经可以接受的程度了，在最开始的那个公式中，除了保存历史部分，其他部分都已经做了足够的优化。当然，我相信，保存历史部分也可以优化，但目前来说，就到这里了。

有人在《<秒杀十分钟>之后》之后留言：
玩企业应用的，只要精通数据库和SQL就足够了。

我并不是太同意这个说法，从我写的这三篇blog中，可以看出，其实，真正属于SQL优化的少之又少，大部分都是逻辑的分析上。所以，如果有时间抱怨程序设计语言慢（比如Ruby），不妨先考虑一下自己的程序逻辑是不是真的写对了。

做了三天性能优化的工作，这是最近一段时间玩得最High的几天。眼瞅着程序几倍、几十倍的提升着，心里非常痛快，当然，第一天成百上千倍的提升是最快乐的。

这就是程序设计的快乐之处！

zdonking在《秒杀十分钟》中留言：
只是把一个10分钟的运算变成瞬间，就能解决“发布一次要5个小时”的问题吗？ 难道这个10分钟的方法 在发布过程中被反复调用？

好吧！我承认，《秒杀十分钟》只是故事的开始，那只是我当天所做的工作，所以，这个故事还有后续。

做程序的人都知道，优化一个循环中的内容，往往比只调用一次的操作来得更加有效，因为循环里面的东西会执行很多次，看似一小点的浪费，累计起来也是很可怕的。《秒杀十分钟》所做的优化其实只是一个只调用一次的操作，对它的优化并不会让整个发布操作提高很多，但是如果不优化这部分的话，那么每次到循环之前，我们都要等待非常漫长的一段时间。当然，如果喜欢偷懒，置之不理也许是一个非常不错的选择。

在克服了前面一个漫长的过程之后，我们站在了循环的面前。这个循环里面是一个重算分的操作，因为每次发布都会带来一些改变，所以，需要重算分来保证正确性。

一如既往，优化之前，首先要找到一些慢的地方。所以，在代码加了日志，记录不同部分的调用时间。测试依然用的是产品数据，这样做的好处是，能够尽可能贴近实际情况，而且因为数据量够大，运行可以消耗很长时间，这时候，你可以选择做一些其他的，别人一旦问起，大可以骄傲的说，跑测试呢！这种行为俗称偷懒。

当我们吃完午饭回来的时候，和我Pair的同事决定杀死这个进程，真的要把5个小时的程序运行完，我们今天真的可以休息了，更重要的是，这时在日志里已经有足够我们进行下一步分析的结果了。我们在巨大的日志中搜索，大多数算分的操作都是在可以接受的范围内，不过，我们还是找到了一些扎眼的数据，我们把一个超过35秒的算分过程单独拿了出来，它也许可以帮助我们发现问题所在。

这个算分的方法里面实际上包括了两个部分，一部分是真正的算分，另一部分是算分之后，要保存历史信息。把这个两个部分分离开来的话，算分部分大约是25秒，保存历史部分大约是10秒。我的主要目标瞄准了算分部分。

这个操作大概的逻辑是这样的，有6类的分数，我们需要分别为这6个类别计算得分。我们进一步加了些日志，分别为这6类统计时间，测试结果告诉我们，我发现有一个计算失分点的操作很耗时，而且这个操作是每个类别都需要的。进一步打开这个计算失分点的操作，我突然发现，这个里面计算出现了“类别”。我们每个失分点计算的操作都会计算所有类别的失分点，然后，每个类别都根据自己的类别取到失分点。这意味着什么？6个类别就把失分点计算了6次，而每一次的计算都是计算所有的类别的失分点，换句话说，本来应该一次完成的操作就多了5次，而且这还是一个耗时的操作。好在rails本身还为我们做了一些缓存，否则，这个操作的耗时会更多。找到问题之后，解决起来就容易了，我们把这个操作提取出来，对于每次算分，失分点只计算一次就可以了。再次运行我们的程序，算分部分的时间降到了10秒左右。

在测试过程中，我和Pair的同事一直在观察日志，我们发现了一个奇怪的问题，计算一个企业得分的过程中，会不断有查询其它企业的信息。在整体运行的时候，这个操作就显得尤为扎眼。很快，我们定位到出现这个查询的代码。经过分析，我们发现，这是由于一个关联查询带来的结果。正如我们这里分析的，其实，我们根本不需要这些信息。经过对这个方法的分析，我们发现其实，这里也是一个SQL查询就可以搞定，换句话说，我们不知不觉中，我们又多出许多数据库查询来。经过努力，我们把这段方法变成了一句SQL，再次运行那个曾经复杂的操作，算分部分降到7秒以下。其实这个方法是系统中一个比较基本的方法，对它的修改不仅仅会对我们这里的优化有意义，对其他部分也是有好处的。

把一个25秒的操作优化到7秒，这就是我第二天优化工作的结果。虽然不能说循环中的类似部分都有相同的提高，但一定量的提高肯定是有的。

测试显示，这部分已经不再那么漫长，但整个发布过程依然很漫长，所以，我们可走的路还很多。算分时间主要是
    需要算分的企业 * (真正算分的时间 + 保存历史的时间)

大致看了一下代码，保存历史部分可优化的空间可能不会太大，所以，我们下一个目标瞄准了需要算分的企业。

我们系统有一个发布的功能，这个发布非常慢，因为它牵扯到很多内容，所以，我们把这个发布变成了异步操作。不过，最近一段时间，这个发布变本加厉的慢了，据PM在UAT上测试的结果，发布一次要5个小时。于是，我今天决定看看为什么这个发布会慢到这个地步。

当我分阶段为这个发布过程加上日志之后，定位到了一个非常慢的方法。我简单测试了一下这个方法，耗时在十分钟以上。这个方法要做的是，如果一个对象所关联的一些对象都已经被废弃的话，那么就把这个对象废弃。这里的废弃实际上就是一个标记的工作。说起来很简单，但是真正理解这个方法所做的事却花了我很多时间，这段代码的实现是这样的：
* 它在关联对象的表进行查找，找到那些那些关联对象都已经废弃的情况，然后，找到这些关联对象所指的目标对象，也就是这些目标对象应该废弃，由此得到一个目标对象数组。
* 遍历目标对象表，如果这个目标对象在目标对象数组中，那么把它标记为废弃。

确实不好理解吧！如果你理解了这段代码的意思，你可能会问为什么会这么做，我也想知道。

当我用产品数据库进行测试时，第一步产生的目标对象数组包含超过12000个对象，而第二步遍历目标对象表则有近8000个对象。那么判断目标对象是否在目标对象数组的操作就是一个上亿规模的操作，这是这个操作缓慢的原因。可以预见，随着这个系统使用的增多，这两个表里面的内容会越来越多，这个操作的规模会越来越大，那么这个方法就会越来越慢。

之前曾有同事解决过一个问题，就是这里。问题是这样的，这里的操作有很长时间没有访问数据库，所有有时候，数据库连接会超时。我在这里做了一个统计，真正需要标记为废弃的对象大约只有800个，而前面提到了，这是一个上亿的数据规模，也就是说，大部分时间，系统是在空跑，而且你知道，Ruby并不是以高性能著称的程序设计语言，所以，会长时间没有任何操作。当时的解决方案是，定期进行一个对连接进行verify，告诉连接我们还活着。这是一个治标不治本的解决方案。

简单分析一下，我们便不难发现一些问题：
* 目标对象表一共只有8000个对象，为什么目标对象数组会超过12000。
* 既然目标对象数据包含了所有要废弃的对象，为什么还要遍历目标对象表。

简单这样一想，似乎解决方案就在眼前了，删除第二步操作，把第一步得到的数组做uniq，去除相同的内容，然后，遍历得到的数组，将所有的目标对象废弃。按照这个思路，把对象拿到内存中，进行处理的话，那么我们要做的是，把所有的对象找出来，然后遍历，修改状态，之后保存数据。内存操作虽好，但最终还需要写回数据库，这样算下来，这里要进行的数据库访问就是1（查找）+ N（保存）。

且慢，我们的目标是什么？其实，这只是一个标记对象的过程，也就是一个更新表中一个字段的操作，解决问题的关键就在于如何写更新条件。更重要的是，如果这样做的话，一条SQL语句就可以搞定问题。

好吧！我承认，我是一个SQL白痴。但我可以找到人帮忙，于是，我请了一个DBA帮忙，果不其然，当DBA明白了这里的需求，很快就帮我们写出了所需的SQL语句。

当我们敲下回车的时候，瞬间操作就完成了。大于十分钟的操作，再见了！

实现一个将图像所有点按位反转的功能，下面是最直接的一个实现。稍微需要解释一下的是src_step和dst_step，它们是为了存储时可以对齐，所以，可能会与宽度有所差异。

这里的uchar定义为unsigned char。

void not_ver1(uchar* src, int src_step, uchar* dst, int dst_step,
int width, int height) {
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
int src_pos = i * src_step + j;
int dst_pos = i * dst_step + j;
dst[dst_pos] = ~src[src_pos];
}
}
}

过往的经验告诉我，最直接的方法往往是最为笨拙的，但却是一个很好的起点，可以作为下一步的参照物。在C/C++中，指针和数组之间关系密切，但在性能问题上，二者之间还是存在一些差异，下面是一个改进的版本。

void not_ver2(uchar* src, int src_step, uchar* dst, int dst_step,
int width, int height) {
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
dst[j] = ~src[j];
}

src += src_step;
dst += dst_step;
}
}

如果所上面的改进只是小步幅的前进，那下面这个版本应该是一个大刀阔斧的变革了。它是从OpenCV相关代码拿出来的，OpenCV是Intel提供的一个开源计算机视觉库。因为来自Intel，所以，OpenCV在PC上有着良好的表现。

void not_ver3(uchar* src, int src_step, uchar* dst, int dst_step,
int width, int height) {
for (; height--; src += src_step, dst += dst_step) {
int i = 0;

if ((((size_t)src | (size_t) dst) & 3) == 0) {
for (; i <= width - 16; i += 16) {
int t0 = ~((const int*)(src + i))[0];
int t1 = ~((const int*)(src + i))[1];

((int*)(dst + i))[0] = t0;
((int*)(dst + i))[1] = t1;

t0 = ~((const int*)(src + i))[2];
t1 = ~((const int*)(src + i))[3];

((int*)(dst + i))[2] = t0;
((int*)(dst + i))[3] = t0;
}

for (; i <= width - 4; i += 4) {
int t = ~*(const int*)(src + i);
*(int*)(dst + i) = t;
}
}

for (; i < width; i++) {
int t = ~((const uchar*)src)[i];
dst[i] = (uchar)t;
}
}
}

让我们来看看这里都做了些什么，对比第二个版本，外层循环变化不大，但这里控制变量由原来“++”变成了“--”，因为有不少机器对JNZ有特别的指令处理，速度非常快。

内层循环则完全改变了模样。表面上看，似乎循环更多了。

首先来看if语句，这段话是对内存地址进行判断，看是否两段内存的最后两位是否都为0，换句话说，按4对齐，在下面我们可以看到，后续的处理都是按4字节进行处理（在32位机器上，一个int是4个字节），内存地址的按4对齐，可以保证读读取一个int不必跨越边界造成多次访问。这里实际的输入是uchar类型，也就是一个字节，而在这里处理的是4个字节，也就是实现了一种软件的SIMD（单指令多数据）。看到这里，就可以理解前面参数设置时那两个step的作用了，对齐是为了提高性能。

在if语句块中第一个循环中，一次处理了16个字节，也就是四个int。这里运用了循环展开的方法，这是一种常见的优化方法，另外，这样的分解可以更好的利用流水线进行计算，提高代码的并行性。有些编译器优化时可以完成简单循环展开，但这里控制循环的存在变量，所以，代码没有依赖于编译器自动展开。另外，我们可以看到，在循环中，还有t0和t1，它们的存在是为了减少代码之间没有必要的读写依赖。

有了上面的分析，后面的代码就容易懂了，剩下的循环，是在没办法大踏步前进时，选择小步伐前进。至于最后的循环，它既是不对齐的无奈选择，也是不足4象素时的更小步伐。

优化是要有证据的，下面给出我在自己机器上测试的一个结果，测试环境如下：
CPU：1.86GHz
内存：1GB
OS：Windows XP SP2
开发环境：Cygwin
编译器：GCC
数据规模：10000×10000

这里使用测试方法是用gettimeofday获取时间，需要注意的是，gettimeofday本身会受到进程调度的影响，但对于这里所做性能估计来说，这种影响是可以忽略的。下面的时间单位为微秒。

在未优化的情况下，
ver1 1423000 1450000 1398000
ver2 867000 838000 901000
ver3 189000 184000 190000

在O3优化的情况下，
ver1 224000 195000 200000
ver2 213000 192000 195000
ver3 166000 158000 165000

可以看出，在未优化的情况下，三个版本的性能差异非常大，而在优化的情况下，三者的性能差异就会缩小许多，但是第三个版本在性能上依然有比较大的优势。

关于C代码优化方法的讨论，可以参考《C代码优化方案》。