Try   HackMD

2017q3 Homework1 (phonebook)

contributed by<zhanyangch>

Reviewed by tina0405

  • 檢查 memory leak 的部份很好，也讓我發現自己平常沒有注意的部份，在 github 上 commit 的 Fix bug in opt anddelete executable file ，會讓人不清楚是哪部份的 bug

紀錄一下自己在重新 fork 的步驟
首先直接在自己目前的專案下 pull 課程的專案

git pull https://github.com/sysprog21/phonebook

之後會自動進行 merge，如果出現 merge conflit 就必須要處理

git config --global merge.tool kidiff3
git merge

這裡使用 kidiff3 也可以使用其他相同功能的軟體像是 vimdiff，將 conflit 的部份進行修正。
修改完成後記得將程式重新測試一次，如果有問題趕快與原先的程式碼對照，確認之後就像一般 commit、push 的步驟即可。

之前作過的部份，hackmd

執行環境

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

執行原始版本

$ 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
  • 用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 的效果。
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% )
  • 時間比較圖
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之下是否有更簡潔的寫法？













































#define TABLESIZE 5393
entry **entryArray=NULL;
entry **entryArrayHead=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。

  • 修改 main 和 calculate 即可 double 精度可以到小數點 15 位，diff_in_second 提供 nanosecond (10-9) 精度， 將 findName 的時間顯示 %lf 改為 %.9lf

  • 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% )

利用 perf record 分析，發現 hash 的部份為函式熱點

  15.79%  phonebook_opt_h  phonebook_opt_hash  [.] BKDRHash                    ▒
  14.84%  phonebook_opt_h  phonebook_opt_hash  [.] main                        ▒
  14.04%  phonebook_opt_h  phonebook_opt_hash  [.] append                      ◆
   9.80%  phonebook_opt_h  libc-2.23.so        [.] _int_malloc                 ▒
   7.94%  phonebook_opt_h  libc-2.23.so        [.] __memcpy_sse2               ▒
   7.08%  phonebook_opt_h  libc-2.23.so        [.] _IO_fgets                   ▒
   5.26%  phonebook_opt_h  libc-2.23.so        [.] __strcpy_sse2_unaligned     ▒
   4.26%  phonebook_opt_h  libc-2.23.so        [.] _IO_getline_info            ▒
   2.92%  phonebook_opt_h  libc-2.23.so        [.] memchr                      ▒
   2.33%  phonebook_opt_h  libc-2.23.so        [.] malloc

Memory leak

參考ierosodin的共筆

valgrind --leak-check=full ./phonebook_orig 

==5682== HEAP SUMMARY:
==5682==     in use at exit: 47,586,264 bytes in 349,899 blocks
==5682==   total heap usage: 349,906 allocs, 7 frees, 47,596,856 bytes allocated

可以看到 allocs 與 frees 不相等
修改 main.c 釋放記憶體的部份

    entry *tmp;
    while ((tmp = pHead) != NULL) {
        pHead = pHead->pNext;
        free(tmp);
    }
#ifdef HASH
    hash_free();
#endif 

==5792== HEAP SUMMARY:
==5792==     in use at exit: 0 bytes in 0 blocks
==5792==   total heap usage: 349,906 allocs, 349,906 frees, 47,596,856 bytes allocated

處理 hash 版本的Memory leak，在 phonebook_opt_hash.c加入

void hash_free(){
    int i;
    entry *tmp;
    entry *pHead;
    for(i=0;i<TABLESIZE;i++){
        pHead=*(entryArrayHead+i);
        while ((tmp = pHead) != NULL) {
            pHead = pHead->pNext;
            free(tmp);
        }
    }
    if(entryArrayHead) free(entryArrayHead);
    if(entryArray) free(entryArray);
}

==6709== HEAP SUMMARY:
==6709==     in use at exit: 0 bytes in 0 blocks
==6709==   total heap usage: 355,301 allocs, 355,301 frees, 11,466,032 bytes all

問題探討

  • 本例選用的 dataset (也就是輸入電話簿的姓名) 是否存在問題？
  • 有代表性嗎？跟真實英文姓氏差異大嗎？
    預設使用的 word.txt 內的資料，有一大部分都是沒有意義的字詞，與現實中常見的英文姓名差異大。
  • 資料難道「數大就是美」嗎？
  • 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
    需要考慮到姓名相同的情況，能夠先利用 last name 找出多筆結果，利用其他欄位進行搜尋，此外也必須考慮資料修改與刪除的動作。

參考資料

gnuplot 語法解說和示範
觀察 Linux 的虛擬記憶體
淺談memory cache
關於 CPU Cache：程序猿需要知道的那些事
hash function 觀念和實務
Hashing原理介紹
Is malloc thread-safe?
在 Linux 中以特定的 CPU 核心執行程式

Last changed by 
 
陳展揚
0
361
Published on HackMD