# 2016q3 Homework 1(phonebook)
contributed by <`Weinux`>
### Reviewed by `believe7028`
- git commit 時可以忽略執行檔(phonebook_hash)
- 可以比較更多的雜湊函式。
- Hash 對資料表增加與刪除的操作會使得程式整體效能下降，也可以增加刪除的方法與效能評估。
- 如果未來資料一直增長，Hash 沒有機制應對而退化成Linked list。
- 如果資料一直增加，記憶體會放置不下。
- 可以加入刪除的功能以符合實際的需求。
## 開發環境
* OS：Lubuntu 15.10
* Linux系統版本: 4.2.0-42-generic
* CPU: Intel(R) Core(TM) i5-2410M CPU @ 2.30GHz
* MEM: 6GB
* Cache:
* L1d cache: 32K
* L1i cache: 32K
* L2 cache: 256K
* L3 cache: 3072K
使用指令：`$ lstopo`可列出機器的 cache 架構。lstopo 由 `hwloc`套件提供
* [感謝Louie Lu同學的問題與Scott Tsai, Champ Yen學長](https://www.facebook.com/groups/system.software2016/permalink/1124571464289024/)
## 開發目標
* 準備 GNU/Linux 開發工具
* 學習使用 Git 與 GitHub
* 學習效能分析工具
* 研究軟體最佳化
## 案例分析：Phonebook
### Makefile
+ Makefile 裡面幫我們整理要編譯哪些檔案,並且輸出成執行檔. 包含使用編譯器的最佳化等級警告訊息與遵循哪種c語言的規格.....等
+ 其中的 -DIMPL="" 是 #define IMPL是什麼.以下的程式碼代表在編譯 phonebook_orig 這個執行檔過程中,IMPL 為"phonebook_orig.h" 這樣在main.c中就可以根據不同的-DIMPL 來#include 不同的.h file 而只需要一個main.c檔案即可。
+ 要注意的是為了顯示出雙引號 " 前面必須加入跳脫符號\
```c=
phonebook_orig: $(SRCS_common) phonebook_orig.c phonebook_orig.h
$(CC) $(CFLAGS_common) $(CFLAGS_orig) \
-DIMPL="\"$@.h\"" -o $@ \
$(SRCS_common) $@.c
```
### main.c
```c=
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <assert.h>
#include IMPL
```
### **Cache Miss**
### 原始版本
+ #### PHONE_BOOK_ENTRY struct
```c=
#define MAX_LAST_NAME_SIZE 16
typedef struct __PHONE_BOOK_ENTRY {
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];
struct __PHONE_BOOK_ENTRY *pNext;
} entry;
```
```text=
size of entry : 136 bytes
execution time of append() : 0.062888 sec
execution time of findName() : 0.006345 sec
```
+ 比較未優化前的append() 與 findName()所執行的時間,
``` text=
Performance counter stats for ./phonebook_orig (100 runs):
2,067,590 cache-misses # 91.407 % of all cache refs
2,263,739 cache-references
263,109,049 instructions # 1.26 insns per cycle
205,633,764 cycles
0.077700382 seconds time elapsed ( +- 1.27% )
```
+ 使用pref 觀察 `./phonebook_orig & sudo perf top -p $!`
* 可以分析出消耗 CPU 週期最多的部份，結果顯示函式 **findName()** 佔了近 20.31％，
```text =
30.50% libc-2.21.so [.] __strcasecmp_l_avx
20.31% phonebook_orig [.] findName
12.21% phonebook_orig [.] main
3.49% libc-2.21.so [.] __strcpy_sse2_unaligned
3.08% libc-2.21.so [.] _IO_getline_info
```
+ 由於搜尋時僅會尋找 lastName
```c=69
assert(findName(input, e) &&
"Did you implement findName() in " IMPL "?");
assert(0 == strcmp(findName(input, e)->lastName, "zyxel"));
```
### 縮小Struct size
+ level 1 cache 有 32 kbit，struct 的大小有 136 bytes，32 * 1024 / (136*8) ＝30.12，若把整個struct entry都丟進 findName() 尋找，level 1 cache 最多也只能放 30 個entry，一共有 35 萬個單字，必定會發生頻繁的 cache miss。
+ 將**entry**內其他資料封裝到另一個結構 **detail**, 並且用指標加入原來的entry 結構中
```c=
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;
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
detail *pDetail;
struct __PHONE_BOOK_ENTRY *pNext;
} entry;
```
+ 結構從136 byte 降為 32 byte, 而且**append()** 與 **findName()** 執行時間也有下降
```text=
size of entry : 32 bytes
execution time of append() : 0.041963 sec
execution time of findName() : 0.002994 sec
```
```text=
Performance counter stats for './phonebook_opt' (100 runs):
369,581 cache-misses # 57.650 % of all cache refs
628,276 cache-references
245,601,976 instructions # 1.66 insns per cycle
154,732,401 cycles
0.057283161 seconds time elapsed ( +- 1.63% )
```
### Hash table
```c=
unsigned int BKDRHash(char *str)
{
unsigned int seed = 131;
unsigned int hash = 0;
while (*str) {
hash = hash * seed + (*str++);
}
return (hash & 0x7FFFFFFF);
}
```
```c=
unsigned int hash(hash_table *hashtable , char *str)
{
unsigned int hash_value = 0;
while(*str)
hash_value = (hash_value << 5) - hash_value + (*str++);
return (hash_value % SIZE);
}
```
###### tags: `phonebook` `cache miss` `Weinux`
Sign in with Wallet
Connect another wallet