# 2017q1 Homework1 (phonebook) contributed by<`zhanyangch`> ###### tags:`zhanyangch` `sysprog2017` `week1` >中英文字間請以空白隔開，數字與文字間也是 >[color=red][name=課程助教] ### Reviewed by `you74674` * 執行檔也在commit裡面，好像不太對？ * 最新的commit標題太長了，裡面也沒有提到append function的變更。 * 開發紀錄中的code可能忘了把entryArrayHead的宣告也放進去。 * append看起來不像有處理一次以後的碰撞？紀錄所提的「再用原本findName找到資料」，但append裡面沒有呼叫，main裡面也沒有相關的處理。 ## 執行環境 lscpu 的資訊 ``` $ lscpu Architecture: x86_64 CPU 作業模式： 32-bit, 64-bit Byte Order: Little Endian CPU(s): 4 On-line CPU(s) list: 0-3 每核心執行緒數：2 每通訊端核心數：2 Socket(s): 1 NUMA 節點： 1 供應商識別號： GenuineIntel CPU 家族： 6 型號： 42 Model name: Intel(R) Core(TM) i7-2640M CPU @ 2.80GHz 製程： 7 CPU MHz： 855.421 CPU max MHz: 3500.0000 CPU min MHz: 800.0000 BogoMIPS: 5587.06 虛擬： VT-x L1d 快取： 32K L1i 快取： 32K L2 快取： 256K L3 快取： 4096K NUMA node0 CPU(s): 0-3 ``` ## <s>運行</s>執行原始版本 >> execute 在台灣/繁體中文的慣用翻譯是「執行」 [name="jserv"] ``` $ make $ make run size of entry : 136 bytes execution time of append() : 0.105809 sec execution time of findName() : 0.007168 sec ``` * Makefile 中 `echo 3 | sudo tee /proc/sys/vm/drop_caches` * tee 為雙向重導向可以將資料同時導向檔案和螢幕 * /proc/sys/vm/drop_caches 設定為 3 時釋放大多數的Cachem emory * 使用 gnuplot 顯示，修改 runtime.gp 刪除optimized(尚未實做的欄位) `$ make plot` ![](https://i.imgur.com/2qbQ3p3.png) * 用perf分析cache miss `$perf stat --repeat 100 -e cache-misses,cache-references,instructions,cycles ./phonebook_orig ` ``` Performance counter stats for './phonebook_orig' (100 runs): 2,064,274 cache-misses # 91.100 % of all cache refs ( +- 0.12% ) 2,265,937 cache-references ( +- 0.11% ) 261,177,434 instructions # 1.28 insns per cycle ( +- 0.02% ) 204,356,391 cycles ( +- 0.39% ) 0.071805217 seconds time elapsed ( +- 2.00% ) ``` 可以看出 cache miss 高達 91.1% * 用 perf 分析熱點函式 ``` $ perf record ./phonebook_orig $ perf report ``` ``` Samples: 484 of event 'cycles:pp', Event count (approx.): 212235201 Overhead Command Shared Object Symbol 13.49% phonebook_orig libc-2.23.so [.] __strcasecmp_l_avx 12.59% phonebook_orig phonebook_orig [.] main 10.77% phonebook_orig libc-2.23.so [.] _int_malloc 8.47% phonebook_orig phonebook_orig [.] findName 6.54% phonebook_orig libc-2.23.so [.] __memcpy_sse2 6.24% phonebook_orig libc-2.23.so [.] _IO_fgets 5.74% phonebook_orig libc-2.23.so [.] _IO_getline_info 5.20% phonebook_orig libc-2.23.so [.] __strcpy_sse2_unaligned 4.05% phonebook_orig [kernel.kallsyms] [k] clear_page 3.37% phonebook_orig phonebook_orig [.] append 2.72% phonebook_orig libc-2.23.so [.] memchr 2.47% phonebook_orig [kernel.kallsyms] [k] get_page_from_freelist 2.34% phonebook_orig libc-2.23.so [.] malloc 2.23% phonebook_orig [kernel.kallsyms] [k] native_irq_return_iret 1.75% phonebook_orig [kernel.kallsyms] [k] handle_mm_fault 0.93% phonebook_orig phonebook_orig [.] fgets@plt 0.91% phonebook_orig [kernel.kallsyms] [k] __mod_zone_page_state 0.86% phonebook_orig [kernel.kallsyms] [k] unmap_page_range 0.86% phonebook_orig [kernel.kallsyms] [k] __pagevec_lru_add_fn 0.84% phonebook_orig libc-2.23.so [.] __strcasecmp_avx 0.57% phonebook_orig [kernel.kallsyms] [k] free_hot_cold_page ``` Overhead 最高的前幾名為 findName 與 __strcasecmp_l_avx 字串比較的部份， 若能夠改善 findName 的效能，對程式整體的速度影響較大。 ## 優化一：縮小 struct * 先看一下 Cache 的詳細資訊 ``` Cache Information Socket Designation: L1-Cache Configuration: Enabled, Not Socketed, Level 1 Operational Mode: Write Back Location: Internal Installed Size: 32 kB Maximum Size: 32 kB Supported SRAM Types: Other Installed SRAM Type: Other Speed: Unknown Error Correction Type: None System Type: Unified Associativity: 8-way Set-associative ``` * findName 只查詢 lastName，entry 的其他資料會被搬移至cache，原本的entry佔136byte若將其他資料以令一個 strut details 儲存，可將 entry 縮小到 32byte，在 Cache 內可以存放更多的 entry，達到降低 Cache miss 的效果。 ```C typedef struct __DETAILS { 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]; } details; typedef struct __PHONE_BOOK_ENTRY { char lastName[MAX_LAST_NAME_SIZE]; details *data; struct __PHONE_BOOK_ENTRY *pNext; } entry; ``` * cache-misses 從 91.1% 降低為 58.18% ``` Performance counter stats for './phonebook_opt' (100 runs): 382,089 cache-misses # 58.184 % of all cache refs ( +- 0.17% ) 656,691 cache-references ( +- 0.36% ) 244,028,058 instructions # 1.63 insns per cycle ( +- 0.02% ) 149,303,793 cycles ( +- 0.45% ) 0.046472370 seconds time elapsed ( +- 1.08% ) ``` * 時間比較圖 ![](https://i.imgur.com/hYX3bzW.png) ``` Samples: 347 of event 'cycles:pp', Event count (approx.): 156687981 Overhead Command Shared Object Symbol ▒ 19.20% phonebook_opt phonebook_opt [.] main ◆ 13.37% phonebook_opt libc-2.23.so [.] _int_malloc ▒ 12.93% phonebook_opt libc-2.23.so [.] __strcasecmp_l_avx ▒ 7.09% phonebook_opt libc-2.23.so [.] _IO_getline_info ▒ 6.31% phonebook_opt libc-2.23.so [.] __memcpy_sse2 ▒ 6.23% phonebook_opt libc-2.23.so [.] _IO_fgets ▒ 5.57% phonebook_opt libc-2.23.so [.] __strcpy_sse2_unaligned ▒ 4.48% phonebook_opt phonebook_opt [.] append ▒ 4.30% phonebook_opt libc-2.23.so [.] malloc ▒ 3.91% phonebook_opt phonebook_opt [.] findName ▒ 3.82% phonebook_opt libc-2.23.so [.] memchr ▒ 2.02% phonebook_opt [kernel.kallsyms] [k] clear_page ▒ 1.31% phonebook_opt [kernel.kallsyms] [k] release_pages ▒ 0.84% phonebook_opt [kernel.kallsyms] [k] native_irq_return_iret ▒ 0.73% phonebook_opt phonebook_opt [.] strcasecmp@plt ▒ 0.69% phonebook_opt [kernel.kallsyms] [k] unmap_page_range ▒ 0.58% phonebook_opt [kernel.kallsyms] [k] get_page_from_freelist ▒ 0.56% phonebook_opt phonebook_opt [.] strcpy@plt ▒ 0.56% phonebook_opt [kernel.kallsyms] [k] handle_mm_fault ▒ 0.55% phonebook_opt libc-2.23.so [.] _IO_getline ▒ 0.53% phonebook_opt [kernel.kallsyms] [k] __rmqueue.isra.79 ``` ## 優化二：使用hash function * hash 原理：雜湊函式 把訊息或資料 (key) 壓縮成摘要，使得資料量變小，將資料的格式固定下來。該函式將資料打亂混合，重新建立一個叫做雜湊值的指紋。 * 好的 hash function 可以減少碰撞 (collison)，碰撞指的是 不同的 key 卻得到相同的雜湊值。 * 解決碰撞的方法有兩種 1. 封閉式雜湊法(closed hashing, open addressing) collision發生時，無法儲存的資料會被儲存到雜湊表中的其它 位置。線性偵測法與平方偵測法都屬於此法。 2. 開放式雜湊法(open hashing, separate chaining) collision發生時，無法儲存的資料會被儲存到雜湊表之外的空間 * 在這次作業當發生碰撞時，利用原本 entry 的 pNext 建立一個 list，可以把它看作將 phonebook 分冊， hash function 找到第幾冊，再用原本 findName 找到資料。 * Table size 使用質數，可降低碰撞機率，且數值越大碰撞機率越低，但會使用較多記憶體空間。 * 程式碼如下，思考在不修改main之下是否有更簡潔的寫法？ ```clike= #define TABLESIZE 5393 entry **entryArray=NULL; unsigned int BKDRHash(char *str) { unsigned int seed = 131; // 31 131 1313 13131 131313 etc.. unsigned int hash = 0; while (*str){ hash = hash * seed + (*str++); } return (hash % TABLESIZE); } entry *findName(char lastName[], entry *pHead) { unsigned int hashvalue = BKDRHash(lastName); pHead = *(entryArrayHead+hashvalue); while (pHead != NULL) { if (strcasecmp(lastName, pHead->lastName) == 0) return pHead; pHead = pHead->pNext; } return NULL; } entry *append(char lastName[], entry *e) { if(entryArray == NULL) { entryArray = (entry **)malloc((TABLESIZE+1)*sizeof(entry *)); entryArrayHead = (entry **)malloc((TABLESIZE+1)*sizeof(entry *)); } unsigned int hashvalue = BKDRHash(lastName); e = *(entryArray+hashvalue); if(*(entryArrayHead+hashvalue) == NULL) { e = (entry *) malloc(sizeof(entry)); *(entryArrayHead+hashvalue) = e; } e->pNext = (entry *) malloc(sizeof(entry)); e = e->pNext; strcpy(e->lastName, lastName); e->pNext = NULL; *(entryArray+hashvalue) = e; return e; } ``` * 修改 calculate.c、runtime.gp來紀錄資料與繪圖，可以發現由於 hash 版本的 append 時間太短，須另外找方式紀錄，而 append 的時間增加，試著找方法優化 append。 >runtime.gp 如何取消自動超連結? >[color=blue][name=zhanyangch] * 修改 main 和 calculate 即可 double 精度可以到小數點 15 位，diff_in_second 提供 nanosecond (10^-9^) 精度， 將 findName 的時間顯示 %lf 改為 %.9lf ![](https://i.imgur.com/5RQBVVX.png) * cache miss 降低至 35% ``` Performance counter stats for './phonebook_opt_hash' (100 runs): 306,952 cache-misses # 35.750 % of all cache refs ( +- 0.08% ) 858,599 cache-references ( +- 0.26% ) 242,237,830 instructions # 1.49 insns per cycle ( +- 0.02% ) 162,039,957 cycles ( +- 0.28% ) 0.064788502 seconds time elapsed ( +- 3.89% ) ``` * 想法：利用平行化處理 append， 但要注意每個 hash value 對應的 list 只有一個 thread 可以修改，使用的函式是否為 thread-safe，在 POSIX 標準下 malloc 為 thread-safe，可以使用。 參考資料 == [gnuplot 語法解說和示範](https://hackmd.io/s/Skwp-alOg#) [觀察 Linux 的虛擬記憶體](http://blog.linux.org.tw/~jserv/archives/002039.html) [淺談memory cache](http://opass.logdown.com/posts/249025-discussion-on-memory-cache) [關於 CPU Cache：程序猿需要知道的那些事](https://read01.com/0A6Dxg.html) [hash function 觀念和實務](https://hackmd.io/s/HJln3jU_e#) [Hashing原理介紹](http://note-whu.rhcloud.com/2015/09/27/hashing%E5%8E%9F%E7%90%86%E4%BB%8B%E7%B4%B9/) [Is malloc thread-safe?](http://stackoverflow.com/questions/855763/is-malloc-thread-safe) [ 在 Linux 中以特定的 CPU 核心執行程式](https://blog.gtwang.org/linux/run-program-process-specific-cpu-cores-linux/)