16.2.5 示例：矩阵初始化
为了演示优秀的内存访问模式，我们将使用一个巨大的矩阵，所有元素值都是 42。该矩阵以行存储。
列表 16-27 中的程序按行初始化该矩阵；列表 16-28 中的程序按列初始化。哪一个程序执行更快？
Listing 16-27.matrix_init_linear.c
#include <stdio.h>
#include <malloc.h>
#define DIM (16*1024)
int main( int argc, char** argv ) {
size_t i, j;
int* mat = (int*)malloc( DIM * DIM * sizeof( int ) );
for( i = 0; i < DIM; ++i )
for( j = 0; j < DIM; ++j )
mat[i*DIM+j] = 42;
puts("TEST DONE");
return 0;
}
Listing 16-28.matrix_init_ra.c
#include <stdio.h>
#include <malloc.h>
#define DIM (16*1024)
int main( int argc, char** argv ) {
size_t i, j;
int* mat = (int*)malloc( DIM * DIM * sizeof( int ) );
for( i = 0; i < DIM; ++i )
for( j = 0; j < DIM; ++j )
mat[j*DIM+i] = 42;
puts("TEST DONE");
return 0;
}
再次使用 linux 的 time 工具(不是 shell 自带的)来测试执行时间。
> /usr/bin/time -v ./matrix_init_ra
Command being timed: "./matrix_init_ra"
User time (seconds): 2.40
System time (seconds): 1.01
Percent of CPU this job got: 86%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:03.94
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 889808
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 2655
Minor (reclaiming a frame) page faults: 275963
Voluntary context switches: 2694
Involuntary context switches: 548
Swaps: 0
File system inputs: 132368
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0
> /usr/bin/time -v ./matrix_init_linear
Command being timed: "./matrix_init_linear"
User time (seconds): 0.12
System time (seconds): 0.83
Percent of CPU this job got: 92%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:01.04
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 900280
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 4
Minor (reclaiming a frame) page faults: 262222
Voluntary context switches: 29
Involuntary context switches: 449
Swaps: 0
File system inputs: 176
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0
因为 cache misses 的关系执行慢了很多，这样的输出可以使用 valgrind 加上 cachgrind 组件来进行观察。valgrind 输出见列表 16-29 所示。
Listing 16-29.cachegrind_matrix_bad
> valgrind --tool=cachegrind ./matrix_init_ra
==17022== Command: ./matrix_init_ra
==17022==
--17022-- warning: L3 cache found, using its data for the LL simulation.
==17022==
==17022== I refs: 268,623,230
==17022== I1 misses: 809
==17022== LLi misses: 804
==17022== I1 miss rate: 0.00%
==17022== Lli miss rate: 0.00%
==17022==
==17022== D refs: 67,163,682 (40,974 rd + 67,122,708 wr)
==17022== D1 misses: 67,111,793 ( 2,384 rd + 67,109,409 wr)
==17022== LLd misses: 67,111,408 ( 2,034 rd + 67,109,374 wr)
==17022== D1 miss rate: 99.9% ( 5.8% + 100.0% )
==17022== LLd miss rate: 99.9% ( 5.0% + 100.0% )
==17022==
==17022== LL refs: 67,112,602 ( 3,193 rd + 67,109,409 wr)
==17022== LL misses: 67,112,212 ( 2,838 rd + 67,109,374 wr)
==17022== LL miss rate: 20.0% ( 0.0% + 100.0% )
我们可以看到，线性地访问内存显著地减少了 cache misses。
==17023== Command: ./matrix_init_linear
==17023==
--17023-- warning: L3 cache found, using its data for the LL simulation.
==17023==
==17023== I refs: 336,117,093
==17023== I1 misses: 813
==17023== LLi misses: 808
==17023== I1 miss rate: 0.00%
==17023== LLi miss rate: 0.00%
==17023==
==17023== D refs: 67,163,675 (40,970 rd + 67,122,705 wr)
==17023== D1 misses: 16,780,146 ( 2,384 rd + 16,777,762 wr)
==17023== LLd misses: 16,779,760 ( 2,033 rd + 16,777,727 wr)
==17023== D1 miss rate: 25.0% ( 5.8% + 25.0% )
==17023== LLd miss rate: 25.0% ( 5.0% + 25.0% )
==17023==
==17023== LL refs: 16,780,959 ( 3,197 rd + 16,777,762 wr)
==17023== LL misses: 16,780,568 ( 2,841 rd + 16,777,727 wr)
==17023== LL miss rate: 4.2% ( 0.0% + 25.0% )
■Question 334 查看 GCC 的 man page 的 optimizations 小节。