HackMD
2017q1 Homework1 (phonebook)
contributed by <Sean1127>
Reviewed by chenweiii
- 可以嘗試看看每個 hash table row 擁有自己的 memory pool，如此在搜尋該 row 的其他 entries 時可發揮到空間的 locality，在我的電腦實驗中，cache misses 可下降約 10%，效果還不錯。
- git commit message fc4529f:
Clone "phonebook", attempt no.1 to lower cache miss rate- 建議直接將修改的主旨寫在標題，而不是藏在接下來的內容。
Redesign a smaller phone book entry structure
記得列出硬體相關資訊，如：cache, memory
課程助教已補上Sean1127
Prologue
我是抱著當砲灰的心態來上這堂課
老實說我上大學之後一直很混，大一的程式都麻最後兩三天才寫，數學物理不是蹺課就是睡覺，線代還被當
大二的時候上了資安要寫Java，資料結構要寫C/C++，才忽然意識到我連最基本的東西都要回去查，我的程度根本就跟一個剛進資訊系的大一一樣
但我的努力也就是跟上課程的進度而已，大二到大三上的程式課並不多，相反的數學課倒是頗多（離散、機率、演算法）
雖然說是比之前好，但認真講，就從'爛'進步到'普通'而已
等到三下也就是現在，畢業倒數的時刻，又是一個檢視自己的機會，就說我太容易滿足，覺得之前那樣就夠了，但好像不是這麼一回事XD
反正我是知道現在才開始學已經太晚了，也知道我這學期一定會爆炸
可是俗話說： Better late than never.
第一次用不是 VM 裝 linux，第一次注意程式的效能（之前只要跑出正確的結果就感謝上蒼了），第一次用 HackMD，第一次認真學 Git…
Well, here I am. 如果有其他像我一樣經歷的人，我想我這種廢咖的程度都能來這兒，你們這些不比我差的傢伙憑什麼不行？
Schedule
- 2/21:
-
install ubuntu 16.04 with 輕鬆學會 Windows / Ubuntu 雙系統安裝
-
install ibus-chewing with 如何在 Ubuntu 16.04 上使用預設的 ibus 中文輸入法，但不知道為什麼多了一個 bopomofo，而且還刪不掉
Image Not Showing Possible Reasons- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
-
set vim environment with 終端機，Vim 設定
-
- 2/22:
- learn git with Learn Git Branching
- read course material
- 2/23:
- learn gnuplot with gnuplot 語法解說和示範
- read course material
- 2/24:
- learn Perf with Linux 效能分析工具: Perf
- read homework document
- 2/25:
- test 1 & 2
Requirement
- cache miss 降低
- findName() 的時間必須原本的時間更短
- 回答以下問題：本例選用的 dataset (也就是輸入電話簿的姓名) 是否存在問題？
- 有代表性嗎？跟真實英文姓氏差異大嗎？
- 資料難道「數大就是美」嗎？
- 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
Computer Info
CPU:
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 69
Model name: Intel(R) Core(TM) i5-4210U CPU @ 1.70GHz
Stepping: 1
CPU MHz: 1678.710
CPU max MHz: 2700.0000
CPU min MHz: 800.0000
BogoMIPS: 4789.04
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 3072K
NUMA node0 CPU(s): 0-3
Kernel:
$ uname -a
Linux sean 4.8.0-39-generic #42~16.04.1-Ubuntu SMP Mon Feb 20 15:06:07 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux
Preperation
Perf
- 重點整理：
- 多次使用 perf record 會產生 perf.data, perf.data.old 等等，注意清除舊的
- perf 監測 CPU 時需要開啟 kernel pointer 權限（預設為3，需要設為0），有時重開機之後會變回3，這時要再手動改回來
- 要用
$ perf record須開啟 kernel address map$ sudo sh -c " echo 0 > /proc/sys/kernel/kptr_restrict" - 要用
$ perf stat須開啟$ sudo sh -c " echo 0 > /proc/sys/kernel/perf_event_paranoid" - record 之前記得清空 cache!!!（設定在 Makefile 內較方便）
$ echo 3 | sudo tee /proc/sys/vm/drop_caches
這邊數字代表的意義 1, 2, 3 有所不同，之後會補上資料
老師用的是 $ echo 1 | sudo tee /proc/sys/vm/drop_caches
- 不知道為什麼輸入
$ ./phonebook_orig & sudo perf top -p $!會跑出
┌─Error:─────────────────────────────────────────┐
│Couldn't create thread/CPU maps: No such process│
│ │
│ │
│Press any key... │
└────────────────────────────────────────────────┘
所以我一律用
$ perf record -e cache-misses,cache-references,instructions,cycles ./phonebook_orig
$ perf report
或是 $ make cache-test
gnuplot
- 重點整理
$ eog [圖檔名]$ make plotcalculate.c main.c需要修正
看了影片和 document 後，還是不太了解 $0 和 3:xtic(1) 的意義，目前先照範例依樣畫葫蘆，之後再研究
Makefile
Test Area
- 先重現其他人的實驗結果，此處參考 dada, rnic, Yuron, ktvexe and Programming Small
- 幾個較明顯的改善方法
- 縮小資料結構：entry size 變小之後，相對的 cache 內可放入的 entry 增加，cache hit 的機率也增加
- 新增 hash function：目的在於加速 findName() 的速度，append() 速度可能會稍微受損，但與 1. 結合後的速度仍比 orig 來的快
- 壓縮字串：間接縮小了 entry size，與 1. 同理
- 建立 memory pool，減少 append() malloc 時間
- 建立 search tree，但有因有 0140454 的前車之鑑，時間不減反增，這邊可能要再多想一下
Original
Performance counter stats for './phonebook_orig' (100 runs):
1,216,932 cache-misses # 91.071 % of all cache refs ( +- 0.26% )
1,336,239 cache-references ( +- 0.21% )
262,822,206 instructions # 1.45 insn per cycle ( +- 0.02% )
181,112,861 cycles ( +- 0.10% )
0.070162363 seconds time elapsed ( +- 0.17% )
Test 1: smaller entry size
- 在 findName() 與 append() 中都只用到了 lastname 這個member，但又要符合原本的功能，所以不考慮直接註解其他member
- 參考 dada 另外設計一個 structure 只存 lastName，並加一個 pointer 指到原本的完整資料
- 另外 pFull 沒有 malloc 空間，等以後需要其他功能時再調整
typedef struct __PHONE_BOOK_LASTNAME {
char lastName[MAX_LAST_NAME_SIZE];
struct __PHONE_BOOK_ENTRY *pFull;
struct __PHONE_BOOK_LASTNAME *pNext;
} entry;
-
結果：
Performance counter stats for './phonebook_opt' (100 runs): 106,448 cache-misses # 25.202 % of all cache refs ( +- 0.43% ) 422,371 cache-references ( +- 0.62% ) 244,884,604 instructions # 1.94 insn per cycle ( +- 0.02% ) 126,549,548 cycles ( +- 0.27% ) 0.049344870 seconds time elapsed ( +- 0.31% ) -
比較
- time: 0.070162363 -> 0.049344870
- cache-misses: 91.071 % -> 25.202 %
- 在兩個 function 裡面都用了新的 struct entry，若只改 findName() 不改 append()，這個設計就變得沒有意義，因為無法避免掉在 malloc 大量耗時與 cache 頻繁更新
如同參考文件寫的，append的時候還有malloc detailEntry的話，cache miss不降反生，從93.309%升到94.412 %，但是這裡可以看出來findName的cache miss比原先版本的下降，從10.3%到3.03%cheng hung lin
Test 1.1
我就不信邪，把 append() 跟 main 的 entry 寫回去看看會發生什麼事
entry *append(char lastName[], entry *e)
{
e->pNext = (entry *) malloc(sizeof(entry));
e = e->pNext;
strcpy(e->lastName, lastName);
e->pNext = NULL;
e->pFull = (full *) malloc(sizeof(full));
strcpy(e->pFull->lastName, lastName);
return e;
}
Performance counter stats for './phonebook_opt' (100 runs):
1,265,668 cache-misses # 91.709 % of all cache refs ( +- 0.34% )
1,380,095 cache-references ( +- 0.88% )
355,297,877 instructions # 1.26 insn per cycle ( +- 0.03% )
281,243,138 cycles ( +- 1.17% )
2,742,130 L1-dcache-load-misses ( +- 0.56% )
0.114042676 seconds time elapsed ( +- 2.23% )
- 時間變快了沒問題，但是 cache-misses 高達 91.709 %(orig: 91.071 %，還多了一丁點兒)
- 看來前人的錯還是不要再犯比較好…
- 另外補充
cache-misses跟L1-dcache-load-misses的差別
根據PERF_EVENT_OPEN ：Cache misses. Usually this indicates Last Level Cache misses，在perf中cache miss指的是在任何階層的cache都找不到資料，所以要從memory載入資料至cache這種情況發生的event
L1-dcache-load-miss基本上就是字面的意思Yuron
果然還是學長眼尖啊，但在這種定義下，我們要看的應該是L1-dcache-load-miss
Test 2: hash function
- 參考 案例分析：phonebook, Yuron 與 nekoneko 的研究(主要是 nekoneko，等於複習了一整堂資結)
- hash 三大重點（引用 Yuron）
- table size
- function
- overflow handle
- 白話來說，hash 希望建立一個一一對應的函數關係，但那是只最完美的狀態。一般來說還是會有有兩個值 map 到同一個 set 的情況，這時就用 link list 把它們連接
- 設 hash function distribution = uniform
- slot = 8
- object = list length = 64
- new list length = 64 / 8 = 8
- 也就代表 new list 上面的 operation 會加速 8 倍
- hash 效果如此強大，重點也就變成如何產生 uniform hash 連結裡面簡單介紹了 3 個方法，我就先借 djb2 用用
- hash 為何要乘上一個大的質數在 Programming Small 最後有提到
- 實做部份參考 ktvexe/phonebook-1 寫法，main 用最笨的方法寫
int main()
{
#if defined(HASH)
...
#else
...
#endif
}
等於是複製一份 main 來改，但我就是笨，之後有空再回來改吧（這種寫法比較好 debug，照 ktvexe 的方法我大概會直接昏倒）
-
結果
Performance counter stats for './phonebook_hash' (100 runs): 100,791 cache-misses # 23.689 % of all cache refs ( +- 2.22% ) 425,469 cache-references ( +- 0.97% ) 239,077,278 instructions # 1.70 insn per cycle ( +- 0.02% ) 140,451,230 cycles ( +- 0.67% ) 1,114,672 L1-dcache-load-misses ( +- 0.35% ) 0.057939853 seconds time elapsed ( +- 1.61% )cache-misses比先前的 25.202 % 又進步了- 但時間上變得很慘，有圖有真相
- 問題來了，我修改了
main之後，好像把 original 的部份弄壞啦… - 但就算如此，hash 的表現無論是跟 original's original: 0.089145 或是 new original: 0.054776 比，都來的快
目前先這樣，這部份要念的話念不完啊Sean1127
Test 3: fix test 1 & 2
- orig 的數據跑掉之後，我用 git 回朔到先前的版本重新測試，發現 orig 還是維持 0.5 ~ 0.6，比一開始測試的 0.8 ~ 1.0 還快的多
- 進到 Makefile 看就發現
run: $(EXEC)
echo 3 | sudo tee /proc/sys/vm/drop_caches
watch -d -t "./phonebook_orig && echo 3 | sudo tee /proc/sys/vm/drop_caches"
cache-test: $(EXEC)
perf stat --repeat 100 \
-e cache-misses,cache-references,instructions,cycles \
./phonebook_orig
perf stat --repeat 100 \
-e cache-misses,cache-references,instructions,cycles \
./phonebook_opt
output.txt: cache-test calculate
./calculate
plot: output.txt
gnuplot scripts/runtime.gp
- 若用
$ make run則會每次清除 cache，出現的數據也較接近原始數據 - 用
$ make cache-test之前必須手動清除 cache，且在第一次之後的執行都是沿用之前的 cache - 再打開
orig.txt觀察就很容易發現規律
append() findName() 0.062958 0.005667
append() findName() 0.048825 0.005518
append() findName() 0.049174 0.005507
append() findName() 0.047186 0.005497
append() findName() 0.047982 0.005529
append() findName() 0.048004 0.005543
append() findName() 0.047304 0.005514
...
- 第一比資料花的時間特別久，之後 orig 都跟 opt 版本差不多快了
- 同理可證，opt 的資料也同樣有測不準的情況
如何解決？
- 簡單看兩個例子
$ echo 3 | sudo tee /proc/sys/vm/drop_caches
3
$ perf stat -e cache-misses,cache-references,instructions,cycles ./phonebook_orig
size of entry : 136 bytes
execution time of append() : 0.181801 sec
execution time of findName() : 0.006251 sec
Performance counter stats for './phonebook_orig':
62,4197 cache-misses # 85.606 % of all cache refs
72,9147 cache-references
2,6558,1572 instructions # 1.52 insn per cycle
1,7416,1931 cycles
0.264308628 seconds time elapsed
$
$
$
$ perf stat -e cache-misses,cache-references,instructions,cycles ./phonebook_orig
size of entry : 136 bytes
execution time of append() : 0.050006 sec
execution time of findName() : 0.005566 sec
Performance counter stats for './phonebook_orig':
124,7285 cache-misses # 90.716 % of all cache refs
137,4933 cache-references
2,6357,6114 instructions # 1.48 insn per cycle
1,7750,6742 cycles
0.071150082 seconds time elapsed
- 第二次執行的時間誤差非常大(0.264 -> 0.071，將近 1/4 倍)，但 cache 的表現差不多，再測試
phonebook_opt也是一樣的規律 - 比對熱點
Samples: 307 of event 'cycles', Event count (approx.): 182165922
Overhead Command Shared Object Symbol
17.62% phonebook_orig phonebook_orig [.] main
14.81% phonebook_orig libc-2.23.so [.] __strcasecmp_l_avx
11.53% phonebook_orig phonebook_orig [.] findName
9.10% phonebook_orig libc-2.23.so [.] _int_malloc
6.96% phonebook_orig libc-2.23.so [.] _IO_fgets
5.41% phonebook_orig libc-2.23.so [.] __memcpy_sse2
3.47% phonebook_orig phonebook_orig [.] append
Samples: 327 of event 'cycles', Event count (approx.): 186019183
Overhead Command Shared Object Symbol
13.79% phonebook_orig libc-2.23.so [.] __strcasecmp_l_avx
12.01% phonebook_orig phonebook_orig [.] findName
11.57% phonebook_orig libc-2.23.so [.] _int_malloc
10.02% phonebook_orig phonebook_orig [.] main
7.16% phonebook_orig libc-2.23.so [.] _IO_fgets
4.95% phonebook_orig libc-2.23.so [.] __memcpy_sse2
4.94% phonebook_orig libc-2.23.so [.] _IO_getline_info
3.57% phonebook_orig [kernel.kallsyms] [k] clear_page_c_e
3.29% phonebook_orig [kernel.kallsyms] [k] page_fault
3.26% phonebook_orig libc-2.23.so [.] __strcpy_sse2_unaligne
3.12% phonebook_orig phonebook_orig [.] append
| function | cycles (cache cleared) | cycles (not cleared) |
|---|---|---|
| main | 32097635 | 18639122 |
| findName | 21003730 | 22361366 |
| append | 6321157 | 5803798 |
Linux 的記憶體快取（Cache Memory）功能：Linux 系統把記憶體用光了？
要釋放 Linux 的記憶體快取，可以透過更改 /proc/sys/vm/drop_caches 這個檔案的內容來達到，當這個檔案內容被設為 1 時，是表示要求 Linux 釋放沒在使用的一般性快取（pagecache），而設為 2 時，則代表要求釋放 dentry 與 inode 所使用到的快取，若設為 3 則是釋放所有的快取（也就是包含 1 與 2 的狀況）。
- 目前還沒查到如何在
$ perf stat --repeat觀測時每一次都預先清除 cache - 兩種方法出現的時間誤差是來自 main，因為 main 當然也是會被放在 cache 裡面的，就算不是在 L1-dcache，也可能是在 L2, L3，比起重頭到 memory 拿一定還是來的快
findName,append沒有太大影響，所以無論有無清除 cache，都不會改變不同演算法的排序
| speed | cache cleared | not cleared |
|---|---|---|
| method | orig < hash < opt | orig < hash < opt |
Test 4: memory pool
-
好…其實上個實驗只是因為我眼殘搞錯
對那麼多的資料來說，有時候跑出來的結果根本不是我要的，就好像方程式等號兩邊的單位不一樣，也就沒有意義
雖然可參考 louielu 對於 perf event 的整理，但我真的只看懂 30 % 左右而已…
總而言之，output.txt裡面的數據是根據同一個基準點去測的，所以畫出來的圖應該是沒問題 -
下一個目標是用 mem pool
因為append的呼叫次數很高，裡面 malloc 的成本也就被放很大，如果可以在main就預備一塊夠大的空間，希望可以:append的成本移動到main之中，成本還是在但是轉移了- 呼叫 100 一次，跟呼叫 1 一百次，後者的呼叫成本比較高，因為函式會有 push, pop 等額外作業
- 善用 cache 空間集中性，因為 link listed 的各個節點在記憶體上是非連續的，用 memory pool 應可以把節點跟節點間的地址拉近
-
L1 cache 可放入的 entry number = 32KB / 32 B = 1024 個
/* build the entry */
entry pHead[MAX_HASH_TABLE_SIZE], *e[MAX_HASH_TABLE_SIZE];
printf("size of entry : %lu bytes\n", sizeof(entry));
for (i = 0; i < MAX_HASH_TABLE_SIZE; ++i) {
e[i] = &pHead[i];
e[i]->pNext = NULL;
}
- 我的
MAX_HASH_TABLE_SIZE剛好也設1024，代表 cache 裡面剛好可以完全放進我的 table，所以查表非常快 - 而
pHead是用矩陣宣告，所以也保持了 locality，這算是參考學長誤打誤撞的一次小成功… - 程式碼參考 Implement own memory pool
- 結果
Performance counter stats for './phonebook_hash' (100 runs):
90,706 cache-misses # 40.360 % of all cache refs ( +- 3.77% )
224,744 cache-references ( +- 3.85% )
167,708,391 instructions # 1.49 insn per cycle ( +- 0.05% )
112,453,444 cycles ( +- 1.44% )
934,537 L1-dcache-load-misses ( +- 0.64% )
cache-misses比率變高( 23 % -> 40 %)，但總數是變低的！(misses: 100,791 -> 90,706)(references: : 425,469 -> 224,744)
（太好了沒有比較久）
因為更加集中了記憶體位置，連帶findName()也變快了一點點
Test 5: 用字典詞彙
根據 stack overflow 上的回答，可以用 SCOWL (And Friends) 列出字典裡約 675k 個字（有分大小寫），這些字包含地名、人名、與其他有意義的詞彙
- 注意！需要修正
main.c 的總記憶體量（超過350k）、搜尋字等等 - 結果
Performance counter stats for './phonebook_pool' (100 runs):
196,072 cache-misses # 38.689 % of all cache refs ( +- 4.77% )
506,785 cache-references ( +- 5.17% )
344,977,883 instructions # 1.43 insn per cycle ( +- 0.03% )
240,840,199 cycles ( +- 1.81% )
0.108246834 seconds time elapsed ( +- 2.80% )
- 總時間比較長，
$ make plot需要耐心等候 - 以比較有代表性的輸入檔，hash 反而表現更差了，
clock_gettime(CLOCK_REALTIME, &start);
while (fgets(line, sizeof(line), fp)) {
while (line[i] != '\0')
i++;
line[i - 1] = '\0';
#if defined(HASH)
key = djb2(line) % MAX_HASH_TABLE_SIZE;
e[key] = append(line, e[key]);
#elif defined(POOL)
key = djb2(line) % MAX_HASH_TABLE_SIZE;
e[key] = append(line, e[key], p);
#else
e = append(line, e);
#endif
i = 0;
}
clock_gettime(CLOCK_REALTIME, &end);
- 猜測原因出在
hash比原本的多了djb2轉換，且還有malloc memory pool雖然也有djb2，但省了malloc時間- perf report:
Samples: 453 of event 'cycles', Event count (approx.): 285436920
Overhead Command Shared Object Symbol
28.23% phonebook_hash phonebook_hash [.] main
16.84% phonebook_hash phonebook_hash [.] djb2
9.17% phonebook_hash libc-2.23.so [.] _int_malloc
8.12% phonebook_hash libc-2.23.so [.] _IO_fgets
6.79% phonebook_hash libc-2.23.so [.] _IO_getline_info
6.73% phonebook_hash libc-2.23.so [.] __strcpy_sse2_unaligned
4.54% phonebook_hash libc-2.23.so [.] __memcpy_sse2
3.38% phonebook_hash libc-2.23.so [.] malloc
2.93% phonebook_hash phonebook_hash [.] append
- 更正
- 就算是用原本的
word.txt，hash的表現還是比struct差，上面 Test 4 的圖其實是奇蹟
- 照理說畫圖是執行 100 次之後的平均，應該不會出現極端值，看來我很幸運呢，但這也告訴我們實驗多做幾次，有時後得到的結果不一定是正確的！！！
- 就算是用原本的
- 比較
Test 4,Test 5發現其實名次是一樣的，只是時間都照比例放大了一點，所以就可以知道：字彙有無意義或是有沒有真實存在不會影響演算法 - 但順序還不一定，因為新的字典也是以 A-Z 排列好的
Conclusion
- Test 1 修改 struct: 成功
- Test 2 struct + djb2: 沒有比 Test 1 還好，失敗
- Test 3 了解問題: 成功
- Test 4 struct + djb2 + memory pool: 成功
其實不太知道這次作業要完成到什麼程度才算 ok，因為永遠都有改進的空間
但可以知道的是我的能力還很不足，連重複別人的實驗結果都要花上很久時間
如果沒有學長姐的筆記的話，下場一定很慘
往後的方向可以是：
- hash 調整
- 簡化
djb2()或是採用其他 hash function - 修改 hash 使用的位移常數
- 修改 hash table 大小
- 簡化
- 字串壓縮
- 搜尋樹（BST, 紅黑, balaned BST…）
- 打亂字典 input 順序（unsorted）
Answer the folloing questions
- cache miss 降低
miss:
percentage:
- findName() 的時間必須原本的時間更短
- 回答以下問題：本例選用的 dataset (也就是輸入電話簿的姓名) 是否存在問題？
-
有代表性嗎？跟真實英文姓氏差異大嗎？
word.txt裡面只有普通單字，沒有姓名，並且有一些甚至是無意義的字
但從實驗五的數據來看，目前的演算法並不會因為輸入的字是否是有意義、是否是姓名而改變時間 -
資料難道「數大就是美」嗎？
「數大就是美」對這次作業的意義與平常我們理解的不同，這裡要理解成：資料越多越好，而不是資料本身的值越大越好
而「好」的意思可能是有代表性，或是提供的資訊較多
要破除全稱命題只需要舉一個反例
例一：把word.txt第一個字複製 500,000 次，比 350,000 還多，卻沒有代表性，也沒有提供更多資訊 -
如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
可能需要使用爬蟲程式去網路抓資料，例如建立「台南美食店家」的電話簿，此外還需要做字串前處理，再放到 entry 中的各個欄位
-
進度請加速亮谷
