C语言程序循环结构中的代码优化分析

c语言论文第四篇：C语言程序循环结构中的代码优化分析

　　摘要：循环结构是C语言程序的基本结构之一。程序运行时，在循环中的时间开销往往占据了总时间开销的大部分。利用C语言程序编译后的存储特性和处理器的局部性原理，适当地调整程序中循环结构的代码，充分释放处理器的潜力，可以大大提高程序的执行效率。文章的对比实验验证以上结论。

　　关键词：C语言; 循环结构优化; 缓存; 并行;

　　Performance Optimization of Cyclic Structure in C Language Programs

　　WANG Shu-xin HE Xi-ping

　　Information Science and Technology College of Hunan Agricultural University

　　Abstract：Loop structure is one of the basic structures of C language programs. When the program is running, the time overhead in the loop tends to account for most of the total time overhead. Take use of the storage characteristics of the C language program and the locality principle of the processor, proper adjustment on the code of the loop structure in the program will completely unlock the potential of the processor, therefore, greatly improve the efficiency of program execution. The comparative experiment in this paper verifies the above conclusions.

　　随着微处理器技术的发展，其周期时间从1985到2010年，提升了大约500倍[1]，然而，DRAM,SRAM的性能提升严重滞后于CPU的性能提升，DRAM访问时间提高只有大约25倍，SRAM大约只提高了20倍[1],CPU与存储器的差距一直在增大。随着多核CPU的出现，对存储器性能的要求进一步提高，CPU与存储器的矛盾愈发加剧。同时流水线，超标量等技术的引入[2]使得内存的使用更加复杂。先进的编译器使用了复杂的分析技术来优化我们的程序，并且相关技术在进一步发展，正变的越来越好。但是，即使是最好的编译器也会在那些阻止优化的代码面前受挫。因此我们需要了解CPU是如何工作的，以此来调整我们的程序以获得更高的执行效率。

　　1 存储技术

　　速度较快的存储器每字节的生产成本要比速度较慢的存储器的成本高，而且容量比慢速存储器小，为了在成本和性能之间取得平衡，产生了处理器层次结构。不同层次的存储器访问时间差距很大，通常，CPU访问寄存器只需要不到1个时钟周期，而访问SDRAM高速缓存需要几个到几十个时钟周期，访问DRAM则需要上百个时钟周期[2]。处理器层次结构的核心思想是使用高一层快而小的存储器作为低一层大而慢的存储器的缓存。实际程序读取数据时会出现两种情况，如果数据刚好在缓存中则缓存命中，没有则缓存不命中。如果缓存命中，则程序直接从缓存中读取数据，这比从低一级的存储层次中读取更快，如果不命中，则采用一定的策略从低一层读取数据写入缓存中，然后程序从缓存中读取数据，这会产生缓存不命中惩罚。通常，层次越低，缓存不命中的惩罚越高。

　　2 循环遍历顺序

　　不同层次之间的数据传输以数据块的形式传送[2]，写入缓存时，写入的是一组数据，而不仅仅是未命中的数据。按照局部性原理[1]，程序下一步会使用相邻的数据，所以缓存总是读取一组相邻的数据并保存，这样当读取下一个数据时，就可以直接从缓存中读取，而不用承受缓存未命中的代价，有效的提高程序的吞吐量。然而，如果是局部性非常糟糕的程序，将无法在这种机制下受益。考虑如下代码：

　　程序1  

　　程序2  

　　程序1,2实现的功能是将两个矩阵求和，结果存放在另一个矩阵中，在此，矩阵直接用二维数组存放。两者在功能上完全一致，唯一的区别是对二维数组的行下标和列下标迭代的先后顺序不同，但是实际的性能差距却很大。由于C语言中二维数组是按行存储的[4]，也就是说，二维数组的实际内存空间是连续的线性地址空间，首先存放第1行，接着存放第2行，依次类推。按局部性原理，CPU会每次缓存内存中一行的部分数据。程序2-1在第一次读取数据时，会出现缓存未命中，但是接下来数个数据都在缓存中，可以直接从缓存中读取，而不需要从速度相对较慢的主存中读取数据了。而程序2-2局部性非常糟糕，它每次都读取下一行的某个数据。如果一组缓存无法放下一行的数据，那么它每次都会缓存未命中，完全无法从缓存机制中受益。当然，如果缓存足够大能够放下整个数组，程序1与程序2的运行效率区别不大。

　　图1 两个程序在维度为104*104的两个矩阵之和的执行时间对比  

　　表1 不同数据规模的缓存未命中次数    

　　图1显示，在维度为104*104的矩阵上，程序1和程序2执行时间相差10倍之多。表1的数据表明，在数据规模比较大的情况下，程序2缓存未命中的次数几乎是程序1的10倍，但是不是1000或者更多，因为数据很大，缓存空间并不足以存下一行。值得一提的是，实验证明，在10*10这种很小的数据量的情况下，两个程序的运行效率完全是一样的。因为替换策略，主存地址连续的几组数据被放置在缓存中不同的地址上，而不是放在相同的地址中，从而避免了数据的覆盖。即使编译器开启最高级别的优化，两者性能的差距依旧不会缩短，编译器对此无能为力。足以见得，正确的访问顺序可以大大提高我们的程序效率。

　　3 提高并行性

　　程序的性能受到运算单元延迟的限制，但得益于现代处理器的设计，我们的CPU有足够潜力来更加高效的执行我们的程序。考虑如下代码：

　　程序3  

　　程序4  

　　程序3和程序4的功能是求数组中每个数字的和，前者是单步执行的，后者则是一次迭代执行两次运算，相对于程序3，程序4将会有更少的迭代次数。这意味着，循环方面的开销，比如比较、循环索引的计算会降低。另一方面，程序3每次迭代都要等待一个内存读取，一个加法操作的完成。但是，由于CPU内指令执行的流水线设计，再加上CPU的多个功能单元可以同时执行操作，CPU可以并行的完成多个内存读和加法操作。将循环展开为程序5所示形式，在相同的数据集下，不同的循环步数所需的执行时间进行对比如图2所示。

　　程序5  

　　程序5  

　　图2 不同循环步数的运行时间  

　　图2表明，在整数加中，当单次循环步数为2时，程序的性能提高了38%。步数为3时，相比之前进一步提高了28%。但是，当步数再一步提高时，性能的提高非常微弱，甚至有所下降。因为程序的性能已经达到了运算单元的延迟极限，除非CPU有更多的ALU，否则，程序的性能将无法通过这种方式进一步提升。对于浮点求和，程序性能得到了更大的提升，步数为2时提高了76%，步数为3时进一步提高了30%。但是，由于部分浮点数无法在计算机中准确表示，所以计算机中的浮点运算不满足结合律，计算顺序的改变会带来微小的误差。出于这个原因，编译器不会使用这种方法来优化程序。但如果程序能够接受这种误差，就可以通过使用上述方法调整代码来获得性能上的提升。

　　4 结束语

　　通过本文的讨论可以得知，通过优化循环结构中的代码，能使程序的运行性能有一定的提升。

　　在编程中，一些看似微小的调整会使得程序的性能产生巨大的变化。通过使用正确的内存访问顺序，降低循环开销，提高并行性，成功的提高了程序的执行效率，使之获得了数倍的提升。现代处理器有很高的潜力来更快的执行程序，但在大多数时候这种潜力不容易被程序察觉和发掘出来。当所设计的程序对运行的时间效率有比较严苛的要求，需要优化程序以提高程序的运行性能时，就要求程序员对程序的编译和处理器执行程序的特性有一定的了解，并且通过不断调整程序代码来完全释放处理器的潜力。

　　参考文献

　　[1] (美)Randal E. Bryan,(美)David R. O’Hallaron(著).深入理解计算机系统原书第三版[M],龚奕利,贺莲(译).机械工业出版社2018.
　　[2] (美)John L. Hennessy,(美)David A. Patterson(著).计算机体系结构量化研究方法(第五版)[M],贾洪峰(译).人民邮电出版社.2018.
　　[3]谭浩强.C语言程序设计(第3版)[M].清华大学出版社, 2014.
　　[4] (美)STEPHEN PRATA著.C Primer Plus第6版中文版[M],姜佑译.人民邮电出版社,2016.
　　[5]黄立慧.C语言中循环嵌套的教学设计与探讨[J].福建电脑,2018,34(12):81-82+122.
　　[6]马学敏.计算机C语言循环语句的应用研究[J].中国新通信,2016,18(17):87-88.
　　[7]唐楚然.内存分配在C指针教学中的作用[J].信息技术与信息化,2016(04):128-133.