Try   HackMD

Phonebook案例分析

架環境

先架構起可以運行作業所需要的環境
我在電腦中安裝的是ubuntu14.04的版本

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Gunplot印不出優化解決辦法

前幾次再使用語法$make plot時，都只會印出兩條orig的時間條，努力看懂main.c後，找到了問題所在，希望能幫到印不出來的同學

#if defined(OPT)
        output = fopen("opt.txt", "a");
#else
        output = fopen("orig.txt", "a");
#endif

這段程式碼就是讓gunplot印出奇怪東西的原因，但老師原本打的#if defined(OPT)是甚麼意思呢？這邊的指示詞 #if 如果搭配 define 時，就可以再前置處理時檢查是否有此項識別項，這邊的識別項 (identifier) 指的就是 OPT，於是他會檢查 OPT 是否被定義，所以打開phonebook_opt.h，再裡頭加上一行：

#define OPT 1

Hua：這裡想請問老師，這類指示詞的前置處理指的是在程式執行前先判斷嗎？

Jim H：OPT 應該定義在 Makefile 中 CFLAGS，請注意看 "-DOPT=" 的設定

HUA-YUAN：
可以在Makefile的CFLAGS中 加上-DOPT="1" 去 define
也可以在*.[ch]裡面寫上 #define OPT 1
但是寫在*.[ch]的彈性沒有比在Makefile中來的好

Hua：恩恩，我在下面有修改過Makefile了，謝謝同學><

phonebook_opt: $(SRCS_common) phonebook_opt.c phonebook_opt.h
        $(CC) $(CFLAGS_common) $(CFLAGS_opt) \
                -DIMPL="\"$@.h\"" -o $@ \
                $(SRCS_common) $@.c

Hua：這是Makefile在處理phonebook_opt時的語法，可是我找不到定義OPT

Jim H：你要自己定義

Hua：了解！

phonebook_opt: $(SRCS_common) phonebook_opt.c phonebook_opt.h
        $(CC) $(CFLAGS_common) $(CFLAGS_opt) \
                -DIMPL="\"$@.h\"" -o $@ \
                -DOPT="1" \
                $(SRCS_common) $@.c

直接在Makefile裡修改並定義OPT的值

這裡之後在去嘗試執行make plot就應該會有正確的結果囉 (前提是phonebook_opt.c或.h有做過優化！)

Hua：如果不想經由 directive 去達成，也可以偷偷修改 main.c 裡的內容，直接透過判斷 IMPL 這個變數值也可以達到一樣的效果，不過要看懂 makefile 裡再幹嘛QQ

嘗試優化方法

參考過去的課程及開發紀錄，大致上有多種優化方法

  1. 縮小資料的struct
  2. 利用hash縮小資料量
  3. 資料連續排序
  4. 利用壓縮字串演算法處理
  5. 自己想(努力ing)

效能分析

未優化版本

針對原本未優化的程式進行perf的分析，可以發現findname( )的使用比率15.77%佔了第3，確實是此程式的「熱點」，而相比之下append反倒只使用了0.84%，但append( )執行時間卻比findname( )多了將近6倍。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More → 

size of entry : 136 bytes
execution time of append() : 0.031616 sec
execution time of findName() : 0.005111 sec

優化版本 1 (縮小struct大小)

藉由縮小struct大小來增加裝載在cache裡的資料數，進而降低cache miss

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More → 

size of entry : 32 bytes
execution time of append() : 0.024877 sec
execution time of findName() : 0.001999 sec

Performance counter stats for './phonebook_opt 2' (100 runs):

           200,026      cache-misses              #   54.181 % of all cache refs    
           465,553      cache-references                                            
       246,297,602      instructions              #    2.07  insns per cycle        
       116,494,982      cycles                                                      

       0.033493941 seconds time elapsed                                          ( +-  0.49% )

對於這個方法，跟同組的成員有討論過是否有刪減功能的疑慮

entry *append(char lastName[], entry *e)
{
    e->pNext = (entry *) malloc(sizeof(entry));
    e = e->pNext;
    strcpy(e->lastName, lastName);
    e->pNext = NULL;
    return e;
}

原程式碼當中並沒有針對struct裡的detail指標去配置記憶體，於是嘗試malloc記憶體給detail

entry *append(char lastName[], entry *e)
{
    e->pNext = (entry *) malloc(sizeof(entry));
    e = e->pNext;
    strcpy(e->lastName, lastName);
    e->pNext = NULL;
    e->detail = (entry1 *) malloc(sizeof(entry1));
    return e;
}

其中的entry1是原struct的宣告型態，因為detail是指向原本的struct的，故記憶體也要配一樣大
可以想的到，勢必會讓運算及cache miss增加

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More → 

size of entry : 32 bytes
execution time of append() : 0.040050 sec
execution time of findName() : 0.010390 sec

 Performance counter stats for './phonebook_opt 2' (100 runs):

         1,231,212      cache-misses              #   90.445 % of all cache refs    
         1,374,492      cache-references                                            
       342,840,812      instructions              #    1.16  insns per cycle        
       276,229,352      cycles                                                      

       0.082166540 seconds time elapsed                                          ( +-  1.02% )

對於這裡detail的看法，我會將資料視為兩層的結構，再搜尋功能方面先不要配置記憶體給detail (虛線表示)，等到搜尋結束後在針對得到的搜尋結果給予*detail指向的entry記憶體，就可以達到一樣查找到細節功能，而不增加findname( ) 的負擔

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

優化版本 2 (hashfunction)

過去沒有再實作中使用過 hashfunction，於是再使用前查找並了解 hashfunction，並簡單理解為"幫資料做編碼"，如何透過運算式讓資料依據 (key) 去轉為獨一無二的數值，讓查找的時間複雜度大幅的降低。但基本上完美的hashfunction是相當相當困難的 (不敢斷言不存在)，於是選擇一個讓資料均勻度高的hashfunction是不錯的出發點。

道歉啟事：回去重看我的hashfunction的實作後，發現有瑕疵跟錯誤，馬上奉上修正後的可怕結果，真是太對不起看過的同學了QQ

實作後的結果：

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

findname() 幾乎降到看不到，但 append() 本身的速度卻衝到天堂去了QQ

size of entry : 136 bytes
execution time of append() : 0.241334 sec
execution time of findName() : 0.000007 sec

 Performance counter stats for './phonebook_opt_hash 2':

         1,900,949      cache-misses              #   28.082 % of all cache refs    
         6,769,278      cache-references                                            
       313,549,151      instructions              #    0.36  insns per cycle        
       882,918,535      cycles                                                      

       0.245116261 seconds time elapsed

一開始先採用簡單的 hashfunction，也就是利用 lastname 的值對某數進行 mod 後，這邊我並沒有額外建立hashtable，而是利用資料本身的 pointer 來相互連接，也就是資料結構本身就是 hashtable 來達成目的。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

但是再研究過以前學長github裡的程式碼後，發現append( )再組成hash所需要的資料結構時，有邏輯上的錯誤，導致collision發生時，會直接覆蓋前一筆資料，而不是將資料接在資料串的最後端，所以才有append( )只增加些許的錯覺，這方面要跟老師請益(會找時間去問老師)

推測

  • 再怎麼均勻的hashfunction都會讓append( )的時間暴增，因為要將資料放再linked-list的最末端時，會利用到迴圈的語法來進行幫助，所以時間的消耗會難以避免 。(ex：35萬筆資料均勻分散在5萬組之中，而每一組都會有7個entry，所以while迴圈會多執行(0+1+2+3+4+5+6)*50000=1050000的操作！！！勢必append( )的時間會增長許多，況且這是在perfect-hashfunction的大前提下，真實的時間只會更加的大

剛剛翻找到神人對hashtable的做法，直接將資料接在linked list前端，就可以省去不必要的迴圈時間，實在太令人興奮了，回家後立馬實作分享跟補上莊彥宣學長筆記

Jim H：人家有名字的！請做出最基本的尊重，把人名寫好

Hua：好的！馬上改

實作結果：

append( )跟之前的0.2~0.3秒鐘相比有了相當的縮短，果然append( )的時間最主要還是取決於資料結構的型態及如何配置記憶體給資料，而0.04秒要更加的接近原本的時間，就取決於hashfunction的優化，使得均勻度提高。

size of entry : 136 bytes
execution time of append() : 0.039045 sec
execution time of findName() : 0.000008 sec

 Performance counter stats for './phonebook_opt_hash 2' (100 runs):

           135,656      cache-misses              #   26.088 % of all cache refs    
           522,893      cache-references                                            
       271,834,151      instructions              #    1.71  insns per cycle        
       155,104,850      cycles                                                      

       0.043292796 seconds time elapsed                                          ( +-  0.59% )

為了不多增加一個main.c，而是像模組化的感覺安置進原程式，於是開始動手修改原本的 main.c 並增加了 phonebook_opt_hash.[ch] 來當作 hashfunction 優化的程式碼，更正後程式碼的部分已經在Github做更新了，要是邏輯有錯誤的地方，麻煩別吝嗇的告訴我> <

實作fuzzy search

Levenshtein distance

首先從 Levenshtein distance 開始研究跟實作，Charles的學習筆記以及 NIKITA'S BLOG 中有相當詳細的介紹以及原理，以下紀錄我學習的理解：

Levenshtein distance將字串間的差異簡單的區分為三種模式：插入、刪>除、替換
(以 jarsvs 轉為 jersv 做舉例)

  • jarsvs -> jarsv (刪除)
  • jarsv -> jersv ( "e"去替換"a" )
  • 因此這兩個字串間的 Levenshtein distance 就為 2

利用這張圖可以簡單理解其實作原理( ELEPHANT v.s. RELEVANT )，將母字串與子字串不斷的去進行 Levenshtein distance 的運算後，取其中最小值回傳，以 XX 與 XY 為範例。

Levenshtein distance (以下簡稱：LD)
LD ( XX , XY ) = min( LD( X , XY ) + 1 , LD( XY , X ) + 1 , LD ( X , X ) + Last )
Last當字串最後字元不相等時為 1

  • Q：為何當比較 LD( X , XY ) 或 LD( XX , X) 時，需要 +1？
    A：因為 X 與原字串 XX 、XY 相比多做了一個刪除的動作，所以 Levenshtein distance 必須+1 回傳

  • Q：為何當比較 LD( X , X )時，是 + Last？
    A：因為 LD ( X , X )與 LD( XX , XY ) 相比會差異在尾巴字串的異同，所以 Levenshtein distance 必須+Last 回傳

實作一(Recursive)

Recursive再實作上的缺點就是效率極差，於是先建立一個 test.txt (只有15筆資料)來實作驗證

實作數據：
資料數：15、搜尋字串：zyexl

size of entry : 136 bytes
Levenshtein numver set:2
Distance=1,ayexl
Distance=0,zyexl
Distance=1,zyecl
Distance=1,zyexls
execution time of append() : 0.000005 sec
execution time of findName() : 5.243732 sec

可以發現少少15筆資料就讓 findName( ) 找了將近5秒，而且可以發現資料中有一個較長的字串，執行到那邊時會運算很久，這是因為 LD( ) 不斷的呼叫自己，總共呼叫了將近 3^16 次自己，導致5秒的時間幾乎都落在運算那個字串上。

size of entry : 136 bytes
Levenshtein numver set:2
Distance=1,ayexl
Distance=0,zyexl
Distance=1,zyecl
Distance=1,zyexls
execution time of append() : 0.000008 sec
execution time of findName() : 0.043940 sec

在這邊做個簡單設計就可以改善這個問題，再 findName( ) 之中，對字串長度做篩選就可以提高效率，欲搜尋字串的長度 ± Levenshtein numver 就可以稍微優化，但當字串本身太長時，還是沒辦法避免效率低落。

實作二 (Iterative)

(晚一點更新 Iterative 的實作跟原理)(研究ing)

參考資料

Last changed by 
 
ShaoHua Wang
0
642
Published on HackMD