# 2016q3 Homework2 (phonebook-concurrent)
contributed by <`shouchengH`>
# malloc、calloc、alloca 比較
* **malloc** : 向 heap 申請空間，一開始無做初始化 (type為void *，回傳NULL表示無空間)，所以需要 memset。realloc 則是用來調整空間大小，作法為重新宣告一段空間，在搬之前空間到目前空間 (回傳NULL表示ptr為原來位址，否則為新位址空間)，使用free 釋放。 ==void *malloc(size_t size);==
* **calloc** : 類似malloc，將空間初始化設置 0，sbrk則是增加、釋放空間大小，void *sbrk(intptr_t increment); ，increment + 則分配空間，- 則釋放空間， ==void *calloc(size_t nmemb, size_t size);==
* **alloca** : 向 stack 申請空間，所以不需要釋放，因為在某function內宣告，只會存在此function。 ==void *alloca( size_t size );==
* **alloc** : alloc.h 不是一個在ANSI(American Standards Association)的函式庫，其中定義alloca、malloc 等函式。
C99 SPEC中出現 ：
```
extern void *alloc(size_t);
double *dp = alloc(sizeof *dp);
```
alloc function需要回傳一個 大小與宣告一樣的空間 (sizeof *dp -> double 大小)
* **測試結果** ： 分別使用-std=c99、C11、C90 測試alloc 、 aligned_alloc 、 malloc， aligned_alloc 用於C11， C11 SPEC 中定義 void *aligned_alloc(size_t alignment, size_t size); 。 alloc 並無被定義
目前參考這兩篇 :
1. http://stackoverflow.com/questions/9144686/alloca-function-in-c
2. http://stackoverflow.com/questions/32685851/alloc-malloc-and-alloca-whats-the-difference
:::info
* free只需要傳開頭的指標，不需要傳大小，因為malloc如果宣告12byte，他12byte+cookie來紀錄狀況
* 使用 `malloc` 分配出來的每個區塊會有一些管理這些區塊的額外的開銷，稱為 "cookie"，這些額外開銷可能有 4~32 個 bytes，如果你分配的是小區塊，那這些額外開銷就會變得非常可觀
* 如果額外的開銷是 4 bytes，那你每新建一個 4 bytes 的區塊，額外開銷就佔 50%
* [sysconf](https://github.com/c14006078/PracticeMakePerfect/commit/6e3ae2b25a75c6ad11d556838c4a75e7ab738b87)
:::
# 編譯器最佳化
* 編譯器最佳化會造成程式碼順序變動 ， ==int a 表示 alloca i32, align 4== ， 每次存取空間會有load/store ，
* Static Single Assignment : 編譯器每個變數只能被賦值一次，所以會採用再每次賦值時加上一個編號。 如果遇到if else ， 會採用a~3~ = Φ(a~1~, a~2~)，等判斷完才給其值
```
Example 1 ->
int foo() { int foo() {
int a; int a;
a = 0; a1 = 0;
a = 1; a2 = 1;
return a; return a2;
} }
此時第二個foo 可以直接回傳a2
```
* Constant Propagation : 將b以數值代入， 可以少一個load的時間， 是一種 Copy Propagation
```
Example 2 ->
int foo(int a) { int foo(int a) {
int b = 10; int b = 10;
return a + b; return a + 10;
} }
```
* Copy Propagation : 去掉變數不必要的複製 ， 減少 cache miss
```
Example 3 ->
b = a; b = a;
c = b; c = a;
```
* Inline Function : 這樣可以減少函數呼叫的時間， 如果運算過大(如遞迴)， 編譯器不會執行Inline
```
Example 4 ->
int main() { int main() {
square(2); {
square(4); x = 2;
} printf("%d", x*x);
}
inline void square(int x){ {
printf("%d", x*x) x = 4;
} printf("%d", x*x);
}
}
```
* Dead Code Elimination : 將多餘的程式碼去除， 使用上述方法，會出現很多不被需要的程式碼
* Common Subexpression Elimination : 可以減少許多 多餘的運算
```
Example 5 ->
#define STEP 3
#define SIZE 100
int i, j, k, p[SIZE]; j = 2 * STEP;
for (i = 0; i < SIZE; ++i) { for (i = 0; i < SIZE; ++i)
j = 2 * STEP; k = p[i] * j;
k = p[i] * j;
}
```
* Loop Unroll : 再HW1介紹過
- [ ] GCC 提供-O0(不做最佳化)、-O1、-O2、-O3、-Os ， 可將C程式碼轉成組合語言，分別看其最佳化結果
# MMAP
* 所有user建立的執行檔都是user space，OS kenrel的執行程式碼則是kernel space 程式碼。在32位元的CPU，LINUX把0~3G的虛擬位址空間分給user space，3G~4G的虛擬位址空間分給kernel space
* 通常 I/O 對應的位址在kernel space ，不由 user 隨意使用，要使用則需使用system call
* 使用MMAP, user 可以載user space直接使用記憶體配置的 file 空間
* ==void *mmap(void *start,size_t length, int prot, int flags, int fd, off_t offsize);==
**start** : 起始位置，通常設為NULL，kernel 會自己找尋位置
**length** : 映射大小 (文件大小)，
**prot** : PROT_EXEC 映射區域可被執行
PROT_READ 映射區域可被讀取
PROT_WRITE 映射區域可被寫入
PROT_NONE 映射區域不能存取
**flags** : MAP_SHARED 允許其他映射該文件的行程共享，對映射區域的寫入資料會複製回文件
**fd** : open 的回傳值，-1代表
**回傳值** ： 回傳起始位置
# POSIX Thread
* Thread = 4的結果圖
* 方法一 ：使用CPU榜定，預想如果OS只讓thread 都執行在同一個CPU，所以讓thread分別榜定在某一個CPU上，達成加快效能
```
#define __USE_GNU
#include <unistd.h>
#include <sched.h>
CPU_ZERO(&mask);
CPU_SET(count%num, &mask);
sched_setaffinity(app->tid+1, sizeof(mask), &mask);
```
結果 :
Thread = 4 :
cache miss 增加了， 但總體時間減少了
# Reference
* [GoRoutine Introduce](https://polor10101.gitbooks.io/golang_note/content/goroutine.html)
* [stack vs heap](http://antrash.pixnet.net/blog/post/70456505-stack-vs-heap%EF%BC%9A%E5%9F%B7%E8%A1%8C%E6%99%82%E6%9C%9F%E5%84%B2%E5%AD%98%E5%85%A9%E5%A4%A7%E8%A6%81%E8%A7%92)
:+1: [heap alloaction](http://silcnitc.github.io/run_data_structures/heap.html)
:+1: [淺談編譯器最佳化技術](http://www.slideshare.net/kitocheng/ss-42438227)
* [GCC 編譯器優化選項](http://blog.csdn.net/gatieme/article/details/48898261)
* [Linux MMAP & Ioremap introduction](http://www.slideshare.net/gene7299/linux-mmap-ioremap-introduction)
* [C99 SPEC](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)
* [C11 SPEC](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf)
* [C89/C90 SPEC](http://read.pudn.com/downloads133/doc/565041/ANSI_ISO%2B9899-1990%2B[1].pdf)
Sign in with Wallet
Connect another wallet