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

Sisker1111(范皓翔)

Sisker1111 (范皓翔)

自我介紹 Introduction

2020冬季班 個人評量

作業及筆記

期末專題 Final Project

  • 主題 Topic：dict
  • 工作 Work：整合 Hw3 同學的成果，並繼續深入研究其相關議題，並更新、補充與改善內容.
  • 成果 Presentation： Github Hackmd

學期回顧 :

(a). 知道 x - y < 0 敘述為何不能寫為 x < y 嗎？ (CS:APP 第 2 章) Ans: 雖然在數學上，x - y < 0 和 x < y 是等價的，但在數值系統中每個型態的數值的上下界的，因此在做 x - y 的運算時有可能產生 overflow 的問題，這樣會使得結果不如預期而導致錯誤發生.

(b). 知道 C 語言規格書如何解釋 ptr++ 和 *ptr++ 行為的差異嗎？ Ans : 規格書寫到 postfix increment 是對 operand 相加一個單位，因此 ptr++ 則是對 ptr 的資料型態相加一個對應的 byte ， *ptr++ 則是取 *ptr 的值之後再對 ptr 加上一個對應的單位.

(c). 知道 void (*signal(int sig, void (*handler)(int))) (int); 這樣的宣告該如何解讀嗎？ Ans:

signal is a pointer to a funtion that takes two parameters:

  1. a parameter named sig of type int.
  2. a parameter named handler which is a pointer to a function taking an int parameter and returning void.

and signal returning a pointer to a function taking an int parameter and returning void.

(d). 知道 Linux 核心 < include/linux/list.h> 裡頭 #define list_for_each_prev(pos, head) for (pos = (head)->prev; pos != (head);pos = pos->prev) 這樣的巨集到底在做什麼？以及 head 使用時需要加小括號，為何？Ans:

  1. 巨集到底在做什麼? 由定義可以知道是在走訪整個link-list，pos為一個指標並指向最後一個項目(head->prev)，以此為起點一路反著訪問下去，終止條件是當pos指向head時，代表已經走訪完一圈了。
  2. head 使用時需要加小括號?

考慮 head 帶入到巨集 list_for_each_prev 的輸入可能是 *ptr 的形式，然後就會致使 *ptr->prev 成為被處理的程式碼，會發生以下錯誤:

若是沒有小括號的話 for loop 起始條件會變成 pos = *ptr->prev，根據 C operator precedence 可以知道會先執行 arrow operator 再作 dereference，而這和我們所希望表現的行為就不一樣了。

(e). 知道從 color space RGBA8888 轉換為 8-bit 灰階的程式如何撰寫，又如何透過 SIMD 進行最佳化嗎？ Ans: 參考資料

(f).知道如何對 linked list 進行 merge sort 嗎？真實世界中的應用場景為何？Ans: linked-list merge sort 的程式可以放在lab0

(g). 知道 memory misalignment 對程式正確性和效能的影響嗎？Ans: CPU通常一次會抓取 4 byte、8 byte的資料，並且是按照順序取的，如果今天沒有對齊，那麼本來只需存取一次記憶體的操作就可能需要存取 2 個不同的 WORD，然後各自做bit shift再組合起來，才有辦法得到想要的值，原本只要存取記憶體一次的，結果現在要兩次，還有額外計算bitshifting的開銷。這是很嚴重的問題，在某些架構上可以造成兩倍以上的效能差異。另外，對於有些RISC架構，例如ARM和MIPS，如果存取未對齊的記憶體處理器會產生alignment fault。

(h). 知道如何用 bit-wise operator 實作 clz / ctz (count leading/tailing zero) 嗎？Ans: clz: 每次都對 x shift不同的變量來算出首位 1 左邊有幾個 0 參考資料，CTZ 可以通過把 x 的每個 Bits 反轉，在實施 CLZ，或者使用 bit-mask 的方式，詳見hackmd。

(i).知道如何寫出時間複雜度和空間複雜度皆為 O(1) 的 abs64 嗎？(沒有分支) 這樣的 abs64 又可用於真實世界哪邊？Ans: 假設傳進來的數叫 a 先 b = a >> 63，然後 return (a ^ b) - b

(k). 知道 C 語言編譯器如何做 Tail Call Optimization (TCO) 嗎？以 gcc 來說，什麼樣的遞迴程式可做TCO，又有什麼樣的遞迴程式無法呢？Ans: tail call optimization 指的是一個函數裡的最後一個動作是回傳另一個函式的呼叫結果的情形，即最後一步新呼叫的回傳值直接被當成當前函式的回傳結果。 幾例來說: return funcB(i - 1); 就是一個 TCO ，而 return 5 * funcA(i - 1); 則不是。 其好處是，TOC是函數的最後一步操作，所以不需要保留外層函數的使用記錄，因為回傳位址與其內部變數等資訊都不會再用到了，只要直接用內層函數的使用記錄，取代外層函數的使用記錄就可以了。

考慮測試 C 編譯器 (TCO) 能力的程式 tco-test，在 gcc-9.3.0 中抑制最佳化 (也就是 -O0 編譯選項) 進行編譯，得到以下執行結果:

$ gcc -Wall -Wextra -Wno-unused-parameter -O0 main.c first.c second.c -o chaining
$ ./chaining
No arguments:                                no TCO
One argument:                                no TCO
Additional int argument:                     no TCO
Dropped int argument:                        no TCO
char return to int:                          no TCO
int return to char:                          no TCO
int return to void:                          no TCO

而在開啟最佳化 (這裡用 -O2 等級) 編譯，會得到以下執行結果:

$ gcc -Wall -Wextra -Wno-unused-parameter -O2 main.c first.c second.c -o chaining
$ ./chaining
No arguments:                                TCO
One argument:                                TCO
Additional int argument:                     TCO
Dropped int argument:                        TCO
char return to int:                          no TCO
int return to char:                          no TCO
int return to void:                          TCO

(q). 知道傅立葉分析在通訊領域的應用嗎？舉例說明 Ans: 傅立葉轉換就是要將一個時域訊號，轉換到頻域上去。不管這個訊號是以時域的方式表現(波形, waveform)，還是以頻域的方式表現出來(頻譜, spectrum)，指的都是同一個訊號. 參考資料

(r). 知道如何用 gcc 內建的 __builtin_ctz 改寫 GCD (最大公因數) 求值程式嗎？做了這樣的最佳化，預期在 x86_64 上可省下多少 cycle 呢? Ans: 可以用 min(__builtin_ctz(u), __builtin_ctz(v)) 找出可以同時將兩數除以幾次 2，程式碼參考如下: Quiz3

(t). 知道 Bloom filter 嗎？以你寫過或用過的程式，舉例說明這機制帶來的好處 Ans: Bloom filter可以讓我們快速查找一個元素是否在一個集合裡面，因為程式會將輸入的 Key value 通過多個 hash function 轉換到所對應的 Table 上做紀錄，查詢時只要確定這 K 個 hash 後取得的值都是 1 即可確定該元素存在集合中，缺點是 Bloom filter 會有 false positive(因為有可能多個 Key hash 到一樣的值)以及無法 Delete 的問題.

(v). 本學期課程內容中，讓你印象最深刻、顛覆過往認知的部分是什麼？請舉例說明 Ans.1:數值系統、pointer 操作、處理器架構等等。

自我評量 (1 ~ 10) Self-assessment

學期剛開始的時候我認為自己還算有點認真，每周都有花一定的時間在專研作業、對小考的code及做一些追蹤及改進，也有確實學到不少觀念及實作，不過還是離jserv本來的原本的預期目標有一些距離就是了。期中之後，不僅開始忙論文的東西，也花很多時間幫實驗室老師撰寫計畫書，讓我空閒之餘都只想好好放鬆，越來越沒花時間在這門課上，說來慚愧，不過這還是因為我自己決心不夠所導致，但我還是想通過這門課不然會白花學分費，所以我還是想給自己好一點的分數，我希望之後我也能鞭策自己透過線上參與的方式再來旁聽老師的課，把以前沒學好的部分一點一點補回來.

總評: 我給自己的分數為 9 分.

心得 Review

這是我第一次修jserv老師的課，當初就是因為大家說這堂課很硬、能學到很多東西就來了，因為我想成為一個比較有競爭力的工程師。首先，這門課給我最大的啟發就是:“發現我自己原來爛的一蹋糊塗”，我覺得這對我而言是很有意義的，因為這能使我更踏實的成長。而本學期的課程主要著重於效能上的提升，這使我們必須更熟悉各種工具的應用來分析出效能瓶頸。不只這些，當一個作業下來，所要查的東西是看也看不完的，更讓我體會到自己離這個資訊世界還非常遙遠，最後，我很慶幸有來修這門課，雖然通過這門課我學會的知識 可能只是全部的冰山一角，但確實讓我成長不少。