数据布局

数据重组

程序的核心循环中常常存在多个数组之间的运算，而这些数组在内存中并不是连续存放的，会导致程序的访存局部性较差。此时可以使用数组重组的方式将多个数组合并成为结构体数组，该结构体的属性域为重组前各数组的元素，从而提高程序访问数据的局部性。

原始代码：

优化后代码：

数据转置

当循环访问数组中元素时，若最内层循环对数组的索引方式与内存中的存放方式不同，会导致数据的访问不连续，无法充分利用程序的空间局部性。针对这一问题，可以使用数组转置的方法对数组的数据布局进行变换，使得内层循环对数组的访问连续。

原始代码：

优化后代码：

结构属性域调整

程序中访问结构体变量时，常被访问的可能是少量的属性域，如果改变这些结构的定义，使经常被访问的属性域组织在一起，能够有效地提高结构定义变量的空间局部性。示例如下。

原始代码：

优化后代码：

属性域调整后改善了内存中数据的连续性。经过测试，进行100000次循环迭代，结构属性域调整前耗时494us，调整后耗时395us。优化人员在编写程序时合理的运用此类技巧，可以使得程序的运行情况更好。

结构体拆分

除了结构体属性域调整能够改进数据的局部性，结构体拆分也能改进数据的局部性。上节列举的示例经过结构体属性域调整后，虽然同一次迭代内x维的时间t_x、速度v_x和位移d_x在内存中存放连续，但是相邻的迭代间P[i]和P[i+1]的数据在内存中还是不连续的，此时可以利用结构体拆分的方法进行改写。

将结构体拆分成三个结构体后，以motion_x为例，数据在内存中的布局如图示

继续以上述结构拆分的代码段定义的motion_x结构体为例，经过结构拆分之后相邻的迭代间P[i]和p[i+1]的数据已经连续，但t_x、v_x、d_x相邻迭代的数据在内存中依然不是连续的。此时可以使用结构体数组转为数组结构体的方法，将不连续的数据存放在数组结构体中，改进程序的数据布局情况。

将结构体数组转换为数组结构体后，数据t_x、v_x和d_x相邻迭代的数据在内存中连续存放，如图所示。

总结

访存性能优化是程序性能优化中重要的组成部分。这部分内容从计算机多层次存储结构的基本概念出发，按照离处理器从近至远的顺序介绍了一些如何更好地利用多层次存储结构的程序优化方法，并说明了如何在编写程序时改善数据局部性，以提高程序的访存性能。