题目要求

将文件「性能优化实验分析.pdf」中讨论的程序编译运行，并记录运行时间，然后利用 Linux 性能剖析工具 perf 分析程序被加速的原因。

实验过程

#include <stdio.h>
typedef struct pixel
{
	int red, green, blue;
} pixel;
#define RIDX(i, j, dim) ((i) * (dim) + (j))
void naive_rotate(int dim, pixel *src, pixel *dst)
{
	int i, j;
	for (i = 0; i < dim; i++)
		for (j = 0; j < dim; j++)
			dst[RIDX(dim - 1 - j, i, dim)] = src[RIDX(i, j, dim)];
}
void rotate1(int dim, pixel *src, pixel *dst)
{
	int i, j, ii, jj;
	for (ii = 0; ii < dim; ii += 4)
		for (jj = 0; jj < dim; jj += 4)
			for (i = ii; i < ii + 4; i++)
				for (j = jj; j < jj + 4; j++)
					dst[RIDX(dim - 1 - j, i, dim)] = src[RIDX(i, j, dim)];
}
void rotate2(int dim, pixel *src, pixel *dst)
{
	int i, j, ii, jj, k;
	for (ii = 0; ii < dim; ii += 32)
		for (jj = 0; jj < dim; jj += 32)
			for (i = ii; i < ii + 32; i += 4)
				for (j = jj; j < jj + 32; j += 4)
					for (k = j; k < j + 4; ++k)
					{
						dst[RIDX(dim - 1 - k, i, dim)] = src[RIDX(i, k, dim)];
						dst[RIDX(dim - 1 - k, i + 1, dim)] = src[RIDX(i + 1, k, dim)];
						dst[RIDX(dim - 1 - k, i + 2, dim)] = src[RIDX(i + 2, k, dim)];
						dst[RIDX(dim - 1 - k, i + 3, dim)] = src[RIDX(i + 3, k, dim)];
					}
}
#define COPY(d, s) *(d) = *(s)
void rotate3(int dim, pixel *src, pixel *dst)
{
	int i, j, k;
	for (i = 0; i < dim; i += 32)
		for (j = dim - 1; j >= 0; j -= 1)
		{
			pixel *dptr = dst + RIDX(dim - 1 - j, i, dim);
			pixel *sptr = src + RIDX(i, j, dim);
			for (k = 0; k < 32; ++k)
			{
				COPY(dptr + k, sptr);
				sptr += dim;
			}
		}
}
#define N (1 << 13)
pixel s[N * N], d[N * N];
int main()
{
	naive_rotate(N, s, d);
	rotate1(N, s, d);
	rotate2(N, s, d);
	rotate3(N, s, d);
}

在老师提供的机器上运行下述指令（只截取了报告中和优化部分相关的三个函数）。

lnszyd@201-NF5280M3:~$ gcc -g a.c
lnszyd@201-NF5280M3:~$ sudo perf record -g ./a.out
[ perf record: Woken up 10 times to write data ]
[ perf record: Captured and wrote 2.468 MB perf.data (28285 samples) ]
lnszyd@201-NF5280M3:~$ sudo perf report -g -i perf.data
-   52.13%    47.82%  a.out    a.out              [.] naive_rotate
   + 47.82% 0x2be258d4c544155
   - 4.31% naive_rotate
      - 2.48% page_fault
         - 2.48% do_page_fault
            - 2.41% __do_page_fault
               - 2.23% handle_mm_fault
                  - 1.87% __handle_mm_fault
                     - 1.31% alloc_pages_vma
                        - 1.30% __alloc_pages_nodemask
                             1.12% clear_page_erms
      - 0.77% swapgs_restore_regs_and_return_to_usermode
           prepare_exit_to_usermode
-   24.30%    23.90%  a.out    a.out              [.] rotate1
     23.90% 0x2be258d4c544155
        __libc_start_main
        main
        rotate1
-   11.86%    11.68%  a.out    a.out              [.] rotate3
     11.68% 0x2be258d4c544155
        __libc_start_main
        main
        rotate3
-   11.72%    11.49%  a.out    a.out              [.] rotate2
     11.49% 0x2be258d4c544155
        __libc_start_main
        main
        rotate2

可以看到，函数按照运行时间从大到小的排列依次为naive_rotate、rotate1、rotate_3、rotate2。

分析具体原因：rotate1相对于naive_rotate，按照4*4的大小对矩形分块，提高了缓存访问的局部性。而rotate2相对于rotate1分块更大，因此拥有更好的内存局部性，进一步减少了 Cache Miss。而rotate3与rotate2相比运行时间几乎没有变化，推测在这个运行环境上存储器写时间的影响不是很大，调整写地址连续没有带来很大收益。

此外，当调小 N 至1 << 8时，会得到完全不同的结果（rotate3速度远慢于naive_rotate）。这说明，调整矩阵分块的时候需要根据具体机器的缓存配置来决定，否则反而会带来额外的开销。