# 2017q1 Homework4 (phonebook-concurrent) contributed by <`claaaaassic`> ## 開發環境 ```shell 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(並行) 把可以拆開的部份拆開，不一定要同時執行 ![](https://i.imgur.com/rweOyiD.png) * parallelism(平行) 把程式拆開"一起執行"，最後在一起相加 ![](https://i.imgur.com/Oom3wM5.png) multithread環境下，程式會出問題，往往在於執行順序的不確定性。 * Concurrency * Sequenced-before * 一種對同一個 thread 下，求值順序關係的描述 * Happens-Before * 前一個操作的效果在後一個操作執行之前必須要可見 * Synchoronizes-with * 跨 thread 版本的 happens-before * Sequential Consistency 1. 對於每個獨立的處理單元，執行時都維持程式的順序 (Program Order) 2. 整個程式以某種順序在所有處理器上執行 ## 開發紀錄 首先是最原始的效能 ![](https://i.imgur.com/OVpgE7x.png) 先研究一下 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％ 的速度，改善一點點而已 ![](https://i.imgur.com/BZljsjo.png) :::danger 不要打錯字: row major --jserv :::