2024q1 Homework1 (lab0)

# 2024q1 Homework1 (lab0) contributed by < `yeh-sudo` > ## 開發環境 ```shell $ uname -a Linux andyyeh-ubuntu 6.5.0-21-generic #21~22.04.1-Ubuntu SMP PREEMPT_DYNAMIC Fri Feb 9 13:32:52 UTC 2 x86_64 x86_64 x86_64 GNU/Linux $ gcc --version gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0 Copyright (C) 2021 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 44 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 16 On-line CPU(s) list: 0-15 Vendor ID: AuthenticAMD Model name: AMD Ryzen 7 4800HS with Radeon Graphics CPU family: 23 Model: 96 Thread(s) per core: 2 Core(s) per socket: 8 Socket(s): 1 Stepping: 1 Frequency boost: enabled CPU max MHz: 2900.0000 CPU min MHz: 1400.0000 BogoMIPS: 5788.79 Virtualization features: Virtualization: AMD-V Caches (sum of all): L1d: 256 KiB (8 instances) L1i: 256 KiB (8 instances) L2: 4 MiB (8 instances) L3: 8 MiB (2 instances) ``` ## 指定的佇列操作開發順序依照[作業要求](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-a#-%E6%94%B9%E5%AF%AB%E8%87%AA-CMU-%E9%9B%BB%E8%85%A6%E7%B3%BB%E7%B5%B1%E6%A6%82%E8%AB%96%E7%9A%84%E4%BD%9C%E6%A5%AD)依次進行。 ### `q_new` > commit [544eb0](https://github.com/yeh-sudo/lab0-c/commit/544eb07aeba4e934624013859affb84158fd8702) 配置記憶體空間，並使用 `list.h` 中提供的 `INIT_LIST_HEAD` 進行初始化。 ### `q_free` > commit [544eb0](https://github.com/yeh-sudo/lab0-c/commit/544eb07aeba4e934624013859affb84158fd8702) 首先檢查佇列是否為 `NULL` ，若不為 `NULL` ，則使用 `list_for_entry_safe` 這個巨集，避免在走訪的時候出現未定義行為。 ### `q_insert_head`, `q_insert_tail` 這兩者在邏輯上類似，都是新增一個 `element_t` ，如果是 `q_insert_head` ，在函式最後呼叫的API就是 `list_add` ，如果是 `q_insert_tail` ，則呼叫 `list_add_tail` 。 > commit [544eb0](https://github.com/yeh-sudo/lab0-c/commit/544eb07aeba4e934624013859affb84158fd8702) 在此 commit 中兩者重複的部份太多，會在之後的 commit 中修改。 > commit [68caaa](https://github.com/yeh-sudo/lab0-c/commit/68caaa144f85c32119b0e9b13ab779689c9f9b16) 在這個 commit 中補足巨集 `strlcpy` ，因為我原本的是使用 `strcpy` 將移除節點裡面的字串複製到 `sp` 這個變數之中，但在 commit 時顯示出以下警告訊息。閱讀[訊息中的內容](https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml)，將 `strcpy` 改成建議的方法，確保複製字串是安全的。 ```shell Dangerous function detected in /home/andyyeh/linux2024/lab0-c/queue.c 85: strcpy(sp, remove_element->value); 97: strcpy(sp, remove_element->value); Read 'Common vulnerabilities guide for C programmers' carefully. https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml ``` `strlcpy` 巨集 ```c #ifndef strlcpy #define strlcpy(dst,src,sz) snprintf((dst), (sz), "%s", (src)) #endif ``` ### `q_remove_head`, `q_remove_tail` 這兩者在邏輯上也是相同的，差別在於一開始取得的節點位置， `q_remove_insert` 是取 `head->next` ，而 `q_remove_tail` 是取 `head->prev` 。 > commit [544eb0](https://github.com/yeh-sudo/lab0-c/commit/544eb07aeba4e934624013859affb84158fd8702) 此 commit 的實作也是重複的部份太多。 > commit [68caaa](https://github.com/yeh-sudo/lab0-c/commit/68caaa144f85c32119b0e9b13ab779689c9f9b16) 在執行 `make test` 時，在 `TESTING trace trace-08-robust` 這項測試資料一直觸發 segmentation fault ，經過檢查，發現是在函式一開始沒有檢查佇列是否為空，所以導致 segmentation fault ，補上 `list_empty()` 這個條件就不會在發生錯誤。在其他測試，發現只要有觸發 segmentation fault ，最後的得分顯示位置與其他測資不太一樣，造成版面不一致且閱讀困難。 ```shell +++ TESTING trace trace-07-string: # Test of truncated strings ERROR: Removed value aardvark_bear_dolphin_gerbil_jaguar != expected value meerkat_panda_squirrel_vulture_wolf ERROR: Removed value aardvark_bear_dolphin_gerbil_j != expected value meerkat_panda_squirrel_vulture ERROR: Removed value meerkat_ != expected value aardvark ERROR: Removed value meerkat_panda_squirrel_vulture_wolf != expected value aardvark_bear_dolphin_gerbil_jaguar --- trace-07-string 0/6 +++ TESTING trace trace-08-robust: # Test operations on empty queue Segmentation fault occurred. You dereferenced a NULL or invalid pointer--- trace-08-robust 0/6 +++ TESTING trace trace-09-robust: # Test remove_head with NULL argument --- trace-09-robust 6/6 ``` ### `q_size` > commit [544eb0](https://github.com/yeh-sudo/lab0-c/commit/544eb07aeba4e934624013859affb84158fd8702) 使用 `list_for_each` 去走訪整個鏈結串列，以此算出這個佇列的大小。 ### `q_delete_mid` > commit [544eb0](https://github.com/yeh-sudo/lab0-c/commit/544eb07aeba4e934624013859affb84158fd8702) 使用快慢指標的方式，找出佇列中間的節點並將它刪除。 ### `q_delete_dup` > commit [f379f3](https://github.com/yeh-sudo/lab0-c/commit/f379f34ff2511ce9dac3aa7ede0cccb96ebd6603) 使用 `list_for_each_entry_safe` ，比較 `entry` 和 `safe` 的字串是否相等，如果相等，就將 `delete_entry` 這個變數設為 true ，在 `entry` 和 `safe` 都不相等時，如果 `delete_entry` 為 true ，代表 `entry` 是連續相等字串的最後一個。 ### `q_swap` > commit [bf3125](https://github.com/yeh-sudo/lab0-c/commit/bf31255fe53577398151ea5123f431e2d91d1a80) 原本的做法是使用迴圈走訪整個鏈結串列，並將每一個節點的 `prev` 和 `next` 都交換，但是運行的結果不如預期，有些節點會沒有連結到。 > commit [b64103](https://github.com/yeh-sudo/lab0-c/commit/b64103d619fa8d86b682bee1c500e1d61bdd6894) 捨棄原本的做法，使用 `list.h` 的 `list_move` 將現在的節點移到下一個節點前面，比較簡潔易懂。 ```diff - for (node = head->next; node != head; node = node->next) { - if (node->next == head) { - break; - } - struct list_head *next = node->next; - node->next = next->next; - if (node->prev == head) { - head->next = next; - } - next->prev = node->prev; - node->prev = next; - next->next = node; + for (node = head->next; node != head && node->next != head; + node = node->next) { + list_move(node, node->next); } ``` ### `q_reverse` > commit [949343](https://github.com/yeh-sudo/lab0-c/commit/9493430c5ebbae50a5f59f668af21530a7923254) 原本的做法是將每個節點的 `prev` 與 `next` 互換。 > commit [b64103](https://github.com/yeh-sudo/lab0-c/commit/b64103d619fa8d86b682bee1c500e1d61bdd6894) 經過測試，原本的做法是錯的，想到反轉整個鏈結串列就是將節點刪除再加到開頭的節點上，所以採用 `list_del_init` 與 `list_add` 配合，成功將整個鏈結串列反轉。 ```diff - struct list_head *node; - for (node = head; node != head; node = node->prev) { - struct list_head *next = node->next; - node->next = node->prev; - node->prev = next; + struct list_head *node, *safe; + list_for_each_safe (node, safe, head) { + list_del_init(node); + list_add(node, head); } ``` ### `q_reverseK` > commit [82f7ba](https://github.com/yeh-sudo/lab0-c/commit/82f7bad8f00de45d765a87d7b3babd79e026ce34) 將鏈結串列拆分成很多個長度為 K 的小鏈結串列，並分別將這些較小的鏈結串列反轉，再透過 `list_splice_tail_init` 將反轉過的鏈結串列加入到另外一個鏈結串列中，當全部的鏈結串列反轉過後，就將這些鏈結串列重新加入到 `head` 中。 > commit [5c6a07](https://github.com/yeh-sudo/lab0-c/commit/5c6a07979b987d2c9224994541d8f8394bbe7a15) 原本是使用 `q_new` 去初始化反轉鏈結串列和臨時存放反轉過鏈結串列的 `head` ，但是在進行這項測試的時候，是禁止配置記憶體的，於是改用一般變數的方法宣告以及初始化。 ```diff - struct list_head *tmp_head = q_new(); - struct list_head *reverse_head = q_new(); - struct list_head *node; - int cnt; - for (cnt = 0, node = head->next; node != head;) { + LIST_HEAD(tmp_head); + LIST_HEAD(reverse_head); + struct list_head *node, *safe; + int cnt = 1; + list_for_each_safe (node, safe, head) { if (cnt == k) { - node = node->next; - cnt = 0; - list_cut_position(reverse_head, head, node->prev); - q_reverse(reverse_head); - list_splice_tail(tmp_head, reverse_head); - continue; + list_cut_position(&reverse_head, head, node); + q_reverse(&reverse_head); + list_splice_tail_init(&reverse_head, &tmp_head); + cnt = 1; + } else { + cnt++; } - node = node->next; - cnt++; } - list_splice(tmp_head, head); + list_splice(&tmp_head, head); +} ``` ### `q_sort` > commit [b64103](https://github.com/yeh-sudo/lab0-c/commit/b64103d619fa8d86b682bee1c500e1d61bdd6894) 首先，實作 `mergeTwoLists` 這個函式，參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists)中的 `mergeTwoLists` ，並額外加上 `descend` 這個參數，決定要升序排序或是降序排序。接著實作比較字串大小的 `cmp` 函式。因為才剛學完 bitwise 的章節與操作，我想試試不需要判斷 `cmp` 的大小與 `descend` 參數就可以決定要用 `L1` 的節點還是 `L2` 的節點，參考[解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation#%E5%B8%B8%E6%95%B8%E6%99%82%E9%96%93%E5%AF%A6%E4%BD%9C)中的常數時間實作，將 `strcmp` 的結果右移 31 位，如果比較出來的結果是 `s1 > s2` ，右移 31 位之後會得到 `0x00000000` ，再加上一之後就會變成 `0x00000001` ，但如果 `s1 < s2` ，右移 31 位會得到 `0xffffffff` ，加上一之後會變成 `0x00000000` ，再加上以下的真值表，就可以得出 `cmp(s1, s2) + 1` 與 `descend` 的關係是進行 `xor` 之後再進行 `not` 操作，即可決定要使用 `L1` 或是 `L2` 。 :::danger 避免非必要的項目縮排 (即 `* `)，以清晰、明確，和通順的漢語書寫。 ::: | cmp(s1, s2) + 1 | descend | need | | --- | --- | --- | | 0 | 0 | 1 (L1) | | 0 | 1 | 0 (L2) | | 1 | 0 | 0 (L2) | | 1 | 1 | 1 (L1) | 從此表格可以得出與判斷使用 `L1` 或是 `L2` 的關係式如以下 Version 1 中的第 11 行。 - [ ] Version 1 ```c int cmp(const chat *s1, const chat *s2) { return strcmp(s1, s2) >> 31; } ``` ```c void mergeTwoLists(struct list_head *L1, struct list_head *L2, bool descend) { if (!L1 || !L2) return; struct list_head head; INIT_LIST_HEAD(&head); while (!list_empty(L1) && !list_empty(L2)) { element_t *e1 = list_first_entry(L1, element_t, list); element_t *e2 = list_first_entry(L2, element_t, list); struct list_head *node = !((cmp(e1->value, e2->value) + 1) ^ descend) ? L1->next : L2->next; list_move_tail(node, &head); } list_splice_tail_init(list_empty(L1) ? L2 : L1, &head); list_splice(&head, L1); } ``` 但是在進行 `git commit -a` 時，顯示出以下的錯誤。 ```shell queue.c:223:27: portability: Shifting signed 32-bit value by 31 bits is implementation-defined behaviour [shiftTooManyBitsSigned] return strcmp(s1, s2) >> 31; ``` 依照 C 語言規格書 6.5.7.5 敘述： > The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined. 為了修正這個錯誤，只能改成以下的 Version 2 。 - [ ] Version 2 ```c bool cmp(const char *s1, const char *s2) { return strcmp(s1, s2) > 0 ? true : false; } ``` ```c void mergeTwoLists(struct list_head *L1, struct list_head *L2, bool descend) { if (!L1 || !L2) return; struct list_head head; INIT_LIST_HEAD(&head); while (!list_empty(L1) && !list_empty(L2)) { element_t *e1 = list_first_entry(L1, element_t, list); element_t *e2 = list_first_entry(L2, element_t, list); struct list_head *node = !(cmp(e1->value, e2->value) ^ descend) ? L1->next : L2->next; list_move_tail(node, &head); } list_splice_tail_init(list_empty(L1) ? L2 : L1, &head); list_splice(&head, L1); } ``` 實作完 `mergeTwoLists` 與 `cmp` 兩個函式之後，接著實作 `q_sort` ，參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)中的遞迴版本，以快慢指標的方式找到中間節點並分割成兩個鏈結串列，在遞迴分割後，兩兩分個的鏈節串列使用 `mergeTwoLists` 合併。 ```c struct list_head *slow = head; struct list_head *fast = head->next; for (; fast != head && fast->next != head; fast = fast->next->next) slow = slow->next; struct list_head left; list_cut_position(&left, head, slow); ``` :::warning TODO: 考慮到後續 Timsort 的整合，除了原本亂數產生的節點內容外，要針對不同情境提供排序用的測試資料。 ::: ### `q_ascend`, `q_descend` > commit [5c6a07](https://github.com/yeh-sudo/lab0-c/commit/5c6a07979b987d2c9224994541d8f8394bbe7a15) 兩個函式的作用是差不多的，差別只在於是升序還是降序，所以我用一個函式 `remove_nodes()` 將這兩個操作合併。做法是使用一個堆疊存放節點，當堆疊是空的，就將現行的節點 `entry` 放入堆疊，若不是空的，就將堆疊最上面的元素與現行節點比較，只要判斷式為 `true` ，就會持續將堆疊最上方的元素取出並釋放，當判斷式為 `false` 時，就將現行節點放入堆疊，而判斷式的邏輯與 `q_sort` 類似，就不多贅述，當迴圈結束時，就將堆疊中的元素全部都放回 `head` 中，並回傳鏈結串列的大小。 ```c int remove_nodes(struct list_head *head, bool descend) { if (!head || list_empty(head)) return 0; if (list_is_singular(head)) return 1; element_t *entry, *safe; LIST_HEAD(tmp_head); list_for_each_entry_safe (entry, safe, head, list) { if (list_empty(&tmp_head)) { list_move_tail(&entry->list, &tmp_head); } else { element_t *e = list_last_entry(&tmp_head, element_t, list); while (!list_empty(&tmp_head) && (cmp(e->value, entry->value) ^ descend)) { list_del(&e->list); free(e->value); free(e); e = list_last_entry(&tmp_head, element_t, list); } list_move_tail(&entry->list, &tmp_head); } } list_splice_tail(&tmp_head, head); return q_size(head); } ``` ### `q_merge` > commit [b64103](https://github.com/yeh-sudo/lab0-c/commit/b64103d619fa8d86b682bee1c500e1d61bdd6894) 核心邏輯與 `mergeTwoLists` 函式相同，做法是以 `list_for_each_entry_safe` 走訪整個鏈結串列，並且將現行的鏈結串列 `entry` 與第一個鏈結串列合併，最後回傳第一個鏈結串列的大小。 --- ## 閱讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉提出 [dudect](https://github.com/oreparaz/dudect/tree/master) ，分為以下三個步驟： 1. Measure Execution Time * 使用 fix class 和 random class 作為輸入，不斷測量函式的執行時間。 * 為了將環境對結果的影響降到最低，美一次測量都對應到一個隨機的類別，並且，決定類別與準備輸入資料的工作都在測量前結束。 3. Apply Post-processing * Cropping 。 * Higher-order preprocessing 。 5. Apply Statistical Test 使用統計方法嘗試拒絕虛無假設，「 the two timing distributions are equal 」，若拒絕，則說明程式不是以常數時間運行。 * 使用 t-test 檢測平均值，也是本次作業使用的方法。 * 使用 non-parametric test ，但可能收斂較慢且需要更多樣本。 ### Simulation 原理 `oreparaz/dudect` 中的 `dudect_main` 對應到 `dudect/fixture.c` 中的 `doit` ，而 `lab0-c` 的執行順序是如下，而 `lab0-c` 缺少 `percentile` 的步驟，也就是去除極端值。 1. `measure` 測量方法都是先插入一個字串，再測量插入令一個字串或是刪除的時間，若兩者之間的佇列大小差值不是 1 ，則算失敗。 2. `differentiate` 取 `before_ticks` 與 `after_ticks` 的差值。 3. `update_statistics` 透過 `t-push` 執行 t-test。 4. `report` 得出函式是否為常數時間。 ### `percentile` `percentile` 在 [dudect](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 中對應的程式碼如下，目的是為了去除極端值。 ```c=205 static int64_t percentile(int64_t *a_sorted, double which, size_t size) { size_t array_position = (size_t)((double)size * (double)which); assert(array_position < size); return a_sorted[array_position]; } /* set different thresholds for cropping measurements. the exponential tendency is meant to approximately match the measurements distribution, but there's not more science than that. */ static void prepare_percentiles(dudect_ctx_t *ctx) { qsort(ctx->exec_times, ctx->config->number_measurements, sizeof(int64_t), (int (*)(const void *, const void *))cmp); for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) { ctx->percentiles[i] = percentile( ctx->exec_times, 1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)), ctx->config->number_measurements); } } ``` > 去除極端值可參考 [25077667](https://hackmd.io/@25077667/SkpLspWnT#%E6%94%B9%E9%80%B2-dudect-%E5%AF%A6%E4%BD%9C) 的實作。 > commit [f379f3](https://github.com/yeh-sudo/lab0-c/commit/f379f34ff2511ce9dac3aa7ede0cccb96ebd6603) ```diff bool ret = measure(before_ticks, after_ticks, input_data, mode); differentiate(exec_times, before_ticks, after_ticks); + prepare_percentiles(exec_times); update_statistics(exec_times, classes); ret &= report(); ``` ```diff static void update_statistics(const int64_t *exec_times, uint8_t *classes) { - for (size_t i = 0; i < N_MEASURES; i++) { + for (size_t i = 10; i < N_MEASURES; i++) { int64_t difference = exec_times[i]; /* CPU cycle counter overflowed or dropped measurement */ - if (difference <= 0) + if (difference < 0) continue; /* do a t-test on the execution time */ - t_push(t, difference, classes[i]); + t_push(t[0], difference, classes[i]); + + for (size_t crop_index = 0; crop_index < DUDECT_NUMBER_PERCENTILES; + crop_index++) { + if (difference < percentiles[crop_index]) { + t_push(t[crop_index + 1], difference, classes[i]); + } + } } } ``` :::warning 當你確認上方程式碼修改符合論文精神 (部分內容不精準，需要重新詮釋)，對 `sysprog21/lab0-c` 提交 pull request。 ::: --- ## 以 Valgrind 排除記憶體錯誤以 `make valgrind` 運行，在 `trace-17-complexity` 出現以下錯誤。訊息顯示在 `fixture.c` 中的 `test_const` 有記憶體洩漏。 ```shell # Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant Probably constant time Probably constant time Probably constant time Probably constant time ==6944== 48 bytes in 1 blocks are possibly lost in loss record 1 of 5 ==6944== at 0x484DA83: calloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==6944== by 0x1108C0: test_const (fixture.c:213) ==6944== by 0x110E70: is_insert_head_const (fixture.c:245) ==6944== by 0x10C988: queue_insert (qtest.c:190) ==6944== by 0x10CD40: do_ih (qtest.c:280) ==6944== by 0x10E011: interpret_cmda (console.c:181) ==6944== by 0x10E5C6: interpret_cmd (console.c:201) ==6944== by 0x10E9C7: cmd_select (console.c:610) ==6944== by 0x10F2B3: run_console (console.c:705) ==6944== by 0x10D403: main (qtest.c:1258) ==6944== ==6944== 4,848 bytes in 101 blocks are definitely lost in loss record 2 of 5 ==6944== at 0x484DA83: calloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==6944== by 0x1108C0: test_const (fixture.c:213) ==6944== by 0x110E70: is_insert_head_const (fixture.c:245) ==6944== by 0x10C988: queue_insert (qtest.c:190) ==6944== by 0x10CD40: do_ih (qtest.c:280) ==6944== by 0x10E011: interpret_cmda (console.c:181) ==6944== by 0x10E5C6: interpret_cmd (console.c:201) ==6944== by 0x10E9C7: cmd_select (console.c:610) ==6944== by 0x10F2B3: run_console (console.c:705) ==6944== by 0x10D403: main (qtest.c:1258) ==6944== ==6944== 4,896 bytes in 102 blocks are definitely lost in loss record 3 of 5 ==6944== at 0x484DA83: calloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==6944== by 0x1108C0: test_const (fixture.c:213) ==6944== by 0x110E8E: is_insert_tail_const (fixture.c:245) ==6944== by 0x10C93F: queue_insert (qtest.c:190) ==6944== by 0x10CD24: do_it (qtest.c:286) ==6944== by 0x10E011: interpret_cmda (console.c:181) ==6944== by 0x10E5C6: interpret_cmd (console.c:201) ==6944== by 0x10E9C7: cmd_select (console.c:610) ==6944== by 0x10F2B3: run_console (console.c:705) ==6944== by 0x10D403: main (qtest.c:1258) ==6944== ==6944== 4,896 bytes in 102 blocks are definitely lost in loss record 4 of 5 ==6944== at 0x484DA83: calloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==6944== by 0x1108C0: test_const (fixture.c:213) ==6944== by 0x110EAC: is_remove_head_const (fixture.c:245) ==6944== by 0x10C4B2: queue_remove (qtest.c:302) ==6944== by 0x10C8FC: do_rh (qtest.c:410) ==6944== by 0x10E011: interpret_cmda (console.c:181) ==6944== by 0x10E5C6: interpret_cmd (console.c:201) ==6944== by 0x10E9C7: cmd_select (console.c:610) ==6944== by 0x10F2B3: run_console (console.c:705) ==6944== by 0x10D403: main (qtest.c:1258) ==6944== ==6944== 4,896 bytes in 102 blocks are definitely lost in loss record 5 of 5 ==6944== at 0x484DA83: calloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==6944== by 0x1108C0: test_const (fixture.c:213) ==6944== by 0x110ECA: is_remove_tail_const (fixture.c:245) ==6944== by 0x10C469: queue_remove (qtest.c:302) ==6944== by 0x10C8E0: do_rt (qtest.c:415) ==6944== by 0x10E011: interpret_cmda (console.c:181) ==6944== by 0x10E5C6: interpret_cmd (console.c:201) ==6944== by 0x10E9C7: cmd_select (console.c:610) ==6944== by 0x10F2B3: run_console (console.c:705) ==6944== by 0x10D403: main (qtest.c:1258) ==6944== ``` :::danger 從錯誤訊息中，摘錄後續討論用到的部分即可。 > 了解。 ::: 經過檢查，發現在 `init_once` 函式中重複配置記憶體，導致記憶體洩漏，修改完程式碼後， valgrind 就沒有再顯示有任何的記憶體洩漏或是其他錯誤。 > commit [2234ec](https://github.com/yeh-sudo/lab0-c/commit/2234ec9510ed1e60862c95a38658c2d92a92662b) ```diff @@ -201,7 +201,6 @@ static void init_once(void) { init_dut(); for (int i = 0; i < DUDECT_TESTS; i++) { - t[i] = calloc(1, sizeof(t_context_t)); t_init(t[i]); } } ``` Valgrind 測試結果 ```shell scripts/driver.py -p /tmp/qtest.nfmAYL --valgrind --- Trace Points +++ TESTING trace trace-01-ops: # Test of insert_head and remove_head --- trace-01-ops 5/5 ... # Test performance of insert_tail --- trace-16-perf 6/6 +++ TESTING trace trace-17-complexity: # Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant Probably constant time Probably constant time Probably constant time Probably constant time --- trace-17-complexity 5/5 --- TOTAL 100/100 Test with specific case by running command: scripts/driver.py -p /tmp/qtest.nfmAYL --valgrind -t <tid> ``` ## 整合 Timsort ### 實作並測試 Timsort 正確性 > commit [bfad4d](https://github.com/yeh-sudo/lab0-c/commit/bfad4dd6119cc34124b2c305bde4311d5e1aca17) 在整合之前，為了之後能將 Timsort 與 `q_sort` 一起測試，將參數都統一，我修改了 `cmp` 這個函式，加入 `priv` 計算比較次數。 ```diff -bool cmp(const char *s1, const char *s2) +bool cmp(void *priv, const char *s1, const char *s2) { + if (priv) + *((int *) priv) += 1; return strcmp(s1, s2) > 0 ? true : false; } ``` 另外，與測驗不同的是，在這裡的 Timsort 必須要是比較字串，還要有決定升序或是降序的功能，所以也必須要修改 Timsort 中相對應的程式碼。 Timsort 中的所以函式都必須再多增加一個參數 `descend` 用來決定要升序還是降序，另外，有使用到 `cmp` 的函式，判斷條件都要改成與 `qsort` 一樣。 - [ ] 以 `merge` 函式為例 ```diff static struct list_head *merge(void *priv, list_cmp_func_t cmp, struct list_head *a, - struct list_head *b) + struct list_head *b, + bool descend) { struct list_head *head; struct list_head **tail = &head; @@ -30,11 +32,15 @@ for (node = NULL; a && b; *node = (*node)->next) { /* if equal, take 'a' -- important for sort stability */ - node = (cmp(priv, a, b) <= 0) ? &a : &b; + node = !(cmp(priv, list_entry(a, element_t, list)->value, + list_entry(b, element_t, list)->value) ^ + descend) + ? &a + : &b; *tail = *node; tail = &(*tail)->next; } - *tail = (struct list_head *)((uintptr_t) a | (uintptr_t) b); + *tail = (struct list_head *) ((uintptr_t) a | (uintptr_t) b); return head; } ``` 接著在 `qtest` 中新增 `timsort` 的命令，用來測試 Timsort 的正確性，修改 `traces/trace-15-perf.cmd` ，將 `sort` 命令改成 `timsort` ，另外加入 `descend` 命令，同時檢測升序與降序的正確性，並且確認時間複雜度在 $O(nlogn)$，測試後沒有出現錯誤，以 valgrind 檢測，也沒有出現記憶體洩漏。 ``` # Test performance of Timsort with random and descending orders # 10000: all correct sorting algorithms are expected pass # 50000: sorting algorithms with O(n^2) time complexity are expected failed # 100000: sorting algorithms with O(nlogn) time complexity are expected pass option fail 0 option malloc 0 new ih RAND 10000 timsort reverse timsort free new ih RAND 50000 timsort reverse timsort free new ih RAND 100000 timsort reverse timsort free option descend 1 new ih RAND 10000 timsort reverse timsort free new ih RAND 50000 timsort reverse timsort free new ih RAND 100000 timsort reverse timsort free ``` - [ ] Valgrind 測試結果 ![Screenshot from 2024-03-15 15-19-05](https://hackmd.io/_uploads/HktFI_W0a.png) ### 問題 1 ：無法修改 `queue.h` 我在 `queue.h` 中新增操作 `q_timsort` ，結果在 commit 時出現以下警告， pre-commit 設定 `queue.h` 與 `list.h` 是無法修改的，意謂現階段我沒辦法新增 `q_timsort` 的操作，要另外想辦法。 ```shell Following files need to be cleaned up: qtest.c queue.c queue.h sort_impl.h timsort.c /usr/bin/sha1sum: WARNING: 1 computed checksum did NOT match [!] You are not allowed to change the header file queue.h or list.h ``` - [ ] 修改 `queue.h` ```diff /** * q_sort() - Sort elements of queue in ascending/descending order + * @priv: count the number of compare calls * @head: header of queue * @descend: whether or not to sort in descending order * * No effect if queue is NULL or empty. If there has only one element, do * nothing. */ -void q_sort(struct list_head *head, bool descend); +void q_sort(void *priv, struct list_head *head, bool descend); /** * q_ascend() - Remove every node which has a node with a strictly less @@ -250,4 +251,16 @@ int q_descend(struct list_head *head); */ int q_merge(struct list_head *head, bool descend); + +/** + * q_timsort() - Sort elements of queue in ascending/descending order by Timsort + * @priv: count the number of compare calls + * @head: header of queue + * @descend: whether or not to sort in descending order + * + * No effect if queue is NULL or empty. If there has only one element, do + * nothing. + */ +void q_timsort(void *priv, struct list_head *head, bool descend); + #endif /* LAB0_QUEUE_H */ ``` ### 問題 2 ： Null pointer dereference 修改完之後，再做一次 commit ，這次是沒辦法通過靜態檢查，顯示的錯誤訊息如下，但是在 `merge` 與 `merge_final` 中迴圈的判斷條件是 `a && b` ，而在 `find_run` 中的判斷條件是 `while(next && ...)` ，因此在使用 `list_entry` 時，傳入的參數不可能出現 `NULL` ，經過確認我的 Cppcheck 版本為 2.7 ，並且參考 [jasperlin1996](https://hackmd.io/@jasperlin1996/linux2022-lab0#Cppcheck-Null-pointer-dereference) 的 pull request ，其中有說明這個錯誤是因為 `container_of` 中的 `(type *) 0` 造成，修改 pre-commit.hook 後順利 commit 。 > C99 (6.3.2.3): An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant. ```shell Following files need to be cleaned up: qtest.c queue.c sort_impl.h timsort.c timsort.c:35:28: error: Null pointer dereference: (struct element_t*)0 [nullPointer] node = !(cmp(priv, list_entry(a, element_t, list)->value, ^ timsort.c:36:22: error: Null pointer dereference: (struct element_t*)0 [nullPointer] list_entry(b, element_t, list)->value) ^ ^ timsort.c:76:28: error: Null pointer dereference: (struct element_t*)0 [nullPointer] node = !(cmp(priv, list_entry(a, element_t, list)->value, ^ timsort.c:77:22: error: Null pointer dereference: (struct element_t*)0 [nullPointer] list_entry(b, element_t, list)->value) ^ ^ timsort.c:104:19: error: Null pointer dereference: (struct element_t*)0 [nullPointer] if (cmp(priv, list_entry(list, element_t, list)->value, ^ timsort.c:105:13: error: Null pointer dereference: (struct element_t*)0 [nullPointer] list_entry(next, element_t, list)->value) ^ ^ timsort.c:116:36: error: Null pointer dereference: (struct element_t*)0 [nullPointer] } while (next && cmp(priv, list_entry(list, element_t, list)->value, ^ timsort.c:117:30: error: Null pointer dereference: (struct element_t*)0 [nullPointer] list_entry(next, element_t, list)->value) ^ ^ timsort.c:125:38: error: Null pointer dereference: (struct element_t*)0 [nullPointer] } while (next && !(cmp(priv, list_entry(list, element_t, list)->value, ^ timsort.c:126:32: error: Null pointer dereference: (struct element_t*)0 [nullPointer] list_entry(next, element_t, list)->value) ^ ^ Fail to pass static analysis. ``` - [ ] 修改 pre-commit.hook ```diff --suppress=nullPointerRedundantCheck:harness.c \ --suppress=nullPointer:queue.c \ --suppress=nullPointer:qtest.c \ +--suppress=nullPointer:timsort.c \ --suppress=returnDanglingLifetime:report.c \ --suppress=constParameterCallback:console.c \ --suppress=constParameterPointer:console.c \ ``` ### 問題 3 ： Misspelled word 在撰寫完 commit message 之後進行存檔，又顯示出拼字錯誤，結果是檢查到 Timsort ，因為暫時想不到解決方法，所以只能先將 Timsort 改成 another sort 。 ```shell Implement Timsort and test it's correctness [line 1] - Possible misspelled word(s): Timsort How to Write a Git Commit Message: https://chris.beams.io/posts/git-commit/ Proceed with commit? [e/n/?] ``` --- ## 整合 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) ### [Bottom-up Mergesort: A Detailed Analysis](https://doi.org/10.1007/BF01294131) 這篇論文分析了 bottom-up 的合併排序法，得出最佳、平均與最差情況下的比較次數，並與 top-down 的合併排序法進行比較。 | | best case | average case | worst case | | --------- |:--------------:|:--------------:|:--------------:| | top-down | $nlogn-0.146n$ | $nlogn-1.248n$ | $nlogn-0.943n$ | | bottom-up | $nlogn-0.146n$ | $nlogn-0.965n$ | $nlogn-0.701n$ | 在 commit [b5c56e](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09) 中，多次使用這篇論文的數值，像是 bottom-up 的係數 0.965 ，並且也提出了使用 queue-mergesort 的特性，解決了 bottom-up 合併排序在 n 比大小為 2 的冪次多一點點，效能變差的情況，例如 commit 文中提到的 n=1028 。 > The simple eager merge pattern causes bad performance when n is just over a power of 2. If n=1028, the final merge is between 1024- and 4-element lists, which is wasteful of comparisons. (This is actually worse on average than n=1025, because a 1204:1 merge will, on average, end after 512 compares, while 1024:4 will walk 4/5 of the list.) > > 在 commit 中， n=1025 的舉例，後面應該是 1024:1 而不是 1204:1 。 ### [Queue-mergesort](https://doi.org/10.1016/0020-0190(93)90088-q) 這篇論文介紹了合併排序法的另一種變形，適合用來對鏈結串列進行排序的 queue-mergesort ，藉由不斷將佇列中的鏈結串列取出，合併後再放回佇列裡面來達成排序的目的，也證明了 queue-mergesort 是 optimal mergesort ，也就是在最差的情況下，比較次數小於或等於其他種合併排序。與 bottom-up 的合併排序法進行比較，在最差情況， $n=2^k+1$ 時， bottom-up 合併排序會比 optimal 的合併排序多出 $n-log_2n$ 次比較次數，但在這篇論文中，並沒有提及合併時要維持 2 : 1 的比例，也沒有任何與 cache 優化相關的敘述。 ``` queue-mergesort(Q): while (Q.size != 1) do Q.put(Merge(Q.get, Q.get)) ``` ### 將 `list_sort.c` 引入 `lab0-c` > commit [6f1a59](https://github.com/yeh-sudo/lab0-c/commit/6f1a5954f074a67a3da96221e24b0422bed07b6a) 有了引入 Timsort 的經驗，我以同樣的方式引入 list_sort ，在 `qtest.c` 中新增新的命令 `listsort` ，接著修改 list_sort 中的 `cmp` 函式，讓比較的規則與 Timsort 和 q_sort 相同，最後修改 `pre-commit.hook` ，使 `Null pointer dereference` 的錯誤不要出現。 - [ ] 在 `qtest.c` 中新增命令 ```diff ADD_COMMAND(reverseK, "Reverse the nodes of the queue 'K' at a time", "[K]"); ADD_COMMAND(timsort, "Sort the queue with Timsort", ""); + ADD_COMMAND(listsort, "Sort the queue with list_sort", ""); add_param("length", &string_length, "Maximum length of displayed string", NULL); add_param("malloc", &fail_probability, "Malloc failure probability percent", ``` - [ ] 修改 `pre-commit.hook` ```diff --suppress=nullPointer:queue.c \ --suppress=nullPointer:qtest.c \ --suppress=nullPointer:timsort.c \ +--suppress=nullPointer:list_sort.c \ --suppress=returnDanglingLifetime:report.c \ --suppress=constParameterCallback:console.c \ --suppress=constParameterPointer:console.c \ ``` 與 Timsort 一樣，修改 `trace-15-perf.cmd` 進行測試，沒有發生錯誤，並以 valgrind 檢測結果，沒有記憶體洩漏。 - [ ] Valgrind 測試結果 ![image](https://hackmd.io/_uploads/SkWp53BCp.png) --- ## 提供新的命令 `shuffle` > commit [b4c4e9](https://github.com/yeh-sudo/lab0-c/commit/b4c4e952b3598c84610733bb34b3102bc1e80ae8) 在 `qtest.c` 加入新的命令 `shuffle` ，並新增 shuffle.c ，在這個檔案中實作 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) ，依照維基百科中的虛擬碼進行實作，不斷將 `len` 減一，將最後一個沒有被抽到的節點與隨機抽取的節點作交換，交換的方式是使用 `list_move` 移動節點，直到整個鏈結串列的節點都被抽到後，就結束 shuffle 。 ```diff ADD_COMMAND(timsort, "Sort the queue with Timsort", ""); ADD_COMMAND(listsort, "Sort the queue with list_sort", ""); + ADD_COMMAND(shuffle, "Shuffle all the nodes in queue with Fisher-Yates shuffle", ""); add_param("length", &string_length, "Maximum length of displayed string", NULL); ``` - [ ] shuffle.c ```c while (len >= 1) { int random = rand() % len; old = q_nth_node(head, random); prev = old->prev; if (old != new) { list_move(old, new); list_move(new, prev); } new = old->prev; len--; } ``` ### 測試結果利用[作業說明](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F)中的測試程式，得出的圖表是大致符合 uniform distribution 的。 ![Figure_1](https://hackmd.io/_uploads/ryYwVbwCp.png) --- ## 以不同的資料測試排序演算法 ### 新增 `mergesort` 命令新增 `mergesort` 命令用來執行合併排序，因為 `queue.c` 沒辦法修改，使得想要在 `q_sort` 的參數中代入計算比較次數的 `count` 會變得麻煩，所以直接將合併排序法獨立出來，其中的實作方式與 `q_sort` 一模一樣。 ```diff ADD_COMMAND(listsort, "Sort the queue with list_sort", ""); ADD_COMMAND(shuffle, "Shuffle all the nodes in queue with Fisher-Yates shuffle", ""); + ADD_COMMAND(mergesort, "Sort the queue with list_sort", ""); add_param("length", &string_length, "Maximum length of displayed string", NULL); add_param("malloc", &fail_probability, "Malloc failure probability percent", ``` ### 新增 `quicksort` 命令新增 `quicksort` 命令，將測驗 1 的 quick 移植過來，選擇 pivot 的方式選用效能測試中最穩定的隨機選取，詳細實作請見 [2024q1 Homework2 (quiz1+2)](https://hackmd.io/godDgeeFQGGO1tWZtU9LSQ?view#%E8%A7%A3%E9%87%8B-quick-sort-%E7%A8%8B%E5%BC%8F%E7%A2%BC%E7%9A%84%E9%81%8B%E4%BD%9C%E5%8E%9F%E7%90%86) 。 ```diff ADD_COMMAND(timsort, "Sort the queue with Timsort", ""); ADD_COMMAND(listsort, "Sort the queue with list_sort", ""); + ADD_COMMAND(mergesort, "Sort the queue with merge sort", ""); + ADD_COMMAND(quicksort, "Sort the queue with quick sort", ""); ADD_COMMAND(shuffle, "Shuffle all the nodes in queue with Fisher-Yates shuffle", ""); - ADD_COMMAND(mergesort, "Sort the queue with list_sort", ""); add_param("length", &string_length, "Maximum length of displayed string", NULL); add_param("malloc", &fail_probability, "Malloc failure probability percent", ``` ### 修改 `shuffle` 函式在現實世界的資料中，很多往往都不是完全隨機的，因此，我在 `shuffle` 函式中多加入了一個參數 `n` ，代表要進行幾次 `shuffle` ，如果 `n` 為 0 ，則進行 Fisher-Yates shuffle ，若 `n` 不為 0 ，則進行 `n` 次 shuffle 的操作，以下面的例子為例，原本排序好的鏈結串列，在經過 4 次 shuffle 後，會變成一個部份排序好的鏈結串列。 ```shell cmd> show Current queue ID: 0 l = [0 1 2 3 4 5 6 7 8 9] cmd> shuffle 4 l = [6 7 2 3 4 5 9 8 1 0] ``` - [ ] 修改 `shuffle` ```diff -void shuffle(struct list_head *head) +void shuffle(struct list_head *head, int n) { if (!head || list_empty(head) || list_is_singular(head)) return; - int len = q_size(head); + int len = (n == 0) ? q_size(head) : n; struct list_head *prev = NULL; struct list_head *old = NULL; ``` ### 進行測試 #### 測試 `1`: 隨機資料 ##### 比較次數以隨機資料測試四種排序演算法的比較次數，其中，快速排序法的表現是最差的，其比較次數高出其他排序演算法很多，根據[維基百科](https://en.wikipedia.org/wiki/Quicksort#Using_recurrences)的敘述，快速排序法需要經過大約 $1.39nlogn$ 的比較次數，遠比合併排序要大的多。 Timsort 在針對隨機的鏈結串列排序的表現稍差，由於隨機的資料有可能被分成很多很小的 run ，為了分割這些很小的 run ，在比較次數上就略多於合併排序。在 commit [b5c56e](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09) 中的第三篇論文有提到， top-down 與 queue-mergesort 都是 optimal merge sort ，但是兩者的比較次數仍是 top-down 的方法較小，在 commit 中也有點出 list_sort 的方法比較次數與 top-down 的方法相差 $0.04n$ 倍。 :::warning 在〈[Linux 核心的鏈結串列排序](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-e#%E8%AD%89%E6%98%8E-list_sort-%E7%9A%84%E6%BC%94%E7%AE%97%E6%B3%95%E6%98%AF-optimal-mergesort)〉中有證明 list_sort 是 optimal sort ，為何 top-down merge sort 與 list_sort 都是 optimal merge sort ，但還是會有微小的差距？ ::: ![counts](https://hackmd.io/_uploads/S1f0xdaR6.png) ##### 執行時間執行時間使用 `dudect` 裡面的 `cpucycle` 進行測量，由於快速排序法是使用隨機挑選 `pivot` ，會需要額外的時間成本來存取 `pivot` ，由於 Timsort 與 list_sort 都是採用深度優先的合併順序，將較於對 cache 較不友善的 top-down 方法， Timsort 與 list_sort 的執行時間會快一點，由於是隨機的鏈結串列， Timsort 的效能又會比 list_sort 再差一些。 ![cycles](https://hackmd.io/_uploads/rkkkqOTRT.png) #### 測試 `2`: 已排序資料 ##### 比較次數比較次數的與隨機資料的結果，兩種合併排序法與快速排序法的順序是一樣的，但是 Timsort 的比較次數領先了一大截，因為已排序的鏈結串列就是部份排序的資料的特例，所以相比於隨機資料有顯著的提升。 ![counts](https://hackmd.io/_uploads/BJVcgFT0T.png) ##### 執行時間在這個例子中， Timsort 只分割出一個 run ，不需要進行其他合併的操作，所以效能相比於合併排序更好。 ![cycles](https://hackmd.io/_uploads/H1molFpCT.png) #### 測試 `3`: 部份排序 #### 比較次數測試 `3` 的結果與測試 `2` 相同，都是 Timsort 比較次數最好，而 top-down 合併排序法與 list_sort 幾乎一模一樣，在這個部份比較符合 optimal merge sort 的定義。 ![counts](https://hackmd.io/_uploads/r1BgM56Ap.png) #### 執行時間由於 Timsort 分割 run 的特性，使得它的效能比 list_sort 好一點，而 top-down 由於對 cache 不友善，所以效能與前兩者有落差。 ![cycles](https://hackmd.io/_uploads/SyLZfqaCp.png) ### 分析 cache --- ## 閱讀〈[Teach Yourself Programming in Ten Years](https://norvig.com/21-days.html)〉 ### 踏實在聽老師上課與我們的互動時，可以很清楚的感受到，老師希望我的深入的了解一件事背後的原理，而不是只有完成作業的要求，在與同學的互動中，總會有同學沒辦法對目前自己做的作業有清楚的理解，例如在課堂討論中，老師問同學快速排序法與合併排序法的差異，以及兩者的 locality 哪個較好，但同學僅止於做好作業的要求，完成程式碼的實作，沒有深入探討兩者的差異。一件事新不新其實一點都不重要，關鍵是「做得好不好」。 > As Alexander Pope said, a little learning is a dangerous thing. > One possible point is that you have to learn a tiny bit of C++ (or more likely, something like JavaScript or Processing) because you need to interface with an existing tool to accomplish a specific task. But then you're not learning how to program; you're learning to accomplish that task. ### 寫作業才是主體在本學期的第一堂課，也就是課程說明，在投影片中清楚地說，本課程寫作業才是主體，在課堂中最主要是做互動，老師花三小時講解作業規範，學員花 30 小時學習並在過程中檢討，也說不適合的選修學生族群是「覺得每週看著游泳教練或鋼琴教師表演，但自己不下水或不動手，卻又期盼可學到什麼技能的人」。 > The best kind of learning is learning by doing. ### 師生互動授課時間最主要是師生互動，包含 code review 、問答還有認識自己，老師在業界待了很多年，也算是 programmers ，與其他的 programming 討論，才能意識的自己的不足，有經驗的 programmers ，包含以後面試的主管或是資深工程師，判斷一個人懂不懂，只需要一些很基礎的問題，這些問題看似不難，但對於沒辦法深入了解一件事背後原理的人來說，是非常困難的問題，老師在上課的時候就像模擬面試，我在課堂分享我的[快速排序的實作評估](https://hackmd.io/_GIs8jAvQH2q505AiAbQ4A#yeh-sudo)時，清楚的感受到面試的氛圍，我自己也有面試過一些公司，但都是實習生的職位，問的問題都非常淺，但假如今天是面試正職，我已經被刷掉了。另外，老師在上課時常講一句話，「每天都與大牛合作討論，怎麼能不牛」，經由與更有經驗的 programmer 討論，或是親自參與開源專案，與開發者互動，學到那些大師們的經驗，勝過單純只閱讀網路上的教材或書籍。 > Talk with other programmers; read other programs. This is more important than any book or training course. > When you're the worst, you learn what the masters do, and you learn what they don't like to do (because they make you do it for them). ### 閱讀各種第一手資料與規格書老師在同學們的作業中，或是講座中，時常會強調一定要閱讀 C 語言規格書，還要了解編譯器的原理，也有許多作業要求是要我們援引規格書中的解釋，目的是要讓我們更加了解 C 語言的特性，寫出更優雅簡潔的程式碼，也要讓我們重視程式安全性的議題，避免因為忽略了規格書或是編譯器的規範，而造成程式的錯誤，或是遭到各種攻擊，歷史上有太多事件都是因為程式碼的疏忽而造成不必要的人員傷亡或是巨大的金錢損失，在[軟體缺失導致的危害](https://hackmd.io/@sysprog/software-failure)這份教材中就有許多血淋淋的案例。 > Get involved in a language standardization effort.