什么样的代码算好代码,现在大家已经有比较清晰的答案。编写简洁、可靠、可维护、可测试、高效和可移植的好代码是每一位软件开发人员的责任及目标,这六大特征就是好软件的Program SMaRT标准。
在我们的实际业务开发编码过程中,“高效”常常被“可靠”、“简洁”等抢走了注意力。但在实时系统软件开发中,我们需要将更多的注意力聚焦到“高效”上,让软件“飞”起来。
What:
什么是高效的软件?高效的代码对系统资源的占用较少,包括时间资源、空间资源。如何编写、重构或优化出高效的代码?常见的方法有三个层次: 系统层次、算法层次、代码层次。
1、系统层次关注系统的控制流程和数据流程,优化主要考虑如何减少交互;如何使系统的负载更加均衡;如何充分利用硬件的性能和设施;如何减少系统额外开销。
2、算法层次关注算法的选择(用更高效的算法替换现有算法,如快速排序替换冒泡排序);现有算法的优化(时间和空间的优化);并发和锁的优化(增加任务的并行性,减小锁的开销);数据结构的设计(比如lock-free的数据结构和算法)。
3、代码层次关注代码优化,主要是cache相关的优化、代码执行顺序的调整;编译优化选项;语言相关的优化技巧等
下面我们将从缓存等资源使用的视角来思考如何做代码层次的效率优化。
Why:
1、基础知识回顾:CPU和缓存的那点事
参考一个整体架构图:
CPU—缓存—内存,大致上工作过程是:
CPU要读取数据进行计算的时候,首先是从内部的缓存中查找需要的数据,如果有,可以最短时间最快速度交付CPU。但是如果没有找到,CPU就会提出“要求”经过缓存从内存中读取,再原路返回到CPU进行计算。同时,把这个数据所在的数据也调入缓存,可以使得以后对整块数据的读取都从缓存中进行,不必再调用内存。
Cache 的理论基础是程序局部性原理,包括时间局部性和空间局部性。即最近被CPU访问的数据,短期内CPU 还要访问(时间);被 CPU 访问的数据附近的数据,CPU 短期内还要访问(空间)。因此如果将刚刚访问过的数据缓存在Cache中,那下次访问时,可以直接从Cache中取,其速度可以得到数量级的提高。CPU的几层缓存分布如下图:
2、缓存对性能的影响
三级cache,越靠近CPU,速度越快,空间更小,价格更高。他们的访问速度对比如下:
Cache Line是CPU Cache中的最小缓存单位,目前主流的CPU 的Cache Line大小都是64Bytes。假设我们有一个512字节的一级缓存,那么按照64B的缓存单位大小来算,这个一级缓存所能存放的缓存个数就是512/64 = 8个。当访问的内容在64B以内,则一次cache line load就可以解决。当数组大于64B时,则需要多条cache line,每一次cache line的填充都是需要花费比CPU访问数据更长的时间。
Cache miss是当CPU从存储器中提取数据时,它依次在各级cache中寻找。如果在cache中找到,则称为命中hit;反之,则称为不命中miss。Cache命中率是很关键的指标,代码优化的核心就是想办法提高cache命中率。Cache本身为了提高命中率,也做了很多优化设计。比如防止性能跳水,CPU在访问一片连续内存且发生连续n次cache miss,则不再分配cache资源,让CPU直接访问DDR。
How:
前面知道了cache的相关知识,下面看看怎么利用cache的特点编写或优化高效率代码:
1、针对I-Cache的优化,主要方法有简化调用关系,减少冗余代码等。尽量减少不必要的调用,这个当然又涉及业务相关,联合进行流程、算法优化,达到减少指令的目的。
2、在设计数据结构的时候,尽量将只读数据与读写数据分开,并且尽量将同一时间访问的数据组合在一起。这样 CPU 能一次将需要的数据读入。如果两个无关的变量,一个读,一个写,而这两个变量在一个cache line里面。那么写会导致cache line失效(通常是在多核编程里面,两个变量在不同的core上引用)。 另外尽可能让数据结构是cache line对齐的,就有可能减少一次读写,但数据结构的首地址cache line对齐,意味着可能有内存浪费,这个需要权衡好空间和时间。举个例子:如下两段代码,写法A比写法B效率高。
写法A:
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
int num;
arr[i][j] = num;
}
}
写法B:
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
int num;
arr[j][i] = num;
}
}
3、根据“时间局部性”原理,对数据的使用访问,尽可能保持使用时间足够长。假如CPU 访问了一 个数组地址X上的元素,那么X+1,X+2被立即访问的概率就很高。举例:如下代码块对比,代码A比代码B效率高,因为X[i] 被重复使用。
代码A:
for (i=0; i<N; i++) {
for (loop=0; loop<10; loop++) {
... = ... x[i] ...
}
}
代码B:
for (loop=0; loop<10; loop++) {
for (i=0; i<N; i++) {
... = ... x[i] ...
}
}
4、空间局部性:空间局部性是指当前访问地址附近的地址可能随后被访问。一个矩阵乘法的例子:
代码A:
for i=1..n
for j=1..n
for k=1..n
c[i,j] += a[i,k]*b[k,j]
代码2:
for i=1..n
for k=1..n
for j=1..n
c[i,j] += a[i,k]*b[k,j]
代码2的性能优于代码一的性能。两者实现上的差异:
代码2的b[k,j]是按行访问的,所以存在良好的空间局部性,cache line被充分利用。代码1中,b [k,j]由列访问。 由于行的存储矩阵,因此对于每个缓存行加载,只有一个元素用于遍历 .
5、指令预取是CPU自动完成的,但是数据预取就是一个有技术含量的工作。数据预取的依据是预取的数据马上会用到,这个也应该符合空间局部性,但是如何知道预取的数据会被用到,这个要看上下文的关系。一般来说,数据预取在循环里面用的比较多,因为循环是最符合空间局部性的代码。 但是数据预取的代码本身对程序是有影响(影响美观和可读性),而且优化效果不一定很明显(命中的概率)。数据预取可以填充流水线,避免访问内存的等待,还是有一定的好处的。
6、避免过度使用memset,避免对对超大空间进行memset(大于1K),Cache可能会自动优化,不在分配cache资源,让CPU直接访问DDR。虽然保护了Cache被大片替换,但访问DDR带宽的效率显著低于Cache,且此类操作还增加了DDR带宽消耗。
代码效率提升除了上面这些优化方法,还有一些比较常规的优化手段,比如有些变量提前计算,避免多次使用时重复计算;使用inline函数、宏定义或宏函数;避免定义大于1K的具备变量;减少函数调用层次等等;
PS: 代码优化有时与编程规则是冲突的,比如直接访问成员变量,还是通过接口来访问,当然直接访问效率更高。代码层次的优化是基本功课,但是指望代码层次的优化来解决所有问题,无疑是缘木求鱼。从系统层次和算法层次考虑问题,可能效果会更好。
by:HW-HMJ





































苏公安网备 32011402010933号