# 2017 Homework1 (phonebook) contributed by <`kairx772`> >中英文字間請記得以空白隔開! >[name= 課程助教][color=red] ### Reviewed by `jack81306` * 除了優化資料結構外,還有許多的優化方法可以使用,像是 hash function 或者是 search tree 等方法可以實作. * 能稍為的解釋一下為何更改 struct 結構可以優化時間. ## 開發環境 * OS： Linux Mint 18 Sarah * kernel: 4.4.0-21-generic ``` $ lscpu ``` ```shell 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: 37 Model name: Intel(R) Core(TM) i5 CPU M 540 @ 2.53GHz Stepping: 5 CPU MHz: 1199.000 CPU max MHz: 2534.0000 CPU min MHz: 1199.0000 BogoMIPS: 5053.55 Virtualization: VT-x L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 3072K NUMA node0 CPU(s): 0-3 ``` ``` $ lstopo ``` ![](https://i.imgur.com/J6IFczw.png) ## 練習使用perf 根據 [perf 原理和實務](https://hackmd.io/s/B11109rdg) 練習使用 perf 計算圓周率 編譯並執行 [perf_top_example.c] ```shell $ g++ -c perf_top_example.c $ g++ perf_top_example.o -o example $ ./example ``` perf stat ``` $ perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./example ``` 執行結果 ``` Performance counter stats for './example' (5 runs): 7,316 cache-misses # 22.737 % of all cache refs ( +- 4.05% ) 32,175 cache-references ( +- 1.94% ) 1,451,406,965 instructions # 0.66 insns per cycle ( +- 0.00% ) 2,203,744,568 cycles ( +- 0.01% ) 0.730500411 seconds time elapsed ( +- 0.11% ) ``` perf record & perf report ``` $ perf record -e branch-misses:u,branch-instructions:u ./example $ perf report ``` ``` 6 branch-misses:u 46.46% example libc-2.23.so [.] _dl_addr 42.63% example ld-2.23.so [.] _dl_relocate_object 10.53% example ld-2.23.so [.] _dl_sysdep_start 0.38% example ld-2.23.so [.] _dl_start 2K branch-instructions:u 99.99% example example [.] _Z19compute_pi_baselinem 0.01% example ld-2.23.so [.] check_match 0.00% example ld-2.23.so [.] _dl_cache_libcmp 0.00% example ld-2.23.so [.] _dl_start 0.00% example ld-2.23.so [.] _start ``` perf top ## phonebook 根據作業說明 ``` $ git clone https://github.com/sysprog21/phonebook/ $ cd phonebook $ make $ make run $ make plot $ eog runtime.png ``` 建立 gnulot 圖表 ![](https://i.imgur.com/YOcDYD4.png) 由於 findName 及 append 只用到 lastName,先把 lastName以外的欄位都註解掉,試試看能優化多少. 注意!要把 phonebook_opt.h 裡的 //#define OPT 1 註解拿掉才能跑 make plot 參考之前同學的[作業(louielu)](https://hackmd.io/s/BJjL6cQ6) ![](https://i.imgur.com/biKzAlR.png) cache-misses 也從 90% 降到77% ``` Performance counter stats for './phonebook_orig' (100 runs): 1,010,466 cache-misses # 90.800 % of all cache refs ( +- 0.11% ) 1,112,845 cache-references ( +- 0.53% ) 265,271,433 instructions # 0.88 insns per cycle ( +- 0.02% ) 300,794,810 cycles ( +- 0.45% ) 0.108809104 seconds time elapsed ( +- 0.59% ) ``` ``` Performance counter stats for './phonebook_opt' (100 runs): 236,047 cache-misses # 77.342 % of all cache refs ( +- 0.24% ) 305,200 cache-references ( +- 1.57% ) 244,877,042 instructions # 1.39 insns per cycle ( +- 0.02% ) 176,286,837 cycles ( +- 0.92% ) 0.066051719 seconds time elapsed ( +- 1.00% ) ``` ### 優化-改變資料結構 將lastName以外的資料都以另一個結構儲存 ```clike= typedef struct __PHONE_BOOK_DETAIL { char email[16]; char phone[10]; char cell[10]; char addr1[16]; char addr2[16]; char city[16]; char state[2]; char zip[5]; } detail; typedef struct __PHONE_BOOK_ENTRY { char lastName[MAX_LAST_NAME_SIZE]; detail *pInfo; struct __PHONE_BOOK_ENTRY *pNext; } entry; ``` ![](https://i.imgur.com/wKg2jpb.png) >> 進度嚴重落後，加緊趕工！ [name="jserv"] ## Git 點右上角fork鍵建立fork clone程式碼 ``` $ git clone https://github.com/kairx772/phonebook-1.git ``` 同步 ``` $ git push -u origin master ``` 更新檔案 ``` $ git add <file> ``` 提交 ``` $ git commit -m "commit message" ``` 上傳 ``` $ git push ``` ## 參考資料 複習c語言 [高等 C 語言](http://ccckmit.wikidot.com/cp:main) [語言技術：C 語言](https://openhome.cc/Gossip/CGossip/) 複習資料結構 [資料結構教學講義](http://www.tnu.edu.tw/ee/upimages/TA-Web/kenhuang/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E6%95%99%E5%AD%B8%E8%AC%9B%E7%BE%A9.htm) 學習makefile [Makefile教學](http://jayextmemo.blogspot.tw/2015/01/linux-gcc-makefile-2.html) [Makefile 語法簡介](http://tetralet.luna.com.tw/?op=ViewArticle&articleId=185) 共筆參考 [yenWu](https://hackmd.io/s/BkN1JNQp#降低-append-時間開銷：延後fgets完newline的替換--延後補上-detail) [hsuedw](https://embedded2016.hackpad.com/ep/profile/zyCLlsjr99A)