Try   HackMD

2018q1 Homework1 (phonebook)

contributed by < AliennCheng >

tags: syshw

Reviewed by workat60474

  • 正好近日也在建立本地server，你的筆記幫了我很大的忙，非常感謝！
  • 在減少struct size降低cache misses的部分，如果能夠提出更加詳盡，從locality of reference等cache特性去說明cache misses下降的原因會更好！
  • Hash funtion 的部分也是，如果能夠透過collision去說明如何影響cache misses的次數會使報告更加詳盡。

前置作業

由於我在這個禮拜上個禮拜才剛買了這台電腦（現在好貴，奉勸大家忍一時省一千），基本上這幾天都在調整環境設定，其中許多程式都需要重灌， Ubuntu 也不例外。

完成前置作業的時候已經是禮拜日了，嗚嗚嗚…

開機碟的製作

主要參考 輕鬆學會 Windows / Ubuntu 雙系統安裝 (簡易教學)，但開機碟的製作我參考 [教學] 製作可開機 USB 隨身碟來安裝 Windows 7/8/10/Vista，使用 Rufus 製作。

在這邊特別要建議和我一樣菜的新手，趁這個機會搞清楚 Rufus 當中各個選項的意義，例如 磁碟分割表 (MBR v.s GPT) 以及 檔案系統 (NTFS v.s. FAT32)，進而選出最適合你的系統的配置。

為什麼這麼說呢？因為我就是疑似在製作開機碟的時候選錯格式，導致我灌好 Ubuntu 後開機的 Grub 直接進到一個 command line interface 的畫面，我還在那邊研究要怎麼進入我的 Ubuntu 作業系統，研究半天一點進展都沒有，最後果斷連著開機碟全部重灌才進入系統選單…

連線設定

然而，好不容易灌好 Ubuntu ，終於登入成功的時候，卻發生了上網失敗的狀況。

原本以為是線路問題，檢查一遍路由器之後感覺應該沒問題，換到 Windows 系統後確認線路正常。
接著開始檢查 PPPoE 設定，由於上一台桌機的網路是中華電信工程師幫忙設定的，於是又花了一些時間研究是不是哪裡設定有誤，在重新設定之後發現我的網路已經可以連上多數網站，但仍有部份網站連不上（包括 Hackmd.io 網域）。

最後轉向研究防火牆 ufw ，原先我只是把它關掉

$sudo ufw disable

此時仍然無法連上 Hackmd.io ，這時候又重新檢查線路及 PPPoE 設定，又經過各種測試皆無效，最後我想說死馬當活馬醫，直接把 ufw 砍了

sudo apt-get remove ufw
sudo apt-get purge ufw

砍掉之後竟然就連上了…
重新安裝 ufw 之後也沒出現問題，連問題出在哪都不知道就解決了…?
以上莫名地花掉我好幾天的時間，嗚嗚嗚…

建立 SSH 伺服器

由於我的筆電容量極為有限（只有 128 GB…），考量到未來的擴充性，我選擇把作業系統灌在家裡電腦，筆電端再透過 SSH 方式連上家裡的伺服器操作。這邊簡短敘述一下我設定的步驟：

Step 1: 申請固定 IP

只要是中華電信的網路都可以免費申請一組固定 IP ，直接到這申請就好，過程很簡單就不贅述。

申請完之後記得改用固定 IP 建立 PPPoE 連線，帳號為下面格式

xxxxxxxx@ip.hinet.net

Step 2: 建立本地 SSH 伺服器

主要參考這裡，Ubuntu 端先安裝 openssh-server

$ sudo apt-get install openssh-server

安裝完後可由下方指令先確認設定值，網路上都建議可將 port 改掉（預設是22），但改的時候要查一下不要和其他正在使用的衝突。

$ sudo gedit /etc/ssh/sshd_config

確認設定無誤後，儘管申請固定 IP 時就應該會知道自己 IP ，但若想要再次確認，可輸入

$ hostname -I

以上就算是完成伺服器的設定了。

Step 3: Client 端建立連線

若是 Windows 系統的話可下載 Putty，打開之候選 SSH 連線輸入 IP 就可建立連線。

而若是 OSX 系統的話，直接打開終端機，輸入以下指令即可建立連線，其中 hostname 即是伺服器的 IP 位址。

$ ssh hostname

理論上完成上述設定就可建立連線，但目前我筆電端在建立 SSH 連線時會連線逾時，如下所示，原因仍不清楚。

Alienn-MacBookPro:~ apple$ ssh 220.134.158.143
ssh: connect to host 220.134.158.143 port 22: Operation timed out

終於找到原因了，原來 Ubuntu 的防火牆預設會擋掉 ssh 連線，只要設定一下允許 ssh 連線就可以了！

$ sudo ufw allow ssh

開發環境

終於可以開工了xD
由於基礎不好，所以這次我打算跟隨 ryanpatiency同學的腳步，站在巨人的肩膀上一步一步完成我的作業。

$ uname -a
Linux alienn-desktop 4.13.0-36-generic #40~16.04.1-Ubuntu SMP
Fri Feb 16 23:25:58 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux

$ lscpu
Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                6
On-line CPU(s) list:   0-5
Thread(s) per core:    1
Core(s) per socket:    6
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 158
Model name:            Intel(R) Core(TM) i5-8400 CPU @ 2.80GHz
Stepping:              10
CPU MHz:               2800.000
CPU max MHz:           4000.0000
CPU min MHz:           800.0000
BogoMIPS:              5616.00
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              9216K
NUMA node0 CPU(s):     0-5
Flags:                 fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single pti retpoline intel_pt rsb_ctxsw tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp

原始結果

尚未修改 phonebook_opt 的輸出結果如下：

$ make plot

initial

$ make cache-test

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

         4,513,850      cache-misses              #   90.072 % of all cache refs      ( +-  0.23% )
         5,011,375      cache-references                                              ( +-  0.07% )
       263,326,586      instructions              #    1.41  insn per cycle           ( +-  0.02% )
       187,377,151      cycles                                                        ( +-  0.11% )

       0.049544563 seconds time elapsed                                          ( +-  0.13% )

站在巨人的肩膀上

首先我繼續跟隨ryanpatiency同學的腳步，參考ryanwang522同學的共筆，參考的過程我儘量參考概念，自己動手，如此一來，經過比較也能知道自己 coding 時有哪些地方可以改進。

仿效ryanwang522

試圖縮減 struct 所佔的空間

觀察原始檔案可發現，在 findName 中只參照到 struct 的 lastName 部份，於是嘗試把 lastName 和其他資料隔開成兩個獨立的 struct ，這部份的編輯我完全沒動 .c 檔，純粹改寫 .h 檔如下























#define MAX_LAST_NAME_SIZE 16
#define OPT 1
typedef struct __PHONE_BOOK_DETAIL {
    char lastName[MAX_LAST_NAME_SIZE];
    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];
} detail;

typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    struct __PHONE_BOOK_ENTRY *pNext;
} entry;

entry *findName(char lastName[], entry *pHead);
entry *append(char lastName[], entry *e);

實驗成果如下

$ sudo make plot

structModified

$ sudo make cache-test

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

           916,028      cache-misses              #   57.283 % of all cache refs      ( +-  0.94% )
         1,599,122      cache-references                                              ( +-  0.06% )
       241,385,144      instructions              #    2.16  insn per cycle           ( +-  0.02% )
       111,662,312      cycles                                                        ( +-  0.13% )

       0.029573474 seconds time elapsed                                          ( +-  0.14% )

可以發現 append 有大約 25% 的效能提升，findName 則有將近 70% ，可見 struct 的大小在 findName 這個逐項比較的過程中有相當顯著的影響。
另一方面 cashe-misses 從原本的 90% 驟減到 57% ，也證明了原本 struct 多餘的部份佔用了太多 cache 而導致 cache-misses 的提升。

後來發現程式無論尋找或輸出都只有參考 lastName 根本沒用到 detail ，於是我就把整個 detail struct 砍了。

使用 Hash Function

首先看到ryanwang522同學採用這個方法，接著發現這部份在作業區就有提供教學了，所以我就沒特別參考他的共筆，打算自己完成這個部份。

該教學底下有篇 Hash function 的比較，這篇文章給了 BKDRHash 非常高的評價，加上作業區已經有提供 BKDRHash 的解析，於是我決定也採用 BKDRHash 。

一開始，我在網路上找到了一份用 C 語言實現 BKDR Hash 的原始碼，後來發現這好像也是 Jserv 老師的學生，老師真是桃李滿天下xD。總之，我把這份程式碼稍加修改過後放進這次的作業裡。

第一次執行的時候，程式慢到我以為當機，經過簡單的 trace 之後得知是 hash table 的 size 太小，剛 clone 的時候只有 12 ，難怪直接卡在那裡，我首先嘗試把 size 改成 2 的 16 次方，也就是 65536，這次雖然也是不夠快但至少跑得動了，成果如下：

$ sudo make plot

hash_table_ver1

$ sudo make cache-test

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

         5,878,092      cache-misses              #   51.049 % of all cache refs      ( +-  1.39% )
        11,514,554      cache-references                                              ( +-  0.07% )
       490,407,979      instructions              #    1.01  insn per cycle           ( +-  0.02% )
       483,626,637      cycles                                                        ( +-  0.66% )

       0.127340529 seconds time elapsed                                          ( +-  0.70% )

可以看出這時候所有的時間都花在建立 Hash Table 上，findName 所花的時間已經趨近於 0 了，接著就是要試著降低建立 Hash Table 的時間，目標為至少和建立 linked list 差不多。

改良如下：

  1. 首先我發現 ryanwang522 同學的 Hash Function 是錯的，這個錯誤和我copy參考的原始碼，以及這篇解析裡的範例的錯誤一樣，他們的 hash value 計算式為
    while(*str)
        hash = hash * seed + (*str++);

然而 BKDR Hashing 中，Seed 值的用意在於作為隔開各個字元的加權值，意即計算式應為

    while(*str)
        hash += hash * seed + (*str++);

經過這個修正，理論上可以大幅降低 collision，因為原本的 Hash 值等於只是取最後一個字元而已。

重新思考過原始程式的邏輯後發現是我自己邏輯上的誤會，每次計算 hash 時都會將前面計算完的 hash 往前挪，所以原本是沒有問題的。(Github 上稍後會更新)

  1. 接著我大致看了一下字典裡的字，裏面的單字全部都是小寫，且不超過 15 字元。
    全部都是小寫代表每個字元的範圍在 ASCII code 上為 97 ~ 122，因此我的 seed 選擇取最接近且不小於 26 且為 2 的次方減 1 的奇數（這部份可以參考 BKDR Hashing 解析），也就是 31。
    不超過 15 字元代表 Hash value 最多為 15 * 31 + 122，再扣掉前面 96 個位置不會被第一個字元佔用，也就是可以作為最後字元所超出的餘數對應，因此我的 Hash Table size 選擇取 512，這樣應該是最有效率的取法。

  2. 我參考的原始碼在建立 Hash Table 時，在 chaining 之前還先查找了一次 table 已確認沒有重複 data，已知不會有重複單字的情況下省略這個步驟可以大幅減少花費時間。

改良成果如下：

$ sudo make plot

hash_table_ver2

$ sudo make cache-test

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

         3,031,633      cache-misses              #   69.065 % of all cache refs      ( +-  0.28% )
         4,389,517      cache-references                                              ( +-  0.06% )
       396,988,087      instructions              #    1.76  insn per cycle           ( +-  0.02% )
       226,077,580      cycles                                                        ( +-  0.08% )

       0.059652025 seconds time elapsed                                          ( +-  0.09% )

耗費時間看起來已經沒什麼問題了，但 cache-misses 高達 69% ？？ 為什麼…

為了解決上述問題，我 clone 了上面提到的兩位同學的 code 來研究，首先我發現 ryanwang522 同學所建立的 hash chain 應該是錯的，因為他用到老師給的 append 函式卻沒有保留 linked list 的首項，這樣會導致隨著 node 增加而丟失前面的 node。

接著我參考了 ryanpatiency 同學的 code ，他也是用上述方法而且有確實保留 pHead，並且採用陣列儲存 hash table ，於是我仿效了他的方法改良了我的 code 之後，結果如下：

$ sudo make plot

hash table ver 3

$ sudo make cache-test

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

         1,401,546      cache-misses              #   38.182 % of all cache refs      ( +-  0.77% )
         3,670,715      cache-references                                              ( +-  0.06% )
       269,277,024      instructions              #    1.57  insn per cycle           ( +-  0.02% )
       171,435,761      cycles                                                        ( +-  0.17% )

       0.045110686 seconds time elapsed                                          ( +-  0.17% )

改良成功！雖然沒有到 ryanpatiency 同學的 21% 那麼低，但已經在可以接受的範圍了，其他應該只是參數調整問題。

從這次修正可以發現，用不同方式建 hash table 效率大不同，原先我建了一個 hash table 的 struct 並不斷地拿新的 node 插在對應 bucket chain 的最前面，這種方法會一直叫用到整個 hash table，佔用了極大的 cache 空間。後來改成用陣列方式存 hash table ，每次只會叫用相對應的 bucket ，這大大地降低了 cache miss 的次數。

參考資料

如何寫一個 git commit message
連猴子都能懂的 Git 入門指南
makefile 心得、教學
簡單學 makefile：makefile 介紹與範例程式
ryanpatiency同學的共筆
ryanwang522同學的共筆

問題紀錄與解答

參考了ryanpatiency同學的共筆後，看到他把寫作業過程中遇到的問題全部整理在後面，並把檢討後的結果一併紀錄，我覺得這個作法非常好，不僅可以提醒自己避免重複犯錯，遇到類似的問題時也可以快速地找到之前的解決辦法參考。

一開始我直接 clone sysprog 底下的 phonebook，但在 summit 時有權限問題，才發現應該要從 fork 過來自己帳號底下的那一份 clone 到 local ，但就在我重新 clone 後，新的 phonebook file 竟然是 read-only，想刪也刪不掉，發生什麼事了？

  • 我不確定是不是我在下 Git 指令時有錯誤，有可能是因為我一開始用 Git 通訊協定 clone 下來的緣故，這部份等整份作業告一段落再回頭來驗證。
  • 解決辦法：我用 sudo rm -rf phonebook/ 把整個 file 移除，重新用 SSH 通訊協定 clone 下來就可以編輯本地端的檔案了。

有沒有可能你 clone 下來的時候不小心下了 sudo ? Chen WeiThu, Mar 8, 2018 10:40 PM

感謝回覆，不過我 google 了一下，找到這篇，如果我沒理解錯的話，我如果下 sudo 應該是連 clone 都沒辦法才對，但是我的狀況是 clone 下來之後沒有權限修改，所以我猜測應該不是 sudo 的問題。 AliennCheng

參考了 Git - 協議這篇文章後，裏面有提到：SSH 也是唯一一個同時支持讀寫操作的網路通訊協定。另外兩個網路通訊協定（HTTP 和 Git）通常都是唯讀的，確認是通訊協議的問題。 AliennCheng

#if defined(__GNUC__)
    __builtin___clear_cache((char *) pHead, (char *) pHead + sizeof(entry));
#endif

在 main.c 中發現以上這段程式碼，為什麼在執行程式前已經清過一次 cache ，現在卻還要再清一次呢？且其中的 __GNUC__ 定義在哪裡呢？

  • 參考這篇 得知這個函式的目的在於清掉該 processor 特定位置的 instruction cache，也就是在把字庫裡的字串連接起來（append）或搜尋字串（findName）之前，確保稍後要用到的 pHead 所對應到的 cache 是空的。
  • 尚未找到 __GNUC__

該函數為 GCC compiler 自行提供的函數 (built-in)，所以這行程式碼必須給 GCC 編譯才可以編進去。 Chen WeiThu, Mar 8, 2018 10:44 PM

感謝魏同學回覆，一開始我還是沒有很了解這段話的意思，查到了這篇What is this #ifdef __GNUC__ about? 之後才了解這個 macro 的意義，結合上面提到那篇簡單來說， __builtin_ 開頭的函式是 GCC compiler 提供的函式，而這個 __GNUC__ macro 則是用來指定 GNU compiler 所設計，也就是只有在使用 GCC compiler 時才會執行裡面的最佳化函式。AliennCheng

    if (pHead->pNext) free(pHead->pNext);
    free(pHead);

在 main.c 中發現原本清掉 linked list 的方法如上，這樣子不是只能清掉前面兩個 node 嗎？

這部份我仍然覺得我的想法沒有問題，原本寫法確實會造成 memory leak，所以我另外寫了一個 function 用來清除 linked list












void free_list(entry *e)
{
    if(e==NULL) return;
    entry *temp;

    while(e!=NULL) {
        temp = e;
        e = e->pNext;
        free(e);
    }
}

原來這部份真的有問題 xD，原始 phonebook 已經做修正了。
經過提交 pull request 的魏同學證實，他是在這邊看到我提出這個問題之後才想到他以前也發現過這個 bug ，只是他當初還不太會用 Git，我也算是功德一件了xD AliennCheng

回答問題

本例選用的 dataset 是否存在問題？

  • 有代表性嗎？跟真實英文姓氏差異大嗎？
    • 還有改進空間，因為真實英文姓氏是不會有不同數量的連續單一字母，然而此字庫的這個特性反而增加了查找的困難度。
  • 資料難道「數大就是美」嗎？
    • 由此範例可知，數大不一定美，甚至還會造成麻煩，我們真正需要的是有效數據，否則也只是 garbage in, garbage out 。
  • 如果我們要建立符合真實電話簿情境的輸入，該怎麼做？
    • 這邊我提供一個資料庫網站 kaggle，註冊就能使用並下載裏面各式各樣的資料
    • 我也順便查了一下真實電話簿名稱，在這
Last changed by 
 
AliennCheng
0
605
Published on HackMD