# 2017q1 Homework1 (phonebook)
contributed by <`ierosodin`>
[github](https://github.com/ierosodin/phonebook)
### Reviewed by `janetwei`
* 電話簿是否做到動態資料新增和刪除
* 還有其他的方法可以實驗，如：字串壓縮法
* 還未引進符合現實狀況的 data set實驗
## 開發環境
作業系統 : elementary OS loki
`$ lscpu`
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 45
Model name: Genuine Intel(R) CPU @ 3.30GHz
Stepping: 5
CPU MHz: 2101.558
CPU max MHz: 3900.0000
CPU min MHz: 1200.0000
BogoMIPS: 6600.00
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 15360K
NUMA node0 CPU(s): 0-11
## Astyle
To format your file you can execute below command:
`$ astyle --style=kr --indent=spaces=4 --indent-switches --suffix=none *.[ch]`
## 未優化效能分析
`$ perf stat --repeat 100 -e cache-misses,cache-references,instructions,cycles ./phonebook_orig`
```
199,0010 cache-misses # 90.561 % of all cache refs ( +- 0.07% )
219,7433 cache-references ( +- 0.07% )
2,6118,9558 instructions # 1.24 insns per cycle ( +- 0.02% )
2,1139,7062 cycles ( +- 0.38% )
```
`$ ./phonebook_orig & perf top -p $!`
```
29.23% libc-2.23.so [.] __strcasecmp_l_avx
17.38% phonebook_orig [.] findName
10.93% phonebook_orig [.] main
```
## 優化
### 縮減 struct 大小
從 `$ perf top` 中可以發現，程式的熱點在 __strcasecmp_l_avx ，也就是花費許多的時間在比較字串，然而 findName() 中，字串的比較只使用到 entry 結構的 lastName，但程式每次在 cache data 時，卻要 cache 整個 136 bytes 的 entry，這也造成大量的 cache misses ，因此嘗試重寫 entry 的結構，將 append() 與 findName() 不會用到的資料獨立出來，增進程式 cache 時的效能。
```clike=
typedef struct __PHONE_BOOK_INFO {
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];
} info;
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
struct __PHONE_BOOK_INFO *info;
struct __PHONE_BOOK_ENTRY *pNext;
} entry;
```
```
33,4150 cache-misses # 50.126 % of all cache refs ( +- 0.66% )
66,6618 cache-references ( +- 0.20% )
2,4425,0894 instructions # 1.65 insns per cycle ( +- 0.02% )
1,4798,1744 cycles ( +- 0.19% )
```
### 使用 hash function (BKDR)
從 `$ perf top` 中可以發現， findName() 花費了相當多的時間，嘗試在 append() 中使用 hash function ，加速 findName() 的效能。
參考 [Hash function](http://algs4.cs.princeton.edu/34hash) 中的 Hash Tables
>有非常多不同的 hash function，請問是哪一個呢？
>[name=課程助教][color=red]
>>這裡使用了 BKDR Hash Function ，有時間再來比較不同 function 的效能比較XD[name=ierosodin][color=green]
```clike=
int hash_number = 0;
for (int i = 0; i < s.length(); i++)
hash_number = (seed * hash_number + s.charAt(i));
return hash_number %= SIZE;
```
perf stat:
```
45,4762 cache-misses # 31.637 % of all cache refs ( +- 0.52% )
143,7442 cache-references ( +- 0.07% )
3,5411,1494 instructions # 1.51 insns per cycle ( +- 0.15% )
2,3525,5300 cycles ( +- 0.31% )
```
從效能分析圖中可以發現， findName() 的時間有大幅度的下降，不過相對的， append() 必須要額外花費時間。
#### 比較不同 hash table size 對效能的影響
不同的 table 大小，會影響資料的分佈，越大的 size ，可以使每一個 hash number 的 linked-list 變短，加速 findName() 的速度。
這裡以 lastName = odontomous 為例，比較不同 size 對搜尋速度的影響：
| table size | search time |
|:------:|:------:|
|17|0.000267s|
|33|0.000151s|
|997|0.000004s|
|3571|0.000001s|
|9137|0.000001s|
可以發現，當 table size 越大時，點的分佈會越均勻， slot 數下降，而搜尋速度也會更快。
#### 比較使用不同的 hash function
* ELF Hash Function
* P. J. Weinberger Hash Function
* AP Hash Function
* SDBM Hash Function
* RS Hash Function
* JS Hash Function
* BKDR Hash Function
>只看 slot 數好像不容易比較不同方法間的效能差異，沒有找到一個比較適當的量測方式@@[name=ierosodin][color=green]
~~### OpenMP~~
~~在建立 linked-list 時，需要花費許多時間在 for 迴圈，可以利用 OpenMP 進行平行化的處裡，增進 append() 的效能。~~
>append() 若沒有謹慎的使用平行化處理，會造成 race condition ，使 linked-list 的內容發生遺失。[name=ierosodin][color=green]
### Memory pool
:::success
Wikipedia : 預先規劃一定數量的記憶體區塊，使得整個程式可以在執行期規劃 (allocate)、使用 (access)、歸還 (free) 記憶體區塊
:::
>在寫這段筆記前，必須要說... memory pool 太神啦！！！深深體會到，好的記憶體使用，可以大大提升效能[name=ierosodin][color=green]
比起原先在每次需要配置記憶體才使用 malloc() ， memory pool 主要的目的就是先配置好一大串連續的記憶體，之後要使用時再分配。不過在釋放記憶體的部分要非常小心，可以利用 valgrind 作為驗證的工具。
```clike=
m_pool *pool_allocate(int size)
{
m_pool *pool = (m_pool *) malloc(sizeof(m_pool));
pool->head = pool->next = (char *) calloc(1, size);
pool->tail = pool->head + size;
return pool;
}
void *pool_access(m_pool *pool, int size)
{
if (pool->tail - pool->next < size)
return NULL;
void *tmp = pool->next;
pool->next = pool->next + size;
return tmp;
}
void pool_free(m_pool *pool)
{
free(pool->head);
free(pool);
}
```
>這只是比較簡單的 memory pool 實作，如果一開始配置的記憶體大小不夠使用，將會造成 segmentation fault，在此實作中沒有做相對應的處裡。[name=ierosodin][color=green]
從下面的效能比教圖可以發現，使用 memory pool 後，append() 的時間下降許多：
而觀察優化後的 perf 分析可以發現，整體的 cache-misses 數量下降了！
```
13,1139 cache-misses # 29.716 % of all cache refs ( +- 1.66% )
44,1314 cache-references ( +- 0.27% )
2,4768,6310 instructions # 1.78 insns per cycle ( +- 0.21% )
1,3943,8197 cycles ( +- 0.52% )
0.090425028 seconds time elapsed ( +- 1.58% )
```
### GCC optimization
對原程式碼做 compilier 的 -Ofast 最佳化，結果可以發現，我們做的優化已經超越 compiler 啦～
再對所有方法做一次 -Ofast 的最佳化：
## Memory leak
為了確認使用完的 Linked-list 的記憶體空間是否被釋放，利用 valgrind 工具來檢測使用 memory 的狀況。
檢查 phonebook_orig：
`$ valgrind --leak-check=full ./phonebook_orig`
結果：
```
==21434== HEAP SUMMARY:
==21434== in use at exit: 47,586,264 bytes in 349,899 blocks
==21434== total heap usage: 349,906 allocs, 7 frees, 47,596,856 bytes allocated
```
可以明顯看到，程式執行過程中，總共 alloc 了 349,906 次，卻只有釋放 7 次記憶體！
修改 main.c 中釋放記憶體的部份：
```clike=
entry *tmp;
while ((tmp = pHead) != NULL) {
pHead = pHead->pNext;
free(tmp);
}
```
重新檢查：
```
==22359== HEAP SUMMARY:
==22359== in use at exit: 0 bytes in 0 blocks
==22359== total heap usage: 353,476 allocs, 353,476 frees, 11,321,392 bytes allocated
==22359==
==22359== All heap blocks were freed -- no leaks are possible
```
Sign in with Wallet
Connect another wallet