利用多核多线程进行程序优化
简介： 大家也许还记得 2005 年 3 月 C++ 大师 Herb Sutter 在Dr.Dobb’s Journal 上发表了一篇名为《免费的午餐已经结束》的文章。文章指出：现在的程序员对效率、伸缩性、吞吐量等一系列性能指标相当忽视，很多性能问题都仰仗越来越快的 CPU 来解决。但 CPU 的速度在不久的将来，即将偏离摩尔定律的轨迹，并达到一定的极限。所以，越来越多的应用程序将不得不直面性能问题，而解决这些问题的办法就是采用并发编程技术。
样例程序
程序功能：求从1一直到 APPLE_MAX_VALUE (100000000) 相加累计的和，并赋值给 apple 的 a 和 b ；求 orange 数据结构中的 a[i]+b[i ] 的和，循环 ORANGE_MAX_VALUE (1000000) 次。
说明：
1. 由于样例程序是从实际应用中抽象出来的模型，所以本文不会进行test.a=test.b= test.b+sum、中间变量(查表)等类似的优化。
2. 以下所有程序片断均为部分代码，完整代码请参看本文最下面的附件。

清单 1. 样例程序
#define ORANGE_MAX_VALUE      1000000
#define APPLE_MAX_VALUE      100000000
#define MSECOND              1000000
struct apple
{
    unsigned long long a;
    unsigned long long b;
};
struct orange
{
    int a[ORANGE_MAX_VALUE];
    int b[ORANGE_MAX_VALUE];
   
};
int main (intargc, const char * argv[]) {
    // insert
struct apple test;
    struct orange test1;
   
    for(sum=0;sum<APPLE_MAX_VALUE;sum++)
    {
        test.a += sum;
        test.b += sum;
    }
   
    sum=0;
    for(index=0;index<ORANGE_MAX_VALUE;index++)
    {
        sum += test1.a[index]+test1.b[index];
    }
    return 0;
}
回页首
怎么写代码做软件
K-Best 测量方法
在检测程序运行时间这个复杂问题上，将采用 Randal E.Bryant和 David R. O’Hallaron提出的 K 次最优测量方法。假设重复的执行一个程序，并纪录 K 次最快的时间，如果发现测量的误差 ε 很小，那么用测量的最快值表示过程的真正执行时间，称这种方法为“ K 次最优（K-Best）方法”，要求设置三个参数：
K: 要求在某个接近最快值范围内的测量值数量。
ε 测量值必须多大程度的接近，即测量值按照升序标号 V1, V2, V3, … , Vi, … ，同时必须满足（1+ ε）Vi >= Vk
M: 在结束测试之前，测量值的最大数量。
按照升序的方式维护一个 K 个最快时间的数组，对于每一个新的测量值，如果比当前 K 处的值更快，则用最新的值替换数组中的元素 K ，然后再进行升序排序，持续不断的进行该过
程，并满足误差标准，此时就称测量值已经收敛。如果 M 次后，不能满足误差标准，则称为不能收敛。
在接下来的所有试验中，采用 K=10，ε=2%，M=200 来获取程序运行时间，同时也对 K 次最优测量方法进行了改进，不是采用最小值来表示程序执行的时间，而是采用 K 次测量值的平均值来表示程序的真正运行时间。由于采用的误差 ε 比较大，在所有试验程序的时间收集过程中，均能收敛，但也能说明问题。
为了可移植性，采用gettimeofday() 来获取系统时钟（system clock）时间，可以精确到微秒。
回页首
测试环境
硬件：联想 Dual-core 双核机器，主频 2.4G，内存 2G
软件：SuseLinunx Enterprise 10，内核版本：linux-2.6.16
回页首
软件优化的三个层次
医生治病首先要望闻问切，然后才确定病因，最后再对症下药，如果胡乱医治一通，不死也残废。说起来大家都懂的道理，但在软件优化过程中，往往都喜欢犯这样的错误。不分青红皂白，一上来这里改改，那里改改，其结果往往不如人意。
一般将软件优化可分为三个层次：系统层面，应用层面及微架构层面。首先从宏观进行考虑，进行望闻问切，即系统层面的优化，把所有与程序相关的信息收集上来，确定病因。确定病因后，开始从微观上进行优化，即进行应用层面和微架构方面的优化。
1. 系统层面的优化：内存不够，CPU 速度过慢，系统中进程过多等
2. 应用层面的优化：算法优化、并行设计等
3. 微架构层面的优化：分支预测、数据结构优化、指令优化等
软件优化可以在应用开发的任一阶段进行，当然越早越好，这样以后的麻烦就会少很多。
在实际应用程序中，采用最多的是应用层面的优化，也会采用微架构层面的优化。将某些优化和维护成本进行对比，往往选择的都是后者。如分支预测优化和指令优化，在大型应用程序中，往往采用的比较少，因为维护成本过高。
本文将从应用层面和微架构层面，对样例程序进行优化。对于应用层面的优化，将采用多线程和 CPU 亲和力技术；在微架构层面，采用 Cache 优化。
回页首
并行设计
利用并行程序设计模型来设计应用程序，就必须把自己的思维从线性模型中拉出来，重新审视整个处理流程，从头到尾梳理一遍，将能够并行执行的部分识别出来。
可以将应用程序看成是众多相互依赖的任务的集合。将应用程序划分成多个独立的任务，并确定这些任务之间的相互依赖关系，这个过程被称为分解（Decomosition）。分解问题的方式主要有三种：任务分解、数据分解和数据流分解。关于这部分的详细资料，请参看参考资料一。
仔细分析样例程序，运用任务分解的方法，不难发现计算 apple 的值和计算 orange 的值，属于完全不相关的两个操作，因此可以并行。
改造后的两线程程序：

清单 2. 两线程程序
void* add(void* x)
{       
    for(sum=0;sum<APPLE_MAX_VALUE;sum++)
    {
        ((struct apple *)x)->a += sum;
        ((struct apple *)x)->b += sum;   
    }
       
    return NULL;
}
   
int main (intargc, const char * argv[]) {
        // insert
    struct apple test;
    struct orange test1={{0},{0}};
    pthread_tThreadA;
       
    pthread_create(&ThreadA,NULL,add,&test);
       
    for(index=0;index<ORANGE_MAX_VALUE;index++)
    {
        sum += test1.a[index]+test1.b[index];
    }       
   
pthread_join(ThreadA,NULL);
    return 0;
}