# 2017q1 Homework4 (phonebook-concurrent)
contributed by <`claaaaassic`>

## 開發環境

Architecture:          x86_64
CPU 作業模式：    32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s):             1
NUMA 節點：         1
供應商識別號：  GenuineIntel
CPU 家族：          6
型號：              42
Model name:            Intel(R) Core(TM) i5-2410M CPU @ 2.30GHz
製程：              7
CPU MHz：             799.890
CPU max MHz:           2900.0000
CPU min MHz:           800.0000
BogoMIPS:              4589.59
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           3072K
NUMA node0 CPU(s):     0-3

## [Toward Concurrency](https://hackmd.io/s/Skh_AaVix)

* concurrency(並行) 把可以拆開的部份拆開，不一定要同時執行
* parallelism(平行) 把程式拆開"一起執行"，最後在一起相加

multithread環境下，程式會出問題，往往在於執行順序的不確定性。
* Concurrency
* Sequenced-before
* 一種對同一個 thread 下，求值順序關係的描述
* Happens-Before
* 前一個操作的效果在後一個操作執行之前必須要可見
* Synchoronizes-with
* 跨 thread 版本的 happens-before
* Sequential Consistency
1. 對於每個獨立的處理單元，執行時都維持程式的順序 (Program Order)
2. 整個程式以某種順序在所有處理器上執行
## 開發紀錄

首先是最原始的效能

先研究一下 opt 的版本，一開始看到有的是 `ifndef OPT` 有的是 `if defined(OPT)` 蠻不習慣的，有時間把它改好看一點。

還沒使用過 pthread 要先讀個 code
> 有個疑惑，不知道為什麼`pthread_setconcurrency(THREAD_NUM + 1);`要+1

看完沒什麼好改善的主意，只好來選讀的前一屆的共筆，這邊我想到我在 Homework1 就有觀察過 memory leak 了

## memory leak

先使用以前用過的 `valgrind` 來觀察一下，能看到有 4 個尚未被 free，opt 版本裡面跟 4 有關的應該就是 pthread_num ，我大概是各個 thread 裡面有東西忘記 free

$ valgrind --leak-check=full ./phonebook_opt
==10606== HEAP SUMMARY:
==10606==     in use at exit: 1,614 bytes in 4 blocks
==10606==   total heap usage: 24 allocs, 20 frees, 8,421,863 bytes allocated
==10606== 
==10606== LEAK SUMMARY:
==10606==    definitely lost: 0 bytes in 0 blocks
==10606==    indirectly lost: 0 bytes in 0 blocks
==10606==      possibly lost: 0 bytes in 0 blocks
==10606==    still reachable: 1,614 bytes in 4 blocks
==10606==         suppressed: 0 bytes in 0 blocks

參考[LanKuDot (李昆憶)](https://hackmd.io/s/HJFhaiAp#asanaddres-sanitizer)，這裡面提到 asan 這個東西，在 Makefile 裡面也有放上相關的參數

ifdef CHECK_LEAK
CFLAGS_common += -fsanitize=address -fno-omit-frame-pointer
endif

大概是誘惑我去用用看

$ make CHECK_LEAK=1
$ ./phonebook_opt 
orginal file size = 3206080
size of entry : 24 bytes
execution time of append() : 0.010399 sec
execution time of findName() : 0.007910 sec

！！！我還以為哪個指令下錯了，結果再去共筆看一下，原來我發現剩餘的 memory leak 也是屬於 `still reachable`
這邊因為還有有效指標指著未被 free 的記憶體區塊，並不會對程式造成什麼影響，所以 asan 才會沒有顯示出錯誤訊息

## Optimized + ~~raw~~ row major

目前暫時只有看到 [共筆](https://hackmd.io/s/HJFhaiAp#進一步優化-append) 這裡說的蠻有道裡但是我一開始沒有注意到的地方，thread 裡面是用 column-major 的方式去存取，可能會造成 cache-misses

thread 從每次跳 (numOfThread) 改成總共切(numOfThread)塊每次跳一個，做出來效能沒有太大提昇，沒有共筆講的那麼厲害

加上 <s>raw major</s> row major 的方法只在 append() 加快 18％ 的速度，改善一點點而已
:::danger
不要打錯字: row major --jserv
:::