2017 Homework1 (phonebook)

contributed by <kairx772>

中英文字間請記得以空白隔開!
課程助教

Reviewed by jack81306

• 除了優化資料結構外,還有許多的優化方法可以使用,像是 hash function 或者是 search tree 等方法可以實作.
• 能稍為的解釋一下為何更改 struct 結構可以優化時間.

開發環境

• OS： Linux Mint 18 Sarah
• kernel: 4.4.0-21-generic

$ 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:                 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

練習使用perf

根據 perf 原理和實務 練習使用 perf
計算圓周率 編譯並執行 [perf_top_example.c]

$ 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 圖表

由於 findName 及 append 只用到 lastName,先把 lastName以外的欄位都註解掉,試試看能優化多少.

注意!要把 phonebook_opt.h 裡的 //#define OPT 1 註解拿掉才能跑 make plot
參考之前同學的作業(louielu)

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以外的資料都以另一個結構儲存

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;

進度嚴重落後，加緊趕工！ "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 語言
語言技術：C 語言
複習資料結構
資料結構教學講義
學習makefile
Makefile教學
Makefile 語法簡介
共筆參考
yenWu
hsuedw