CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
题目要求
将文件「性能优化实验分析.pdf」中讨论的程序编译运行，并记录运行时间，然后利用 Linux 性能剖析工具 perf 分析程序被加速的原因。
实验过程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#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);
}
在老师提供的机器上运行下述指令（只截取了报告中和优化部分相关的三个函数）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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）。这说明，调整矩阵分块的时候需要根据具体机器的缓存配置来决定，否则反而会带来额外的开销。