分享到plurk 分享到twitter 分享到facebook

ChingChieh(黃敬傑)

黃敬傑

  • 成功大學資訊工程學系108級
  • Github: https://github.com/ChingChieh
  • gmail: garnett.huang@gmail.com
  • 修課: 進階電腦系統理論與實作 (Fall 2018)

作業 Lab

  • lab0:
    • 重新複習 linked-list 實作，以及了解自動評分系統如何偵測 malloc 的記憶體空間是否有正確釋放
    • 共筆
    • Github
  • datalab:
    • 學習利用 bitwise operation 代替 conditional branch 來完成各個 function 所需要的功能
    • 共筆
    • Github
  • dict
    • 探討 memory pool 和每當需要時才 malloc 那個發生 cache miss 機率較高，以及哪個執行速度較快
    • 學習使用 perf 工具來分析程式效能
    • 學習使用 linux 畫圖工具 gnuplot
    • 共筆
  • 期中分組作業
    • 了解 bit field 的 variable 不能對其取址
    • 重新複習 big & little endian 差異以及 union 特性
    • 學習使用 SIMD 來改寫 parity function
    • 共筆
    • 影片
  • 期末分組作業
    • 複習多執行緒的程式以及 mutex ，測試有 mutex lock 的程式在多執行緒的情況下的正確性
    • 看了老師的 concurrent-ll 了解 lockfree 在多執行緒的情況下如何實作
    • 學習利用 valgrind 來 debug 多執行緒的程式
    • 共筆

回顧

  • 知道 x - y < 0 敘述為何不能寫為 x < y 嗎？
    • 假設 x = 1, y = INT_MIN 那便不成立了
  • 知道 C 語言規格書如何解釋 ptr++ 和 *ptr++ 行為的差異嗎？
    • 規格書寫到 postfix increment 是對 operand 相加一個單位
    • 而 ptr++ 則是對 ptr 的資料型態相加一個對應的 byte ， *ptr++ 則是對 *ptr 的值相加一個對應的單位
  • 知道通訊領域中如何應用 parity bit 嗎？
  • 知道 void (*signal(int sig, void (*handler)(int))) (int); 這樣的宣告該如何解讀嗎？
    • signal 這個 function 吃兩個參數，分別是一個 integer 和一個 handler 這個 function pointer 指向吃一個 integer 的參數且沒有回傳值的 function ，而這個 signal 會回傳一個 function pointer 指向吃一個 integer 的參數且沒有回傳值的 function
  • 知道 Linux 核心 < include/linux/list.h> 裡頭 #define list_for_each_prev(pos, head) for (pos = (head)->prev; pos != (head); pos = pos->prev) 這樣的巨集到底在做什麼？以及 head 使用時需要加小括號，為何？
    • 這個 macro 是反方向走訪整個 list ， head 使用時要加小括號是因為 macro 會把傳來的東西直接展開，所以有時候可能會因為 precedence 的問題讓後面的 -> 先做了而出錯
  • 知道如何用 bit-wise operator 實作 clz / ctz (count leading/tailing zero) 嗎？
    • 以 clz 總共 32 bit 來說，技巧就是分成 16 8 4 2 1 1 bit 來檢查，一開始把全部的 bit 先看其中一半是否符合，也就是 31 到 16 bit 是否全部是 0 如果是則讓數字直接左移 16 bits 然後繼續看剩下未檢查的一半 8 bits，如果不符合就不左移然後繼續看剩下未檢查的的一半 8 bits，然後重複以上步驟，最後一定可以檢查完每個bits，當時在 datalab 寫到這題時也是想了很久
  • 知道 C 語言編譯器如何做 Tail Call Optimization (TCO) 嗎？以 gcc 來說，什麼樣的遞迴程式可做 TCO，又有什麼樣的遞迴程式無法呢？
    • 只知道做 TOC 時， 會捨棄 caller 的 stack ，所以如果遞迴程式美呼叫一次自己會是呼叫其他 function 時並不需要知道 caller stack 裡面的值則可以使用 TCO
  • 知道如何寫出時間複雜度和空間複雜度皆為 O(1) 的 abs64 嗎？(沒有分支) 這樣的 abs64 又可用於真實世界哪邊？
    • 假設傳進來的數叫 a 先 b = a >> 63，然後 return (a ^ b) - b
  • 知道如何用 bitwise operator 實作出沒有分支的 FizzBuzz 程式嗎？
    • 參考老師的 Github
    • 裡面用到的技巧是先以一個 mask 分辨所有狀況，在巧妙利用 start 和 length 來切割 “FizzBuzz%u” 這個字串，以達到 3 的倍數印出 Fizz , 5 的倍數印出 Buzz , 15 的倍數印出 FizzBuzz , 其他情況印出數字
  • 知道 Bloom filter 嗎？以你寫過或用過的程式，舉例說明這機制帶來的好處
    • 在 dict 作業裡面有用到，Bloom Filter 就是利用一個 n bits 的 table，不走訪資料結構就能透過這個 table 預測字串是不是在這個資料結構內。而這樣時間複雜度就變為 𝑂(1)。

期末自評(1-10)

總合這學期所學，相比於還未修這門課的我來說我覺得我寫 c 方面有進步，尤其是對指標的理解，也學到滿多好用的工具及技巧，更重要的是一些心態像是誠實面對自己，以前分組時往往會找比自己厲害很多的人一組因為遇到問題時可能比較快就能解決，但修這堂課時我都是跟程度跟自己差不多的人一組，雖然遇到問題時會花比較多時間，但至少是靠自己解決，但有的時候真的想不到還是會問別人，我覺得我有盡力了但老師的課的資訊量真的很多，我還是很多東西不知道，所以我給自己 8 分