2024q1 Homework4 (quiz3+4)

contributed by < vestata >

第 3 周測驗題

測驗一

commit 401bd93

這段程式碼中的 log2(N) 函數用來計算數字 N 的以 2 為底的對數。

在這個 i_sqrt 函數中，log2(N) 用於找出 N 的最高有效位（most significant bit, msb）。這是因為 N 的平方根絕不會大於 N 本身的二進位數值。舉例來說，如果 N 是 16，其二進位表示為 10000（5位），則其平方根不會超過

2^{l} o g (N) = 16

。因此，通過 log2(N)，我們可以找到一個大約的起始點來進行平方根的計算，從而減少計算次數。

在 i_sqrt 函式中，a 被設置為 1 << msb，即 2 的 msb 次方。這是對 N 進行二進位搜索的起始點，然後逐步右移（a >>= 1），進行逼近計算，直到找到最接近 N 的平方根為止。

log 函數通常返回一個浮點數，因此這裡將結果轉換為整數（使用 (int) 強制類型轉換），依賴於標準數學庫，並涉及浮點運算。

版本二過程中直接在整數的二進位表示上操作，不涉及浮點運算。

整理數學式

自 Digit-by-digit calculation 中:

先簡單舉例：
令
$Z = 10 X + Y$ , 平方根為 10 位數的狀況。

$Z = (10 X + Y)^{2} = 100 X^{2} + 20 X Y + y^{2}$
這時候使用 digit-to-digit algo
1. 先找 x 使用：每一輪
  $x * 2$ 使其滿足
  $x^{2} <= (Z >> 2)$
2. 找到最大之 X 帶入找 Y
延伸到所有狀況：

$N = (a_{1} + a_{2} + a_{3} + . . . a_{n})^{2}$
又

$(a_{1} + a_{2} + a_{3} + \dots + a_{n})^{2} =$

$a_{1}^{2} + 2 a_{1} a_{2} + a_{2}^{2} + 2 (a_{1} + a_{2}) a_{3} + a_{3}^{2} + \dots + a_{n - 1}^{2} + 2 (\sum_{i = 1}^{n - 1} a_{i}) a_{n} + a_{n}^{2} =$

$a_{1}^{2} + [2 a_{1} + a_{2}] a_{2} + [2 (a_{1} + a_{2}) + a_{3}] a_{3} + \dots + [2 (\sum_{i = 1}^{n - 1} a_{i}) + a_{n}] a_{n}$
再根據上面的算法由
$a_{1} . . . a_{m - 1}$ 逐一去猜。
令
$a_{1} . . . a_{m - 1}$ 已被猜到
$a_{m}$ 那一項便會是
$Y_{m} = [2 P_{m - 1} + a_{m}] a_{m}$ ，其中
$P_{m - 1}$ 是前面已備猜到的部份。
所以要猜
$a_{m}$ 會滿足遞迴式
$X_{m} = X_{m - 1} - Y_{m}$

在 Binary numeral system (base 2)之下略有不：

N^{2} = (a_{n} + . . . + a_{0})^{2}, a_{m} = 2^{m} o r a_{m}

根據第 3 週測驗題的推導：

P_{m} = a_{n} + a_{a - 1} + . . . + a_{m}

P_{m} = a_{n} + a_{a - 1} + . . . + a_{0}

為平方根

N

所以便是針對

P_{m}

逐一嘗試：

由於無法每一輪檢驗

N^{2} - P_{m}^{2}

成本過高，所以可以用跟上一輪的差值做比較。
再將 Y_m 做細分成

c_{m}, d_{m}

c_{m} = P_{m + 1} 2^{m + 1}

d_{m} = (2^{m})^{2}

在每一輪會更新

c_{m}, d_{m}

c_{m - 1} = P_{m} 2^{m} = (P_{m + 1} + a_{m}) 2^{m} = P_{m + 1} 2^{2 m} + a_{m} 2^{m} = {\begin{cases} c_{m} / 2 + d_{m} & if a_{m} = 2^{m} \\ c_{m} / 2 & if a_{m} = 0 \end{cases}

d_{m - 1} = \frac{d_{m}}{4}

最終條件會是

c_{- 1} = P_{0} 2^{0} = P_{0} = N

程式修正

__builtin_clz 之功能為回傳從前面數有多少 0

Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

針對第 2 週測驗題之中的 ffs (從後面數有多少 0) 所採用 binary search 的方法做出與 __builtin_clz 相同功能的 fls
針對提供分支和無分支 (branchless) 的實作，目前不確定如何實作。

commit 8bd78f4

在看了 linux kernel 中的 fls 使用發現這邊的誤用，這邊做了修正。

     int z = 0;
-    for (int m = 1UL << ((31 - fls(x)) & ~1UL); m; m >>= 2) {
+    for (int m = 1UL << ((fls(x) - 1) & ~1UL); m; m >>= 2) {
         int b = z + m;
         z >>= 1;

commit 29b0769

Linux 核心 `linux/block/blk-wbt.c`

在以下程式碼有提到：

static void rwb_arm_timer(struct rq_wb *rwb)
{
	struct rq_depth *rqd = &rwb->rq_depth;

	if (rqd->scale_step > 0) {
		/*
		 * We should speed this up, using some variant of a fast
		 * integer inverse square root calculation. Since we only do
		 * this for every window expiration, it's not a huge deal,
		 * though.
		 */
		rwb->cur_win_nsec = div_u64(rwb->win_nsec << 4,
					int_sqrt((rqd->scale_step + 1) << 8));
	} else {
		/*
		 * For step < 0, we don't want to increase/decrease the
		 * window size.
		 */
		rwb->cur_win_nsec = rwb->win_nsec;
	}

	blk_stat_activate_nsecs(rwb->cb, rwb->cur_win_nsec);
}

blk-wbt.c 代表 Buffered writeback throttling 是一調節 I/O 的技術。策略如下：

在一個定義的時間窗口內監控延遲。
如果該時間窗口內的最小延遲超過某個目標值，則增加 scaling step ，並將 queue 深度縮小 2 倍。然後將時間窗口縮小到 100 / sqrt(調節步驟 + 1)。
對於任何沒有確鑿延遲數據的窗口，保持現狀。
如果延遲看起來不錯，則減小 scaling step 。

直接對應 sqrt() 程式：

if (rqd->scale_step > 0) {
    rwb->cur_win_nsec = div_u64(rwb->win_nsec << 4,
                    int_sqrt((rqd->scale_step + 1) << 8));
} else {
    rwb->cur_win_nsec = rwb->win_nsec;
}

rwb->win_nsec 會初始為 100ms，但是這邊這邊跟敘述的 100 / sqrt(調節步驟 + 1) 實作不一樣，分別對 rwb->win_nsec << 4，(rqd->scale_step + 1) << 8 ，為何要位移不知道為何作用。

TODO 去翻 block 的 commit message

閱讀〈Analysis of the lookup table size for square-rooting〉和〈Timing Square Root〉，嘗試撰寫更快的整數開平分根運算程式。

測驗二

測驗三

解釋程式碼運作原理

版本一

使用最直觀的方式，使用 while loop 不斷對 i 除以 2 得出

l o g_{2} (i)

版本二

commit e66f2c9

以 binary search 針對不同大小 i 可以一次做多位數的計算，增加其速度。

版本三

commit cb2ec77

使用 GNU extension __builtin_clz(x)

Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

所以它會回傳 x 前面有多少位元為 0。如果講他視為以下格式 __builtin_clz(x) 便會是 n 等價於它最高位的非 0 元素是 (n-1) = 31 - n，便會是 log(n)

31	30	…	n	n-1	…	0
0	0	…	0	1	…	1

TODO: 分析上述實作手段的指令延遲

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

好的，以下為實作 vestata

clock_gettime() 測量

以下分析三種實作手段的延遲差異：

commit 61732ea

修改原本的程式，加入 Designated Initializers：

int main(){
    Log2Impl impls[] = {
        {.func = ilog2, .file_name = "out_ilog2.txt"},
        {.func = ilog2_2, .file_name = "out_ilog2_2.txt"},
        {.func = ilog32, .file_name = "out_ilog32.txt"}
    };

    for (int j = 0; j < sizeof(impls) / sizeof(impls[0]); j++) {
        FILE *fp = fopen(impls[j].file_name, "w");

        struct timespec start, end;
        int i;

        for (i = 1; i < 1000000 && i; i++) {
            clock_gettime(CLOCK_MONOTONIC, &start);
            impls[j].func(i);
            clock_gettime(CLOCK_MONOTONIC, &end);

            long long time = (long long) (end.tv_sec * 1e9 + end.tv_nsec) - \
                         (long long) (start.tv_sec * 1e9 + start.tv_nsec);  \

            fprintf(fp, "%u, %lld\n", i, time);
        }
        fclose(fp);
    }

    return 0;
}

新增 gnuplot 腳本
修改 Makefile

對 1~5000 的資料：

對 1~10000 的資料：

對 1~1000000 的資料：

可以觀察到 ilog32 的速度跟穩定度相較 ilog2, ilog_binary 都很高，因為使用 __builtin_clz(x) 比起其他兩個方法還省去 bitwise 的操作，還可以快速找到 msb 直接算出 log2 答案。ilog2 在時間上的表現是最差的辦多的噪點，使用最基本的除法方式，效率會很慢。ilog_binary 因為其 binary search 的性質在較大的數值會有比較好的表現。

在這個實驗我發現使用 log2 的時間會有許多噪點，目前這些噪點出現的原因我尚未釐清。我在 gnuplot 時為了清楚的繪圖，使用 threshold 去捨棄 200ns 以上的數值。

為何有如此多噪點呢？
先思考是否為計時程式導致的問題？

Perf 測量

所以我更新了我實驗的方式，改為使用 perf ，我使用命令 perf stat --repeat=5 -e task-clock ./2024w3q3 method x 有定義三種方法 0, 1, 2 分別對應上述三種方法，x 定義為 ilog(x) 的參數，x 大小定義為 1 - 10000，並平均五次測試的結果。
接下來撰寫了一個 bash 腳本以分別完成對三種方法的測量輸出 csv 檔案。

executable_name="./2024w3q3"
output_file_prefix="perf_output_function_"

if [ "$#" -ne 1 ]; then
  echo "Usage: $0 <function_index>"
  exit 1
fi

function_index="$1"

output_file="${output_file_prefix}${function_index}_r5.csv"

rm -f "$output_file"

for i in $(seq 1 10000)
do
  echo "Measuring performance for function index $function_index with input: $i"
  perf stat --repeat=5 -e task-clock -o temp_perf_data -- "$executable_name" $function_index $i 2>/dev/null

  task_clock=$(grep 'task-clock' temp_perf_data | awk '{print $1}')

  echo "$i, $task_clock" >> "$output_file"

done

echo "Performance measurement for function index $function_index completed."

此次實驗得出的結果使用 gnuplot 繪出以下：

雖然使用 perf 中的 task-clock 沒有出現像上一個實驗的噪點，但是圖像中顯示 ilog32() 沒有像理論上產生如此大的優勢。我回頭思考使用 perf 作為時間測量的正確性。
perf 的 task-clock 是以一個程式為單位，但是如今我們測試目標是 ilog2() ，是一個計算速度非常快的函式，其時間只會佔執行程式非常小的部份，所以使用 perf 之 task-clock 不會是正確的選擇。

實驗結論

所以實驗結果還是依據還是使用 clock_gettime() 但是噪點原因還在分析中。但就算有噪點，但是因為 ilog2() 運算速度極快，對整個程式影響不大。

附上三種方法 perf 10000 筆資料平均的比較：

The average time for ilog2() is 0.268591 ms
The average time for ilog2_2() is 0.264863 ms
The average time for ilog32() is 0.262433 ms

Linux 核心原始程式碼

在 include/linux/log2.h 中可以見到它取 ilog2 使用的方式是調用 fls() 來進行，它可以快速取的最大的非 0 位置， fls(x) - 1 便是

l o g_{2} (x)

我們可以看到它分定義針對 32 位元架構 __ilog2_u32 與 64 位元架構的 __ilog2_u64，皆是採用 fls 的作法。

之後會在主要 ilog2(n) 巨集被調用

#define ilog2(n) \
( \
	__builtin_constant_p(n) ?	\
	((n) < 2 ? 0 :			\
	 63 - __builtin_clzll(n)) :	\
	(sizeof(n) <= 4) ?		\
	__ilog2_u32(n) :		\
	__ilog2_u64(n)			\
 )

__builtin_constant_p 是 GCC 編譯器提供的一個內建函數，用來檢查其參數是否是在編譯時已知的常數表達式。如果參數是一個常數表達式，則 __builtin_constant_p 返回 1；如果參數不是常數表達式，則返回 0。而常數表達式表示該便書在編譯期間不會改變，提高程式碼的效率和執行速度。
如果是常數便進入 (n) < 2 ? 0 : 63 - __builtin_clzll(n)) : 如果 n 是 0 或是 1 便直接回傳 0，再來檢查 n 的大小如果他是 32 位元 ((sizeof(n) <= 4)) 便使用 __ilog2_u32(n)，若不是則使用 __ilog2_u64(n) 。

測驗四

EWMA

原理詳見第 3 週測驗題

觀察 EWMA 的可能實作中提到：

主要針對降低 rounding 所帶來的誤差。
透過 Scaling factor 使 internal 可以更準確的運算。
有 ewma_read() 來輸出 internel 的值，不要直接存取結構體中的 internel。

struct ewma

/* Exponentially weighted moving average (EWMA) */
struct ewma {
    unsigned long internal;
    unsigned long factor;
    unsigned long weight;
};

internal：
$S_{t}$
factor：scaling factor 用途
- EWMA 結構可以表示的最大平均數值。這個值由公式 ULONG_MAX / (factor * weight) 決定，其中 ULONG_MAX 是 unsigned long 數據類型能夠表示的最大值。這個公式顯示了 scaling factor 和權重如何共同影響可表示的最大平均值。
weight：
$α$ 用於衰減舊數據影響的指數權重

`ewma_init`

 if (!is_power_of_2(weight) || !is_power_of_2(factor))
        assert(0 && "weight and factor have to be a power of two!");

限制為 2 的冪主要是基於性能和計算效率的考慮。

`ewma_add()`

@avg: Average structure
@val: Current value

struct ewma *ewma_add(struct ewma *avg, unsigned long val)
{
    avg->internal = avg->internal
                        ? (((avg->internal << avg->weight) - avg->internal) +
                           (val << avg->factor)) >> avg->weight
                        : (val << avg->factor);
    return avg;
}

這邊 ewma_add() 按照上述取平均的統計手法，根據

S_{t} = α Y_{t} + (1 - α) * S_{t - 1}

進行計算，對應到上述程式如以下：

$(1 - α) * S_{t - 1}$	$α Y_{t}$
`((avg->internal << avg->weight) - avg->internal)`	`(val << avg->factor)) >> avg->weight`

注意：這邊換進去 internal 都進行 factor scaling

Linux 核心無線網路裝置驅動程式

針對 linux/drivers/net/wireless 去做探討。
EWMA 常被用於無線網絡驅動開發中，特別是用於信號強度的測量、網絡品質的評估，以及調整和優化網絡性能。

巨集無法「呼叫」(call)，因其本質的操作是「展開」(expand)，注意用語。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

收到！會注意的 vestata

可以大量調用 DECLARE_EWMA 巨集，找到位在 include/linux/average.h 中對 ewma 的定義。

其中有三個參數：
1. name：
2. _precision：這邊相當於上邊所訴 scaling factor
3. _weight_rcp：這邊相當於上面所訴的權重，
  $α$
在這邊對於 name 使用 ## token pasting。
- 例如，如果使用 DECLARE_EWMA(avg_rssi, 10, 8)，##name 會將 name 替換為 avg_rssi，從而生成 ewma_avg_rssi、ewma_avg_rssi_init、ewma_avg_rssi_read 和 ewma_avg_rssi_add，詳見你所不知道的 C 語言：前置處理器應用篇
可以在 include/linux/average.h 中看到 ewma_##name##_add， ewma_##name##_read中類似於剛剛提到的例題相同的操作。

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

收到，未來會注意的！ vestata

而在 linux/drivers/net/wireless 這個目錄中觀察到針對：avg_rssi, beacon_rssi, rate, signal等等進行 DECLARE_EWMA

針對 ath11k/ 進行實際應用介紹
- 在 mac.c 中 ath11k_mac_op_sta_statistics 函數中，ewma_avg_rssi_read 被用來獲取當前的 EWMA 值。這個值反映了考慮到之前的 RSSI 測量後的平均信號強度，用於更新 sinfo 中的 signal_avg 。據接收到的數據包信息更新無線站點的統計和信號質量指標，其中包括實時更新 EWMA 計算的 RSSI 值，從而提供對無線信號質量的動態評估。
- 在 dp_rx.c 使用 ewma_avg_rssi_add(&arsta->avg_rssi, ppdu_info->rssi_comb) 更新 EWMA 平均值。這一步將當前的 RSSI 值加入到 EWMA 計算中 (arsta 為一個 ath10k_sta 結構體的變數，裡面存放各種無線連接訊息)

TODO

嘗試更深入理解網路 drivers/ 實際操作

測驗五

解釋程式碼運作原理

計算

⌈ l o g_{2} (x) ⌉

，第一眼看這個程式碼真的是毫無頭緒。

int ceil_ilog2(uint32_t x)
{
    uint32_t r, shift;

    x--;
    r = (x > 0xFFFF) << 4;                                  
    x >>= r;
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    shift = (x > 0x3) << 1;
    x >>= shift;
    return (r | shift | x > 1) + 1;       
}

先逐一分解程式：

x--：為了針對處理 x 本身是 2 的冪的清況，若不做此處理，最後一步 ceiling + 1 會導致推到下一個對數。
由於是 unsign integer 32 bit，先查看 x 的最高為元是在前 16 位元還是後 16 位元。其中 << 4 是代表如過 x 在高位元，我們要對 x 右移 16 位元。
- 可理解為將位移量存在 r 之中。

    r = (x > 0xFFFF) << 4;                                  
    x >>= r;

在這邊 shift 作為變量使 x 移動 shift 位元，在此處 r 改為儲存位移總數的變量。

    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;

同 2. 範圍在 0xF
最後一步 (r | shift | x > 1) + 1 是多步驟寫在一起可以以下拆解：
- r | shift：程式進行到這等價於 r |= shift。
- (r | shift | x > 1)：最後做 if (x > 1) 的判斷，如果為真會加到 r 的位移總量。
- +1：取 ceiling。

改進程式碼

使可以處理 x = 0 ，並仍是 branchless 這個問題

\equiv

不要使用 x--; 處理 2 的冪問題

\equiv

在這邊發現另一個問題：

x	0	1	2	3	4	…
$l o g_{2} (x)$	32	1	1	2	2	…

所以有 log0 = 32, log1 = 1 共兩個問題。

針對 log0 做修正

commit 7d30243

使用 bitwise 操作：

     uint32_t r, shift;
 
-    x--;
+    x -= !!x;
     r = (x > 0xFFFF) << 4;

使用此方法 log0 = 0， log1 = log2 = 1 尚有錯誤。

Linux 核心原始程式碼

根據提示到 Linux 核心排程器 kernel/sched/ 尋找：

第 4 周測驗題

測驗一

popcount 是計算數值的二進位表示中，有多少位元是 1。

版本一
使用的是 naive 手段，v &= (v - 1) 會在每一輪將位置最低的 1 清為 0。又每一次操作會有一個 n 作為計數，這邊使用 n = -(~n)
$\equiv$ n++ 實踐，是一個活用二補數系統的方法。詳細可以見第 4 周測驗題。
版本二
改寫為 branchless 的手法
使用數學式：

$p o p c o u n t (x) = x - ⌊ \frac{x}{2} ⌋ - ⌊ \frac{x}{4} ⌋ - . . . - ⌊ \frac{x}{2^{31}} ⌋$
以下皆為二進位去觀察：
令
$x = b_{31} . . . b_{2} b_{1} b_{0}$

TODO 完成 __builtin_popcount 的原理解析。

hammind distance: 為二進位的每個位元的差，而 a ^ b，XOR 操作留下相異的位元，取其 popcount 便是 hamming distance.

考慮 LeetCode 477. Total Hamming Distance 這提的目標是求所有點之間的 hamming distance 之總和。
測驗題提供的程式碼：

int totalHammingDistance(int* nums, int numsSize)
{
    int total = 0;;
    for (int i = 0;i < numsSize;i++)
        for (int j = 0; j < numsSize;j++)
            total += __builtin_popcount(nums[i] ^ nums[j]); 
    return total >> 1;
}

這是使用暴力法使用二層 for 迴圈計算所有 pair，所以每個 pair 會計算兩次 hamming distance。所以最後一步再回傳質需要再除以二已得到正確答案。
此方法在 LeetCode 477 會 Time Limit Exceeded。

修正此暴力法：

-    for (int i = 0;i < numsSize;i++)
+    for (int i = 0;i < numsSize - 1;i++)
-        for (int j = 0; j < numsSize;j++)
+        for (int j = i+1; j < numsSize;j++)
            total += __builtin_popcount(nums[i] ^ nums[j]); 
-    return total >> 1;
+    return total;

可以通過 LeetCode 477 但是時間表現在最後 20%，尚有進步空間。

找到其規律：

	4	3	2	1	0
7	0	0	1	1	1
5	0	0	1	0	1
10	0	1	0	0	1
17	1	0	0	0	1
result	3	3	4	3	0

我們使用列的視角去觀看二進位表示。根據上面暴力法我們使用的 XOR 操作是針對每一位數有多少相異的位元。以上面的例子（依據上面列的標示）：
第 0 列有 4 個 1，其 XOR 結果也都會是 0，所以最後再計算 popcount 也會是 0。
第 1 列有一個 1 與三個 0 ，在整個遍歷會出現 (1 ^ 0) 三次，所以總共的 popcount 次數會有 3 次。
第 2 列有兩個 1 兩個 0，會分別有 ((1 ^ 0), (1 ^ 0)), ((1 ^ 0), (1 ^ 0))總共四次，所以在 popcount 也會增加 4 次。
以此類推…

同理我們可以每一列將它拆成：x 個 1 與 y 個 0，將 x * y 便是上面的結果（這是觀察的結果），也可以說是上面做法的歸納。

實作如以下：

int totalHammingDistance(int* nums, int numsSize) {
    int i, j, k, t;
    t = 0;
    for (i = 0; i < 32; i++) {
        k = 0;
        for (j = 0; j < numsSize; j++) {
            k += (nums[j] & (1U << i)) ? 1 : 0;
        }
        t += k * (numsSize - k);
    }
    return t;
}

k 為 1 的計數，而整列不是 1 就是 0 所以使用 (numsSize - k) 作為0的數量。

在 leetcode 上測試使用 (1 << i) 會出現以下錯誤：

left shift of 1 by 31 places cannot be represented in type 'int'

原本 1 預設為 int 不能進行 << 31 操作，要使用 1U unsigned int 才可以。
但是而在本地電腦 gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0 (1 << 31)可以正常編譯。也查看了 AddressSanitizer 也尚未發現問題。

TODO 為何會這樣？

測驗二

目標：不使用任何除法就算出某數除以另一個數的餘數

\begin{array}{r} 2^{k} \equiv {\begin{cases} 1 (\mod 3), & if k is even \\ - 1 (\mod 3), & if k is odd \end{cases} \end{array}

TODO 理解這段程式，真看不懂

測驗三

考慮 XTree，XTree 的平衡機制與 AVL tree 相似，利用 hint 來評估是否需要做 rotate，然而 xt_node 的 hint 的計算方式是，其左右節點 hint 最大值 +1 並且只有在被呼叫到 xt_update 時才會被更新。

hint 怎麼去評估的？
近似而非精確：在 XTree 中，每個節點的提示值用於判斷樹的平衡狀態，但這個值並不需要與實際的最長子節點鏈長度完全一致。這樣可以減少在每次樹的修改操作後更新高度信息所需的計算量。

平衡操作的依據：當執行插入或刪除操作時，XTree 通過比較節點的提示值來決定是否需要進行旋轉來重新平衡樹。如果提示值顯示一側的鏈比另一側長得多，則可能需要進行平衡操作。

程式碼解釋

treeint.c

treeint_ops 五種操作，再接上 xt_ops 對 treein_xt 進行操作。
bench 計算執行時間。
選擇 xt_ops 樹操作
通過 ops->init 初始化樹結構，並將其地址存儲在 ctx 中。
進行插入操作，根據種子是否為零使用線性或隨機方式生成元素值，測量並輸出每次插入操作的時間。
進行查找操作，方法同插入操作，測量並輸出每次查找操作的時間。
進行刪除操作，方法同插入和查找操作，測量並輸出每次刪除操作的時間。
最後，銷毀樹結構並結束程序。

Additionally, if the node's hint becomes zero or experiences a change compared to its previous state during the update, modifications are made to the node's parent, as it existed before these update operations.

xtree.c

XTree 的操作基於四個基本的二元搜尋樹操作：rotate_left、rotate_right、replace_right、replace_left。
xt_dir ：指示方向（左、右、無）。
插入：按照二元搜尋樹的標準方法插入新節點，然後調用 xt_update 來保持或恢復平衡。
xt_balance 如果左子節點存在，則計算左子樹的高度（l），加上左子節點的 hint 屬性值加 1（hint 是用於存儲或表示節點高度或深度的字段）。

treeint_xt.c

如何將 XTree 整合為一個特定於整數的二元搜尋樹

2024q1 Homework4 (quiz3+4)

第 3 周測驗題

測驗一

整理數學式

自 Digit-by-digit calculation 中:

在 Binary numeral system (base 2)之下略有不：

程式修正

Linux 核心 linux/block/blk-wbt.c

測驗二

測驗三

解釋程式碼運作原理

clock_gettime() 測量

Perf 測量

實驗結論

Linux 核心原始程式碼

測驗四

EWMA

struct ewma

ewma_init

ewma_add()

Linux 核心無線網路裝置驅動程式

測驗五

解釋程式碼運作原理

改進程式碼

Linux 核心原始程式碼

第 4 周測驗題

測驗一

測驗二

測驗三

程式碼解釋

treeint.c

xtree.c

treeint_xt.c

Read more

2025q1 Homework1 (lab0)

2025q1 Homework1 (ideas)

Assignment1: RISC-V Assembly and Instruction Pipeline

Kernel_matmul

Linux 核心 `linux/block/blk-wbt.c`

`ewma_init`

`ewma_add()`