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

## 硬體規格

dennis@dennis-X550CC:~$ lscpu
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
型號：              58
Model name:            Intel(R) Core(TM) i5-3337U CPU @ 1.80GHz
製程：              9
CPU MHz：             1270.898
CPU max MHz:           2700.0000
CPU min MHz:           800.0000
BogoMIPS:              3592.04
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           3072K
NUMA node0 CPU(s):     0-3

## 分析實作
- text_align

      text_align(DICT_FILE, ALIGN_FILE, MAX_LAST_NAME_SIZE);
      int fd = open(ALIGN_FILE, O_RDONLY | O_NONBLOCK);
      off_t file_size = fsize(ALIGN_FILE);

- `text_align` 將原本 `DICT_FILE` 的每一行名字都對齊 `MAX_LAST_NAME_SIZE` 的長度，長度太短就在後面補滿 `\0`，最後輸出成 `ALIGN_FILE`，這樣之後讀檔每一行的大小就都是一樣的，目的要讓記憶體對齊可加速讀取。
- `open` 為開啟檔案函式，第二個參數為開啟檔案的方式，若開啟成功則會回傳 0。
- `fsize` 會利用 `stat()` 回傳以 **byte** 為單位的檔案大小。

- [mmap](http://welkinchen.pixnet.net/blog/post/41312211-%E8%A8%98%E6%86%B6%E9%AB%94%E6%98%A0%E5%B0%84%E5%87%BD%E6%95%B8-mmap-%E7%9A%84%E4%BD%BF%E7%94%A8%E6%96%B9%E6%B3%95)

- 利用處理過的 `ALIGN_FILE` 直接對映到記憶體上，mmap 會回傳資料起始位址

    map = mmap(NULL, file_size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);

- 順便利用計算過的 `file_size`，**一次**就把所有的 entry 給 malloc 好

    entry_pool = (entry *)malloc(sizeof(entry) *
                                 file_size / MAX_LAST_NAME_SIZE);

- pthread
- `pthread_setconcurrency(THREAD_NUM + 1)`
用來提示系統，表明希望的 thread 數量，這邊 `+1` 應該是希望能排除 main-thread。
[參考資料](http://www.cnblogs.com/nufangrensheng/p/3522583.html)說到，如果 CPU 同時一被分配給一個以上的 thread 的話，可能就會改善性能。
但是[這裡說到](http://man7.org/linux/man-pages/man3/pthread_getconcurrency.3.html)`LinuxThreads` 跟 `NPTL` 都是 1：1，用`pthread_setconcurrency` 好像沒啥用處@@
:::danger
應該使用繁體中文/台灣地區的慣用科技術語，請修改。不要輕易說「好像」，你做過實驗了嗎？ --jserv
:::
> 好的老師，我會改進，發揮實驗精神 --xdennisx

根據我的硬體規格是 2 threads per core, 2 cores per socket.
嘗試用不同的 THREAD_NUM 去看結果
`n=3`

  execution time of append() : 0.004465 sec
  execution time of findName() : 0.001146 sec

`n=4`

  execution time of append() : 0.008299 sec
  execution time of findName() : 0.003174 sec

`n=5`

  execution time of append() : 0.004265 sec
  execution time of findName() : 0.001105 sec

`n=6`

  execution time of append() : 0.006449 sec
  execution time of findName() : 0.001518 sec

`n=7`

  execution time of append() : 0.006740 sec
  execution time of findName() : 0.004059 sec

`n=8`

  execution time of append() : 0.007461 sec
  execution time of findName() : 0.004209 sec

原本想用 `pthread_getconcurrency()` 看看是不是設定超過最大數量的 thread，`pthread_getconcurrency()` 會回傳一樣的值，不過結果我設多少他就回傳多少，而且 `pthread_setconcurrency()` 設多少效能上也沒有什麼太大的改變，從此判定 `pthread_setcomcurrency()` 在 Linux 上是沒什麼太大用處
- 我的 kernel model：

    dennis@dennis-X550CC:~/phonebook-concurrent$ getconf GNU_LIBPTHREAD_VERSION
    NPTL 2.23

- 分配每個 thread 下去工作

    for (int i = 0; i < THREAD_NUM; i++)
        // Created by malloc, remeber to free them.
        thread_args[i] = createThread_arg(map + MAX_LAST_NAME_SIZE * i, map + file_size, i,
                                          THREAD_NUM, entry_pool + i);

- 最後再把他串起來

    for (int i = 0; i < THREAD_NUM; i++) {
        if (i == 0) {
            pHead = thread_args[i]->lEntry_head->pNext;
        } else {
            e->pNext = thread_args[i]->lEntry_head->pNext;
        }
        e = thread_args[i]->lEntry_tail;
    }

- 原始輸出圖

## 改善方法
### Thread pool
- ThreadPool 的基本原理是將要執行的工作放進一個 Queue 裡，然後啟動多條 Thread，每條 Thread 會去檢查 Queue 裡還有沒有工作要做，若有就取出來。
- 由於要管控每件工作只交給其中一個 Thread 去處理，所以得動用 **lock機制**；也就是同一時間只能開放一條 Thread 去檢查 Queue 並取出工作，可以想像成全部的 Thread 排成一列輪流存取。
- 在程式裡透過 `pool->count` 掌握工作何時全部做完，在遞減 `pool->count` 也要等同要啟動 lock 機制，任何時間下只允許一個 Thread 去修改它的值。
- 概念圖

- `threadpool_add` function 就是把工作塞進去 Queue 裡面，`*threadpool_thread` function 就是把 Queue 裡面的工作分配給 Thread
- Queue 裡面每個元素

- 參考 [0140454](https://github.com/0140454/phonebook-concurrent) 跟 [ierosodin](https://github.com/ierosodin/phonebook-concurrent) 實作 threadpool 結果...
> Hmmm....哪邊出問題R 0.0

不過 cache-miss 有降
- phonebook_opt

  Performance counter stats for './phonebook_opt' (100 runs):

           731,497      cache-misses              #   40.420 % of all cache refs      ( +-  0.93% )
         1,809,747      cache-references                                              ( +-  1.81% )
       246,807,242      instructions              #    1.20  insns per cycle          ( +-  0.12% )
       205,503,773      cycles                                                        ( +-  1.06% )

       0.083420525 seconds time elapsed                                          ( +-  1.80% )

- phonebook_tp

  Performance counter stats for './phonebook_tp' (100 runs):

           789,868      cache-misses              #   36.357 % of all cache refs      ( +-  0.60% )
         2,172,511      cache-references                                              ( +-  1.40% )
       259,023,470      instructions              #    1.16  insns per cycle          ( +-  0.05% )
       223,875,263      cycles                                                        ( +-  0.71% )

       0.079537321 seconds time elapsed                                          ( +-  0.79% )

## Reference
[ierosodin](https://hackmd.io/s/rkCrQGbR)
[C 的 Thread Pool 筆記](http://swind.code-life.info/posts/c-thread-pool.html)
[Threadpool 比較](http://blog.darkthread.net/post-2010-01-02-multicore-1.aspx)