Try   HackMD

2018q1 Homework1 (phonebook)

contributed by <afcidk>

Reviewed by ryanpatiency

  • Could you explain under which condition trie will be faster than hash ?

Reviewed by LinYunWen

  • 後面的 commit message 寫得很不錯,甚至還有畫些圖,不過有兩個 commit message 的 title 一樣,雖然內文不同,但是會有點奇怪 (commit 29f0572commit ebca2de)
  • 最後的 trie 可以多說明一些 cache miss 上的比較或解釋,多偏向只有時間上的看法

對應的程式碼修改應一併傳到 github 上
課程助教

開發環境

afcidk@Lubuntu1:~$ 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:  1
Core(s) per socket:  4
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               94
Model name:          Intel(R) Core(TM) i5-6400 CPU @ 2.70GHz
Stepping:            3
CPU MHz:             2700.000
CPU max MHz:         3300.0000
CPU min MHz:         800.0000
BogoMIPS:            5424.00
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            6144K
NUMA node0 CPU(s):   0-3

目標

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

TODO

  • binary search
  • fuzzy search
  • memory pool

理解 cache 是什麼

因為 CPU 的速度太快了,而主記憶體( DRAM )和 CPU 的速度也不是只有差一點點。為了避免整體速度被拖延到,產生了 cache 的技術。 cache 的存在就是為了解決 DRAM 和 CPU 的處理速度差距而產生的瓶頸。為什麼這樣說呢?

CPU 處理的速度很快,但是因為 DRAM 速度比較慢,所以會讓 CPU 有空閒的時間。想要讓 CPU 忙一點,我們勢必要讓輸入趕上處理速度,在硬體的部份就產生了快一點的 cache( SRAM ) 來當中介。可是又有新問題了,cache 裡面的資料要放什麼呢?

cache 裡面的資料遵守 Locality of Reference

Locality of Reference 代表的是 cache 在儲存資料時會選擇

  • 頻繁被要求的資料 ( temporal locality )
  • 現在使用中的資料附近的資料 ( spatial locality )

這讓 CPU 在處理的時候可以優先從 cache 裡面選擇這些比較有可能會用到的資料,進而提昇效能

上面這句話不精確,請翻閱計算機組織的教材,重新用自己的認知表達過。
:notes: jserv

已重新表達!

cache( SRAM ) 比主記憶體( DRAM )還要快,可以用來銜接 CPU 和 DRAM 之間的訊息傳輸。SRAM 是由電晶體構成,DRAM 是由電容構成,充放電的速度導致在讀寫速度上 SRAM > DRAM。

memory 一般翻譯為「記憶體」,是通用詞彙,而 cache 是一種 memory,你在表達時,應該區分 cache 和 DRAM 一類的「主記憶體」
:notes: jserv

已更改敘述!

关于CPU Cache 程序猿需要知道的那些事介紹完什麼是 cache line 後,他有提出兩段相差不大的C語言程式碼,但是執行速度卻有很大的落差。

//比較快
int num = 0;
for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        //code
        arr[i][j] = num++;
    }
}
//比較慢
int num = 0;
for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {   
        //code
        arr[j][i] = num++;
    }
}

根據自己對於 cache line 的理解,第二份程式碼比較慢的原因是因為它每次要被assign的位置都不是相鄰的,有比較大的機會讓需要操作到的記憶體空間不在 cache 上,導致 cache miss 比較大

「根據自己對於 的理解」這種話就不需要在共筆提及,這裡本來就是你的理解。你應該要精確地描述 locality 的影響。
:notes: jserv

關鍵字:row major, column major
課程助教

在 C 語言中,陣列的儲存方式採用 row major 的方式,再回頭看看上述的例子
假設陣列大小( n )是 3 x 3
第一個版本儲存的資料按照順序會是 0 1 2 3 4 5 6 7 8

0 _ _ _ _ _ _ _ _ 0 1 _ _ _ _ _ _ _ 0 1 2 _ _ _ _ _ _ 0 1 2 3 _ _ _ _ _ 0 1 2 3 4 _ _ _ _ 0 1 2 3 4 5 _ _ _ 0 1 2 3 4 5 6 _ _ 0 1 2 3 4 5 6 7 _ 0 1 2 3 4 5 6 7 8

第二個版本儲存的資料按照順序會是 0 3 6 1 4 7 2 5 8

0 _ _ _ _ _ _ _ _ 0 _ _ 1 _ _ _ _ _ 0 _ _ 1 _ _ 2 _ _ 0 3 _ 1 _ _ 2 _ _ 0 3 _ 1 4 _ 2 _ _ 0 3 _ 1 4 _ 2 5 _ 0 3 6 1 4 _ 2 5 _ 0 3 6 1 4 7 2 5 _ 0 3 6 1 4 7 2 5 8

可以發現第一個版本的數字是一個一個放上去的,而第二個版本的數字是跳著放上去的
(從 0 依序放到 8 )

實際執行看看 cache 的變化大不大 (使用 n = 3 )

理論上比較快的程式碼


793         cache-misses   #    2.302 % of all cache refs    ( +- 16.37% )
34,459      cache-references                                 ( +-  0.46% )

理論上比較慢的程式碼

819         cache-misses     #    2.387 % of all cache refs     ( +- 15.70% )
34,307      cache-references                                 ( +-  0.53% )

在陣列大小不大時影響似乎看不太出來,因為 cache 都還放得下,但是如果數據量大一點呢?
可以使用指令lshw( list hardware )查看電腦的 cache 大小

*-cache:0
          description: L1 cache
          physical id: 3e
          slot: L1 Cache
          size: 128KiB
          capacity: 128KiB
          capabilities: synchronous internal write-back data
          configuration: level=1

128210=217
217/22=215=32768

這次讓 n = 3000,再比對一次 cache 的變化

為什麼選 3000 的原因是要讓 cache 小於陣列的大小

30003000>32768

751,144    cache-misses      # 87.156 % of all cache refs    ( +-  0.07% )
861,836    cache-references                                  ( +-  0.06% )
1,700,256   cache-misses     # 5.942 % of all cache refs     ( +-  0.13% )
28,616,391  cache-references                                 ( +-  0.21% )

這次 cache-miss 就增加了兩倍以上,cache-reference 也跟著增加到三倍以上

原本 performance

entry size 為 136 bytes

 Performance counter stats for './phonebook_orig' (100 runs):
          453,7987      cache-misses              #   92.087 % of all cache refs      ( +-  0.07% )
          492,7930      cache-references                                              ( +-  0.05% )
       2,7522,5199      instructions              #    1.41  insn per cycle           ( +-  0.02% )
       1,9559,6852      cycles                                                        ( +-  0.07% )

       0.062733108 seconds time elapsed                                          ( +-  0.48% )

減少 entry size

要減少 cache miss 的其中一個方法是讓 entry size 小一點,這樣 cache 裡面可以放的資料就比較多

原本的 entry size 是 136 bytes,也許可以試著讓裡面的資料壓縮一點,或是把某部份只是用來紀錄的資料搬到別的地方

用語要精確!搬動資料不算「壓縮」,理工人如果連說話都不精確,要怎麼說服他人呢?
:notes: jserv

謝謝老師的提醒!其實我最初的想法是要陳述可以壓縮空間或是搬動資料兩件事的,但是後來覺得我不應該在這方面要求 phonebook 的其他資料大小一定要壓縮成怎樣。
已更改敘述方式! afcidk

嘗試1 只留 lastname

觀察main.c後發現 append 和 findName 這兩個函式都只有用到 lastname,先把__PHONE_BOOK_ENTRY 其他的變數都拿掉試試看

編譯完後執行:$ make cache-test

修改後的 entry size 為 24 bytes

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

          100,8296      cache-misses              #   62.527 % of all cache refs      ( +-  0.42% )
          161,2565      cache-references                                              ( +-  0.12% )
       2,5082,2518      instructions              #    2.06  insn per cycle           ( +-  0.02% )
       1,2185,8684      cycles                                                        ( +-  0.10% )

       0.039152981 seconds time elapsed                                          ( +-  0.14% )

發現 cache-miss 和原本的差了 4 倍左右,時間也差了快一倍。但是 phone book 顯然不會只有 lastname 而已,其他的資料應該也要放上去,查詢到正確的 lastname 時才可以顯示

嘗試2 entry 多加一個 pointer 指向其他資料存放位置

增加了一個 structure ,因為不會參與到查詢,所以把它額外放在別的地方,並用一個指標存取記憶體位址

//size of entry: 32 bytes
typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    struct __PHONE_BOOK_ENTRY *pNext;
    struct __OTHER_PHONE_BOOK_DATA *pData;
} entry;  
typedef struct __OTHER_PHONE_BOOK_DATA {
    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];                             
} phonebookData;

編譯完後執行:make cache-test

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

          148,4340      cache-misses              #   66.452 % of all cache refs      ( +-  0.39% )
          223,3716      cache-references                                              ( +-  0.14% )
       2,5438,6330      instructions              #    1.97  insn per cycle           ( +-  0.02% )
       1,2896,4063      cycles                                                        ( +-  0.09% )

       0.042576904 seconds time elapsed                                          ( +-  0.28% )


發現效能雖然比只留 lastname 差了一點,但是和優化前比較 entry size 仍然大幅度降低,所以整體的效能還是有提高,cache-miss 也有減少

後來發現忘記在 append 時 malloc 空間給pData,加上去後發現效能大幅度的降低了,甚至比沒優化前還要低

看起來應該是 malloc 惹的禍,可是更改append()竟然也會影響到findName()
為什麼會這樣要再想一下

你需要證明上述推論,請試著撰寫更多程式來釐清 malloc() 的影響
:notes: jserv

原本以為是malloc()花費太多時間,沒想到是 cache-miss 導致效能變差

首先,比對程式碼的 cache-miss 狀況
分別是刪除e->pData = (phonebookData *) malloc(sizeof(phonebookData));和沒有刪除的版本

刪除的版本 (沒有配置空間)

1,528,953      cache-misses   #   68.037 % of all cache refs ( +-  0.29% )
2,247,223      cache-references                              ( +-  0.21% )
260,220,582    instructions   #   1.97  insn per cycle       ( +-  0.02% )
131,995,699    cycles                                        ( +-  0.08% )

0.049236369 seconds time elapsed                             ( +-  0.49% )

沒刪除的版本 (有配置空間)

5,855,719      cache-misses  #   95.576 % of all cache refs  ( +-  0.09% )
6,126,743      cache-references                              ( +-  0.08% )
371,742,089    instructions  #   1.37  insn per cycle        ( +-  0.01% )
271,899,335    cycles                                        ( +-  0.21% )

0.090920051 seconds time elapsed                             ( +-  0.49% )

發現 cache-miss 差了將近四倍,再用perf top計算出哪個地方耗費的時間最多

  26.40%  phonebook_opt     [.] main
  14.22%  libc-2.26.so      [.] _int_malloc
   9.03%  libc-2.26.so      [.] __strcasecmp_l_avx
   8.83%  libc-2.26.so      [.] _IO_fgets
  24.60%  libc-2.26.so      [.] __strcasecmp_l_avx
  14.54%  phonebook_opt     [.] main
  11.19%  libc-2.26.so      [.] _int_malloc
   4.14%  phonebook_opt     [.] findName

變化最大的是strcasecmp(),代表有沒有配置空間對strcasecmp()有很大的影響

因此,就算把不是查詢用的資料移到別的地方,在每次配置空間時仍會讓 cache-miss 提高,再加上每次呼叫malloc()的時間,整體效能會比沒有搬動資料還要差。

但是如果不需要事先配置好位置給額外的資料,而是需要填入資料時再配置空間,仍然可以提昇部份效能。

嘗試3 使用hash function

使用類似 Rabin-Karp algorithm 的 rolling hash 方法,因為每個字串的每個字元都會計算到,所以在append()花費的時間比較多。使用質數 40009 作為 hashTable

一開始 hashTable 想要建到 150000 附近,但是因為main.c是共用的, hashTable 太大會讓原本的phonebook_orig無法執行。

後來參考陳冠廷同學的筆記,發現以數據量為 300000 來說,假設資料平均分佈, 300000/150000 = 2 ,而 300000/40000 = 7.5 ,花費在findName()的時間只有極微小的差距。

不要寫「這位同學」,人家有名字 (至少有 GitHub 帳號),你應該清楚提及
:notes: jserv

已補上!


雖然說查詢一個 lastName 的時間已經降到 1e-6 以下,但是查詢量低的時候其實沒有什麼差別,反倒是append()和原本的phonebook_orig相比,效能相差了 4 倍以上,後面應該要找一些 hash function 來比對看看

用 perf top/stat 找出效能瓶頸再來分析
:notes: jserv

又腦補了QQ 直覺就認為是 hash function 的問題,要看數據說話!

使用perf top查看效能瓶頸,得到以下結果

   48.68%  libc-2.26.so      [.] __strncmp_sse42
   33.80%  phonebook_hash    [.] hashFunc
   4.48%   phonebook_hash     [.] main
   3.65%   phonebook_hash     [.] append
   1.91%   libc-2.26.so       [.] _int_malloc
   1.53%   libc-2.26.so       [.] _IO_fgets
   1.48%   libc-2.26.so       [.] __strncpy_sse2_unaligned
   1.29%   libc-2.26.so       [.] malloc

發現append()裡面處理 hash collision 的字串比對佔用最多的時間,其次是產生 hash value

後來又看了一下程式碼發現當初想錯了,處理 hash collision 不用比對字串,直接把新的資料放到 linked list 的尾端就好了

更正後又跑了一次perf top

61.06%  phonebook_hash    [.] hashFunc
8.73%   phonebook_hash    [.] append
6.06%   phonebook_hash    [.] main
4.56%   libc-2.26.so      [.] _int_malloc
3.39%   libc-2.26.so      [.] __strlen_avx2

發現先前錯誤的程式碼中,append()裡的strcmp()幾乎佔據了總時間的一半。改善過後效能提高了,瓶頸也如同預期的一樣卡在生成 hashValue

再來我參考這篇文章使用 djb2 作為 hash function,其餘程式碼沒有變動,執行make plot後產生的效能比對圖如下

可以發現append()的效能提昇了不少,雖然和未優化前的版本相比仍然降低一些,但是透過 hash function 讓查詢資料時的時間大幅縮短

使用perf top指令查看,發現 hash function 佔用的時間縮短許多

24.82%  phonebook_hash    [.] append
19.83%  phonebook_hash    [.] main
13.92%  phonebook_hash    [.] hashFunc
8.33%   libc-2.26.so      [.] _int_malloc

這讓我想到一些問題:

  • 原本使用 rolling hash 當 hash function ,效能低落是不是因為hashFunc()沒有寫好?
  • 這個版本我一樣把不會用來查詢的資料搬到另外一個 structure 以減少 entry size ,但是沒有事先給予這些資料空間來儲存。如果和上面的作法一樣事先配置空間給這些資料,findName()會不會像phonebook_opt實做時一樣效能降低?也許可以從這裡發現什麼東西

對於第二個問題,我做了兩個變動來比對效能

  • 讓 entry size 恢復成 136 bytes
  • 每次執行append()時順便配置空間給未用來查詢的資料

使用 dbj2 hash function,維持 entry size 為 136 bytes

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

         4,068,228      cache-misses              #   69.258 % of all cache refs      ( +-  0.06% )
         5,874,013      cache-references                                              ( +-  0.06% )
       300,915,071      instructions              #    1.16  insn per cycle           ( +-  0.03% )
       259,404,732      cycles                                                        ( +-  0.05% )
28.00%  phonebook_hash    [.] append
13.01%  phonebook_hash    [.] hashFunc
12.86%  phonebook_hash    [.] main
 5.29%  libc-2.26.so      [.] _int_malloc

發現append()時間變長了

使用 dbj2 hash function,每次 append 時配置空間給未用來查詢的資料

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

         3,954,543      cache-misses              #   66.471 % of all cache refs      ( +-  0.19% )
         5,949,307      cache-references                                              ( +-  0.17% )
       384,800,899      instructions              #    1.43  insn per cycle           ( +-  0.02% )
       268,910,185      cycles                                                        ( +-  0.08% )
24.67%  phonebook_hash    [.] append
13.83%  phonebook_hash    [.] main
 9.63%  libc-2.26.so      [.] _int_malloc
 8.22%  phonebook_hash    [.] hashFunc

比對兩張圖的 hash 部份,雖然花費的時間相差不大,但是由perf stat/top可以看出這應該是 cache-miss 和 malloc 花費的時間剛好互相彌補而已,兩個應該沒有直接關係。

嘗試4 使用 trie 資料結構

實做前預想可能得到的結果是

  • entry size 大幅度增加 -> cache-miss 提高 -> append()花費時間較多
  • findName() 時間大幅度縮短,在找 lastName 時複雜度為 O(n),n 是 lastName 的字元個數
  • 因為想到可能比較不出來 hash 和 trie 在findName()的表現,所以會提昇查詢次數

假設 lastName 只有大小寫英文字母,如果有非英文字母以外字元出現會略過

typedef struct __PHONE_BOOK_ENTRY {
    struct __PHONE_BOOK_ENTRY *nch[52]; //A-Z a-z 共52字母
    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];
} entry;

這代表這個方式只適用在英文上,中文可能不行(字太多)。不過如果替換成注音符號或是羅馬拼音應該是可行的

append()findName()很相似,就是把要查詢/加入的字串一個字元一個字元找下去

節錄append()部份程式碼

while (c = *lastName++) {
    int ind;
    if (islower(c)) ind = c-'a'+26;
    else if (isupper(c)) ind = c-'A';
    else printf("invalid name");

    if (iter->nch[ind] == NULL) {
            iter->nch[ind] = (entry *) malloc(sizeof(entry));
    }   
    iter = iter->nch[ind];
}

這個方法 entry size 為 528 bytes,效能比對如下

發現在查詢量大的時候 hash 和 trie 佔了很大的優勢,畢竟append()只要做一次,而findName()會依使用次數而增加

  • 缺點
    太佔空間,無法負荷太多資料
    append()會花費較多時間

  • 優點
    速度快,某些情況下會比 hash 快

    後來發現並不是會比 hash 還要快,而是查詢的速度會浮動,為什麼會造成這種結果還要再找找看

參考資料

心得與啟發<因為自動飲料機而延畢的那一年>