Try   HackMD

2016q3 Homework1 (phonebook)

contributed by <yenWu>

這次的目標會放在減少 append()時間 和 挑戰題 還有修改 hash function

Code Review: Mar 8, 2016

開發環境

  • 作業系統： Ubuntu  14.04  LTS （64 bit）
  • CPU：4-core  2.16 GHz
  • Memory：4G
  • Cache：
    • L1 data : 24kB
    • L1 instruction : 32kB
    • L2 : 1024kB

使用 lscpu 和 sudo lshw 可看到硬體資訊

學習使用 Github

先前按照老師給的作業指示跟著操作，這次有稍微閱讀一下相關資訊，並且嘗試看看強大的回復功能，和了解一下add的真正意義

  • git init    建立目錄 .git
  • git status    確認現在所有檔案的狀況
  • git add 檔名     追蹤此檔案
  • git commit    確認檔案並snapshot（有點像暫時存檔）
  • git remote add <nickname> <repository-URL>    連結遠端的repository並給他取代稱
  • git push <nickname>    把檔案上傳到指定的repository

大概對git的原理和用法有比較基本的認識，但尚未看到branch那邊（有先看fork）

之後會補上SSH的過程(之前都先做完了，沒紀錄到 = =)

Vim設定

自己寫入設定檔

$ vim ~/.vimrc`
  • vimrc  means Run Commands

參考資料：

astyle 和 pre-commit hook

我使用我自己比較偏愛的astyle格式

$astyle --style=kr --indent=spaces=4 --indent-switches --suffix=none *.[ch]

在 pre-commit hook 我卻沒有成功，我有給 hook/ 底下一個soft link，但我在 commit 時卻沒有偵測我亂寫的格式

考慮到團隊合作，請配合原本的指示，使用一致的 coding style jserv
我已經做了修改了。彥寬

這邊要說明一下 pre-commit，這邊我搞錯了一件事，就是 softlink 會以 source 會以 target的所在目錄當作相對位置的起點，其實只要 ll你就會發現，softlink 顯示就是這樣，所以要去看target的link。
ln -sf ../../scripts/pre-commit.hook .git/hooks/pre-commit

效能分析工具 Perf

  • echo -1 > /proc/sys/kernel/perf_event_paranoid
  • $ ./yourapp & sudo perf top -p $! 這可以省略寫sleep()再開令一個終端機輸入pid

Makefile 語法

當只有輸入make時只會進行第一個target，但要執行target前，必須先有後面的相依檔案，如果找不到就會再往下面的target找，把所有相依檔按找完才會執行下面的commond，首先先註記一些較少用到的gcc用法

  • 不是依序！應該說每個 target 被 satisfied 後，就會執行指定命令，若回傳值非 0 就會失敗

  • gcc後面可以加上:

    • -E : 只進行前處理，不進行編譯，結果由 console 直接輸出
    • -C : 進行前處理時保留註解
    • -S : 產生組合語言程式碼 (.s)
    • -c : 只編譯不進行連結 (產生 .o 檔)
    • -I : 指定 INCLUDE PATH
    • -L : 指定 LIBRARY PATH
    • -llibrary – 指定要連結的函式庫
    • -Dname : 定義 macro，同 #define
    • -Uname : 解除 macro 定義，同 #undef

參考資料:

  • GCC
    注意: GCC 是 compiler driver

Makefile 裡頭使用 gcc 的示範:

CC = gcc
INC = -I ./include
OBJ = main.o op.o

test: ${OBJ}
	$(CC) -o $@ ${OBJ}%.o: %.c
	${CC} $< ${INC} -c&nbsp;
.PHONY: clean
clean:
	rm -f test ${OBJ}
  • Makefile 基本語法
目標檔案 (Target)： 相依檔案 (Prerequisites)
	指令 (Commond)

比方說:

test: main.c op.c&nbsp;
	gcc main.c op.c -o test

其中

  • CC=gcc  變數asign
  • ${CC} 取出CC裏面存放的值
  • %.o : %.c 這是像C++的Template的用法，指令要尋找main.o時，%.o = main.o %.c = main.c
  • $@ = Target
  • $< = First  Dependent File

參考資料：

Gnuplot

這邊我用老師提供的 runtime.gp 當學習範例:

reset # 這是清除前面的設定
set ylabel 'time(sec)' # 將y軸的label寫上 'time(sec)'
set style fill solid
set title 'perfomance comparison' # 設定 title name
set term png enhanced font 'Verdana,10' # 設定 png 為輸出格式
set output 'runtime.png' # 設定output file name

plot [:][:0.150]'output.txt' using 2:xtic(1) with histogram title ’original’, \&nbsp;&nbsp;
    using ($0-0.06):($2+0.001):2 with labels title ' ', \
    using 3:xtic(1) with histogram title 'optimized', \
    using ($0+0.3):($3+0.0015):3 with labels title ' '

最近想要再使用時發生這個問題，進入gnuplot 時畫不出 sin(x) (我想要直接顯示在螢幕)，然後看到 terminal type set to ’unknown’，經過查詢得知是抓不到連結，所以方法之一就是更新gnuplot到version 11

參考資料

案例分析：Phonebook

未優化版本

$ make run

size of entry : 136 bytes
execution time of append() : 0.127555 sec
execution time of findName() : 0.015991 sec

$perf stat --repeat 5 -e cycles,instructions,cache-references,cache-misses,branch-instructions,branch-misses ./phonebook_orig

Performance counter stats for ’./phonebook_orig’ (5 runs):
447,819,700 cycles ( +-  1.62% ) [34.16%]
273,082,321 instructions # 0.61  insns per cycle ( +-  0.75% ) [51.33%]
 11,489,866 cache-references                                              ( +-  0.81% ) [52.31%]
3,459,780 cache-misses # 30.112 % of all cache refs ( +-  1.59% ) [50.76%]
 48,161,780 branch-instructions ( +-  0.58% ) [32.11%]
5,558,063 branch-misses # 11.54% of all branches ( +-  0.71% ) [32.97%]

0.182893634 seconds time elapsed                                          ( +-  0.92% )
  • $perf stat -r 10 -e cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-store-misses,L1-dcache-prefetch-misses,L1-icache-load-misses ./phonebook_orig

Performance counter stats for ’./phonebook_orig’ (10 runs):
 3,508,579 cache-misses # 29.720 % of all cache refs ( +-  0.25% ) [49.65%]
11,805,580 cache-references ( +-  0.74% ) [51.67%]
1,347,036 L1-dcache-load-misses ( +-  0.69% ) [50.75%]
<not supported> L1-dcache-store-misses  
<not supported> L1-dcache-prefetch-misses
419,659 L1-icache-load-misses ( +-  3.05% ) [48.73%]

0.186848163 seconds time elapsed ( +-  0.60% )

優化版本:

減少 entry 空間

  • 因為搜尋電話簿時，沒必要先把他的資料全部讀到 cache 裡，只需要讀 lastName 就好，所以我就把詳細資料跟 lastName 分離開來找 。其中 append() 和 findName() 直接複製orig的

  • phonebook_opt.h

typedef struct phonebooK_detail {
    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];
    detail *pDetail;
    struct __PHONE_BOOK_ENTRY *pNext;
} entry;
  • 第二次寫我居然犯了一個笨點，就是直接放detail的 struct 而不是 pointer 難怪結果怪怪的，更新新的圖表，結果也差不多

時間上都有減少，但是append不應該減少才對，我猜想是我再append是貼原本code所以他只會malloc entry的空間，但沒有malloc detail的空間

  • 我還沒看完老師的範例就先做了，後來有看到不需要malloc的原因
  • 並且發現我並沒有真正看懂題目的意思，append是要建立一個dictionary所以我並不需先malloc

附上detail 也malloc後的圖，結果是append()增高,且findname()也因為這樣而升高了

  • 將原本一個的 malloc變成兩個，會對系統造成負擔

這次去 dictionary 看，發現搜的字根本不在，本來有再考慮要用 多個東西一起搜讓搜尋更有保有區域性，看來接下來的方法應該要朝分類進行。

降低 append() 時間開銷：延後fgets完newline的替換 + 延後補上 detail

利用 fgets的特性，man 完就會發現它會在讀到 newline 或是 EOF停下來並且在他們後面會多種一個 '\0'，接著的 code 就是把 newline 變成 '\0'，我們延後替換 newline，我操作只比較前面的長度，真的找到了再把 newline 換掉即可。

  • main.c
while (fgets(line, sizeof(line), fp))
e = append(line, e);
  • phonebook_opt.c
/* because the assert test, we can’t modify the strcut*/
if (strncasecmp(lastname, pHead->lastName, len) == 0 &&
    (pHead->lastName[len] == ’\n’ ||
     pHead->lastName[len] == ’\0’)) {
    pHead->lastName[len] = ’\0’;
   return pHead;

原本的程式是將字典直接建好，這邊我們先建檢索，等到findName找到時我們再去補上他的資料，這樣也能減少 append()。

  • 這邊紀錄一下一個 bug strcpy-sse2-unaligned.S not found 這只有在 gdb 時會看到，簡單來說就是 strcpy很像有問題，而外面就是直接 core dump，而這個問題即是我的 assert 沒考慮清楚，順帶一提 assert並沒辦法做到即時回傳，因為我的 bug 是出在 assert裏面的 function 所以他會直接 core dump 而不會等到你 assert，簡單說就是我忘了我已經我已經替換了 newline 所以我第二次 call findname 就找不到結果了。

我們應該使用 backtrace 來對付這個，因為他沒有指名是哪個 str出問題。(gdb) 彥寬

Multi-thread version

不說了，悲劇，append大概 0.36 …
這邊我使用mutithread在append上

mmap() preload file to memory space

thread 1:

but thread 4 …:

…thread 8 …:

I notice that more thread and more append() time shake.Yen-Kuan Wu
findName() time will decrease because we use the cross append(), and the benchmark only measure the time we find zyxel. Yen-Kuan Wu

  • 終於找到原因了，原因就是 muti-thread 上使用了 malloc()，由於 malloc system call，所以是根本無法平行化的地方。

使用 "Pthread" + "file alignment" + "mmap" + "簡易 memory pool" + 檢索省略尋找 `\n`

thread 1:

thread 2:

thread 4:

thread 8:

thread 16:

  • 這邊很清楚的看出來，太多 thread 會變慢沒問題，但奇怪的是 1 2 4的差別卻不大，我也開啟我自己設定的 debug 模式，發現大加搜尋的數目都是正確的，但問題出在我是使用 sync 的方式，所以假如有一個thread跑比較慢，那總體時間也就會比較慢。

  • 檢索省略尋找 `\n`

這就是我上 降低 append() 時間開銷：延後fgets完newline的替換 + 延後補上 detail的作法

Pthread用法

這邊很單純的，我是打算讓大家先各自串一個 link list 之後我再把他連起來，但一開始成效真的是讓人吐血…，經過老師指點，我知道了 fgets 是一個 blocking IO所以就算我開再多 thread，也只是白搭，老師提示我可以用 mmap()。

mmap() + file alignment

首先想要使用 mmap的動機就是 fgets這個 blocking IO，讓程式更可以平行化，但是由於我們不知道每個字元的 offset，所以我先將 file整理成 16 char alignment，之後再使用 mmap()，就能夠直接 offset 16到下一個 word了。

簡易 memory pool

做完面的東西後，發現效能還是沒有多好，而且跟 thread 的使用量不成正比，找了很久很久…，之後才發現是 malloc()再搞鬼，因為 malloc 也屬於 system call，所以他也是無法平行化的東西，所以我們再使用了簡易的memory pool。

為什麼講簡易呢？ 因為我就直接 malloc 開linklist 會用到的總空間，然後交叉串聯，當然這不是正統的方式，老師有貼給我正確的 memory pool 用法，他將會是我下一個改善的目標。

改善空間

說白了就是 ansyc，由於我是使用 sync的方式，所以 join 一定要等慢的那位，造成我 4 個thread 只要有一個太慢就會拖累總體時間。

使用 Hash function

Hash 42737 bucket

Hash bucket 我使用老師例子裡的 42737 當作第一次測試，而結果不如預期，append() time 太高了，而我也試圖去找一下問題

「程式輸出的文字訊息」請勿使用圖片表示，請改由文字貼上課程助教
不好意思這是從我的 Hackpad貼過來的，年代久遠= =，我記得老師也有提醒過我，我不會再犯的，感謝。彥寬

  • ./phonebook_opt & sudo perf top -p $!

  • 我找到了是在這邊，也就是太多碰撞，可能要調整bucket的大小或者直接紀錄最尾巴
{
    while( ep->pNext != NULL) {
    ep = ep->pNext;
}

新增 pLast 減少找尾巴時間

  • hash_bucket
typedef struct _hash_bucket {
    entry *pNext;
    entry *pLast;
} hash_bucket;

Execution time
size of entry : 32 bytes
execution time of append() : 0.168732 sec
execution time of findName() : 0.000003 sec
  • 還需要繼續改進:

  • hash function 時間過長，要改進

  • append()

寫到一半有bug，嘗試使用了gdb

$ gdb ./phonebook.opt

就會進入gdb的shell，之後再輸入b(breaking)再來輸入run就能看到我的memory dump掛在那一個function

(gdb) b
(gdb) run

ntu gdb 筆記

man index 有這個func

tags: yenWu phonebook sysprog21
Last changed by 
 
Yen-Kuan Wu
0
2184
Published on HackMD