# 2016q3 Homework1(phonebook)
contributed by <`janetwei`>

## 開發環境

這是我第ㄧ次安裝linux的開發環境，一開始我想要用rEFlnd這個軟體，但是在安裝的過程中找不到Users這個資料夾，出現無窮迴圈，這個問題還是沒有解決，因此我先換個方法

在安裝好ubuntu遇到的第一個問題是連不上無線網路，因此我上網找了資料，打了以下指令就解決了

＄  rfkill list all
＄  rfkill unblock all

第二個問題是我的鍵盤無法打出某個符號，因此上網找了資料

＄ sudo dpkg-reconfigure keyboard-configuration

用這個指令可以改變鍵盤的設定，但是我還是不能打出那符號

## Perf
藉由 perf，應用程式可以利用 PMU (Performance Monitoring Unit), tracepoint 和核心內部的特殊計數器 (counter) 來進行統計

perf 基本原理是對目標進行取樣，紀錄特定的條件下所偵測的事件是否發生以及發生的次數。
可取樣的事件分成
- Hardware event: 由 PMU 產生的事件
- Software event:是核心程式產生的事件
- Tracepoint event:是核心中的靜態 tracepoint 所觸發的事件，這些 tracepoint 用來判斷在程式執行時期，核心的行為細節，比如 slab 記憶體配置器的配置次數等

用來檢查perf的有沒有啟用的指令
`＄ cat "/boot/config-`uname -r`" | grep "PERF_EVENT"`

### 基本指令
* perf top

- e <event>: 選擇要測試的PMU event
- p <pid>: 針對某個$pid process做profiling
- perf stat:使用 perf stat 往往是你已經有個要優化的目標，對這個目標進行特定或一系列的 event 檢查，進而了解該程序的效能概況
- repeat <n>: 重複執行n次,並顯示每個event的區間
- :u : 測量的instructions只限在user level,最後可以觀察到迴圈展開前後 branch-instructions 的差距
- :k : kernel level
* perf record
可以針對函式級別進行 event 統計，方便我們對程序「熱點」作更精細的分析和優化

-F: 取樣的平均頻率
-c: 取樣的間距

example: -F 250，以平均每秒250個sample的平率取樣
example: -c 2000，監測event每2000次取樣一次

* perf report

讀取perf.data來顯示profile

若不是root,在`$ perf top`的時候會出現Error
因此要切換,可以打`$ sudo su` or `sudo perf top`

以下指令可以查看權限值
`$ cat /proc/sys/kernel/perf_event_paranoid `
## 背景知識
### cache
硬體特性之 cache
記憶體存取很快，但仍無法和處理器的指令執行速度相提並論。為了從記憶體中讀取指令 (instruction) 和資料 (data)，處理器需要等待，用處理器的時間來衡量，這種等待非常漫長。cache 是一種 SRAM，它的存取速率非常快，與處理器處理速度較為接近。因此將常用的資料保存在 cache 中，處理器便無須等待，從而提高效能。cache 的尺寸一般都很小，充分利用 cache 是軟體效能改善過程中，非常重要的部分。
### cache miss
程序在執行過程中,數據最先在磁盤上，然後被取到內存中,最後如果經過cache(也可以不經過)被CPU使用,如果數據不在cache之中,需要CPU到主存中存取數據,那麼這就是cache miss,這帶來相當大的時間開銷。
[參考](http://blog.csdn.net/trochiluses/article/details/17346803)

## phonebook

### 優化前
在還沒優化的時候，發現cache-misses高達92.33%
instructions也有260939006次
由此可知，減少cache-misses以及instructions為優化程式首要目標


### 優化後
將程式改成


由此圖可知，將未運用到的資料轉移到另一個結構體上可以讓cache-misses降低不少，從92.33%降低為72.976%


優化前後的比較：

## Memory Leak
- Memory Leak指由於疏忽或錯誤造成程式未能釋放已經不再使用的記憶體。
- 記憶體漏失並非指記憶體在物理上的消失，而是應用程式分配某段記憶體後，由於設計錯誤，導致在釋 放該段記憶體之前就失去了對該段記憶體的控制，從而造成了記憶體的浪費。
- 記憶體漏失通常情況下只能由獲得程式原始碼的程式設計師才能分析出來。
- 然而，有不少人習慣於把任何不需要的記憶體使用的增加描述為記憶體漏失，即使嚴格意義上來說這是不準確的。

## Hash function