Try   HackMD

2016q3 Homework2 (phonebook-concurrent)

contributed by <LanKuDot>

閱讀筆記

The free lunch is over

  • Free (performance) lunch 指的是程式設計的效能可以透過 CPU 時脈的進步而得到改善。會說 over 是因為 CPU 的時脈無法得到更進一步的增加，由於耗電和散熱的問題，所以程式設計師必須要修改程式才能改善效能
    • 文章中 Figure 1，可以看到 CPU 時脈並沒有隨著電晶體數量而增加，反而是趨緩了
  • 以前 CPU 如何增進效能
    • Clock speed
    • Execution Optimization
      • Pipelining、Branch prediction
      • Out-of-order execution 還要注意不能讓原本程式崩潰 (read/write reorder)
    • Cache：盡量減少存取 Main memory 的機會
  • 現在 CPU 如何增進效能
    • Hyperthreading：在 single CPU 上同時執行多個 thread，但是共用 ALU、FPU
    • Multicore：多個 CPU
      • 迷思：2 x 3GHz < 6GHz
    • Cache
  • 軟體開發革命 (Software development revolution) 是源自於存在一陣子的技術 (擁有成熟的銷售商和工具支援)，而非新技術一出現即發生。

Concurrency

  • 兩個會使用 Concurrency 的理由：分離可獨立運作的工作；為了效能，像是使用多核新的 CPU
  • 難點：並非所有的程式都合適平行化；程式要設計可以實行 Concurrency 是困難的
  • 如果程式的相依性太高或是太常取用共同資源則會拖慢 Concurrency 的效率
  • 作者提出 Concurrency 對我們的影響
    1. 想要完全使用到 CPU 所有的資源
    2. 程式越來越有機會造成 CPU-bound。雖然主要還是 IO-bound 等，但如果 CPU 時脈無法增加，而其他存取方式速度變快，最後會發生 CPU-bound
    3. 效能優化將會越來越重要
    4. 程式語言強迫必須好好處理 concurrency

Concurrency is not parallelism

  • Concurrency 是指程式架構，將程式拆開成多個可獨立運作的工作。eg：drivers，都可以獨立運作，但不需要平行化。
    • 拆開多個的工作不一定要同時運行
    • 多個工作在單核心 CPU 上運行
  • Parallelism 是指程式執行，同時執行多個程式。Concurrency 可能會用到 parallelism，但不一定要用 parallelism 才能實現 concurrency。eg：Vector dot product
    • 程式會同時執行 (例如：分支後，同時執行，再收集結果)
    • 一個工作在多核心 CPU 上運行

Concurrecncy 系列

  • A happends-before B：在 B 開始執行之前，A 的執行效果必須可見。
  • A is Sequenced-Before B：在同一個 thread 下，A 比 B 先求值。
  • A is synchronized-with B：A 在這一個 thread 對記憶體的操作，在另一個 thread 的 B 必須可見。
  • Sequential consistency：無論處理器實際怎麼執行，確保結果跟照程式順序執行一樣
    • Read before Write：在新值寫入前讀取到舊值
    • Write after Write：在正確值寫入後被舊值複寫 (有先後)

Process && Thread && Coroutine

[Source]

  • Process：一個完整的執行程式，擁有自己的 memory space、執行檔的鏡像、系統配給的存取資源的 descriptor 等
  • Thread：輕量的 process，在 process 中被創造，與同一個 process 中的其他 thread 共用 process 的資源。
  • Coroutine：合作函式 (Cooperative functions)。允許函式執行到一半離開 (yield)，去執行其他函式，再次呼叫這個函式時會從上次離開點開始執行。

用 macro 實現 coroutine

  • 將 Jserv 老師給的用 macro 實現 coroutine 的程式只經過 Preprocessor 處理，會比較容易理解運作，以下程式碼是整理過後的










































static int condition = 1;

static void user_thread_1()
{                            
    static int __s = 0;
    switch (__s) {
        case 0:; 
            for (;;) {
                printf("Run %s\n", __func__);
                { __s = 21;
                  usleep(THREAD_INTERVAL);
                  return;
        case 21: ;
                };
            }
    } __s = 0;; 
}

static void user_thread_2()
{
    static int __s = 0;
    switch (__s) {
        case 0:; 
            for (;;) {
                if (condition) {
                    printf("Run %s - (1)\n" , __func__);
                    { __s = 32;
                      usleep(THREAD_INTERVAL);
                      return;
        case 32: ;
                    };
                }
                printf("Run %s - (2)\n", __func__);
                condition = !condition;
                { __s = 36;
                  usleep(THREAD_INTERVAL);
                  return;
        case 36: ;
                };
            }
    } __s = 0;; 
}

Output:
Run user_thread_1
Run user_thread_2 - (1)
Run user_thread_1
Run user_thread_2 - (2)
Run user_thread_1
Run user_thread_2 - (2)
Run user_thread_1
Run user_thread_2 - (1)
Run user_thread_1
Run user_thread_2 - (2)
Run user_thread_1
Run user_thread_2 - (2)
...

  • 比較令我在意的是那個 case in for loop，所以我寫了小程式驗證

    




















    ​​​​static void caseInForLoop()
​​​​{
​​​​    static int __s = 0;
​​​​    switch (__s) {
​​​​        case 0:
​​​​            for (;;) {
​​​​                printf("Run to case 0.\n");
​​​​                __s = 1;
​​​​                return;
​​​​        case 1:
​​​​                printf("Run to case 1.\n");
​​​​            }   
​​​​    }
​}

​int main(void)
​{
​​​​    caseInForLoop();
​​​​    caseInForLoop();
​​​​    return 0;
​}

    ​Output:
​Run to case 0.
​Run to case 1.
​Run to case 0.
    • 驚呆了，可以發現到 caseInForLoop() 只有呼叫兩次，但實際輸出卻有三次！
    • 分析：
      • 第一次執行沒有問題，一開始 __s 的值為 0，所以會印出 case 0 的訊息，然後值被改為 1，之後回傳。
      • 然而第二次執行時，__s 值為 1，從輸出可以知道他跳到 case 1 開始執行，之後又回到迴圈頭重新執行，所以又會再輸出一次 case 0 的訊息
      • 我現在才知道 switch-case 的 case 是類似 goto，以 switch statement 裡面的值決定要從 switch block 裡面的那一個點開始執行，而 break 是跟程式說執行到這裡就好了

  • 回到 Jserv 老師的程式，user_thread_1 比較好理解，與測試程式一樣，只有第一次進入時 __s 值為 0，之後在無限迴圈中值都會保持在 21，從 case 21 開始執行，在無限迴圈中印完訊息後，delay、回傳。

  • 至於 user_thread_2，

    • 第一次進入時 __s 為 0，condition 為 1，所以會印出 (1)，__s 變為 32
    • 再來從 case 32 開始，印出 (2)，condition 為 0，__s 變為 36
    • 然後下次進來從 case 36 開始

  • 這樣應該就會發現每次再次呼叫函式時，都會從上次的離開點的下一行開始執行，這正是 coroutine 中 yield 的功能。再檢視一次 cr_yield macro

#define cr_yield \
    { __s = __LINE__; \    // 紀錄下一次進來的起始點
        usleep(THREAD_INTERVAL); \
        return; \          // 離開了
        case __LINE__: ; \ // 再回來就從這裡開始
    }
// 用 __LINE__ macro 作為 case 的好處在於一個函式中
// 可能會使用兩次以上的 yield，所以必須要區分不同 yield
// 的重新進入點，比起手動編碼，不如用行號來區分

Switch-Case

  • switch statement 會從輸入的變數值判斷要從 switch statment block 中的哪一個部分開始執行。而 case 就是一個標籤，告訴 switch statment 可以從哪裡開始，break 則是到哪裡結束。
  • 注意 case 之間的 scope 除非特別指定 (用 {})，否則是相通的。見下例： 
    ​​​​switch (foo) {
​​​​    case 1:
​​​​        int z = 1;
​​​​        printf("%d\n", z);
​​​​        break;
​​​​    case 2:
​​​​        int z = 2;
​​​​        printf("%d\n", z);
​​​​        break;
​​​​}
    • 因為 case 之間的 scope 是相通的，會發現在同一個 switch scope 下出現兩個 z 的宣告 (把 case 無視掉可以比較容易理解)，編譯就會出現錯誤訊息。 
      ​​​​​​​ switch (foo) {
​​​​​​​ //  case 1:
​​​​​​​         int z = 1;
​​​​​​​         printf("%d\n", z);
​​​​​​​         break;
​​​​​​​ //  case 2:
​​​​​​​         int z = 2;
​​​​​​​         printf("%d\n", z);
​​​​​​​         break;
​​​​​​​ }
    • 所以要避免這個情況的話，就要特別指定 z 的 scope，讓他只適用在一個 case statement 下： 
      ​​​​​​​​switch (foo) {
​​​​​​​​    case 1: {
​​​​​​​​        int z = 1;
​​​​​​​​        printf("%d\n", z);
​​​​​​​​        break;
​​​​​​​​    }
​​​​​​​​    case 2: {
​​​​​​​​        int z = 2;
​​​​​​​​        printf("%d\n", z);
​​​​​​​​        break;
​​​​​​​​    }
​​​​​​​​}
    • 或 
      ​​​​​​​​switch (foo) {
​​​​​​​​    case 1: {
​​​​​​​​        int z = 1;
​​​​​​​​        printf("%d\n", z);
​​​​​​​​    }
​​​​​​​​        break;
​​​​​​​​    case 2: {
​​​​​​​​        int z = 2;
​​​​​​​​        printf("%d\n", z);
​​​​​​​​    }
​​​​​​​​        break;
​​​​​​​​}

Refactoring

[Source 1] [Source 2]

  • 「在不改變軟體的外在行為之下，改善既有軟體的內部設計」
  • 對於既有的 context (codebase，原始碼)，找到需要重構的對象 form。form 中有東西因為無法平衡 force 而發出壞味道 (像 long method 就會受到 explanation、sharing、choosing 的 force)，讓整個 form 也有壞味道。
  • Refactoring 可以調和不平衡的 force，讓 form 更合適這個 context (例如：提昇可讀性)，但不一定能完全消除壞味道。
  • Refactoring 隨時在進行 (為了增加功能、除錯、程式碼審閱而觸發 refactoring)

SuperMalloc

  • 原本不同時候配置的記憶體會分散在記憶體的各處。SuperMalloc 針對每種不同的 object 大小給予一塊連續的記憶體，例如：bin 0 專屬於 8 bytes 的 objects，bin 1 專屬於 10 bytes 的 objects 以此類推。size_2_bin 負責運算要配置的物件需要從那一塊記憶體去配置。

作業

程式碼解析

file_align.c

  • 目的在於將檔案中每一行的字串長度貼到指定長度
  • stat：display file or file system status
    • 用 $ man 2 stat 可以看到其函式的用法
    • int stat(const char *pathname, struct stat *buf);
    • struct stat：是用來儲存檔案資訊的資料結構，包含檔案大小、類型、修改日期等資訊
  • strncpy：複製 source 的前 n 個 byte 到 destination
    • 如果 source 的程度小於 n 則會用 0 補滿
  • 經過轉換之後的字串會是：<originText>(會有newline)+<serial of \0>
  • 用 size_t fwrite(const void *ptr, size_t size, size_t nmemb, FILE *stream); 會取來自 *ptr 直接寫入 size * nmemb bytes 到檔案中，不會因為有 null character 而中斷寫入
    • 所以用 vim 開啟 aligned 後的檔案會看到 ^@，這是 null character

程式問題

  1. 第一步先改檔名XD，我覺得用 text_align.c 或 line_align.c 更能描述這個程式的功能
  2. wbuf 是用 malloc 配置的，程式結束時沒有使用 free
  3. 當讀入的字串長度"不等於"要 padding 到的長度，rbuf 的內容才會被複製到 wbuf，問題有二：
    a. 當讀入字串長度等於 padding 的長度時 (!= 0不成立)，沒有任何東西被寫到 wbuf，會造成這筆資料遺失
    b. 當字串資料過長時，會被截短。
    • 我這邊選擇的修正是無論來源字串多長，就是會複製要 padding 的 bytes，但是對於過長的來源字串會輸出警告訊息給使用者








suffix = pad - strlen(rbuf);
// The length of the input text is longer than the length to padding to.
// Warn the user, and still write to the output file but with only
// first "PadToLen" bytes.
if (suffix ＜ 0)
    printf("Warning:"
           " The length of %s is longer than %d.\n", rbuf, pad);
strncpy(wbuf, rbuf, strlen(rbuf));
  1. file.c 與 file_align.c 很相似，查看兩者用途發現 file.c 是模組化的版本
    • 留下模組化的版本，建立 header file，讓主程式及測試程式都可以直接使用。模組化的好處是相容性高，而且只要維護一組程式碼就好

debug.h

  • 提供 macro dprintf，與 printf 的用法一樣，只是會在前面增加 DEBUG: 的字樣，透過定義 DEBUG macro 啟用。
    • 與 c library 提供的 dprintf 功能不一樣，c library 的為將輸出寫入指定的 file descriptor

phonebook_opt.c

  • 第一眼看到函式跟變數名稱不知道用途((淚
    • append_a：主要是用在傳遞給 thread 的訊息之資料結構，以下是修改過後的，更能辨別用途 
      ​​​​​​​​typedef struct _thread_argument {
​​​​​​​​    char *data_begin;
​​​​​​​​    char *data_end;
​​​​​​​​    int threadID;
​​​​​​​​    int numOfThread;
​​​​​​​​    entry *lEentryPool_begin;
​​​​​​​​    entry *lEntry_head;
​​​​​​​​    entry *lEntry_tail;
​​​​​​​​} thread_arg;
      • 其對應產生函式 new_append_a() 改為 createThread_arg()
    • kl

主程式

  1. 將檔案的內容映射到 memory 上，讓每個 thread 可以同時存取。
    • mmap：將指定檔案的資料映射到 process 的 virtual memory space 上，可以防止 blocking I/O 的發生。

    關於 mmap 詳細用法可以參考林哲亘的共筆

    • 根據 manual，有提供 munmap system call 來刪除配給的區塊，不過在程式結束時，這個區塊會自動被 delete 掉。關閉對應的 file descriptor 不會刪除配給的記憶體
  2. 一次建立足夠的空 entry 給所有 thread 使用，避免因為 malloc system call 所造成的 waiting。
  3. pthread_setconcurrency：Setting the concurrency level allows the application to give the system a hint as to the number of kernel-scheduling entities that should be provided for efficient execution of the application，還不太懂用途
  4. 準備每個 thread 所需要的資訊，例如：讀取資料區間的開頭與結尾、寫入資料區間的開頭與結尾等
  5. 創造 thread，開始讓各自的 thread 工作
  6. 等待所有 thread 完成之後將每一段 thread 所屬的 entry list 組合起來

程式問題

  • 開啟 aligned 之後的檔案但是沒有關閉，透過 open 開啟檔案會配置資源給對應的 file descriptor，要用 close 來釋放資源
  • 搭配 valgrind 檢查有無 memory leak 的問題。可以發現 malloc 28次，卻只有 13 次 free 
    ​​​​==4768== HEAP SUMMARY:
​​​​==4768==     in use at exit: 2,199 bytes in 15 blocks
​​​​==4768==   total heap usage: 28 allocs, 13 frees, 8,410,205 bytes allocated
​​​​==4768== 
​​​​==4768== LEAK SUMMARY:
​​​​==4768==    definitely lost: 585 bytes in 11 blocks
​​​​==4768==    indirectly lost: 0 bytes in 0 blocks
​​​​==4768==      possibly lost: 0 bytes in 0 blocks
​​​​==4768==    still reachable: 1,614 bytes in 4 blocks
​​​​==4768==         suppressed: 0 bytes in 0 blocks
​​​​==4768== Rerun with --leak-check=full to see details of leaked memory
  • 處理 memory leak
    • 既然 THREAD_NUM 是在 compilation 時期指定，則隨 THREAD_NUM 變動的 array 長度可以不用使用 malloc
    • thread_args 的元素也是透過 malloc 取得，要 free 掉
    • 在 findName() 中會給找到的 entry 的 lastname 和 detail 配給記憶體，但是沒有處理已經被搜尋過的 entry 不需要再配置記憶體的情況，像在主程式中搜尋 zyxel 就有三次，造成前兩次配置的記憶體遺失。
      • 解決方案：在 mmap 多加一個 PROT_WRITE 的 flag，直接在映射的記憶體上處理 \n，而不配置記憶體給他。另外在 append 中取用一個新的 entry 時也會同時初始化 dtl 為 NULL，讓 findName() 判斷要不要配置新記憶體給他。另一個好處是在釋放 entry 的記憶體時不需要檢查 dtl 是否為 NULL，根據 manual 如果 free() 收到 NULL 並不會做任何事情。

      不過我在修改這裡時發生神奇的事情，原先我只加 PROT_WRITE，會在第一個 assertion (問你有沒有實做 findName 那個) 失敗。將 MAP_SHARE 改成 MAP_PRIVATE 才正常運作。是因為沒有 sync? (同一個程序去修改需要 sync 嗎？)

    • 但還是有 memory leak，所以我透過 valgrind --tool=memcheck --leak-check=yes <executable> 可以更詳細知道哪裡有配置記憶體但沒有 free 的程式碼，還包含 call stack。一個是 pHead 在 main 中被移動到下一個，造成原版的頭遺失。另一個是在 findName() 中配置的 detail 記憶體沒有被一併 free 掉。
    ​​​​==6392== 24 bytes in 1 blocks are definitely lost in loss record 1 of 7
​​​​==6392==    at 0x4C2BBA0: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
​​​​==6392==    by 0x400F79: main (main.c:61)
​​​​==6392== 
​​​​==6392== 107 bytes in 1 blocks are definitely lost in loss record 4 of 7
​​​​==6392==    at 0x4C2BBA0: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
​​​​==6392==    by 0x401535: findName (phonebook_opt.c:18)
​​​​==6392==    by 0x4012A6: main (main.c:148)
    • 修正完還是有 5 個 block lost 掉，但是不知道在哪裡

這時候就要出動 LeakSanitizer，可一併對照 Mozilla Taiwan 的網誌: Address-Sanitizer(ASAN): 一個 C/C++ 記憶體偵錯的工具 jserv
我使用 ASAN 去偵測，但是程式很安靜的結束了，不過我檢查 valgrind 的報表，他標示 5 個 block 是 still reachable，然後查 StackOverflow，提到可以不必擔心這一區塊的 memory，整理到下面。LanKuDot

  • 另外這次的 refactoring 中，主程式花最多時間修改。我感受到為了讓優化過的版本可以運作，所以在 code 中這邊貼一塊，那邊補一塊 (原始版到處都是 #ifndef, #else, #endif)。就好像是要重新粉刷牆面的某一些地方，沒有照著原本牆面的粉刷方向去刷，整面牆就會有各種方向的刷痕。
    • 整理過後讓 free processing、build entry、release the memory 這三個部份都只有一組 OPT 的 condition macro，增加可讀性。

ASAN(Addres-Sanitizer)

  • 偵測 Memory corruption，LLVM 3.1 及 GCC 4.8 後內建 ASAN
  • 可以偵測下列問題
    • Use after free (Dangling pointer dereference)
    • Heap buffer overflow
    • Stack buffer overflow
    • Global buffer overflow
    • Use after return
  • 編譯時加入 -fsanitize=address，編譯器會插入除錯程式碼，再加上 -fno-omit-frame-pointer 可以讓錯誤訊息回報正確的 call stack
  • ASAN 是以 continue-after-error mode 執行，所以就算遇到第一個錯誤，程式還是可以繼續執行
  • 示範一個 use after free 的程式
#include <stdlib.h>

int main(void)
{
    char *x = (char *)malloc(10 * sizeof(char));
    free(x);
    return x[5];    // Use after free
}
Compile: gcc -fsanitize=address -fno-omit-frame-pointer useAfterFree.c

Execution: ./a.out
=================================================================
==4547==ERROR: AddressSanitizer: heap-use-after-free on address 0x60200000eff5 at pc 0x4007f4 bp 0x7ffca341e6a0 sp 0x7ffca341e690
READ of size 1 at 0x60200000eff5 thread T0
    #0 0x4007f3 in main
    #1 0x7f4484687a3f in __libc_start_main
    #2 0x4006c8 in _start

關於 Valgrind 回報的 still reachable

根據這篇回答：memory leak 有兩種定義

  • 配置的記憶體在程式結束後沒有被 free
  • 配置的記憶體無法被 free，因為沒有有效指標指向他

只有第二種才是真正的 memory leak。然而如果 valgrind 回報的區塊是分類在 still reachable 的話 (由於 program 尚在追蹤指向這些區塊的指標)，代表這些區塊雖然還沒被 free，但是之後還是可以被系統取回。所以不必擔心被分類在 still reachable 的區塊

==4443== HEAP SUMMARY:
==4443==     in use at exit: 7,780 bytes in 5 blocks
==4443==   total heap usage: 20 allocs, 15 frees, 8,409,647 bytes allocated
==4443== 
==4443== LEAK SUMMARY:
==4443==    definitely lost: 0 bytes in 0 blocks
==4443==    indirectly lost: 0 bytes in 0 blocks
==4443==      possibly lost: 0 bytes in 0 blocks
==4443==    still reachable: 7,780 bytes in 5 blocks
==4443==         suppressed: 0 bytes in 0 blocks

進一步優化 append()

原本的版本中 append() 還有兩個地方可以改進：

  1. C 中 memory 是以 row-major 的方式儲存，但原本程式碼取址的方式 (包含 data 跟 entry) 卻以 column-major 去存取。這樣會造成大量 cache-miss 和 cache-reference。
    • Thread 0: 0, 3, 6, 9, …
      Thread 1: 1, 4, 7, 10, …
      Thread 2: 2, 5, 8, 11, …
  2. 原版程式中的 local linked list 第一個是空資料，而且在連接的時候，會拋棄第一個 entry。所以如果配給剛好數量的 entry，然後都從第二個 entry 開始填資料，一定會有一筆資料沒有地方填。

所以我做了以下修正：

  1. 每個 thread 取得的 entry 跟 data 會是連續的，以 row-major 的方式取址
    • Thread 0: 0, 1, 2, 3, …
      Thread 1: 10, 11, 12, 13, …
      Thread 2: 20, 21, 22, 23, …
    • 要注意每個 thread 的範圍：我讓每個 thread 分到 num_of_data / THREAD_NUM + 1 的資料去處理，+1 是為了避免餘數集中在最後一個 thread。最後一個 thread 的資料結尾則直接指定 data_pool 的結尾。

    想問這邊 num_of_data / THREAD_NUM + 1 如果無法整除的話該如何處理？？
    我嘗試過這樣做，但是如果在 words.txt 裡新增一筆資料後會有問題…
    littlewhiteYA

  2. 處理第二個問題，必須要先讓第一個 entry 填入資料，才能進入迴圈從第二個 entry 開始處理 (因為第一個 entry 沒有前面可以 append)，也能避免少掉幾個資料的問題。

Cache 分析及執行時間

改變取址的方式得到了大量的改進，起飛拉

  • 改進前：
    • append time：0.019036 sec
 Performance counter stats for './phonebook_opt':

           254,263      cache-misses              #    6.179 % of all cache refs     [76.70%]
         4,115,040      cache-references                                             [49.89%]
       251,354,400      instructions              #    1.12  insns per cycle         [76.12%]
       224,681,630      cycles                    [74.70%]
  • 改進後：得到近一倍的改善
    • append time：0.009584 sec (49.6% improved)
    • cache misses 62.9% improved
    • cache references 41.7% improved
 Performance counter stats for './phonebook_opt':

            94,171      cache-misses              #    3.922 % of all cache refs     [78.01%]
         2,400,810      cache-references                                             [45.85%]
       264,389,689      instructions              #    1.41  insns per cycle         [76.93%]
       187,534,122      cycles                    [78.00%]

效能分析

[append() time], [findname() time] in seconds

  • Baseline：0.145418, 0.022165
  • Optimized_Origin：0.022656, 0.012122
  • Handle memory leak：0.019036, 0.011447
  • Use row-major append()：0.009584(!!!) 0.010219
Last changed by 
 
Kun-Yi Li
0
1622
Published on HackMD