2020q3 Homework7 (quiz7)

contributed by < JimmyLiu0530 >

tags: 進階電腦系統理論與實作

測驗一: Tail Recursion

給定兩個函式實作:

int funcA(int i)
{
    if (i == 0)
        return 0;
    return 5 * funcA(i - 1);
}

int funcB(int i)
{
    if (i == 0)
        return 0;
    return funcB(i - 1);
}

以 tail recursion 的觀點，回答 funcA 跟 funcB 是否屬於 tail recursion。

程式說明

根據 tail recursion 的定義:

tail call 指一個函式裡的最後一個動作是返回一個函式的呼叫結果的情形，即最後一步新呼叫的返回值直接被當前函式的返回結果，當新呼叫的函式與當前函式相同，則稱 tail recursion。

顯然 funcA 不屬於 tail recursion，因為此函式的最後一個動作是將 funcA(i - 1) 的結果乘上 5，而不是去呼叫本身。funcB 就屬於 tail recursion。

NOTE

tail recursion(call) 的好處:
當函式被呼叫時，系統會分配一個 stack frame (a.k.a activation record) 來記錄

1. return address
2. argument variables passed on the stack
3. local variables
4. saved copies of any registers modified by the subprogram that need to be restored

並 push 進 call stack 中。

而 tail call 的 call stack 特別易於最佳化，從而可減少記憶體的使用，也能提高執行速度。其中，對 tail recursion 情形的最佳化效果最為明顯。

其原理是因為在 tail call 這種特殊情形中，理論上不需要記住尾呼叫的位置，從被呼叫的函式直接帶著返回值返回呼用函式的返回位置即可（相當於直接連續返回兩次）。

由於當前函式 stack frame 包含區域變數等等大部分的東西都不需要了，因此經過適當的更動以後可以直接當作 tail-called 函式的 stack frame，然後程式即可以跳到 tail-called 函式，此過程稱之為 tail call optimization(TCO)。

延伸問題

1. 設計實驗，解釋 clang/gcc 在最佳化 (-O2 以上) 開啟時，上述程式碼的行為，以及 tail call optimization (TCO) 適用場景為何

---

測驗二: Tail Call Optimization

考慮一個測試 C 編譯器 Tail Call Optimization (TCO) 能力的程式 tco-test，在 gcc-8.4.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

注意 __builtin_return_address 是 gcc 的內建函式:

This function returns the return address of the current function, or of one of its callers. The level argument is number of frames to scan up the call stack. A value of 0 yields the return address of the current function, a value of 1 yields the return address of the caller of the current function, and so forth. When inlining the expected behavior is that the function returns the address of the function that is returned to. To work around this behavior use the noinline function attribute.
The level argument must be a constant integer.

從實驗中可發現下方程式無法對 g 函式施加 TCO:

void g(int *p);
void f(void) {
    int x = 3;
    g(&x);
}
void g(int *p) { printf("%d\n", *p); }

因為函式 f 的區域變數 x 在返回後就不再存在於 stack。考慮以下程式碼:

int *global_var;
void f(void)
{
    int x = 3;
    global_var = &x;
    ...
    /* Can the compiler perform TCO here? */
    g();
}

在第 8 行能否施加 TCO 呢？

程式說明

先解釋為什麼上面的實驗無法對 g 作 TCO:
如果對 g 作 TCO，那麼代表 g 會修改 f 的 stack frame 來做為己用，導致原本存在裏頭的區域變數 x 會消失，也就沒辦法取得 x 的位址 (&x) 了。

瞭解上述的原因之後，我們就可以來回答此題。

這邊使用一個全域指標變數 global_var 來指向 x。如果施加 TCO 後， g 會去修改 f 的 stack frame，而 global_var 不會因此消失。然而，透過 global_var 存取原本的 x 就會變成 undefined behavior，因為不能保證會發生什麼事，有可能原值還在，也有可能已被修改過。因此，只要函式 g 沒有對 global_var 指標作 dereference，那麼 TCO 就有機會。

延伸問題

1. 從 GitHub 裡頭找出 __builtin_return_address 的應用案例並解說

---

測驗三: LeetCode 226. Invert Binary Tree

軟體開發者 Max Howell 在 Twitter 講述他在 2015 年是怎麼在 Google 面試時被刷掉：

「Google：我們 90% 的工程師都用你寫的軟體（Homebrew），但你沒辦法在白板上實作 Invert Binary Tree，所以因此我們決定不聘用你」

摘自 iOS 神人應徵工作之滑鐵盧事件:

• 我們會希望透過高互動的面談程序，來進一步確認被面談者是否是符合開發團隊需求的人。
• 懂得演算法和資料結構的運用，當然是程式設計者的基本必備條件，但是，被面談者或許記不住一些資料結構或演算法的細節，如果面談的重點放在細節必須完全無誤，而這些細節是翻書或網上就隨時可以查到的，那麼，因為被面談者無法正確回答出這些細節，就刷掉一個有潛力的程式設計者，其實是很可惜的一件事

LeetCode 226. Invert Binary Tree 本質上就是找出二元樹的鏡像 (mirror):

以下是參考實作:

struct TreeNode *invertTree(struct TreeNode *root)
{ 
    if (!root)
        return NULL;

    if (!root->left && !root->right)
        return root;

    struct TreeNode *tmp = root->left;
    root->left = root->right;
    root->right = tmp;
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

若將上述程式碼的第 12 行和第 13 行對調，是否會影響最終輸出？

程式說明

上述程式主要利用不斷分成左右子樹，然後遞迴地呼叫 invertTree 去做處理。

首先，當一顆樹 root 進來時，會先去檢查 root 是否為空以及是否為樹葉。
接著，將此樹的兩子樹左右交換後，兩子樹再個別呼叫 invertTree，而這裡是要先反轉左子樹還是右子樹都可以，與順序無關。

延伸問題

1. 用 iteration 改寫，並降低記憶體開銷，需要用 Valgrind 一類的分析工具驗證

// TODO

---

測驗四: LeetCode 201. Bitwise AND of Numbers Range

給一個範圍

$[m,n]$ 且

$0\le m\le n\le 2147483647$，回傳對所有該範圍的數值進行位元運算 AND 的結果，範圍包含邊界。

以

$m=100(01100100{)}_2$,

$n=120(01111000{)}_2$ 來說，

$m\wedge n$ 是

$96(01100000{)}_2$，而

$n-m=20$，於是我們可設計一個 bit mask 來求解，使最低 5 個位元皆為 0。

以下是一個對應的解法：

int rangeBitwiseAnd(int m, int n)
{ 
    if (m == 0) return 0;

    int diff = n - m;
    int count = diff ? 32U - __builtin_clz(diff) : 0;
    return m & n & MASK;
}

程式說明

此題有兩個重點:

1. 變動的位元範圍由頭尾的差所占的位元數即為這些，因此必為 0

   • e.g. m = 100, n = 120，那麼 diff = 120 - 100 = 20 =
     $(00010100{)}_2$，代表從 100 到 120 這些連續數字，他們的最低 5 個位元會變動。
   • 既然位元會變動，要不從 0 -> 1 不然就是從 1 -> 0 (都有 0)，又只要有 0 那麼 AND 的結果必為 0 ，因此最後結果中最低 5 個位數必為 0。
   • 推廣到 m,n 就會是最後結果的最低 32 - __builtin_clz(n - m) 個位數必為 0。而 MASK 的用意就是要把這些位元清成 0，因此 MASK = ~((1U << count) - 1)。

2. 而不會變動的位元範圍可由頭 & 尾得到

   • 因為頭跟尾分別代表範圍裡最小跟最大的數，所以頭 & 尾的最高 __builtin_clz(n - m) 個位元一定是不會變動的位元範圍。最後再跟上述 1. 合併將頭 & 尾的最低 32 - __builtin_clz(n - m) 個位數清成 0 即為答案。

延伸問題

1. 能否實作完全無分支 (branchless) 且滿足上述 LeetCode 要求的程式碼？

int rangeBitwiseAnd(int m, int n)
{
    int count = 0;
    while (m != n) {
        m >>= 1;
        n >>= 1;
        count++;
    }
    return m << count;
}

其概念與上面的方法差不多，只是用不同的方式去實作這些概念。其中 line 4 的 while 用來找不會變動的位元範圍 (即上述 2.)。

count 的用意在於紀錄最低多少個位數需被清成 0，最後利用左移會自動補 0 的特性，將 m 的最低 count 位數清成 0。

• 執行效能:
  
  

---

測驗五: LeetCode 97. Interleaving String

大意是判斷給定的字串 s1 與 s2 可否交錯形成字串 s3。從上圖可見，走訪 s3 所有字元，其字元必定是來自 s1 或來自 s2，並且 s1 與 s2 的字元也是依序取出，也就是 s3[i3] 必定為 s1[i1] 或 s2[i2]，其中 i1, i2, i3 分別為 s1, s2, s3 目前的位置。

解題思路

考慮一項 Dynamic Programming (動態規劃) 的實作如下:

bool isInterleave(char *s1, char *s2, char *s3)
{
    size_t n = strlen(s1), m = strlen(s2);
    if ((n + m) != strlen(s3))
        return false;

    bool dp[m + 1];
    memset(dp + 1, false, m * sizeof(bool));
    dp[0] = true;

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 && j == 0)
                continue;
            int p = RRR;
            if (i == 0)
                dp[j] = dp[j - 1] & (s2[j - 1] == s3[p]);
            else {
                dp[j] &= (s1[i - 1] == s3[p]);
                if (j > 0)
                    dp[j] |= dp[j - 1] & (s2[j - 1] == s3[p]);
            }
        }
    }
    return dp[m];
}

sizeof(bool) is implementation-defined. 不必然為 1

延伸閱讀:

• competitive Programmer’s Handbook - Dynamic Programming 重點提示 / 電子書

程式說明

DP 的本質上還是暴力求解，差異在於會將 sub-problem 的解存起來，之後用到就不用再算一次，用空間換取時間上的效益。

這邊為了說明方便與易懂性，使用二維陣列 dp[i][j] 來儲存 sub-problem 的解，其意義為:

$s1[0:i-1]$ 及

$s2[0:j-1]$ 是否能交錯組成

$s3[0:i+j-1]$，然後會在最後一段將此二維陣列縮減至一維。

了解 dp 的意義後，接著觀察 transfer formula。我們知道

$s3[i+j-1]$ 要不從

$s1[i-1]$ 來，要不從

$s2[j-1]$ 來，因此

• 若是想從
  $s1[i-1]$ 得到，那麼
  
  $dp[i][j]$ =
  $dp[i-1][j]$
  $\mathrm{\&}\mathrm{\&}$ (
  $s1[i-1]==s3[i+j-1]$)
• 若是想從
  $s2[j-1]$ 得到，那麼
  
  $dp[i][j]$ =
  $dp[i][j-1]$
  $\mathrm{\&}\mathrm{\&}$ (
  $s2[j-1]==s3[i+j-1]$)

最後再將兩種可能 OR 起來，得到最終的 transfer formula 即為

$dp[i][j]$ =

$(dp[i-1][j]$

$\mathrm{\&}\mathrm{\&}$ (

$s1[i-1]==s3[i+j-1]))$

$\Vert$

$(dp[i][j-1]$

$\mathrm{\&}\mathrm{\&}$ (

$s2[j-1]==s3[i+j-1]))$

所以 RRR = i + j - 1。

此外，這邊之所以能將二維陣列縮減成一維陣列是因為在決定 dp[i][j] 這格時，只會參考 dp[i-1][j] 及 dp[i][j-1]，不會去參考到其他格，因此每輪 i 都可以將上輪的資料覆蓋過去，以減少空間的利用。

執行效能:

延伸問題

1. Dynamic Programming 技巧需要額外的記憶體空間，請針對上述程式，提出降低記憶體開銷的手段

因為題目限制兩個字串長度不超過 100，因此可以利用一個 128-bit 的 unsigned int 來取代 dp 一維陣列，讓空間複雜度從

$O(m)$ 變成

$O(1)$

typedef unsigned __int128 uint128_t;

/* TODO: 重新編排程式碼，提高易讀性 */
bool isInterleave(char * s1, char * s2, char * s3){
    size_t n = strlen(s1), m = strlen(s2);
    if ((n + m) != strlen(s3))
        return false;
    
    uint128_t table = 1; //00...01
    uint128_t mask = 1;
    
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 && j ==0)
                continue;
            int p = i + j - 1;
            uint128_t tmp;
            if (i == 0) {
                if (s2[j - 1] == s3[p]) {
                    tmp = table;
                    tmp <<= 127 - (j - 1);
                    tmp >>= 127;
                    if (tmp == 0)
                        table &= ~(mask << j); // clear the jth bit
                    else
                        table |= (mask << j); // set the jth bit
                }
                else
                    table &= ~(mask << j); // clear the jth bit
            }
            else {
                if (s1[i - 1] == s3[p]) {
                    tmp = table;
                    tmp <<= 127 - j;
                    tmp >>= 127;
                    if (tmp == 0)
                        table &= ~(mask << j); // clear the jth bit
                }
                else
                    table &= ~(mask << j); // clear the jth bit
                if (j > 0) {
                    if (s2[j - 1] == s3[p]) {
                        tmp = table;
                        tmp <<= 127 - (j - 1);
                        tmp >>= 127;
                        if (tmp == 1)
                            table |= (mask << j); // set the jth bit
                    }
                }
            }
        }
    }
    table <<= 127 - m;
    table >>= 127;
    return table;
}

執行效能: