2025q1 Homework3 (kxo)

contributed by < yy214123 >

ttt

$ make
$ ./ttt
 1 |             
 2 |             
 3 |             
 4 |             
---+-------------
      A  B  C  D

執行可以看到這個專案是

$4\times 4$ 的井字遊戲，其勝負的判斷規則在 game.c 中的：

char check_win(char *t)
{
    for (int i_line = 0; i_line < 4; ++i_line) {
        line_t line = lines[i_line];
        for (int i = line.i_lower_bound; i < line.i_upper_bound; ++i) {
            for (int j = line.j_lower_bound; j < line.j_upper_bound; ++j) {
                char win = check_line_segment_win(t, i, j, line);
                if (win != ' ')
                    return win;
            }
        }
    }
    for (int i = 0; i < N_GRIDS; i++)
        if (t[i] == ' ')
            return ' ';
    return 'D';
}

並在 main 函式中透過 while 迴圈，來不斷檢查當前遊戲的狀況。

勝利的條件有四種，分別是：

1. 直的連續三顆（—）
2. 橫的連續三顆（｜）
3. 斜的連續三顆
   • 由左而右傾斜（/）
   • 由右而左傾斜（\）

此處要先了解關鍵的結構體定義：

typedef struct {
    int i_shift, j_shift;
    int i_lower_bound, j_lower_bound;
    int i_upper_bound, j_upper_bound;
} line_t;

搭配相關的結構體宣告：

const line_t lines[4] = {
    {1, 0, 0, 0, BOARD_SIZE - GOAL + 1, BOARD_SIZE},             // ROW
    {0, 1, 0, 0, BOARD_SIZE, BOARD_SIZE - GOAL + 1},             // COL
    {1, 1, 0, 0, BOARD_SIZE - GOAL + 1, BOARD_SIZE - GOAL + 1},  // PRIMARY
    {1, -1, 0, GOAL - 1, BOARD_SIZE - GOAL + 1, BOARD_SIZE},     // SECONDARY
};

最外層的迴圈每次會針對一種勝利條件來對整個盤面進行檢查，內層迴圈會對特定勝利條件去檢查是否符合條件。

這邊我將迴圈中的 i 及 j 印出，觀察每次的檢查對象：

$i^j$	0	1	2	3
0	0,0	0,1	0,2	0,3
1	1,0	1,1	1,2	1,3
2	2,0	2,1	2,2	2,3
3	3,0	3,1	3,2	3,3

初始化會將（0,0）~（3,3）設為 ' '。

測試程式碼

---- Line type: ROW ----
Checking board indices: (0,0)[0] -> (1,0)[4] -> (2,0)[8]
Checking board indices: (0,1)[1] -> (1,1)[5] -> (2,1)[9]
Checking board indices: (0,2)[2] -> (1,2)[6] -> (2,2)[10]
Checking board indices: (0,3)[3] -> (1,3)[7] -> (2,3)[11]
Checking board indices: (1,0)[4] -> (2,0)[8] -> (3,0)[12]
Checking board indices: (1,1)[5] -> (2,1)[9] -> (3,1)[13]
Checking board indices: (1,2)[6] -> (2,2)[10] -> (3,2)[14]
Checking board indices: (1,3)[7] -> (2,3)[11] -> (3,3)[15]

---- Line type: COL ----
Checking board indices: (0,0)[0] -> (0,1)[1] -> (0,2)[2]
Checking board indices: (0,1)[1] -> (0,2)[2] -> (0,3)[3]
Checking board indices: (1,0)[4] -> (1,1)[5] -> (1,2)[6]
Checking board indices: (1,1)[5] -> (1,2)[6] -> (1,3)[7]
Checking board indices: (2,0)[8] -> (2,1)[9] -> (2,2)[10]
Checking board indices: (2,1)[9] -> (2,2)[10] -> (2,3)[11]
Checking board indices: (3,0)[12] -> (3,1)[13] -> (3,2)[14]
Checking board indices: (3,1)[13] -> (3,2)[14] -> (3,3)[15]

---- Line type: PRIMARY ----
Checking board indices: (0,0)[0] -> (1,1)[5] -> (2,2)[10]
Checking board indices: (0,1)[1] -> (1,2)[6] -> (2,3)[11]
Checking board indices: (1,0)[4] -> (2,1)[9] -> (3,2)[14]
Checking board indices: (1,1)[5] -> (2,2)[10] -> (3,3)[15]

---- Line type: SECONDARY ----
Checking board indices: (0,2)[2] -> (1,1)[5] -> (2,0)[8]
Checking board indices: (0,3)[3] -> (1,2)[6] -> (2,1)[9]
Checking board indices: (1,2)[6] -> (2,1)[9] -> (3,0)[12]
Checking board indices: (1,3)[7] -> (2,2)[10] -> (3,1)[13]

從此處可以發現，實際上的註解有誤，常見的 column 及 row 的定義應該如下：

於是著手進行修改：

const line_t lines[4] = {
-   {1, 0, 0, 0, BOARD_SIZE - GOAL + 1, BOARD_SIZE},             // ROW
+   {1, 0, 0, 0, BOARD_SIZE - GOAL + 1, BOARD_SIZE},             // COL
-   {0, 1, 0, 0, BOARD_SIZE, BOARD_SIZE - GOAL + 1},             // COL
+   {0, 1, 0, 0, BOARD_SIZE, BOARD_SIZE - GOAL + 1},             // ROW
    {1, 1, 0, 0, BOARD_SIZE - GOAL + 1, BOARD_SIZE - GOAL + 1},  // PRIMARY
    {1, -1, 0, GOAL - 1, BOARD_SIZE - GOAL + 1, BOARD_SIZE},     // SECONDARY
};

並將此修改提交 pull request 至原始專案中。

註解修正

jserv #42

過程中出現了意外的小插曲，由於自己的疏忽誤將 ROW 打成 RAW，經由 reviewer 提醒須重新修改。

我沒有相關經驗，所以我最一開始的作法在原先的 commit 之上，再新增一個新的 Commit 8af6a76，但 reviewer 指出：

Please rebase and squash the commits into one.
We don't want a PR to contain commits that fix mistakes from earlier commits in the same PR.

這意味著我需要：

• 保留第一個 commit message。
• 保留第二個 commit 的程式變更。

我進行了以下的操作：

1. 先使用 git rebase 命令

$ git rebase -i HEAD~2

pick 1234567 Fix mislabeled comments for line directions
pick a1b2c3d Fix typo in comment: change RAW to ROW

2. 將第二個 pick 改為 squash

pick 1234567 Fix mislabeled comments for line directions
squash a1b2c3d Fix typo in comment: change RAW to ROW

3. 此時會出現：

# This is a combination of 2 commits.
# This is the 1st commit message:

Fix incorrect comments

Correct ROW and COL labels in comments to match standard
definitions—column as vertical and row as horizontal. This change
improves code clarity and prevents potential confusion when
interpreting line direction logic.

# This is the commit message #2:

Fix typo in comment: change RAW to ROW

The line label was mistakenly written as "RAW" instead of "ROW".

# Please enter the commit message for your changes. Lines starting
# with '#' will be ignored, and an empty message aborts the commit.
#
# Date:      Tue Apr 8 11:44:59 2025 +0800
#
# interactive rebase in progress; onto e8eade4
# Last commands done (2 commands done):
#    pick 36b872e Fix incorrect comments
#    squash 8af6a76 Fix typo in comment: change RAW to ROW
# No commands remaining.
# You are currently rebasing branch 'fix-comment-errors' on 'e8eade4'.
#
# Changes to be committed:
#       modified:   game.c

4. 留下原始的 commit message 再使用命令 git push --force 即可。

算是蠻意外的收穫，所以不要怕做錯事，沒有這次的疏忽也不會有更進一步了解相關 git 運作的經驗。

效能改善

jserv #43

基於上一個 pull request 可以注意到，每下一步棋，第一步是基於 column major 掃描整個棋面是否滿足勝利條件。

實際上 4 * 4 的二維棋面就是 1 * 16 的陣列，是連續的記憶體配置，我參考了：

• CS:APP 第 6 章重點提示
• Row- and column-major order

我認為既然兩種勝利的機率是等價的，那可以先 ROW 的判定再進行 COLUMN 的判定，如此可以充分運用 temporal locality 的特性。

因此我對程式做了以下修改：

const line_t lines[4] = {
+   {0, 1, 0, 0, BOARD_SIZE, BOARD_SIZE - GOAL + 1},             // ROW
+   {1, 0, 0, 0, BOARD_SIZE - GOAL + 1, BOARD_SIZE},             // COL
-   {0, 1, 0, 0, BOARD_SIZE, BOARD_SIZE - GOAL + 1},             // ROW
    {1, 1, 0, 0, BOARD_SIZE - GOAL + 1, BOARD_SIZE - GOAL + 1},  // PRIMARY
    {1, -1, 0, GOAL - 1, BOARD_SIZE - GOAL + 1, BOARD_SIZE},     // SECONDARY
};

將兩個敘述對調。

嘗試提交 pull request 到原始專案中，目前還未被合併，過程中獲得了一些啟發：

最初的提交是 commit ddf7e45，reviewer 同樣是授課老師有邀請回來演講的 linux 核心維護者，對於我這次的提交，他留下這樣的評論：

Looks good.

However, I would appreciate more explanation on why prioritizing row-wise checks improves spatial locality.
Also, I'm curious if there's any observable performance gain or data showing how much faster this change might be.

讓我印象深刻的是，在當時的演講中，他提到了貢獻程式碼到 linux 核心很重要的環節：

• 溝通
• 說服維護者

顯然我在沒有做效能評比的狀況下，這次的 commit message 相當沒有說服力，但當下我沒有什麼想法，所以我將上面所執行的結果，以及我參考的資料附於評論中。並依據其建議修改了 commit message，新的提交為 commit c77acdb。

後來此專案的 owner（即授課老師）也參與了評論，owner 指出：

Instead of appending the references supporting this proposed change, show experimental evidences.

從這邊我也意識到，貢獻開源專案沒有一定的 SOP，reviewer 並沒有強烈要求我要進行效能評比，但 owner 要求我進行效能評比，我得出的結論是以後還是乖乖做效能分析！畢竟數字才能真正的說服人。

效能評比設計

目前的想法是，我直接產生所有會勝利的棋盤，並針對這些勝利棋盤運行 check_win 函式。

在 lab0 的基礎上，將 Fisher–Yates shuffle 演算法及 do_time 引入我的測試中。

測試程式碼如下：

• column_major
• row_major

兩者本質上沒有差異，僅是掃描的順序不同。

實驗一：公平生成的測試資料

在此實驗中，生成的測試資料保證每一組棋盤皆存在一組勝利條件，並且均勻涵蓋各種勝利情況。

在 10 × 10 的棋盤下：

在 50 × 50 的棋盤下：

在 100 × 100 的棋盤下：

由於在資料生成過程中會包含所有可能的勝利條件，對於使用 row-major 的程式來說，掃描 column 勝利條件會產生額外記憶體訪問成本；反之，column-major 亦然。

實驗二：刻意調整樣本分佈（偏向 row）

在相同為 100 × 100 的棋盤條件下，進一步調整測試資料生成策略，使其中 row 方向的勝利樣本佔比提高。（Row：Col=2：1）

在此「不公平」條件下，row-major 儲存方式展現出明顯的優勢，並與 column-major 拉開了更大的性能差距。

使用 perf 進行分析：

指標	column-major	row-major
Instructions	1,585,771,268,229	1,426,533,169,134
CPU cycles	427,169,360,881	390,890,530,455
IPC (insn/cycle)	3.71	3.65
Cache references	3,505,765,178	3,411,224,518
Cache misses	2,549,701,006	2,526,058,997
Cache miss rate	72.73%	74.05%
Time elapsed (s)	85.00 s	77.88 s

受 reviewer 提醒，我上面的實驗並不公平，應該設計對稱的實驗比較：

刻意調整樣本分佈（偏向 column）

Perf analysis summary:

Metric	column-major	row-major
Instructions	1,430,153,246,436	1,585,481,506,424
CPU cycles	390,527,903,361	423,555,794,132
IPC (insn/cycle)	3.66	3.74
Cache references	3,416,572,300	3,496,775,391
Cache misses	2,515,143,524	2,549,693,611
Cache miss rate	73.62%	72.92%
Time elapsed (s)	77.70 s	84.30 s

實驗三：模擬真實對局場景

前述兩個實驗皆為「保證勝利」的條件下進行，與真實下棋過程不同。在實際情況中，棋局常需多次判斷後才出現勝利條件。舉例如下：

 O | O | O | O | O 
---+---+---+---+---
 O |   |   | X |   
---+---+---+---+---
 O |   | X |   |   
---+---+---+---+---
 O |   | X |   | X 
---+---+---+---+---
 X |   |   | X |   

此類情況下，若從左上開始掃描，column-major 可能需檢查多次才能辨識出最左下角的 X（假設五子棋）。

為了公平比較，我生成兩組互為轉置的 5 × 5 棋盤：

• 第一組對 row-major 有利
• 第二組對 column-major 有利

這兩者皆需進行多次無效檢查，之後才發現勝利條件，模擬「邊緣判斷」的效能情況。

 O | O |   |   |  
---+---+---+---+---
 O | O |   |   | 
---+---+---+---+---
   |   |   |   | O
---+---+---+---+---
 O | O |   | O | O
---+---+---+---+---
 O | O |   | O | O

 O | O |   | O | O
---+---+---+---+---
 O | O |   | O | O
---+---+---+---+---
   |   |   |   | 
---+---+---+---+---
   |   |   | O | O
---+---+---+---+---
   |   | O | O | O

在執行 1,000K 次 的 perf 性能監控後，結果如下：

指標	column_major	row_major
Instructions	20,042,179,354	9,528,171,690
CPU cycles	4,974,042,956	3,064,415,787
IPC (insn/cycle)	4.03	3.11
Cache references	205,075	115,548
Cache misses	28,503	20,176
Cache miss rate	13.90%	17.46%
Time elapsed (s)	0.971	0.597

在這種接近實戰的條件下，row-major 方式的效能優勢更加明顯，幾乎在所有指標上都優於 column-major。儘管其 cache miss rate 較高，但這是由於其總 cache reference 數量減少近一半所致，整體表現仍然更為優秀。

$cachemissrate=\frac{cachemisses}{cachereferences}$

總結與展望

綜合實驗二及實驗三，row-major 在實作上具有更佳的空間區域性（spatial locality），尤其當勝利條件以橫向居多或需多次判斷時，表現優勢更加顯著。

因此，未來若設計電腦下棋演算法時能引導 AI 傾向以 row 為主進行布局，不僅在演算法判斷上較為直接，亦可獲得更好的效能表現，尤其在大型棋盤或頻繁檢查勝利條件的場景中，將有顯著助益。

檢討

目前雖然比上次修課更懂如何進行實驗了，但很多面向我還是沒有顧及到，就以實驗二來說，我的初始規劃並不公平。
另外是英文書寫的部份，我還有很大的改善空間，在 comment 中錯誤的描述會產生誤會。要提醒自己要多檢查才送出。

kxo

註解修正

sysprog21 #11
此更新同 jserv #42，一樣也是對錯誤的註解進行修正。

效能優化

syspro21 #20
優先檢查 row。

首先先編譯並掛載 kxo，接著執行下列命令即可看到電腦對奕：

$ sudo insmod kxo.ko 
$ sudo cat /dev/kxo  

接著開啟另一個終端機視窗執行下列命令：

$ sudo ./xo-user

此時可以監看最新棋盤的動態，倘若此時輸入 ctrl+p 就會看到原先執行 $ sudo cat /dev/kxo 的終端機與當前的終端機皆停止。

藉由位元運算降低棋盤判定的成本

popcount 對應到 C 程式的實作：

unsigned popcount_naive(unsigned v)
{
    unsigned n = 0;
    while (v)
        v &= (v - 1), n = -(~n);
    return n;
}

簡單的用一個二進位當作輸入範例，假設 v 為 0b11100011，當 v 非 0 就會進入 while 迴圈：

• 首先是將 v 與 v - 1 進行 and 運算。

1110 0011
1110 0010
---------(and)
1110 0010

此時 v 變成 0b11100010`，接著將計數 +1。

後面也是延續上述步驟。而上述程式可如下優化：

unsigned popcount_branchless(unsigned v)
{
    unsigned n;
    n = (v >> 1) & 0x77777777;
    v -= n;
    n = (n >> 1) & 0x77777777;
    v -= n;
    n = (n >> 1) & 0x77777777;
    v -= n;

    v = (v + (v >> 4)) & 0x0F0F0F0F;
    v *= 0x01010101;                                     

    return v >> 24;
}

這邊數學公式沒看懂。

不用除法取餘數（以 mod 3 為例）

先以簡單的範例進行，5 % 3 = 2 這顯而易見，而 5 的 2 進位表示為 101，相當於 4 + 1，所以：

$5\mathrm{mod}3=(4+1)\mathrm{mod}3=(4\mathrm{mod}3)+(1\mathrm{mod}3)=1+1=2$

那由過程我們可以寫出下列公式：

$x=\sum _{i=0}^{31}{b}_i\cdot 2^i\Rightarrow xmod3=\sum _{i=0}^{31}{b}_i\cdot (2^{i}mod3)$

而

$i$ 非奇即偶，所以

$2^{i}mod3=(-1{)}^i$，這個通式由下列兩個所組成：

• $2^{i}mod3=1$, if
  $i$ is even
• $2^{i}mod3=2=-1$, if
  $i$ is odd

將此結合，可以得到：

$xmod3=\sum _{i=0}^{31}{b}_i\cdot (2^{i}mod3)=\sum _{i=0}^{31}{b}_i\cdot (-1{)}^{i}mod3$

這就相當於「位於偶數位的 1 加起來」減去「位於奇數位的 1 加起來」。將 popcount 引入即：

int popcount_even = popcount(x & 0x55555555);  // 偶數位 (i = 0,2,4,...)
int popcount_odd  = popcount(x & 0xAAAAAAAA);  // 奇數位 (i = 1,3,5,...)
int mod3 = (popcount_even - popcount_odd) % 3;