阅读笔记（二）剖析计算机结构以实现内存优化《what every programmer should know about memory》

深藏阁楼爱情的钟 2023-06-23 06:59 29阅读 0赞

### 一. 简介 ###

《what every programmer should know about memory》是red hat公司的大牛Ulrich Drepper于2007年写的一篇长文，全文114页，分量十足，全程无尿点。本文从计算机组成原理的角度指出在硬件性能提升的情况下，限制程序性能的可能因素来源于程序员对内存(memory)使用上的问题，并由此提出了一系列提高程序性能的方法。通过本文的学习，可以加深对RAM，CPU，虚拟内存， NUMA(Non Uniform Memory Access )全方面的了解，同时掌握一些提升性能和优化的方法。

文章共分八章，1-5章是对RAM， CPU， 虚拟内存，NUMA的技术细节的介绍，第6章是全文核心：回顾了前面的知识并给出了如何在不同情况下写出性能良好的代码的一些建议。第7章介绍了性能测试工具，第8章对未来技术进行了展望。

和作者一样，建议通读全文，如果真的十分没有耐心“The very impatient reader”，可以直接看第6章，看不懂的再看前面几章针对性了解即可。关于前几章的内容此处不做总结，仅仅将性能提升建议提取出来以作记录。

### 二. 性能提升建议总结 ###

##### 1. 略过缓存 #####

很多时候，我们会在短时间内处理大量的数据，但是也有时候我们不会立即进行处理。常见的如一些压缩算法的信息往往存为矩阵数据，而这些数据并不需要立即被使用，因此放在缓存中是一件很浪费的事情：放置很久不用，而且还要多了一个存取的过程，对于这种可以**人为略过缓存**的过程，即**non-temporal write operation**。

#include <emmintrin.h>
    void setbytes(char *p, int c)
    { 
    	__m128i i = _mm_set_epi8(c, c, c, c,
    	c, c, c, c,
    	c, c, c, c,
    	c, c, c, c);
    	_mm_stream_si128((__m128i *)&p[0], i);
    	_mm_stream_si128((__m128i *)&p[16], i);
    	_mm_stream_si128((__m128i *)&p[32], i);
    	_mm_stream_si128((__m128i *)&p[48], i);
    }

##### 2. 数据缓存访问优化 #####

当必须使用缓存的时候，我们就需要对缓存的使用进行优化了。

**（1）顺序读取**  
  例如对于矩阵乘法

for (i = 0; i < N; ++i)
    	for (j = 0; j < N; ++j)
    		for (k = 0; k < N; ++k)
    			res[i][j] += mul1[i][k] * mul2[k][j];

通常做法即为如上所示的三层循环嵌套，其中mul1顺序访问，而内层的mul2却没有，对此我们可以进行调整做到顺序访问从而提升性能：

double tmp[N][N];
    for (i = 0; i < N; ++i)
    	for (j = 0; j < N; ++j)
    		tmp[i][j] = mul2[j][i];
    for (i = 0; i < N; ++i)
    	for (j = 0; j < N; ++j)
    		for (k = 0; k < N; ++k)
    			res[i][j] += mul1[i][k] * tmp[j][k];

这种做法采取空间换时间的方法，用tmp数组存储一个mul2的倒放矩阵，从而实现三层循环两个均顺序访问。这种简单的做法就可以提升76.6%的速度。

在此基础上，仍然可以进行优化，因为采用tmp矩阵的方式对空间消耗很大，如果对空间要求严格的话可能会导致一些不好的后果，比如嵌入式设备。

#define SM (CLS / sizeof (double))
    for (i = 0; i < N; i += SM) 
    { 
    	for (j = 0; j < N; j += SM)
    	{ 
    		for (k = 0; k < N; k += SM)
    		{ 
    			for (i2 = 0, rres = &res[i][j], rmul1 = &mul1[i][k]; 
    			i2 < SM; ++i2, rres += N, rmul1 += N) 
    			{ 
    				for (k2 = 0, rmul2 = &mul2[k][j];
    					k2 < SM; ++k2, rmul2 += N) 
    				{ 
    					for (j2 = 0; j2 < SM; ++j2) 
    					{ 
    						rres[j2] += rmul1[k2] * rmul2[j2];
    					}
    				}
    			}
    		}
    	}
    }

其中CLS表示Cash Line Size，如上代码可视为分治法的一种运用，在不使用tmp矩阵的前提下依然对第二种代码提升了6.1%的速度。

**（2）对齐**  
对于如下结构体：

struct foo { 
    	int a;
    	long fill[7];
    	int b;
    };

采用pahole程序检测结果如下：

struct foo { 
    	int a; /* 0 4 */
    	/* XXX 4 bytes hole, try to pack */
    	long int fill[7]; /* 8 56 */
    	/* --- cacheline 1 boundary (64 bytes) --- */
    	int b; /* 64 4 */
    }; /* size: 72, cachelines: 2 */
    /* sum members: 64, holes: 1, sum holes: 4 */
    /* padding: 4 */
    /* last cacheline: 8 bytes */

由于对齐原则，我们可以看到5-8字节其实是没有使用的，这造成了空间的浪费，比较合理的方法是将b填在a后面，即调整结构体的顺序。

**总的来说应采用如下原则来申明结构体**：  
a. 将长度为字长整数倍的放在结构体开始  
b. 按结构体中定义的顺序来访问结构体中的元素可以提高访问速度  
c. 使用posix\_memalign和\_\_attribute  
d. 如果结构体一部分需要经常调用而其他的不用，则最好分割成两个结构体

**总结：** 对于data cache访问主要的优化方式是1.顺序访问（提高预取性能）2.对齐（和cache line，减少cache读取次数） 3.减少结构体对cache的占用（也是为了减少cache读取） 4.减少conflict miss

##### 3. 1级指令缓存接入优化 #####

通常程序员是不能直接优化指令缓存系统的，但是通过配置编译器，我们可以间接引导编译器使得代码表现得更好。通常情况下，注意一下几点可以使得L1i表现更优。

1.  尽量减小代码的大小
2.  尽量线性的处理代码
3.  注意代码对齐
4.  仅仅当函数足够小的时候才可以采用内联函数的形式

关于代码的对齐，在以下几处最为有效：  
a. 函数的开始部分  
b. 通过跳转到达的快的开始部分  
c. 循环的开始部分  
原因在于这些地方代码对齐造成的损失相对很小，而优点却很明显：对预加载和解码均有显著优化。作为程序员对于代码对齐可以通过以下命令实现

-falign-functions=N
    
    -falign-jumps=N
    
    -falign-loops=N

##### 4. TLB使用优化 #####

TLB的优化主要在于降低TLB miss的概率，主要有两种做法：

1.  减少程序使用的页数
2.  减少TLB配置的更高级索引表项数

##### 5. 预读取 #####

现代处理器为了隐藏延迟做了一些优化，如增加命令行流水线，乱序操作等，但是这些只能增加缓存命中的几率，并不能减少访问主存时的延迟。因此，预读取有其存在的价值。

预读取最大的缺陷在于为了安全起见，预读取不能超过页的范围。由于目前通用的是4K页大小，这导致了预读取并不能很大程度上提高效率。从软件角度考虑，我们可以通过API指导程序进行预读取操作。

#include <xmmintrin.h>
    enum _mm_hint
    { 
    	_MM_HINT_T0 = 3,
    	_MM_HINT_T1 = 2,
    	_MM_HINT_T2 = 1,
    	_MM_HINT_NTA = 0
    };
    void _mm_prefetch(void *p, enum _mm_hint h);

预读取也存在着一些问题：预读取的大小十分考究，并且预读取本身也是需要消耗指令时间的，因此比较好的选择是另开一条线程（Helper Thread）专门做预读取，以便减小代码的复杂度，降低出错概率。常见的做法有以下两种：

1.  在同一CPU内核中采用超线程
2.  采用哑线程作为Helper Thread

### 三. 总结 ###

由于文章及长，并且主要供自己记录参阅使用，本文总结有颇多缺失疏漏之处，如果有人耐心的看到了结尾，谢谢你的耐心也抱歉没有写的更好。