2017q3 Homework1(phonebook)

contributed by <TsengWen>

Review by maskashura

Hash table採用26個字母為key value,是否有考量key value crush所造成的效能瓶頸?

試著用未排序過的資料做輸入,觀察是否有不同的效能差異

試著解釋加入 hash table 對 append() 所造成的影響

預期目標

[x]準備 GNU/Linux 開發工具
[x]學習使用 Git 與 GitHub
[x]學習效能分析工具
[ ]研究軟體最佳化
[ ]技術報告寫作練習

開發環境

安裝雙系統

作業系統：Ubuntu 16.04 LTS (64bit)
CPU：4-core 2.50 GHz
Memory:8G
Cache
- L1d cache: 32K
- L1i cache: 32K
- L2 cache: 256K

使用 lscpu 可查詢硬體資訊

也可以使用Portable Hardware Locality (hwloc) 取得硬體資訊網址

$sudo apt-get install hwloc
$lstopo

修改terminal prompt

vim .bachrc 中加入

## Set git prompt

function git_branch {
    ref=$(git symbolic-ref HEAD 2> /dev/null) || return;
    echo "("${ref#refs/heads/}")";
}

function git_since_last_commit {
    now=`date +%s`;
    last_commit=$(git log --pretty=format:%at -1 2> /dev/null) || return;
    seconds_since_last_commit=$((now-last_commit));
    minutes_since_last_commit=$((seconds_since_last_commit/60));
    hours_since_last_commit=$((minutes_since_last_commit/60));
    minutes_since_last_commit=$((minutes_since_last_commit%60));
    
    echo "${hours_since_last_commit}h${minutes_since_last_commit}m";
}

PS1="${debian_chroot:+($debian_chroot)}\[\033[01;32m\]\u\[\033[00m\]@\[\033[01;36m\]\h\[\033[00m\]:[\[\033[1;32m\]\w\[\033[0m\]]\[\033[0m\]\[\033[1;36m\]\$(git_branch)\[\033[0;33m\]\$(git_since_last_commit)\[\033[0m\]$ "

vimrc 設定

中英文字間需以空白隔開
課程助教

參考

" 自動縮排：啟用自動縮排以後，在貼上剪貼簿的資料時排版可能會亂掉，這時可以手動切換至貼上模式 :set paste 再進行貼上。
set ai

" 文字編碼加入 utf8。
set enc=utf8

" 標記關鍵字。
set hls

" 只在 Normal 以及 Visual 模式使用滑鼠，也就是取消 Insert 模式的滑鼠，
set mouse=nv

" 顯示行號。
" set number

" 搜尋不分大小寫。
set ic

" 自訂縮排 (Tab) 位元數。
set tabstop=2
set shiftwidth=2

" 字數過長時換行。
set wrap

" 自動切換當前目錄。
set autochdir

" 捲動時保留底下 3 行。
set scrolloff=3

" 摺疊 Folding。
set foldenable
set foldmethod=indent
set foldcolumn=1
set foldlevel=5

" 在 fish 裡相容 Vim 裡的 Neobundle。
set shell=/bin/bash
" 複製模式
set paste

Git 操作

參考網站
Learn Git Branching
GitHub 設定指引
 連猴子都能懂的Git入門指南 | 貝格樂（Backlog）
建立好 Git 帳號後，ssh 設定

$ssh-keygen
$cat ~/.ssh/id_rsa.pub

將~/.ssh/id_rsa.pub　加入到 Github 網站

測試是否成功

$ssh -T git@github.com

結果
Hi TsengWen! You've successfully authenticated, but GitHub does not provide shell access.

個人設定筆記

$ git config --global user.email "benson326789@gmail.com" 
$ git config --global user.name "TsengWen"
git config --global alias.st status
git config --global alias.cm "commit -m"
git config --global alias.last 'log -1 HEAD'

Perf（效能分析工具）

參考網址
Wiki - Linux 效能分析工具: Perf

需要先將 perf 權限打開

$ sudo sh -c " echo 0 > /proc/sys/kernel/perf_event_paranoid"

照著步驟實作了一下，但途中使用到一些指令:

$ uname 顯示作業系統
$ uname -r 顯示release time number 應該就是kernel版本
$ perf top -p <pid> 偵測這個process 每個指令所耗費的CPU cycle
$ perf list 列出可以偵測的event
$ perf state –repeat <num> -e <event> <bin>.對這個執行檔，偵測所指定的event
$ ./phonebook_opt & sudo perf top -p $! 這可以省略寫sleep()再開令一個終端機輸入pid

$./phonebook_orig & sudo perf top -p $!

Samples: 27  of event 'cycles', Event count (approx.): 1019759
Overhead  Shared Object   Symbol
  40.36%  libc-2.23.so    [.] __strcasecmp_l_avx
  14.18%  phonebook_orig  [.] findName
   9.12%  [kernel]        [k] release_pages
   9.07%  [kernel]        [k] unmap_page_range
   4.56%  [kernel]        [k] unlink_file_vma
   4.55%  [kernel]        [k] free_pcppages_bulk
   4.55%  [kernel]        [k] free_hot_cold_page_list
   4.55%  [kernel]        [k] free_hot_cold_page
   4.54%  [kernel]        [k] free_pages_and_swap_cache
   4.53%  [kernel]        [k] _raw_spin_lock_irqsave

Valgrind（分析工具）

參考網站
Memory Leak的問題

$valgrind --leak-check=full [./要測的檔案]

原本main.c

==13294== LEAK SUMMARY:
==13294==    definitely lost: 136 bytes in 1 blocks
==13294==    indirectly lost: 16,034,808 bytes in 117,903 blocks
==13294==      possibly lost: 31,551,320 bytes in 231,995 blocks
==13294==    still reachable: 0 bytes in 0 blocks
==13294==         suppressed: 0 bytes in 0 blocks

參考共筆修改 main.c內

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

修改成






while(pHead->pNext){
    entry *next = pHead->pNext;
    pHead->pNext = next->pNext;
    free(next);
}
free(pHead);

程式碼縮排為四個空白鍵，請修正
課程助教

OKTsengWen

再次測試

==13448== All heap blocks were freed -- no leaks are possible

Gnuplot（繪圖工具）

參考網站
- 語法解說和示範

效能分析 - 優化前

程式碼: phonebook

make run

size of entry : 136 bytes
execution time of append() : 0.068333 sec
execution time of findName() : 0.004988 sec

make cache-test

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

         4,733,809      cache-misses              #   93.978 % of all cache refs      ( +-  0.08% )
         5,037,124      cache-references                                              ( +-  0.14% )
       262,003,100      instructions              #    1.45  insn per cycle           ( +-  0.02% )
       180,647,686      cycles                                                        ( +-  0.17% )

       0.060747507 seconds time elapsed                                          ( +-  2.18% )

效能分析 - 優化後

方法一

由於筆電為L1-cache -32Kbit，原本entry結構136Byte，
- 計算能放入cache數量
  
  $\frac{32 \times 1024}{136 \times 8} = 30.1$
將結構化簡，將搜尋用不到的另外弄成指標，希望能再cache放入多一點entry來減少cache miss。
- 計算能放入cache數量
  
  $\frac{32 \times 1024}{32 \times 8} = 128$

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

typedef struct __PHONE_BOOK_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;

修改結果
- cache-miss 下降至70%
- 所花時間也略微下降

size of entry : 32 bytes
execution time of append() : 0.034991 sec
execution time of findName() : 0.004266 sec

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

         1,595,412      cache-misses              #   70.061 % of all cache refs      ( +-  0.12% )
         2,277,159      cache-references                                              ( +-  0.12% )
       244,541,000      instructions              #    2.07  insn per cycle           ( +-  0.02% )
       118,021,002      cycles                                                        ( +-  0.08% )
       0.038790988      seconds time elapsed                                          ( +-  0.52% )

方法二 - 加上hash

想法：依照26個字母，做26個Linked list，做搜尋時根據開頭做搜尋。

加上後，修改結果

size of entry : 32 bytes
execution time of append() : 0.032146 sec
execution time of findName() : 0.000010 sec

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

           510,975      cache-misses              #   74.046 % of all cache refs      ( +-  0.21% )
           690,076      cache-references                                              ( +-  1.02% )
       188,311,835      instructions              #    1.83  insn per cycle           ( +-  0.03% )
       102,881,580      cycles                                                        ( +-  0.35% )

       0.037837179 seconds time elapsed                                          ( +-  7.15% )

astyle

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

style決定程式中，大括弧{ }的擺放方式。
indent=space決定程式中，每個縮排為設定數值的倍數。
indent-switches讓程式中 switch-case 的 case statements 對齊
suffix=none不保留格式化前的文件

2017q3 Homework1(phonebook)

Review by maskashura

預期目標

開發環境

安裝雙系統

修改terminal prompt

vimrc 設定

Git 操作

Perf（效能分析工具）

Valgrind（分析工具）

Gnuplot（繪圖工具）

效能分析 - 優化前

效能分析 - 優化後

方法一

方法二 - 加上hash

astyle

Review by `maskashura`