HackMD
2016q3 Homework 1 (phonebook)
tags: sysprog21 JongSyuGithub cache miss
contributed by <JonSyuGithub>
github: https://gtihub.com/JonSyuGithub/phonebook
contributed by <JonSyuGithub>
請依照指定格式填寫標題和"contributed by" 課程助教
已更正 JonSyuGithub
Environment
-
OS: Ubuntu 16.04 LTS
-
CPU: i5-457
- Cache ($ lscpu | grep cache)
- L1d cache: 32K
- L1i cache: 32K
- L2 cache: 256K
- L3 cache: 6144K
- Cache ($ lscpu | grep cache)
-
Memory 12GB ($ cat /proc/meminfo)
-
Update & Install
$ sudo apt-get update
$ sudo apt-get install build-essential
$ sudo apt-get install linux-tools-common linux-tools-generic
$ sudo apt-get install astyle colordiff gnuplot
- Github
$ git clone https://github.com/JonSyuGithub/phonebook
# setting parameter
$ git config --global user.email "your e-mail"
$ git config --global user.name "your name"
$ git config --global push.default matching
$ git remote set-url origin https://github.com/github/phonebook.git
# update
$ git add .
$ git commit -m "modify XXX"
$ git push
Objective
- try reducing cache miss
Original Version
- Compile & Run
$ make
$ make run
$ make plot
$ perf stat -r 10 -e cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-store-misses,L1-dcache-prefetch-misses,L1-icache-load-misses ./phonebook_opt
$ perf record -F 12500 -e cache-misses ./phonebook_opt && perf report
Optimal Version
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
struct __DETAIL_ENTRY *detail;
struct __PHONE_BOOK_ENTRY *pNext;
} entry;
typedef struct __DETAIL_ENTRY {
char firstName[16];
char email[16];
char phone[10];
char cell[10];
char addr1[16];
char addr2[16];
char city[16];
char state[2];
char zip[5];
} detailEntry;
Result
Performance counter stats for './phonebook_orig' (100 runs):
120,6974 cache-misses # 84.776 % of all cache refs ( +- 0.36% )
142,3717 cache-references ( +- 0.22% )
2,6074,1438 instructions # 1.30 insns per cycle ( +- 0.02% )
2,0000,1906 cycles ( +- 0.17% )
0.057552514 seconds time elapsed ( +- 0.21% )
Performance counter stats for './phonebook_opt' (100 runs):
17,3636 cache-misses # 40.996 % of all cache refs ( +- 0.74% )
42,3539 cache-references ( +- 0.40% )
2,4388,0125 instructions # 1.93 insns per cycle ( +- 0.02% )
1,2660,9129 cycles ( +- 0.23% )
0.036543171 seconds time elapsed ( +- 0.28% )
- optimized
- 由於__PHONE_BOOK_ENTRY的detail改成由指標指向__DETAIL_ENTRY，因而cache Miss從84.776%減至40.996%
- append()並未將__DETAIL_ENTRY進行malloc，因此cache miss大幅降低極為合理
- append()若將__DETAIL_ENTRY進行malloc
- optimized的cache miss反而會高於original
- strcasecmp()所佔的cache miss之overhead會較高
- findName()所佔的cache miss之overhead會較低
- optimized的cache miss反而會高於original
