性能優(yōu)化篇（1）：幾種簡單的訪存優(yōu)化手段
Author:stormQ
Sunday, 10. November 2019 11:36AM
-
目錄
減少不必要的內(nèi)存引用
按順序訪問數(shù)據(jù)
按順序存儲同時要訪問的數(shù)據(jù)
減少不必要的內(nèi)存引用
示例：
void poor(const int *src, int n, int *dest)
{
for (int i = 0; i < n; ++i)
{
*dest += src[i];
}
}
void better(const int *src, int n, int *dest)
{
int sum = *dest;
for (int i = 0; i < n; ++i)
{
sum += src[i];
}
*dest = sum;
}
執(zhí)行時間統(tǒng)計：
| 啟動程序方式 | 第一次執(zhí)行耗時(us) | 第二次執(zhí)行耗時(us) | 第三次執(zhí)行耗時(us) | 第四次執(zhí)行耗時(us) | 第五次執(zhí)行耗時(us) |
|---|---|---|---|---|---|
| ./main_Og | <li>poor:176463</li> <li>better:67489</li> | <li>poor:172714</li> <li>better:69189</li> | <li>poor:170618</li> <li>better:67232</li> | <li>poor:176130</li> <li>better:68082</li> | <li>poor:170447</li> <li>better:69484</li> |
| valgrind --tool=cachegrind ./main_Og | <li>poor:2403126</li> <li>better:1540885</li> | <li>poor:2401457</li> <li>better:1543162</li> | <li>poor:2404605</li> <li>better:1541964</li> | <li>poor:2410699</li> <li>better:1546153</li> | <li>poor:2409636</li> <li>better:1543493</li> |
從統(tǒng)計結(jié)果中可以看出，better() 函數(shù)的執(zhí)行速度比 poor() 函數(shù)快 2.5 倍左右。
從匯編的角度分析：
; With -Og optimization
; Dump of assembler code for function poor(int const*, int, int*):
0x000000000040080c <+0>: mov w3, #0x0 // #0
0x0000000000400810 <+4>: cmp w3, w1
0x0000000000400814 <+8>: b.ge 0x400830 <poor(int const*, int, int*)+36>
0x0000000000400818 <+12>: ldr w5, [x2]
0x000000000040081c <+16>: ldr w4, [x0,w3,sxtw #2]
0x0000000000400820 <+20>: add w4, w5, w4
0x0000000000400824 <+24>: str w4, [x2]
0x0000000000400828 <+28>: add w3, w3, #0x1
0x000000000040082c <+32>: b 0x400810 <poor(int const*, int, int*)+4>
0x0000000000400830 <+36>: ret
; With -Og optimization
; Dump of assembler code for function better(int const*, int, int*):
0x0000000000400834 <+0>: ldr w4, [x2]
0x0000000000400838 <+4>: mov w3, #0x0 // #0
0x000000000040083c <+8>: cmp w3, w1
0x0000000000400840 <+12>: b.ge 0x400854 <better(int const*, int, int*)+32>
0x0000000000400844 <+16>: ldr w5, [x0,w3,sxtw #2]
0x0000000000400848 <+20>: add w4, w4, w5
0x000000000040084c <+24>: add w3, w3, #0x1
0x0000000000400850 <+28>: b 0x40083c <better(int const*, int, int*)+8>
0x0000000000400854 <+32>: str w4, [x2]
0x0000000000400858 <+36>: ret
從匯編代碼中可以看出：
使用
-Og優(yōu)化選項編譯時，poor() 函數(shù)的 for 循環(huán)的一次迭代中：讀內(nèi)存操作數(shù)量為2，寫內(nèi)存操作數(shù)量為1。使用
-Og優(yōu)化選項編譯時，better() 函數(shù)的 for 循環(huán)的一次迭代中：讀內(nèi)存操作數(shù)量為1，寫內(nèi)存操作數(shù)量為0。better() 函數(shù)的內(nèi)存讀寫數(shù)量較少，因此執(zhí)行速度更快。
從 cache 性能的角度分析：
--------------------------------------------------------------------------------
I1 cache: 16384 B, 64 B, 4-way associative
D1 cache: 16384 B, 64 B, 4-way associative
LL cache: 262144 B, 64 B, 8-way associative
Command: ./b_Og
Data file: cachegrind.out.18226
Events recorded: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Events shown: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Event sort order: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Thresholds: 0.1 100 100 100 100 100 100 100 100
Include dirs:
User annotated:
Auto-annotation: off
--------------------------------------------------------------------------------
Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
--------------------------------------------------------------------------------
1,993,889,018 1,004 864 315,036,517 13,121,792 13,115,591 209,899,117 6,555,946 6,555,006 PROGRAM TOTALS
--------------------------------------------------------------------------------
Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw file:function
--------------------------------------------------------------------------------
838,860,804 0 0 209,715,200 6,553,601 6,553,601 104,857,600 0 0 /home/b.cpp:poor(int const*, int, int*)
629,145,606 0 0 104,857,601 6,553,601 6,553,601 1 1 1 /home/b.cpp:better(int const*, int, int*)
524,288,004 1 1 0 0 0 104,857,600 6,553,600 6,553,600 /home/b.cpp:init(int*, int)
輸出結(jié)果解析：
poor() 函數(shù)的讀內(nèi)存操作的數(shù)量為 209,715,200（Dr 列），讀內(nèi)存操作在 L1 級緩存中不命中的數(shù)量為 6,553,601（D1mr 列），讀內(nèi)存操作在 LL 級緩存（最后一級緩存）中不命中的數(shù)量為 6,553,601（DLmr 列）。
poor() 函數(shù)的寫內(nèi)存操作的數(shù)量為 104,857,600（Dw 列），寫內(nèi)存操作在 L1 級緩存中不命中的數(shù)量為 0（D1mw 列），寫內(nèi)存操作在 LL 級緩存（最后一級緩存）中不命中的數(shù)量為 0（DLmw 列）。
better() 函數(shù)的讀內(nèi)存操作的數(shù)量為 104,857,601（Dr 列），讀內(nèi)存操作在 L1 級緩存中不命中的數(shù)量為 6,553,601（D1mr 列），讀內(nèi)存操作在 LL 級緩存（最后一級緩存）中不命中的數(shù)量為 6,553,601（DLmr 列）。
better() 函數(shù)的寫內(nèi)存操作的數(shù)量為 1（Dw 列），寫內(nèi)存操作在 L1 級緩存中不命中的數(shù)量為 1（D1mw 列），寫內(nèi)存操作在 LL 級緩存（最后一級緩存）中不命中的數(shù)量為 1（DLmw 列）。
從上述數(shù)據(jù)中可以看出：1）poor() 函數(shù)的讀內(nèi)存操作的數(shù)量為 better() 函數(shù)的兩倍；2）poor() 函數(shù)的寫內(nèi)存操作的數(shù)量比 better() 函數(shù)多 104,857,599（104,857,599 = 104,857,600 - 1）。這也驗證了better() 函數(shù)執(zhí)行速度較快的原因。
按順序存儲同時要訪問的數(shù)據(jù)
示例：
void poor(const int *src, int *dest, int n)
{
for (int i = 0; i < n; ++i)
{
// 同時要訪問的數(shù)據(jù)（src[i]、dest[i]）在兩個數(shù)組中，即同時要訪問的數(shù)據(jù)不是連續(xù)存儲的
dest[i] = src[i];
}
}
struct Vec2
{
Vec2()
{
static long long count = 0;
a = count++;
}
int a;
int b;
};
void better(struct Vec2 *data, int n)
{
for (int i = 0; i < n; ++i)
{
// 同時要訪問的數(shù)據(jù)（data[i].a、data[i].b）存儲在同一個結(jié)構(gòu)體中，即同時要訪問的數(shù)據(jù)是連續(xù)存儲的
data[i].b = data[i].a;
}
}
執(zhí)行時間統(tǒng)計：
| 啟動程序方式 | 第一次執(zhí)行耗時(us) | 第二次執(zhí)行耗時(us) | 第三次執(zhí)行耗時(us) | 第四次執(zhí)行耗時(us) | 第五次執(zhí)行耗時(us) |
|---|---|---|---|---|---|
| ./main_Og | <li>poor:8591</li> <li>better:2714</li> | <li>poor:4657</li> <li>better:1936</li> | <li>poor:7424</li> <li>better:3436</li> | <li>poor:8976</li> <li>better:1937</li> | <li>poor:4866</li> <li>better:1931</li> |
| valgrind --tool=cachegrind ./main_Og | <li>poor:60573</li> <li>better:52037</li> | <li>poor:59379</li> <li>better:51119</li> | <li>poor:60963</li> <li>better:51360</li> | <li>poor:59742</li> <li>better:51622</li> | <li>poor:64674</li> <li>better:52330</li> |
從統(tǒng)計結(jié)果中可以看出，better() 函數(shù)的執(zhí)行速度比 poor() 函數(shù)快 2 倍左右。
統(tǒng)計 cache 使用情況：
--------------------------------------------------------------------------------
Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
. . . . . . . . . void poor(const int *src, int *dest, int n)
. . . . . . . . . {
8,294,404 0 0 1 1 1 0 0 0 for (int i = 0; i < n; ++i)
. . . . . . . . . {
6,220,800 0 0 2,073,600 129,601 129,601 2,073,600 129,601 129,601 dest[i] = src[i];
. . . . . . . . . }
. . . . . . . . . }
. . . . . . . . .
. . . . . . . . . struct Vec2
. . . . . . . . . {
. . . . . . . . . Vec2()
. . . . . . . . . {
. . . . . . . . . static long long count = 0;
8,294,400 0 0 2,073,600 1 1 4,147,200 259,200 259,200 a = count++;
. . . . . . . . . }
. . . . . . . . . int a;
. . . . . . . . . int b;
. . . . . . . . . };
. . . . . . . . .
. . . . . . . . . void better(struct Vec2 *data, int n)
. . . . . . . . . {
8,294,404 0 0 1 1 1 0 0 0 for (int i = 0; i < n; ++i)
. . . . . . . . . {
8,294,400 0 0 2,073,600 259,201 259,201 2,073,600 0 0 data[i].b = data[i].a;
. . . . . . . . . }
. . . . . . . . . }
輸出結(jié)果解析：
poor() 和 better() 函數(shù)的內(nèi)存讀操作的數(shù)量是相同的，而 better() 函數(shù)的 D1mr、DLmr 比 poor() 函數(shù)分別多 129600 次、129600 次。
poor() 和 better() 函數(shù)的內(nèi)存寫操作的數(shù)量是相同的，而 poor() 函數(shù)的 D1mw、DLmw 比 better() 函數(shù)分別多 129601 次、129601 次。
從內(nèi)存讀和寫操作的不命中總數(shù)量來看，兩者是相同的。但為什么 better() 函數(shù)的執(zhí)行速度比 poor() 函數(shù)快 2 倍？
按順序訪問數(shù)據(jù)
按數(shù)據(jù)在內(nèi)存中排列先后順序進(jìn)行訪問（讀或?qū)懀r，通常會降低 cache 的缺失率，即減少訪問內(nèi)存的次數(shù)，從而執(zhí)行速度更快。比如：C/C++ 中的多維數(shù)組是以行主序（存儲完一行后再存儲下一行）存儲在內(nèi)存中的，那么在循環(huán)中訪問完一行后再訪問下一行的方式更高效。Fortran 中的多維數(shù)組是以列主序（存儲完一列后再存儲下一列）存儲在內(nèi)存中的，那么在循環(huán)中訪問完一列后再訪問下一列的方式更高效。
示例：訪問二維整型數(shù)組
// 按列訪問數(shù)組元素
long long poor(const int *src, int rows, int cols)
{
long long sum = 0;
for (int i = 0; i < cols; ++i)
{
for (int j = 0; j < rows; ++j)
{
sum += *(src + j * cols + i);
}
}
return sum;
}
// 按行訪問數(shù)組元素
long long better(const int *src, int rows, int cols)
{
long long sum = 0;
for (int i = 0; i < rows; ++i)
{
for (int j = 0; j < cols; ++j)
{
sum += *(src + i * cols + j);
}
}
return sum;
}
執(zhí)行時間統(tǒng)計：
| 啟動程序方式 | 第一次執(zhí)行耗時(us) | 第二次執(zhí)行耗時(us) | 第三次執(zhí)行耗時(us) | 第四次執(zhí)行耗時(us) | 第五次執(zhí)行耗時(us) |
|---|---|---|---|---|---|
| ./main_Og | <li>poor:12575</li> <li>better:2479</li> | <li>poor:12661</li> <li>better:2240</li> | <li>poor:12687</li> <li>better:2313</li> | <li>poor:12387</li> <li>better:2241</li> | <li>poor:12493</li> <li>better:2230</li> |
| valgrind --tool=cachegrind ./main_Og | <li>poor:101736</li> <li>better:54882</li> | <li>poor:99056</li> <li>better:56708</li> | <li>poor:96098</li> <li>better:57031</li> | <li>poor:97853</li> <li>better:57691</li> | <li>poor:95651</li> <li>better:57502</li> |
從統(tǒng)計結(jié)果中可以看出，better() 函數(shù)的執(zhí)行速度比 poor() 函數(shù)快 5 倍左右。
統(tǒng)計 cache 使用情況：
--------------------------------------------------------------------------------
Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
. . . . . . . . . long long poor(const int *src, int rows, int cols)
. . . . . . . . . {
2 0 0 0 0 0 0 0 0 long long sum = 0;
4,323 0 0 0 0 0 0 0 0 for (int i = 0; i < cols; ++i)
. . . . . . . . . {
8,296,560 1 1 0 0 0 0 0 0 for (int j = 0; j < rows; ++j)
. . . . . . . . . {
14,515,200 0 0 2,073,600 2,073,600 76,630 0 0 0 sum += *(src + j * cols + i);
. . . . . . . . . }
. . . . . . . . . }
. . . . . . . . . return sum;
1 0 0 1 1 1 0 0 0 }
. . . . . . . . .
. . . . . . . . . long long better(const int *src, int rows, int cols)
. . . . . . . . . {
2 0 0 0 0 0 0 0 0 long long sum = 0;
7,683 0 0 0 0 0 0 0 0 for (int i = 0; i < rows; ++i)
. . . . . . . . . {
8,298,240 0 0 0 0 0 0 0 0 for (int j = 0; j < cols; ++j)
. . . . . . . . . {
14,515,200 0 0 2,073,600 129,601 74,916 0 0 0 sum += *(src + i * cols + j);
. . . . . . . . . }
. . . . . . . . . }
. . . . . . . . . return sum;
1 0 0 1 1 1 0 0 0 }
輸出結(jié)果解析：
poor() 和 better() 函數(shù)的讀內(nèi)存操作的數(shù)量是相同的。
poor() 和 better() 函數(shù)在 L1 級緩存的讀數(shù)據(jù)操作不命中數(shù)量差距很大，前者的讀數(shù)據(jù)操作不命中數(shù)量為后者的 16 倍。這正是 better() 函數(shù)執(zhí)行速度快于 poor() 函數(shù)的原因。
