# 2018q1 Homework1 (phonebook)
contributed by < `winonecheng` >
### Reviewed by `catpig1630`
* 可以試著改變entry size的大小或是使用hash table，看看會不會增進這個程式的效能

### Reviewed by `workat60474`
* 建議可以更加詳盡的分析為何降低struct size能夠降低cache misses，從locality of reference 以及L1 cache size 能夠存放多少個struct 資料，來量化分析。
* 建議可以探討hash funtion對於cache 的影響，https://www.youtube.com/watch?v=ncHmEUmJZf4 ，這個youtube影片有非常詳盡的介紹。

### Reviewed by `YuanHaoHo`
* 建議可以先練習用 gunplot 把結果呈現出來。
* 事前準備很多，但需改善 cache 效能為前題。

---

## 開發環境

### 作業系統

$ lsb_release -a

No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 17.10
Release: 17.10
Codename: artful

$ uname -a

Linux chiehcheng-X455LD 4.13.0-36-generic #40-Ubuntu SMP Fri Feb 16 20:07:48 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux

### CPU資訊

$ lscpu

Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 69
Model name: Intel(R) Core(TM) i5-4210U CPU @ 1.70GHz
Stepping: 1
CPU MHz: 2394.403
CPU max MHz: 2700.0000
CPU min MHz: 800.0000
BogoMIPS: 4788.80
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 3072K
NUMA node0 CPU(s): 0-3

#### Cache

在閱讀 [cache 原理和實驗](https://hackmd.io/s/S14L26-_l) 後想知道自己電腦的 CPU Cache 的 cache line 和 associativity，查詢資料發現，在目錄`/sys/devices/system/cpu`下有 cpu0,cpu1,... 等，再進入後的目錄`cache`有著各式資訊。

$ tree /sys/devices/system/cpu/cpu0/cache/ -L 2

> ├── index0
│   ├── coherency_line_size
│   ├── id
│   ├── level
│   ├── number_of_sets
│   ├── physical_line_partition
│   ├── power
│   ├── shared_cpu_list
│   ├── shared_cpu_map
│   ├── size
│   ├── type
│   ├── uevent
│   └── ways_of_associativity
├── index1
│   ├── coherency_line_size
│   ├── id
│   ├── level
│   ├── number_of_sets
│   ├── physical_line_partition
│   ├── power
│   ├── shared_cpu_list
│   ├── shared_cpu_map
│   ├── size
│   ├── type
│   ├── uevent
│   └── ways_of_associativity
├── index2
│   ├── coherency_line_size
│   ├── id
│   ├── level
│   ├── number_of_sets
│   ├── physical_line_partition
│   ├── power
│   ├── shared_cpu_list
│   ├── shared_cpu_map
│   ├── size
│   ├── type
│   ├── uevent
│   └── ways_of_associativity
├── index3
│   ├── coherency_line_size
│   ├── id
│   ├── level
.
.

- 發現：`line size` 都是 64B，`ways_of_associativity` 在 L1,L2都是8，L3則是12，因為 associativity 和 cache size 的不同，`number_of_sets` 都不相同。
- 以L3為例：
ways_of_associativity： 12
size： 3072KB
coherency_line_size: 64B
number_of_sets: 8192
**8192 * 12 * 64 / 1024 = 3072 KB**

## Makefile 研究
- 程式碼換行：因為C語言在編譯時，讀指令是以分號(;)做區隔，所以直接換行或加很多空白或常用的反斜線`\`都是可以的，例如：

    foo ( bar );
    // same as:
    foo (
      bar )
    ;
    // same as:
    fo\
    o ( b\
    ar );

- `-Wall` : 顯示 warning msgs
- `-O` : 設定compiler最佳化的層級，用法為`-Olevel`，例如`-O1`。
使用`-Ofast` 測試，發現 execution time 確實有減少。
(參考自 [gcc -o / -O option flags](https://www.rapidtables.com/code/linux/gcc/gcc-o.html))

- `$(RM)` : built-in implicit rules, means `rm -f`
可以透過`make -p | grep RM`查詢，常用的變數可參考 [10.3 Variables Used by Implicit Rules](https://www.gnu.org/software/make/manual/html_node/Implicit-Variables.html)

-

    .PHONY: all
    all: $(GIT_HOOKS)   $(EXEC)

Makefile中的第一個目標會被作為其默認目標。我們聲明了一個「all」的偽目標，其依賴於其它三個目標。由於偽目標的特性（不管all檔案是否存在或依賴目標是否最新），all總是會被執行。所以，其它三個目標的規則總是會被決議。也就達到了我們一口氣生成多個目標的目的。
(參考自[跟我一起写Makefile:书写规则](http://wiki.ubuntu.org.cn/%E8%B7%9F%E6%88%91%E4%B8%80%E8%B5%B7%E5%86%99Makefile:%E4%B9%A6%E5%86%99%E8%A7%84%E5%88%99))

- `-DIMPL="\\"$@.h\\""`