# 2016q3 Homework1 (phonebook)
contributed by <`TempoJiJi`>
###### tags: `TempoJiJi` `phonebook` `sysprog21`
## 預期目標
這次會將目標放在挑戰題上，當然基本的需求也會全部再做一次復習。
附上之前的共筆：[2016q1phonebook](https://embedded2016.hackpad.com/ep/pad/static/LjeSJRa0vEO)
* 準備 GNU/Linux 開發工具
* 學習使用 Git 與 GitHub
* 學習效能分析工具
* 研究軟體最佳化
* 挑戰題
* 縮減append()時間
* fuzzy search
* 回顧輸入的資料分佈，指出其中不合理的設計，並且著手改進
## 開發環境
* Ubuntu 16.04 LTS
* L1d cache: 32K
* L1i cache: 32K
* L2 cache: 256K
* L3 cache: 3072K
* Architecture: x86_64
* CPU op-mode(s): 32-bit, 64-bit
* Byte Order: Little Endian
* CPU(s): 4
* Model name: Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz
>> 補上電腦硬體環境描述，像是 CPU, cache, main memory 等資訊，這樣日後重現實驗時，才有參考 [name=jserv]
---
首先測試程式效能：
```
size of entry : 136 bytes
execution time of append() : 0.076191 sec
execution time of findName() : 0.005781 sec
```
```
Performance counter stats for './phonebook_orig' (100 runs):
967,794 cache-misses # 87.985 % of all cache refs ( +- 0.37% )
1,099,949 cache-references ( +- 0.28% )
260,680,693 instructions # 1.48 insns per cycle ( +- 0.02% )
175,878,472 cycles ( +- 0.26% )
0.071930206 seconds time elapsed ( +- 0.79% )
```
## 修改結構大小降低cache miss
```clike=
typedef struct __PHONE_BOOK_DETAILS {
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];
} Details;
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
struct __PHONE_BOOK_ENTRY *pNext;
Details *details;
} entry;
```
結構大小減到32，而cache miss也大幅度降低
```
size of entry : 32 bytes
execution time of append() : 0.042138 sec
execution time of findName() : 0.002712 sec
```
```
Performance counter stats for './phonebook_orig' (100 runs):
115,790 cache-misses # 29.443 % of all cache refs ( +- 0.89% )
393,264 cache-references ( +- 0.64% )
243,880,933 instructions # 1.93 insns per cycle ( +- 0.02% )
126,628,229 cycles ( +- 0.47% )
0.051748813 seconds time elapsed ( +- 0.67% )
```
## 實做Hash降低findname時間
==Table Size 爲 42737，選用質數碰撞的幾率較小==
Table的結構：
```clike=
typedef struct _HAST_TABLE {
entry **table;
} hash_table;
```
爽指標的用意爲：將碰撞的資料用linkedlist鏈接起來
Hash function：
```clike=
int hash(char *str)
{
unsigned int hash_value = 0;
while(*str)
hash_value = (hash_value << 5) - hash_value + (*str++);
return (hash_value % SIZE);
}
```
這裏使用的是BKDR hash function
## 使用PThread降低append時間
觀察append：
```clike=
while (fgets(line, sizeof(line), fp)) {
while (line[i] != '\0')
i++;
line[i - 1] = '\0';
i = 0;
append(line,my_hash_table); //for OPT
}
```
```clike=
void append(char *line)
{
entry *new_entry;
int hash_value = hash(lastName);
new_entry = (entry *) malloc(sizeof(entry));
/* Creating entry list by hash table */
strcpy(new_entry->lastName , lastName);
new_entry->pNext = my_hash_table->table[hash_value];
my_hash_table->table[hash_value] = new_entry;
}
```
由上述的程式碼中，可以確認每筆資料在append時能夠獨立處理，所以能夠使用多執行緒來進行append。
上網爬了一下文，發現POSIX pthread在讀檔時會確保每個執行緒是獨立安全的，所以不需要利用mutex_lock等類似的機制（但是要確保function可以獨立進行），且會將檔案以==byte==來進行分割。
[參考資料](http://stackoverflow.com/questions/18642730/reading-file-using-multi-threads)
之後就是實做方面，以下是我的code：
```clike=
#if defined (OPT)
void work(){
char line[16];
int i = 0;
while(!feof(fp)){
if(fgets(line,sizeof(line),fp)!=NULL){
while(line[i] != '\0')
i++;
line[i-1] = '\0';
i=0;
append(line);
}
}
}
#endif
int main(){
...
#if defined(OPT)
clock_gettime(CLOCK_REALTIME, &start);
pthread_t Thread[MAX_THREAD];
for(i=0;i<MAX_THREAD;i++)
pthread_create(&Thread[i],NULL,(void*)work,NULL);
for(i=0;i<MAX_THREAD;i++)
pthread_join(Thread[i],NULL);
...
}
```
執行結果：
```
size of entry : 32 bytes
execution time of append() : 0.170208 sec
execution time of findName() : 0.000000 sec
```
append時間大幅度飆高...原因還需要在研究看看
爬了一下文，原因是受到I/O的限制，就算分成再多的執行緒效能也不會好到哪裏去，而且還有可能會降低效能。[參考資料](http://stackoverflow.com/questions/1470210/how-to-improve-performance-of-file-reading-by-multiple-threads)
>> 使用 `mmap()` 來存取資料，而非 `read()`，你需要先撰寫一個工具，將文字檔案轉換為 binary representation，之後再用 `mmap()`，這樣才能省去非必要的效能損失 [name=jserv]
---
## 利用mmap改善效能
存储映射I/O(Memory-mapped I/O)使一个磁盘文件与存储空间的一个缓冲区相映射。当从缓存区中取数据，就相当于==读文件中的相应字节==。与此类似，将数据存入缓冲区，相应的就自动地写入文件。==这样就可以在不使用read和write的情况下执行I/O==。普通文件被==映射到进程地址空间后==，==进程可以像访问普通内存一样对文件进行访问==。
優點：
* 操作文件就像操作内存一样，，因此不需要多餘的system call、context switch等，适合于对较大文件的读写
缺點：
* 可能會有多餘沒使用到空間，假設文件大小爲10bytes，那麼（假設每一次mapping size都4096）4096-10=4086bytes的空間就會浪費掉
先來點測試：
```clike=
char *s;
unsigned int size;
struct stat buf;
/* O_RDONLY = read only */
int fd = open (DICT_FILE,O_RDONLY);
/* Get the size of the file */
int status = fstat(fd, &buf);
size = buf.st_size;
/* Start mapping */
clock_gettime(CLOCK_REALTIME, &start);
s = mmap (0, size, PROT_READ, MAP_PRIVATE, fd, 0);
int k = 0;
for(int i = 0; i < size; i++){
line[k] = s[i];
if(s[i] == 10){ //newline
line[k] = '\0';
k = 0;
e = append(line,e);
}
else
k++;
}
```
執行結果：
可以看到append的時間降低了不少。由這個結果就可以發現，read()的system call等機制花了不少時間。
參考資料：
* [共享内存mmap介绍](http://yingshin.github.io/c/cpp/2016/01/07/mmap)
---
## BK TREE
這裏先介紹 ==Levenshtein Distance （編輯距離）== ：
指一個字串轉換成為另外一個字串所需的最少「編輯操作」次數，所謂的編輯操作可以是替換字元、插入字元、刪除字元，是個用來衡量兩字串相似度的重要指標。
```
例如將`kitten`轉成`sitting`：
step 1: kitten → sitten (substitution of "s" for "k")
step 2: sitten → sittin (substitution of "i" for "e")
step 3: sittin → sitting (insertion of "g" at the end)
會經過3次編輯操作，所以編輯距離爲 3
```
而BK tree的構造就是以編輯距離來計算形成的。
在append時計算字串跟當前節點的編輯距離，然後再繼續往下尋找計算，直到空節點爲止，才將字串加入結構。
這樣的結構可以省下不少findname的時間，但在append時每次都需要往下尋找直到空節點，所以時間會較長。
實做方面：
```clike=
/* 計算編輯距離 */
int dist(char *a,char *b)
{
int count = 0;
int max = MAX(strlen(a),strlen(b));
int min = MIN(strlen(a),strlen(b));
for(int i=0; i<max; i++) {
if(a[i] != b[i] || i >= min)
count ++;
}
/* MAX_SIZE爲子節點的數量 */
return count % MAX_SIZE;
}
```
```clike=
void append(char lastName[],entry *e)
{
while(e != NULL) {
int distance = dist(lastName , e->lastName);
if(e->pNext[distance] != NULL)
e = e->pNext[distance];
else {
e->pNext[distance] = (entry *) malloc(sizeof(entry));
e = e->pNext[distance];
strcpy(e->lastName, lastName);
/* Initialize */
for(int i=0; i<MAX_SIZE; i++)
e->pNext[i] = NULL;
return;
}
}
}
```
結果：
```
MAX_SIZE = 16
size of entry : 152 bytes
execution time of append() : 0.645208 sec
execution time of findName() : 0.000014 sec
Performance counter stats for './bk_tree' (100 runs):
2,564,592 cache-misses # 33.193 % of all cache refs ( +- 0.48% )
7,726,256 cache-references ( +- 0.10% )
2,629,117,840 instructions # 1.57 insns per cycle ( +- 0.17% )
1,675,390,835 cycles ( +- 0.10% )
0.654240669 seconds time elapsed ( +- 0.12% )
```
比較不同MAX_SIZE的效能：
```
MAX_SIZE = 8
size of entry : 88 bytes
execution time of append() : 0.665988 sec
execution time of findName() : 0.000016 sec
MAX_SIZE = 4
size of entry : 56 bytes
execution time of append() : 0.654146 sec
execution time of findName() : 0.000014 sec
MAX_SIZE = 2
size of entry : 40 bytes
execution time of append() : 0.699443 sec
execution time of findName() : 0.000014 sec
```
參考資料：
[Levenshtein Distance (編輯距離)](https://charles620016.hackpad.com/ep/pad/static/Japi4qFyAzt)
---
## Fuzzy Seach
支援 fuzzy search，允許搜尋 lastName 時，不用精準打出正確的寫法
比方說電話簿有一筆資料是 McDonald，但若使用者輸入 MacDonald 或 McDonalds，也一併檢索出來。
這裏的實做方面也是利用編輯距離來進行，以編輯距離的大小來進行搜尋
```clike=
void findName(char lastname[], entry *pHead)
{
int distance;
char buf[MAX_LAST_NAME_SIZE];
while (pHead != NULL) {
distance = dist(lastname , pHead->lastName);
if(distance <= 2)
printf("intput=%s , %s , dist=%d\n",lastname,pHead->lastName,distance);
pHead = pHead -> pNext;
}
}
```
將所有編輯距離小於3的資料都列出來
```
以 "douglas" 來進行測試
intput=douglas , dongles , dist=2
intput=douglas , douala , dist=2
intput=douglas , doubles , dist=2
intput=douglas , dougl , dist=2
intput=douglas , douglas , dist=0
intput=douglas , douglass , dist=1
intput=douglas , dougnac , dist=2
intput=douglas , dougnan , dist=2
intput=douglas , dounias , dist=2
size of entry : 32 bytes
execution time of append() : 0.054440 sec
execution time of findName() : 0.022088 sec
```
在這裏想說要加個記錄最小dist的資料，但考慮到如果在真實世界，有太多名字相同且相似的人，那樣列出來的最小dist的資料也會有幾十萬筆，那就有搜尋跟沒搜尋沒什麼差別。但如果再加多幾個詳細資料在details中，那這個fuzzy searching可能就有非常大的作用了。
參考資料：
[Levenshtein Distance (編輯距離)](https://charles620016.hackpad.com/ep/pad/static/Japi4qFyAzt)
---
總結所有效能落差：
優化（mmap 加上 Hash function的優化版本）與未優化版本比較：
Sign in with Wallet
Connect another wallet