代码的优化特别是与循环相关的代码的优化需要考虑计算机系统的各个层次，包括底层CPU的并行处理能力，存储的缓存机制，编译器的优化能力，程序员需要充分创造在CPU、编译器优化时需要具备的条件，同时，需要考虑适当的数据结构和算法。
1 减少循环中函数调用1.1 增加了函数调用的版本
#include <stdio.h>
size_t strlen(char* str);
void lower(char *str)
{
for(size_t i=0; i<strlen(str); i )
if(str[i] >= 'A' && str[i] <= 'Z')
str[i] = ('a'-'A');
}
int main()
{
char str[] = "abcABCaBc";
printf("%s\n",str);
lower(str);
printf("%s\n",str);
getchar();
return 0;
}
size_t strlen(char* str)
{
if(str==NULL)
return 0;
char* pm = str;
while(*pm );
return pm-str-1;
}
1.2 减少了函数调用的版本
void lower(char *str)
{
size_t len = strlen(str);
for(size_t i=0; i<len; i )
if(str[i] >= 'A' && str[i] <= 'Z')
str[i] = ('a'-'A');
}
1.3 可以使用位运算来优化函数体
void lower(char *str)
{
size_t len = strlen(str);
for(size_t i=0; i<len; i )
str[i] |= 1<<5;
}
strlen()在GNU C Library中有更高效率但有变态的写法：
https://code.woboq.org/userspace/glibc/string/strlen.c.html
3 其它与循环相关的优化3.1 循环中数组的行序和列序访问对性能产生的影响
函数sum_array_rows的效率要高一些，为什么呢？
如果看汇编代码，两者产生的汇编指令是一致的。
二者运行的效率差异主要来自于“缓存命中率”。
C语言编译对于二维数组，以行序优先的顺序来翻译，存储时，先存储第一行、然后是第二行，第三行……
计算机的内存是线性结构顺序存储的。
计算机CPU一般都有相对内存速度更快的缓存（称为缓存线（cache line），64个字节），CPU读取数据会一次从顺序存储的内存中读取64个字节到缓存。并且CPU在加载缓存线数据的时间内，能并行处理相当多的工作。
当访问a[i][j]时，需要先将数据读取到寄存器，CPU会先到缓存中去读取，缓存中没有才到内存中去读取。寄存器的速度最快，其次是缓存、内存、硬盘。
由此，连续操作多维数组的最后一个维度最快（最后一个维度的数据是连续存储的），可以获得最大概率的“缓存命中率”。
内循环中的a[i][j]是连续操作最后一个维度，是按照内存线性结构顺序存储来访问的，所以效率最高。这也解释了要将双重循环中将长循环写到内循环。
内循环中a[i][j]操作时，一次加载缓存64个字节（32位平台则是16个整数），则最多可连续命中缓存16次。因为a[i][j]访问时，i是外循环的行，j是内循环的列，按行连续地读取每一列的数据（参考上图），缓存命中率高。
循环中a[i][j]操作时，一次加载缓存64个字节，16个整数，如果数组列数是16，则最多命中一次，如果是8列，最多命中两次。因为a[j][i]访问时，i是外循环的行，j是内循环的列，按列间断地读取每一行的数据（参考上图），缓存命中率低。
3.2 循环中消除内存引用、循环展开、提高并行度
#include <stdio.h> // 《深入理解计算机系统》循环代码优化
#include <stdlib.h>
#include <time.h>
/*
* 程序优化的第一步就是消除不必要的工作，让代码尽可能有效地执行所期望的任务。这包括消除不
* 必要的函数调用、条件测试和内存引用。这些优化不依赖目标机器的任何具体属性。了解了处理器
* 的运作，就可以进行程序优化的第二步，利用处理器提供的指令级并行能力，同时执行多条指令。
* 为了清晰地说明如何去优化一个程序，这里使用一个如下向量数据结构的运行示例。*/
#define data_t int
typedef struct { /* 创建一个vector抽象数据类型 */
long len; /* 长度 */
data_t *data; /* 动态内存起始地址 */
}vec_rec, *vec_ptr;
/* 创建一个指定长度的vector */
vec_ptr new_vec(long len) /* 为头部结构体分配内存 */
{
vec_ptr result = (vec_ptr) malloc(sizeof(vec_rec));
data_t *data = NULL;
if (!result)
return NULL; /* 头部创建失败 */
result->len = len;
if (len > 0)
{
data = (data_t*) calloc(len, sizeof(data_t));
if(!data)
{
free((void*) result);
return NULL; /* 存储空间分配失败 */
}
}
result->data = data;
return result;
}
/* 取vector元素并存在目标位置 */
/* 越界返回0，成功返回1 */
int get_vec_element(vec_ptr v, long index, data_t *dest)
{
if(index < 0 || index >= v->len)
return 0;
*dest = v->data[index];
return 1;
}
long vec_length(vec_ptr v) /* 返回vector的长度 */
{
return v->len;
}
void combine_add0(vec_ptr v, data_t *dest) /* 求向量元素和 低效率版本*/
{
long i;
*dest = 0;
for (i = 0; i < vec_length(v); i )
{
data_t val;
get_vec_element(v, i, &val);
*dest = *dest val; /* 可以是*或用一个宏OP代替 */
}
}
/*
这个函数的功能非常简单，无非就是将传入的向量指针v所指向的vector头对应的各个元素相加，
每加上一个元素，将其结果保存在*dest中。
可以观察到，在求向量元素和的过程中combine_add0函数频繁调用了函数vec_length作为for循环
的测试条件。向量的长度并不会随着循环的进行而改变，但是在这一段代码中每一次循环都需要对
测试条件求值，这就做了很多的重复的无意义的工作。所以这里修改了另外一个版本combine_add
2，只计算一次向量长度，保存在length中，以提升程序运行的效率。
*/
// 1 减少循环中的函数调用1
void combine_add1(vec_ptr v, data_t *dest) /* 向量元素求和 */
{
long i;
long length = vec_length(v);
*dest = 0;
for (i = 0; i < length; i )
{
data_t val;
get_vec_element(v, i, &val);
*dest = *dest val;
}
}
/*
这个优化叫做代码移动。这类优化主要解决那些需要执行多次但每次计算结果不会改变的计算。编
译器会试着进行代码移动以优化程序，但是对于有些函数来说，调用次数不同或者调用位置不同会
导致调用结果也有不同，如一个计算函数自身被调用次数的函数。编译器不能可靠的发现对某些函
数进行代码移动是否会带来负面影响，那么它就不会对这段代码进行优化。为了改进代码，程序员
必须经常帮助编译器显示地完成代码移动。
*/
// 2 减少循环中的函数调用2
/*
函数调用会带来时间开销。在combine_add1的代码中，每次循环迭代都会调用get_vec_element来
获取下一个元素。每次调用这个函数都会把索引i与边界做比较，这就会造成程序运行效率低。这
里增加一个函数get_vec_element，用于返回向量的首个元素的地址：
*/
data_t *get_vec_start(vec_ptr v)
{
return v->data;
}
void combine_add2(vec_ptr v, data_t *dest)/* 直接通过数组访问vector元素 */
{
long i;
long length = vec_length(v);
data_t *data = get_vec_start(v); /* v->data */
*dest = 0;
for (i = 0; i < length; i )
{
*dest = *dest data[i];
}
}
/*
书上在这里给出的结论是，性能并没有明显的提升，甚至求和的性能还略有下降。看来在循环调用
中，还存在着其他因素限制了程序的运行效率。那么是什么原因导致的呢？
分析：现代处理器以指令流水线化的方式工作，当遇到分支的时候，处理器猜测分支该往哪个方向
走。处理器会继续执行其预测的分支指令，分支结果确定之前，处理器会避免修改寄存器或内存值
。如果预测正确，那么处理器就会提交执行的指令的结果，将其存储到寄存器或者内存中。如果预
测错误，处理器必须丢掉这次投机执行的结果，并且跳转到正确位置重新开始取指令的过程，重新
填充指令流水线。但是，这并不意味着所有的程序分支都会减缓程序的执行。在现代处理器中，分
支预测的逻辑非常善于辨别不同的分支指令的长期趋势。例如在循环中，结束循环的分支通常被预
测为选择分支，因此只有最后一次会导致预测错误。而在本例中，检测总是确定索引是在界内的，
只有最后一次i越界了才会预测失败，是高度可预测的。所以代码避免边界比较并没有带来明显的
效率提升。
不是所有的检测都是高度可以测的，有时候甚至需要程序员编写好的代码来引导程序被翻译成尽可
能可预测的汇编代码。这需要一些试验，写出函数的不同版本，然后检查产生的汇编代码，并测试
性能。故而这依然是代码优化的重要步骤，这些步骤将最终产生显著的性能提升。
*/
// 3 消除循环中不必要的内存引用
/*
combine_add3的代码将累加值存放在dest这个指针所指向的位置，下图是编译器编译出来的汇编代
码：
*dest = *dest data[i];
0040E053 mov eax,dword ptr [ebp 0Ch] // *dest读（循环体内）
0040E056 mov ecx,dword ptr [eax]
0040E058 mov edx,dword ptr [ebp-4]
0040E05B mov eax,dword ptr [ebp-0Ch]
0040E05E add ecx,dword ptr [eax edx*4]
0040E061 mov edx,dword ptr [ebp 0Ch] // *dest写（循环体内）
0040E064 mov dword ptr [edx],ecx
可以看到在这个循环中，每次都要从dest指向的内存读出对应的数值，然后把新值又写入内存。考
虑到每次读取的值都是上一次循环写入的值，所以这样的读写非常浪费时间。为了消除这种无意的
内存读写，将代码重写，引入临时变量acc，用于累计计算结果，在循环执行完毕后再讲acc的值写
入内存。
*/
void combine_add3(vec_ptr v, data_t *dest)/* 累加结果存放在局部变量当中 */
{
long i;
long length = vec_length(v);
data_t *data = get_vec_start(v); /* v->data */
data_t acc = 0;
for (i = 0; i < length; i )
{
acc = acc data[i];
}
*dest = acc;
}
/*
161: acc = acc data[i];
0040E0D1 mov edx,dword ptr [ebp-4]
0040E0D4 mov eax,dword ptr [ebp-0Ch]
0040E0D7 mov ecx,dword ptr [ebp-10h]
0040E0DA add ecx,dword ptr [eax edx*4]
0040E0DD mov dword ptr [ebp-10h],ecx
162: }
0040E0E0 jmp combine_add4 40h (0040e0c0)
163: *dest = acc;
0040E0E2 mov edx,dword ptr [ebp 0Ch] // *dest只有一次写（循环体外）
0040E0E5 mov eax,dword ptr [ebp-10h]
0040E0E8 mov dword ptr [edx],eax
*/
/* 减少了大量的内存读写，程序性能得到了极大的提高。 */
// 4 循环展开
/* 循环展开是一种程序变换，通过增加每次迭代计算的元素数量，减少循环的迭代次数。循环按
照因子k展开，即是说每次循环索引增加k。这里展示一个k=2时的循环展开版本： */
/* 按照因子k = 2展开的版本 */
void combine_add4(vec_ptr v, data_t *dest)
{
long i;
long length = vec_length(v);
long limit = length - 1;
data_t *data = get_vec_start(v); /* v->data */
data_t acc = 0;
for (i = 0; i < limit; i =2) /* 一次循环累加两个数 */
{
acc = (acc data[i]) data[i 1];
}
for (; i < length; i ) /* 完成剩下的数的累加 */
{
acc = acc data[i];
}
*dest = acc;
}
/*
在本例中，由于减少了循环开销操作，所以性能有所提升。不过将求累和改为求累积的话，性能并
不能有所提升。其原因在于求乘积的运算占用的时钟数比求和要长，导致在循环执行的过程中性能
瓶颈主要在于求乘积而非循环开销。这说明具体问题还得具体分析，并不是说循环扩展就一定能够
带来性能提升。书中给出了k取不同值以及采用其他combine方法下性能的结果对比。 */
// 5 提高并行性
/*
在前面的五种优化方法中，程序都存在一个问题，即把累加值放在一个单独的变量acc中
。在计算完成之前都不能计算acc的新值。为什么不设置多个acc变量，同时计算多个acc值呢？这
里给出展开次数k = 2，即采用两个acc变量的程序版本： */
void combine_add5(vec_ptr v, data_t *dest)
{
long i;
long length = vec_length(v);
long limit = length - 1;
data_t *data = get_vec_start(v); /* v->data */
data_t acc0 = 0;
data_t acc1 = 0;
for (i = 0; i < limit; i =2) /* 一次处理两个元素 */
{
acc0 = acc0 data[i];
acc1 = acc1 data[i 1];
}
for (; i < length; i ) /* 完成所有的数累加 */
{
acc0 = acc0 data[i];
}
*dest = acc0 acc1;
}
/*
因为程序的性能受运算单元延迟限制，执行加法的功能单元是完全流水线化的，这意味着每个时钟
周期可以开始一个新的操作，并且有些操作可以由多个运算单元执行。硬件具有更高的加法和乘法
效率，所以程序员在编写代码的时候也应该尽可能使得代码能够向硬件的效率靠拢。充分利用各个
运算单元，以提高性能。书中给出了k取不同值以及采用其他combine方法下性能的结果对比，具体
结论和分析见书P370-P373。*/
// 6 提高并行性2，循环展开的不同结合变换
/* 书中还给出了重新结合变换来极大提升性能。这里给出其源代码。详情可见书P373-P376。*/
/* 按照因子k = 2展开重新结合的改进版本 */
void combine_add6(vec_ptr v, data_t *dest)
{
long i;
long length = vec_length(v);
long limit = length - 1;
data_t *data = get_vec_start(v); /* v->data */
data_t acc = 0;
for (i = 0; i < limit; i =2) /* 一次循环累加两个数 */
{
// acc = (acc data[i]) data[i 1];
acc = acc (data[i] data[i 1]);
}
for (; i < length; i ) /* 完成剩下的数的累加 */
{
acc = acc data[i];
}
*dest = acc;
}
/* 可以看出，这里的combine_add6其实是combine_add4的一个改进版本。在累加的时候先求两个读取
到的元素和，再把求和结果与acc变量求和。对于整数加法来说，这样的改进对性能影响并不大，
因为整数加法的运算延迟比较小。但是对于整数乘法和浮点数加乘法来说性能确实质的改变。为什
么有这样的现象呢，主要是因为虽然每次循环要做两次加/乘运算，但是只有其中一次加/乘法会依
赖acc，这就导致从内存读取出来的两个数在相乘的时候并不会对数据数据相关链产生影响，可以
并行执行，从而使效率提升一倍。本质上依然是一种提高并行性的优化方法。 */
int main()
{
const long LEN = 1000000;
vec_ptr vp = new_vec(LEN);
for(int i=0;i<LEN;i )
vp->data[i] = i 1;
data_t dt = 0;
clock_t start,end;
start = clock();
combine_add0(vp,&dt);
end = clock();
printf("时间消耗：%5.2f 结果：%d 0 低效率版本\n",double(end-start),dt);
start = end;
combine_add1(vp,&dt);
end = clock();
printf("时间消耗：%5.2f 结果：%d 1 减少循环中的函数调用1\n",double(end-start),dt);
start = end;
combine_add2(vp,&dt);
end = clock();
printf("时间消耗：%5.2f 结果：%d 2 减少循环中的函数调用2\n",double(end-start),dt);
start = end;
combine_add3(vp,&dt);
end = clock();
printf("时间消耗：%5.2f 结果：%d 3 消除循环中不必要的内存引用1\n",double(end-start),dt);
start = end;
combine_add4(vp,&dt);
end = clock();
printf("时间消耗：%5.2f 结果：%d 4 循环展开\n",double(end-start),dt);
start = end;
combine_add5(vp,&dt);
end = clock();
printf("时间消耗：%5.2f 结果：%d 5 提高并行性\n",double(end-start),dt);
start = end;
combine_add6(vp,&dt);
end = clock();
printf("时间消耗：%5.2f 结果：%d 6 提高并行性2，循环展开的不同结合变换\n",double(end-start),dt);
getchar();
return 0;
}
/* 运行结果
时间消耗：46.00 结果：1784293664 0 低效率版本
时间消耗：16.00 结果：1784293664 1 减少循环中的函数调用1
时间消耗： 0.00 结果：1784293664 2 减少循环中的函数调用2
时间消耗：16.00 结果：1784293664 3 消除循环中不必要的内存引用1
时间消耗： 0.00 结果：1784293664 4 循环展开
时间消耗： 0.00 结果：1784293664 5 提高并行性
时间消耗：15.00 结果：1784293664 6 提高并行性2，循环展开的不同结合变换
*/
// 总结
/* 这里主要是利用一个小程序总结了程序优化的一些方法，在实际的工程当中程序代码异常复杂，在
优化的过程中一定不能影响程序的正确性。应该注意一些函数是否有副作用，有没有改变一些全局
程序状态等。此外，对于复杂的工程，还需要一些测时间的工具和技术来确定应该主要优化哪些地
方的代码。 */
// https://blog.csdn.net/xiaji110901/article/details/79032674
－End－
,
