# 2016q3 Homework2 (phonebook-concurrent)
contributed by <`TotallyWrong`>
###### tags: `TotallyWrong` `On going`

## 開發作業環境
**CPU** : Intel Core i5-5200U
**Cache size**: L1 Cache 128KB, L2 Cache 512K, L3 Cache 3072KB
**Operating System** : Ubuntu 15.10 Wily Werewolf
**Feature**:
* MMX instructions
* SSE / Streaming SIMD Extensions
* SSE2 / Streaming SIMD Extensions 2
* SSE3 / Streaming SIMD Extensions 3
* SSSE3 / Supplemental Streaming SIMD Extensions 3
* SSE4 / SSE4.1 + SSE4.2 / Streaming SIMD Extensions 4 ?
* AES / Advanced Encryption Standard instructions
* AVX / Advanced Vector Extensions
* AVX2 / Advanced Vector Extensions 2.0

## 作業現況

### 程式碼修改

這份作業是延續上一周的作業的延伸，是告改善上一個同學的Concurrent版本的Phonebook Code。做的第一件事是讀懂程式碼，在閱讀期間發現有一些怪怪的地方雖不影響功能但是影響閱讀就先修改了。

typedef detail *pdetail;

typedef struct __PHONE_BOOK_ENTRY {
    char *lastName;
    struct __PHONE_BOOK_ENTRY *pNext;
    pdetail dtl;
} entry;

pdetail 是多餘的，刪除後再把 *.c相對應位址改了。

#ifndef OPT
    if (pHead->pNext) free(pHead->pNext);
    free(pHead);
#else
    free(entry_pool);
    free(tid);
    free(app);
    munmap(map, fs);

前面都是 #if defined(OPT)這突然變#ifndef OPT，所以就改了#if defined(OPT)。

接下來為了測試方便增加了 #define WORD_NAME "zzzzzzzz"來取代數入字元的位置。

接下來是在Main中有許多改動pHead的地方但是pHead不該更動(感謝同實驗室的同學告知)試著查詢字典中的"aaaa"果然不見了，在把幾個 pHead = app[i]->pHead->pNext的pNext消除後就正確了。

 pHead = pHead->pNext;
    for (int i = 0; i < THREAD_NUM; i++) {
        if (i == 0) {
            pHead = app[i]->pHead->pNext;
            dprintf("Connect %d head string %s %p\n", i,
                    app[i]->pHead->pNext->lastName, app[i]->ptr);
        } else {
            etmp->pNext = app[i]->pHead->pNext;
            dprintf("Connect %d head string %s %p\n", i,
                    app[i]->pHead->pNext->lastName, app[i]->ptr);
        }

接下來是把Join 所有Thread的回圈中的if剔除因為沒有必要

pHead = app[0]->pHead;
    etmp = app[0]->pLast;
    dprintf("Connect %d head string %s %p\n", 0, app[0]->pHead->pNext->lastName, app[0]->ptr);
    
    for (int i = 1; i < THREAD_NUM; i++) {
        etmp->pNext = app[i]->pHead;
        dprintf("Connect %d head string %s %p\n", i, app[i]->pHead->pNext->lastName, app[i]->ptr);
        etmp = app[i]->pLast;
        dprintf("Connect %d tail string %s %p\n", i, app[i]->pLast->lastName, app[i]->ptr);
        dprintf("round %d\n", i);
    }

重複的` e = pHead;`刪除。

    e = pHead;

    /* the givn last name to find */
    char input[MAX_LAST_NAME_SIZE] = "zyxel";
    e = pHead;

    assert(findName(input, e) &&
           "Did you implement findName() in " IMPL "?");
    assert(0 == strcmp(findName(input, e)->lastName, "zyxel"));

程式正確後就需要開始改善利用之前學過的perf功能看一下熱區在哪裡

似乎在用了大量的時間再做strncasecmp這動作比較字串，而大部份strncasecmp都是在Findname。

還有試試gprof的分析，而再使用時因為gprof會背時間計算function干擾，所以我就先關掉了。

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
 50.08      0.02     0.02                             append
 25.04      0.03     0.01        1    10.02    10.02  findName
 25.04      0.04     0.01        1    10.02    10.02  frame_dummy
  0.00      0.04     0.00        4     0.00     0.00  new_append_a

因為funcation 呼叫還滿單純的所以覺得滿符合逾期的。

這是修正錯誤但位改善的Concurrent板與原始板的Peformance比較圖。


### 記憶體存取位置改善

接下來我請程式在FindName()的時候把所儲存的字和位置印出，發現搜尋時所搜的順序是Thread0的Link List 接 Thread 1的 Link List 接Thread 2的 Link List .....。這位學長已經很好的使用entrypool去作減少Complier 實作 malloc()要用到的 system call，但是在append或搜尋時因為entrypool使用順序可能會造成不必要的cache-miss。這是我上周沒想到怎麼解決的一個問題，在課堂上詢問老師後了解可以再系統中加Memory Management 上網查了一些資料後大概對要怎麼辦有些初步的想法，但還沒寫出可以回收記憶體和調整位置的Code。目前的這個Phonebook程式還沒有插入和刪除所以可以暫時不要考慮，以下是我印出的結果。

Thread 0
   address="0x7f779ad5c"010 word=aaaaaaaa
   address="0x7f779ad5c"070 word=aaaaaahhhhh
   .
   .
   address=0x7f779b55e210 word=zyzomys
   address=0x7f779b55e270 word=zzzzz

Thread 1
   address="0x7f779ad5c"028 word=aaaaaaaah
   address="0x7f779ad5c"088 word=aaaaaaugh
   .
   .
   address=0x7f779b55e228 word=zyzop
   address=0x7f779b55e2
  88 word=zzzzzz

仔細看一下 " "內的位置Thread　0的list第一個字的位置和Thread　1的list 第一個字的位置，而我的電腦有4個Thread每個Thread的list下的第一個字都很近，而位置上只差24個byte。

這會造成一個問題就是一個 Intel CPU cache line 是64byte而當一個Core在寫入一個Cache Line時另一個Core是無法寫入的這造成有時所有的Core都在搶一個cache line而無法真正達到Concurrent，下面是一個教OMP的影片在解釋我所說的情況。[解釋Cache Line 和Concurrent的關係](https://www.youtube.com/watch?v=x0HkbIuJILk&index=5&list=PLLX-Q6B8xqZ8n8bwjGdzBJ25X2utwnoEG)還有就是Thread 要頻繁的更換寫入的Cache Line， 這也增加不必要的Cache Line 變換。

利用這個資訊我稍微調整了一下記憶體配給的順序，因為利用fs就可以算出所需讀取資料的筆數，可以分配各Threads的起點。

Thread 0
   address=0x7fbc9c28e028 word=aaaaaaaa
   address=0x7fbc9c28e040 word=aaaaaahhhhh
   .
   .
   address=0x7fbc9c48e8a8 word=zyzomys
   address=0x7fbc9c48e8c0 word=zzzzz
   
Thread 1
   address=0x7fbc9c48e8d8 word=aaaaa
   address=0x7fbc9c48e8f0 word=aaaaaaaah
   .
   .
   address=0x7fbc9c68f170 word=zyzop
   address=0x7fbc9c68f188 word=zzzzzz

測試後的結果的確有比較快跟原始的Phoneboook Concurrent Phonebook快，不論是 Append()或是findName()都有變快。

>> 量化！修改 gnuplot 呈現方式，專注於 `append()` 時間成本，並且製作對照圖。 [name=jserv]

下圖是把原始的Phonebook (Original),Phonebook Concurrent (Concurrent Original)，和我調整Memory(Memory Location Adjust)的位置後的Append()時間比較。

下圖是把Phonebook Concurrent (Concurrent Original),和我調整Memory的位置後的(Memory Loaction Adjust)Append時間比較。


### 時間結果的分佈狀況

因為Append的時間有時快有時慢我接下來想了解一下， 怎麼樣去得到一個比較可靠的數值。就去看老師之前推荐[廖健富](https://hackpad.com/Hw1-Extcompute_pi-geXUeYjdv1I)的error rate 計算而這篇文章當中老室友附上95%信[賴區間](http://www.measuringu.com/blog/ci-five-steps.php)的計算在看完後我稍微Wiki 一下信賴區間算法的出處，了解到這是常態分佈的信賴驅間的計算。我想要確認一下這個時間分佈是不是常態分佈，我在跑過6000次收集了時間然後用Gnuplot把分佈畫了出來。[Histogram分佈圖](http://gnuplot-surprising.blogspot.tw/2011/09/statistic-analysis-and-histogram.html)
>X是時間秒忘記放入，

原始Phonebook版本

記憶體位置改善過Phonebook Concurrent版本 4 Threads

記憶體位置改善過Phonebook Concurrent版本 2 Threads

我發現這些分佈都有兩個峰值，我想這能跟Threads數和Core數有關而我的電腦CPU只有兩個真實core卻模擬4個Core。為了解這問借了實驗室同學吳庭安的電腦(因為有真四核)來做實驗，跑出來的結果如下。

原始Phonebook版本

記憶體位置改善過Phonebook Concurrent版本 4 Threads

原始版本的在另一台電時候有4個峰值而在我的電腦有兩個峰值，這可能是因為CPU切換Core造成的。
在Concurrent版本我的電腦有兩個峰值，而庭安的電腦跑出來的結果比起常態分佈更接近瑞利分佈(Rayleigh distribution)。我上網閱讀一些reddit有關Hyperthread的討論似乎在某些狀況下反而造成效率下降。為了測試我的想法我想把我的電腦的虛擬的Core關掉，剛開始想從Bios把Hyperthread，但是關掉我的電腦的Bios不支援後來在查尋後可以從Linux把虛擬[Core關掉](http://www.absolutelytech.com/2011/08/01/how-to-disable-cpu-cores-in-linux/)。先去用`nproc`[確認](http://www.cyberciti.biz/faq/linux-get-number-of-cpus-core-command/)是真的有4個Core，2個虛擬和2個真實的Core，接下來用`sudo sh -c "echo 0 > /sys/devices/system/cpu/cpu3/online"` 把CPU 2 和 3 關掉，再跑一次。結果如下(Threads為程式內的Threads設定)：
記憶體位置改善過Phonebook Concurrent版本2Core和2Threads

記憶體位置改善過Phonebook Concurrent版本2Core和4Threads

記憶體位置改善過Phonebook Concurrent版本2Core和8Threads

只用1個Core跑原始無Concurrent的程式

從這一連串的測試得到幾個可能的研究方向：

1. 程式的預設Threads 跟硬體可以匹配似乎是可以得到比較好的效果，過多或過少似乎都有一些負面影響。

2. 雖然Intel 虛擬的Core表現還是不如真實的Core表現穩定但是整體的表現還是比只有兩個真實Core好。

3. 在多核環境下似乎對Single Core設計的軟體有以些不確定的影響。(還要多做測試才能確認是好是壞)

4. 測試時間的結果好像跟瑞利分佈(Rayleigh distribution)比較接近。

>我目前還在讀瑞利分佈MLE的文章來確認是否可以用數學來確認這件事，如果有人有比較好的方發或是可以給我一個研究方向，也請不吝指教。

### 運用Thread Pool 改善程式