# 2022q1 Quiz2 ###### tags: `linux2022` contributed by <[ganoliz](https://github.com/ganoliz)> ## 測驗1 考慮以下對二個無號整數取平均值的程式碼: ```c #include <stdint.h> uint32_t average(uint32_t a, uint32_t b) { return (a + b) / 2; } ``` 這個直覺的解法會有 overflow 的問題，若我們已知 a, b 數值的大小，可用下方程式避免 overflow: ```c #include <stdint.h> uint32_t average(uint32_t low, uint32_t high) { return low + (high - low) / 2; } ``` 接著我們可改寫為以下等價的實作: ```c #include <stdint.h> uint32_t average(uint32_t a, uint32_t b) { return (a >> 1) + (b >> 1) + (EXP1); } ``` 我們再次改寫為以下等價的實作: ```c uint32_t average(uint32_t a, uint32_t b) { return (EXP2) + ((EXP3) >> 1); } ``` 請問， EXP1 = ? EXP2 = ? EXP3 = ? ### 解題思路 根據左移算子我們可以知道a>>1與b>>1相當於是除以二，那這裡會遇到一個問題是當a為奇數且b為奇數的情況會造成出來的平均會少1。當發生這個情況的時候我們直覺是使用if-else的branch來實作，但這樣就等於沒有用到 bit-wise 操作的快速與不用進行分支預測的好處了。 根據數位邏輯 | a | b | result | | -------- | -------- | -------- | | 0 | 0 | 0 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | 1 | 於是我們只需要把 a,b 最後 1 bits & 起來即可，因此 EXP1 = ```a & b & 1 ``` EXP2與EXP3 我首先使用 bit wise 的寫法，使用 a & b 來當作進位， a | b 當作加法。 得到此式 : ```c ((a & b)+1) >> 1)+((a | b) >> 1) ``` 顯然相當不漂亮，EXP2 這樣寫是為了配合 EXP3 進行 or 運算所損失的數值才寫成這樣。但是的確很不符合 bit-wise 的作法，因為 and 也要位移再做加法才得到最後的進位。後來想起數位邏輯的加法器 ![](https://i.imgur.com/HwauvGY.png) 加法使用 xor 運算來實現，進位則由 and 運算來負責，因此重寫 EXP2 及 EXP3 ```c (a & b)+( (a ^ b) >> 1) ``` --- :::success 延伸問題: 1.解釋上述程式碼運作的原理 2.比較上述實作在編譯器最佳化開啟的狀況，對應的組合語言輸出，並嘗試解讀 (可研讀 [CS:APP 第 3 章](https://hackmd.io/@sysprog/CSAPP-ch3)) 3.研讀 Linux 核心原始程式碼 [include/linux/average.h](https://github.com/torvalds/linux/blob/master/include/linux/average.h)， 探討其 [Exponentially weighted moving average (EWMA)](https://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average) 實作，以及在 Linux 核心的應用。 * 移動平均（Moving average)，又稱滾動平均值、滑動平均，在統計學中是種藉由建立整個資料集合中不同子集的一系列平均數，來 分析資料點的計算方法。 ::: ## 測驗二 改寫〈[解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation)〉一文的「不需要分支的設計」一節提供的程式碼 min，我們得到以下實作 (max): ```c #include <stdint.h> uint32_t max(uint32_t a, uint32_t b) { return a ^ ((EXP4) & -(EXP5)); } ``` 請問， EXP4 = ? EXP5 = ? ### 解題思路 根據式子， * 若 a > b ，則反推 a ^ 0 = a 為 max 的值 * 若 a < b ，則需要 一個 b - a 來跟 a 做 xor 運算 根據EXP5 ，我們假設為 a < b ，當 a > b 時，右式得到的值是0，因此輸出為 a 。若 a < b 則根據 uint32_t 輸出為 0xFFFF (有號位整數的 -1)，因此右式的值會變為 EXP4 的值，也就代表 a ^ EXP4 ，簡單思考一下可以知道 b - a 、 a + b 的值都可以用 xor 表示(不考慮借位與進位)，因此 EXP4 應為 a ^ b ，根據數位邏輯的布林代數驗證一下也可以知道 a ^ a ^ b 為 b 。 因此答案為: ```c return a ^ ((a ^ b) & -(a < b)); ``` :::success 延伸問題: * 1.解釋上述程式碼運作的原理 * 2.針對 32 位元無號/有號整數，撰寫同樣 [branchless](https://en.wikipedia.org/wiki/Branch_(computer_science)) 的實作 * 3.Linux 核心也有若干 branchless / branch-free 的實作，例如 [lib/sort.c](https://github.com/torvalds/linux/blob/master/lib/sort.c): ```c /* * Logically, we're doing "if (i & lsbit) i -= size;", but since the * branch is unpredictable, it's done with a bit of clever branch-free * code instead. */ __attribute_const__ __always_inline static size_t parent(size_t i, unsigned int lsbit, size_t size) { i -= size; i -= size & -(i & lsbit); return i / 2; } ``` 請在 Linux 核心原始程式碼中，找出更多類似的實作手法。請善用 git log 檢索。 ::: ## 測驗三 考慮以下 64 位元 GCD ([greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor), 最大公因數) 求值函式: ```c #include <stdint.h> uint64_t gcd64(uint64_t u, uint64_t v) { if (!u || !v) return u | v; while (v) { uint64_t t = v; v = u % v; u = t; } return u; } ``` 改寫為以下等價實作: ```c= #include <stdint.h> uint64_t gcd64(uint64_t u, uint64_t v) { if (!u || !v) return u | v; int shift; for (shift = 0; !((u | v) & 1); shift++) { u /= 2, v /= 2; } while (!(u & 1)) u /= 2; do { while (!(v & 1)) v /= 2; if (u < v) { v -= u; } else { uint64_t t = u - v; u = v; v = t; } } while (COND); return RET; } ``` 請問， COND = ? RET = ? ### 解題思路 首先我們先看這個 condition : ```c !((u | v) & 1) ``` * u & 1 的意思:在二進制下，若出現 LSB 為 1 則為 1 * (u | v) & 1 的意思: 在二進制下，只要 u 或 v 的 LSB 任一為 1 則輸出為 1 * !((u | v) & 1) 的意思: 在二進制下，只要 u 或 v 的 LSB 不為 1 則輸出為 1 因此，shift 這個 for 迴圈在做的事就是將 u 跟 v 共同的二倍數找出來。 當我們找完之後就是把還有二倍數的任一數除乾淨(因為我們已經不再會有二倍數的公因數了)， 接著進入餘數定理: $a=b_{1}q_{1}+r_{1}$ $q_{1}=b_{2}q_{2}+r_{2}$ 因此，當我們的 v 小於 1時就應該結束，所以跟一開始的程式結束條件是一樣的 while (v)。 然後我們要 return 的值是 u 乘以左移shift的次數(二的次方): u * (1 << shift)。 ```c=21 } while (v); return u * (1 << shift); ``` :::success 延伸問題: 1. 解釋上述程式運作原理; 2. 在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升; 3. Linux 核心中也內建 GCD (而且還不只一種實作)，例如 [lib/math/gcd.c](https://github.com/torvalds/linux/blob/master/lib/math/gcd.c)，請解釋其實作手法和探討在核心內的應用場景。 ::: ## 測驗四 在影像處理中，[bit array](https://en.wikipedia.org/wiki/Bit_array) (也稱 bitset) 廣泛使用，考慮以下程式碼: ```c #include <stddef.h> size_t naive(uint64_t *bitmap, size_t bitmapsize, uint32_t *out) { size_t pos = 0; for (size_t k = 0; k < bitmapsize; ++k) { uint64_t bitset = bitmap[k]; size_t p = k * 64; for (int i = 0; i < 64; i++) { if ((bitset >> i) & 0x1) out[pos++] = p + i; } } return pos; } ``` 考慮 GNU extension 的 [__builtin_ctzll](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 的行為是回傳由低位往高位遇上連續多少個 0 才碰到 1。 :::info 範例: 當 a = 16 16 這個十進位數值的二進位表示法為 00000000 00000000 00000000 00010000 低位元 (即右側) 往高位元，我們可發現 0→0→0→0→1 ，於是 ctz 就為 4，表示最低位元往高位元有 4 個 0 ::: 用以改寫的程式碼如下: ```c #include <stddef.h> size_t improved(uint64_t *bitmap, size_t bitmapsize, uint32_t *out) { size_t pos = 0; uint64_t bitset; for (size_t k = 0; k < bitmapsize; ++k) { bitset = bitmap[k]; while (bitset != 0) { uint64_t t = EXP6; int r = __builtin_ctzll(bitset); out[pos++] = k * 64 + r; bitset ^= t; } } return pos; } ``` 其中第 9 行的作用是找出目前最低位元的 1，並紀錄到 t 變數。舉例來說，若目前 bitset 為 000101b ，那 t 就會變成 000001b，接著就可以透過 XOR 把該位的 1 清掉，其他保留 (此為 XOR 的特性)。 若 bitmap 越鬆散 (即 1 越少)，於是 improved 的效益就更高。 請問， EXP6 = ? ### 解題思路 首先，我參考了 [Introduction to Low Level Bit Hacks](https://catonmat.net/low-level-bit-hacks) 提供的這篇文章，我們可以知道怎麼 get right-most bit value 。 即是使用: ```c y = x & (-x) // -x is 2's complement ``` 因此，EXP6 : ```c uint64_t t = bitset & (-bitset); ``` 其實我一開始是想到使用: ```c uint64_t t = bitset & ~(bitset-1) ``` 不過轉換後其實兩者布林代數是相等的，而且前者的可讀性更好。 :::success 延伸問題: 1. 解釋上述程式運作原理，並舉出這樣的程式碼用在哪些真實案例中; 2. 設計實驗，檢驗 ctz/clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 [bitmap density](http://www.vki.com/2013/Support/docs/vgltools-3.html); 3. 思考進一步的改進空間; 4. 閱讀 [Data Structures in the Linux Kernel](https://0xax.gitbooks.io/linux-insides/content/DataStructures/linux-datastructures-3.html) 並舉出 Linux 核心使用 bitmap 的案例; ::: ### 測驗五 以下是 [LeetCode 166. Fraction to Recurring Decimal](https://leetcode.com/problems/fraction-to-recurring-decimal/) 的可能實作: ```c #include <stdbool.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include "list.h" struct rem_node { int key; int index; struct list_head link; }; static int find(struct list_head *heads, int size, int key) { struct rem_node *node; int hash = key % size; list_for_each_entry (node, &heads[hash], link) { if (key == node->key) return node->index; } return -1; } char *fractionToDecimal(int numerator, int denominator) { int size = 1024; char *result = malloc(size); char *p = result; if (denominator == 0) { result[0] = '\0'; return result; } if (numerator == 0) { result[0] = '0'; result[1] = '\0'; return result; } /* using long long type make sure there has no integer overflow */ long long n = numerator; long long d = denominator; /* deal with negtive cases */ if (n < 0) n = -n; if (d < 0) d = -d; bool sign = (float) numerator / denominator >= 0; if (!sign) *p++ = '-'; long long remainder = n % d; long long division = n / d; sprintf(p, "%ld", division > 0 ? (long) division : (long) -division); if (remainder == 0) return result; p = result + strlen(result); *p++ = '.'; /* Using a map to record all of reminders and their position. * if the reminder appeared before, which means the repeated loop begin, */ char *decimal = malloc(size); memset(decimal, 0, size); char *q = decimal; size = 1333; struct list_head *heads = malloc(size * sizeof(*heads)); for (int i = 0; i < size; i++) INIT_LIST_HEAD(&heads[i]); for (int i = 0; remainder; i++) { int pos = find(heads, size, remainder); if (pos >= 0) { while (PPP > 0) *p++ = *decimal++; *p++ = '('; while (*decimal != '\0') *p++ = *decimal++; *p++ = ')'; *p = '\0'; return result; } struct rem_node *node = malloc(sizeof(*node)); node->key = remainder; node->index = i; MMM(&node->link, EEE); *q++ = (remainder * 10) / d + '0'; remainder = (remainder * 10) % d; } strcpy(p, decimal); return result; } ``` 請問， PPP = ? (表示式) MMM = ? (巨集) EEE = ? (表示式) ### 解題思路 ```graphviz digraph test{ node[shape=record]; rankdir="LR" Map[label="Hash table |<1>0|<2>1|<3>2|<4>3|<5>4|<6>5|...|size - 1" ] Key[label="int Key=remainder|{<1> int index| <2>list_head link} "] Key2[label="int Key=remainder|{<1> int index| <2>list_head link} "] Map:3->Key Key:2->Key2 } ``` 首先我們可以看看 Hash Table 的結構，我們可以知道我們使用 remainder 當作 Key 來查表，當我們有符合的 Key 在該項 Hash Table 裡時則回傳該 node 的 index。因此我們可以先解 MMM 與 EEE 是: ```c list_add_tail(&node->link, &head[reminder % size]); ``` 透過 HashTable 映射到對應的 Hlist_head 來搜尋 key 值，因此我們儲存節點就要依此邏輯來存取。 現在我們考慮 PPP ， ```graphviz digraph test{ node[shape=record]; Map[label="decimal point . |<1>1|<2>2|<3>3|<4>4|<5>5|<6>6|...|size - 1" ] Map:6->Map:3[label="Recurring Decimal"] } ``` 當我們無法從 Hash Table 找到位置時，代表我們尚未有該值，建立一個 hash table 的 element 下次方便找 index 值，然後便將值寫入在 *decimal ( 也就是 q 目前的位置 )，並往下一位數前進。 因此當我們 find 到 pos 的時候，代表我們在這個位數的值等於前面某一個位數的值(已經確定有循環小數了)，此時我們應該先將循環小數前的位數寫入 result ，因此 PPP 應為(原本我想的條件是 ```pos - i > 0``` 但一行解決的確是 pos-- ): ```c if (pos >= 0) { while (pos-- > 0) //while (PPP > 0) *p++ = *decimal++; *p++ = '('; while (*decimal != '\0') *p++ = *decimal++; *p++ = ')'; *p = '\0'; return result; } ``` 最後再將循環位數利用下一個 while 迴圈填入左括號與右括號之間，直到 decimal 為 "\0" 。 :::success 延伸問題: 1. 解釋上述程式碼運作原理，指出其中不足，並予以改進 * 例如，判斷負號只要寫作 bool isNegative = numerator < 0 ^ denominator < 0; 搭配研讀 [The simple math behind decimal-binary conversion algorithms](https://indepth.dev/posts/1019/the-simple-math-behind-decimal-binary-conversion-algorithms) 2. 在 Linux 核心原始程式碼的 mm/ 目錄 (即記憶體管理) 中，找到特定整數比值 (即 fraction) 和 bitwise 操作的程式碼案例，予以探討和解說其應用場景 ::: ## 測驗六 [__alignof__](https://gcc.gnu.org/onlinedocs/gcc/Alignment.html) 是 GNU extension，以下是其可能的實作方式: ```c /* * ALIGNOF - get the alignment of a type * @t: the type to test * * This returns a safe alignment for the given type. */ #define ALIGNOF(t) \ ((char *)(&((struct { char c; t _h; } *)0)->M) - (char *)X) ``` 請問， M = ? X = ? 首先，這段程式雖然短卻不好了解，先拆開來 ```c &((struct {char c; t _h;} *)0) ->M ``` 我們宣告一個 struct 指標， 0 是虛擬地址(正如同[offsetof](https://en.wikipedia.org/wiki/Offsetof)"它假定結構的位址為0，然後獲得成員的偏移值") 重新複習[運算子優先順序](https://docs.microsoft.com/zh-tw/cpp/c-language/precedence-and-order-of-evaluation?view=msvc-170)因此可以知道我們先取 成員 M 再取得它的位置，接著: ```c ((char *)(&((struct { char c; t _h; } *)0)->M) - (char *)X) ``` 就是將我們取得的位置轉型成 char 指標再跟 X 這個char 指標相減。我們要使用 struct 裡面 佔最大的成員當成 alignment 的大小，那由於 char 指標只佔 1 bit ，我們只要看 _h 的大小來決定是幾位元。 因此，M 應為 _h。 而 X 應為 0 (為 struct 的開頭成員 char c 的位置) ，透過相減取得 _h 成員的偏移。 :::success 延伸問題: 1. 解釋上述程式碼運作原理 2. 在 Linux 核心原始程式碼中找出 __alignof__ 的使用案例 2 則，並針對其場景進行解說 3. 在 Linux 核心源使程式碼找出 ALIGN, ALIGN_DOWN, ALIGN_UP 等巨集，探討其實作機制和用途，並舉例探討 (可和上述第二點的案例重複)。思索能否對 Linux 核心提交貢獻，儘量共用相同的巨集 ::: ## 測驗七 考慮貌似簡單卻蘊含實作深度的 [FizzBuzz](https://en.wikipedia.org/wiki/Fizz_buzz) 題目: * 從 1 數到 n，如果是 3的倍數，印出 “Fizz” * 如果是 5 的倍數，印出 “Buzz” * 如果是 15 的倍數，印出 “FizzBuzz” * 如果都不是，就印出數字本身 * 直覺的實作程式碼如下: (naive.c) ```c #include <stdio.h> int main() { for (unsigned int i = 1; i < 100; i++) { if (i % 3 == 0) printf("Fizz"); if (i % 5 == 0) printf("Buzz"); if (i % 15 == 0) printf("FizzBuzz"); if ((i % 3) && (i % 5)) printf("%u", i); printf("\n"); } return 0; } ``` 觀察 printf 的(格式)字串，可分類為以下三種: 1. 整數格式字串 "%d" : 長度為 2 B 2. “Fizz” 或 “Buzz” : 長度為 4 B 3. “FizzBuzz” : 長度為 8 B 考慮下方程式碼: ```c char fmt[M9]; strncpy(fmt, &"FizzBuzz%u"[start], length); fmt[length] = '\0'; printf(fmt, i); printf("\n"); ``` 我們若能精準從給定輸入 i 的規律去控制 start 及 length，即可符合 FizzBuzz 題意: ```c string literal: "fizzbuzz%u" offset: 0 4 8 ``` 以下是利用 bitwise 和上述技巧實作的 FizzBuzz 程式碼: (bitwise.c) ```c static inline bool is_divisible(uint32_t n, uint64_t M) { return n * M <= M - 1; } static uint64_t M3 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1; static uint64_t M5 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 5 + 1; int main(int argc, char **argv) { for (size_t i = 1; i <= 100; i++) { uint8_t div3 = is_divisible(i, M3); uint8_t div5 = is_divisible(i, M5); unsigned int length = (2 << KK1) << KK2; char fmt[9]; strncpy(fmt, &"FizzBuzz%u"[8 >> div5) >> (KK3)], length); fmt[length] = '\0'; printf(fmt, i); printf("\n"); } return 0; } ``` 其中 is_divisible 函式技巧來自 Faster remainders when the divisor is a constant: beating compilers and libdivide，甚至 gcc-9 還內建了 FizzBuzz optimization (Bug 82853 - Optimize x % 3 == 0 without modulo)。 請補完，使得程式碼符合預期，儘量以最簡短且符合一致排版的形式來撰寫。 請問， KK1 = ? (變數名稱) KK2 = ? (變數名稱) KK3 = ? (表示式，不包含小括號) ### 解題思路 我們可以知道 FizzBuzz 的長度變化是跟是否能被 3 與 5 整除來增長的，因此我們可以從 div3 與 div5 得到是否整除的關係，因此 KK1 = div3 , KK2 = div5 兩者其實可以更換。 至於 KK3 則是針對 FizzBuzz 字串要從哪裡複製來做位移。因為字串從起始位置 9 開始，往前四格開始就是 divide 2 因此假如 div5 為 1 就從起始位置 4 開始。至於 KK3 的地方的話，因為只要 div3 為 1 的情況，就應該從起始位置 0 的地方開始，因此 KK3 應為 div3 * 4 直接讓起始位置歸零。 :::success 延伸問題: 1. 解釋上述程式運作原理並評估 naive.c 和 bitwise.c 效能落差 * 避免 stream I/O 帶來的影響，可將 printf 更換為 sprintf 2. 分析 [Faster remainders when the divisor is a constant: beating compilers and libdivide](https://lemire.me/blog/2019/02/08/faster-remainders-when-the-divisor-is-a-constant-beating-compilers-and-libdivide/) 一文的想法 (可參照同一篇網誌下方的評論)，並設計另一種 bitmask，如「可被 3 整除則末位設為 1」「可被 5 整除則倒數第二位設定為 1」，然後再改寫 bitwise.c 程式碼，試圖運用更少的指令來實作出 branchless; * 參照 [fastmod: A header file for fast 32-bit division remainders on 64-bit hardware](https://github.com/lemire/fastmod) 3. 研讀 [The Fastest FizzBuzz Implementation](https://tech.marksblogg.com/fastest-fizz-buzz.html) 及其 [Hacker News 討論](https://news.ycombinator.com/item?id=29413656)，提出 throughput (吞吐量) 更高的 Fizzbuzz 實作 4. 解析 Linux 核心原始程式碼 [kernel/time/timekeeping.c](https://github.com/torvalds/linux/blob/master/kernel/time/timekeeping.c) 裡頭涉及到除法運算的機制，探討其快速除法的實作 (注意: 你可能要對照研讀 kernel/time/ 目錄的標頭檔和程式碼) 過程中，你可能會發現可貢獻到 Linux 核心的空間，請充分討論 :::
Last changed by  
 
ganoliz
196

Read more

2022q1 Homework3 (quiz3)

contributed by < ganoliz >

2/18/2024
Keypoints 流程

首先 UI.py 用來顯示影片結果當我們使用 demo.py 時會有五個按鍵，按下按鈕會開啟另一個 process 執行 run.bat 後面再接一個參數是資料集的人。read_csv 的 csv 為一個人的每一幀的 (x, y, z) 關鍵點，下圖所示

8/30/2023
實驗室交接

先登入 NAS找到 data > 歷屆資料備份 > 郭振鵬 > 其他備份 > 助教 > routine > 實驗室系上信箱.txt

8/9/2023
論文筆記

ResNeSt: Split-Attention Networks 這篇論文主要提出一種簡單的架構結合 channel-wise 的 attention 策略與 multi-path network layout。因此命名上以 : Split-Attention Network (ResNeSt) 來表示 Split-Attention Networks 我們探討所謂的 Featuremap Group: 我們輸入的 feature 會被分成好幾個 groups，這些 groups會被稱為 cardinal groups。 接著每個 groups 會被分成更小的 radix 切割。 因此總共的特徵群會是 $G = KR$。 然後我們會用使用 transformations 來將我們的 feature $F_1, F_2, ... F_G$ 轉變為 $U_i = F_i(X) i∈1,2,...G$。 Split Attention in Cardinal Groups. 我們的 feature 會通過 R 個 radix 相加後得到 $U^k$ ， 接著通過 global average pooling 。

5/17/2023
Read more from ganoliz
Published on HackMD