# 2017q1 Homework4 (mergesort-concurrent)

contributed by <`twzjwang`>
作業說明: [B08: mergesort-concurrent](https://hackmd.io/s/B1xV_p_jl)
github: [twzjwang/mergesort-concurrent](https://github.com/twzjwang/mergesort-concurrent)

# 開發環境
- Ubuntu Ubuntu 16.04.2 LTS
Linux 4.8.0-36-generic

- cpu
version: Intel(R) Core(TM) i5-3337U CPU @ 1.80GHz
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 3072K

- memory
size: 4GiB

# 開發前
- 依照作業說明執行

    $ (for i in {1..8}; do echo $RANDOM; done) | ./sort 4 8
    Segmentation fault (core dumped)

- `argv[2]` 為 `build_list_from_file` 的檔名，而不是先的 `input_count`
- fopen 失敗

- 執行 `$ uniq test_data/words.txt | sort -R > test_data/word_sorted.txt` 取得亂數排列的檔案

- 根據 Manual
- NAME : `sort - sort lines of text files `
- DESCRIPTION :
`--sort=WORD sort according to WORD: random -R`

- 執行 `$ ./sort 4 test_data/word_sorted.txt`
- 結果

        #Total_tasks_consumed: 12
        #Elapsed_time: 51.829 ms
        #Throughput: 231 (per sec)

- list_print

        0
        ...
        0

- 字串經 [atol](http://www.cplusplus.com/reference/cstdlib/atol/) 轉換回傳 long int
- 轉換結果皆為0

# 修改-使用字串排列
- 定義 datatype 為大小 16 的char array
- `typedef char val_t[16];`
- 使用 strcmp 比大小`llist_t *small = (strcmp(a->head->data, b->head->data) <= 0) ? a : b;`

- 自動測試
- `make check_words`

        check_words: sort genData
        ./sort $(THREADS) test_data/input.txt output.txt
        diff output.txt test_data/expected.txt

- diff 沒有輸出 : 內容完全相同
- 結果

        $ make check
        uniq test_data/words.txt | sort -R > test_data/input.txt
        uniq test_data/words.txt | sort > test_data/expected.txt
        ./sort 4 test_data/input.txt output.txt
        #Total_tasks_consumed: 12
        #Elapsed_time: 150.177 ms
        #Throughput: 79 (per sec)
        diff output.txt test_data/expected.txt

- mutrace
- Lock Contention
- lock contention can have a big impact on the runtime behaviour of applications
- 項目
- Locked : 整個 runtime 中 mutex locked 的次數
- Changed : 擁有 mutex 的 thread 改變的次數
- 數量高 => the risk of contention 高
- Cont : contention 發生次數
- 想要取得 lock 但已經先被其他 thread 取得，必須等待
- tot.Time[ms] : 等待的總時間
- avg.Time[ms] : 平均等待時間
- max.Time[ms] : 最大等待時間
- 結果
- Mutex #1 發生大量 contention 並造成等待
- 使用 `addr2line` 找到對應的位置，推測
- Mutex #0
- Mutex #1 : the_queue->mutex
- Mutex #2 : data_context.mutex

    $ mutrace ./sort 4 test_data/input.txt output.txt
    mutrace: 0.2 sucessfully initialized for process sort (pid 3788).
    #Total_tasks_consumed: 12
    #Elapsed_time: 129.242 ms
    #Throughput: 92 (per sec)

    mutrace: Showing statistics for process sort (pid 3788).
    mutrace: 3 mutexes used.

    Mutex #1 (0x0x1fba670) first referenced by:
        /usr/lib/mutrace/libmutrace.so(pthread_mutex_init+0xf2) [0x7fbca7b354b2]
        ./sort(tqueue_init+0x46) [0x4014eb]
        ./sort(tpool_init+0x6a) [0x40174f]
        ./sort(main+0xe5) [0x401ee4]
        /lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0) [0x7fbca756c830]

    Mutex #0 (0x0x7fbca513b860) first referenced by:
        /usr/lib/mutrace/libmutrace.so(pthread_mutex_lock+0x49) [0x7fbca7b356b9]
        /lib/x86_64-linux-gnu/libgcc_s.so.1(_Unwind_Find_FDE+0x2c) [0x7fbca4f37fec]
        [(nil)]

    Mutex #2 (0x0x603140) first referenced by:
        /usr/lib/mutrace/libmutrace.so(pthread_mutex_init+0xf2) [0x7fbca7b354b2]
        ./sort(main+0xab) [0x401eaa]
        /lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0) [0x7fbca756c830]

    mutrace: Showing 3 most contended mutexes:

     Mutex #   Locked  Changed    Cont. tot.Time[ms] avg.Time[ms] max.Time[ms]  Flags
           1    83875    31938    25850       11.116        0.000        0.019 Mx.--.
           0       20       15        8        0.005        0.000        0.001 M-.--.
           2        6        4        0        0.002        0.000        0.001 M-.--.
                                                                               ||||||
                                                                               /|||||
              Object:                                     M = Mutex, W = RWLock /||||
               State:                                 x = dead, ! = inconsistent /|||
                 Use:                                 R = used in realtime thread /||
          Mutex Type:                 r = RECURSIVE, e = ERRRORCHECK, a = ADAPTIVE /|
      Mutex Protocol:                                      i = INHERIT, p = PROTECT /
         RWLock Kind: r = PREFER_READER, w = PREFER_WRITER, W = PREFER_WRITER_NONREC 

    mutrace: Note that the flags column R is only valid in --track-rt mode!

    mutrace: Total runtime is 200.374 ms.

    mutrace: Results for SMP with 4 processors.

:::danger
特別留意 lock contention 對效能的影響，目前整合的 thread pool 實作不是很有效率 (之後我們應該要重寫一套更好的) --jserv
:::

# 修改-[lock free](https://en.wikipedia.org/wiki/Non-blocking_algorithm#Lock-freedom)
- lock free
- individual threads 可能發生 starve ，但保證 system-wide throughput
- All wait-free algorithms are lock-free
- lock-free 演算法的四個 phases
- 完成自己的 operation
- 協助阻塞的 operation
- 中止阻塞的 operation
- 等待

- 針對 lock contention 次數較多的 Mutex #1 : the_queue->mutex
- crtitical section
- pthread_mutex_lock() 和 pthread_mutex_unlock() 之間
-

    task_t *tqueue_pop(tqueue_t * const the_queue)
    {
        task_t *ret;
        pthread_mutex_lock(&(the_queue->mutex));
        ret = the_queue->head;
        if (ret) {
            the_queue->head = ret->next;
            ret->next = NULL;
            if (!(the_queue->head)) {
                the_queue->tail = NULL;
            }
            the_queue->size--;
            the_queue->num_of_consumed++;
        }
        pthread_mutex_unlock(&(the_queue->mutex));
        return ret;
    }
    uint32_t tqueue_size(tqueue_t * const the_queue)
    {
        uint32_t ret;
        pthread_mutex_lock(&(the_queue->mutex));
        ret = the_queue->size;
        pthread_mutex_unlock(&(the_queue->mutex));
        return ret;
    }
    int tqueue_push(tqueue_t * const the_queue, task_t *task)
    {
        pthread_mutex_lock(&(the_queue->mutex));
        task->next = NULL;
        if (the_queue->tail)
            the_queue->tail->next = task;
        the_queue->tail = task;
        if (the_queue->size++ == 0)
            the_queue->head = task;
        pthread_mutex_unlock(&(the_queue->mutex));
        return 0;
    }

# 參考資料
- [LanKuDot 學長 筆記](https://hackmd.io/s/S1ezGhIA)
- [Measuring Lock Contention](http://0pointer.de/blog/projects/mutrace.html)

###### tags: `twzjwang`