HackMD
2025q1 Homework1 (ideas)
contributed by < charliechiou >
針對鏈結串列的資料排序改進
目標 : 嘗試引入 Timsort 及其延伸的演算法並與 listsort 比較。
初步閱讀這份期末專題，以下是目前的疑惑
- Timsort 實做方法及延伸演算法
- 龐大的 linux kernel程式碼應該如何去找出改動程式碼時候會影響到的內容
- 如何編譯及測試 linux kernel 中的程式碼並改良內部的程式
- 比較排序演算法時需要分析的參數
Timsort 演算法
先將需要排序的資料整個掃過一遍，並將單調遞增/遞減的資料視為一個 run 並依照需求先把每個 run 排序好再合併，而每個 run 之間的資料透過 stack 維持。
疑惑 :
- 若需要排序的資料極大，先掃描過一次不會降低效率嗎 ?
- 為何使用 stack ?
想法 :
- Timsort 演算法的時間複雜度為 O(nlogn) ，這樣的掃描僅花費 O(n) 因此不會特別降低效率，且這部份的掃描能夠大幅減少後面所需要的時間。
- stack 有後進先出的特性(LIFO)，合併需要存取最上面的幾個數值因此可以有效減少需要的時間
每次合併時會合併兩個 run ，因此 run 總數略大於 2 的冪時效率會特別低 (資料不平衡)，為了改善平衡問題，因此長度不足於 minrun 的兩個 runs 會做兩兩合併，常見的 minrun 會設定為 64。
前述的 minrun 設定作者解釋為是由於 64 可以一次放入 cache line，但這邊是針對鍊結串列 (Linked-list) 所作的操作，因此不一定是設定為 64，是可以在探討及測試的部份。
adaptive_shiversSort
這部份是針對合併 minrun 所作的改良，若目前 stack 上的 run 為 X,Y,Z 且 Z 為 top ，如果
則合併 X,Y。可以很簡單的透過 clz 來實做
疑問：
- clz 如何很簡單的計算
? 解答：
- 二進位中一個數字可以表示為
因此的 會直接和最高位1的索引值對應
Powersort
(To be done)
資料蒐集
作者先透過搜尋找出 linux_kernel 中有使用到 list_sort 的部份，再查看那些 function 後找到可以在使用者層級使用的命令，因此從這部份著手比較方便查看結果。
可以將這種方法作為改善 linux kernel 程式碼的切入點
接著使用 virtme-ng 的虛擬環境來進行實驗。透過修改 list_sort 使他在被呼叫時會留下對應的紀錄，並透過 list_sort 的 kernel 版本編譯出對應的 perf tools。
是否這邊可以有類似 gdb 的方式來查看修改結果或呼叫結果而不用在程式碼安插一個 print ?
並透過自己撰寫的 kernel module 呼叫 list_sort 並檢視輸出
什麼是 kernel module 又是如何撰寫的 ?
參考 Linux 核心模組運作原理，kernel module 是一個可以載入 (load) 及卸除 (unload) 到核心的模組，詳細的使用辦法參考前述的連結。
[ 0.672210] virtme-ng-init: initialization done
[ 30.108569] list_sort_module: loading out-of-tree module taints kernel.
[ 30.108752] List before sorting:
[ 30.108754] Value: 9
[ 30.108755] Value: 8
[ 30.108755] Value: 7
[ 30.108756] Value: 6
[ 30.108757] Value: 5
[ 30.108757] Value: 4
[ 30.108758] Value: 3
[ 30.108758] Value: 2
[ 30.108759] Value: 1
[ 30.108759] Value: 0
[ 30.108760] Hello from list_sort
[ 30.108761] List after sorting:
[ 30.108762] Value: 0
[ 30.108762] Value: 1
[ 30.108763] Value: 2
[ 30.108763] Value: 3
[ 30.108764] Value: 4
[ 30.108764] Value: 5
[ 30.108765] Value: 6
[ 30.108766] Value: 7
[ 30.108766] Value: 8
[ 30.108767] Value: 9
接著便嘗試使用 perf 呼叫 list_sort ， 這部份會需要重新編譯 libtraceevent 因此在 vng 為系統安裝 libtraceevent
libtraceevent 是 perf 依賴的 library
隨後找到正確會調用到 list_sort 的部份再參考 metric_list_cmp 如何將 metric_list 中要排序的資料解析出來撰寫 dump_metric_list_ele 將資料解析出來。
和先前有一樣的疑惑，是否可以透過類似 gdb 的方法省去這步驟
再接著透過 stress-ng 來進行壓力測試，可以測試 GPU 滿載情況的效能。但 perf 在呼叫到 list_sort 時候只依照輸入的 matric list 順序進行排序，和最後的結果，因此會是固定的資料分佈無法用作測試。
接著測試檔案系統為 ext4 的隨身碟，再透過自己撰寫的程式讓使用者輸入 ext4 裝置路徑並回傳 fsmap 內容。
疑問:
- ext4檔案是怎樣的檔案類型？
解答：
- ext4(fourth extended filesystem)：wiki
並透過編譯好的程式來查看目錄，但為了取得資料分佈，必須修改kernel。由於虛擬機器的檔案系統會變為 tmpfs 因此需要直接編譯完整的 kernel 直接執行。
編譯 linux kernel
先下載需要的套件後，將原先電腦的 config 那來使用做為驅動的設定，再透過 make 安裝所需的 modules。重新啟動後在 grub 中選擇剛剛的 kernel 即可。
從這邊可以更深刻的了解到 linux 作為作業系統的存在
用類似的方式取得 XFS 的資料後便可以開始進行 sorting 的實驗。
整合 Timsort及改進至 Linux 核心
作者透過 linux 中的 module 來方便的完成實做，將 list_sort 等相關算法寫成 module 後再透過 EXPORT_SYMBOL 來導出。
這部份我的理解是透過 linux 中的 module 可以把寫在不同區域的 function 打包，只要打包的 function 是在核心中運作便可以方便的使用它。
接著透過 insmod 將編譯好的 module 載入。
實驗
實驗紀錄對同一筆資料集排序數次後的時間加總，透過 ktime_get 取得經過的時間。且為了避免 interrupt 以及 preemption 對實驗造成影響，因此作者也透過以下指令關閉
local_irq_disable(); // disable local interrupt
get_cpu(); // disable preemption
// Experiments
local_irq_enable(); // enable local interrupt
put_cpu(); // enable preemption
主要測試以下幾項
- ext4 檔案系統的 ext4_getfsmap
- btrfs 檔案系統的 extent_list
- 透過 perf stat -M 照順序輸入所有 metric 的 perf_metric_list
- xfs 檔案系統的
xfs_buf_delwri_submit_buffers,xlog_cil_push_work,xfs_trans_run_precommits以及xfs_extent_busy_sort
在 ex4 及 btrfs 的測試中可以了解到 Timsort 對於 ex4 的表現並不會比原先的 list_sort 較為優異，但在 btrfs 則會有更好的結果。
過去在做其他實驗測量程式執行時間時，常會受到環境中其他因素影響，是否有可以像是 dudect 類似的方法可以更公正的測量程式碼執行時間?
而在 perf stat -M 的實驗測試中雖然 Timsort 比較次數較多，但執行時間則較少。
是否可能就是上述的所說環境中其他因素影響？
而最後也用同樣方法測量 xfs 檔案系統，在部份的結果中 Timsort 也都取得優異的表現。
思考可以改善的方式，是否可以讓 Timsort 在第一次掃描全部資料時若分佈不如預期，就使用原先的 list_sort 來排序？
位元運算的應用
目標 : 解析第七週測驗題 測驗 1, 2 及第九週測驗題 測驗 3
第七週測驗題 測驗 1
延伸問題1.
解釋上述程式碼運作原理
首先先介紹如何判斷一個數是否為奇術，bool odd(uint32_t x){return x & 1}，為減少運算量，我們可以將兩個 32 位元合併為 64 位元並用特殊的位元遮罩做計算，此時可以寫成
static inline uint64_t bit_compound(uint32_t x, uint32_t y)
{
return ((0L + x) << 32) | ((y + 0L) & (-1L >> 32));
}
作者這邊提出 & (-1L >> 32)) 應該是不必要的操作。
在規格書中 6.1.3.8 Usual arithmetic conversions 有提到型別在位移時會自動轉換，因此我認為這邊應該也可以不需要額外的 0L 操作
Many operators that expect operands of arithmetic type cause conversions and yield result types in a similar way. The purpose is to determine a common real type for the operands and result. For the specified operands, each operand is converted, without change of type domain, to a type whose corresponding real type is the common real type.
接著查看 Linux 核心中的 lib/string.c 中 memchr 實作用來在記憶體區塊 str 中搜尋字元 c：
/**
* memchr - Find a character in an area of memory.
* @s: The memory area
* @c: The byte to search for
* @n: The size of the area.
*
* returns the address of the first occurrence of @c, or %NULL
* if @c is not found
*/
void *memchr(const void *s, int c, size_t n)
{
const unsigned char *p = s;
while (n-- != 0) {
if ((unsigned char)c == *p++) {
return (void *)(p - 1);
}
}
return NULL;
}
而透過 SIMD within a register (SWAR) 的技巧，我們可改寫為以下 memchr_opt 函式:
#include <limits.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
/* Nonzero if X is not aligned on a "long" boundary */
#define UNALIGNED(X) ((long) X & (sizeof(long) - 1))
/* How many bytes are loaded each iteration of the word copy loop */
#define LBLOCKSIZE (sizeof(long))
/* Threshhold for punting to the bytewise iterator */
#define TOO_SMALL(LEN) ((LEN) < LBLOCKSIZE)
#if LONG_MAX == 2147483647L
#define DETECT_NULL(X) (((X) - (0x01010101)) & ~(X) & (0x80808080))
#else
#if LONG_MAX == 9223372036854775807L
/* Nonzero if X (a long int) contains a NULL byte. */
#define DETECT_NULL(X) \
(((X) - (0x0101010101010101)) & ~(X) & (0x8080808080808080))
#else
#error long int is not a 32bit or 64bit type.
#endif
#endif
/* @return nonzero if (long)X contains the byte used to fill MASK. */
#define DETECT_CHAR(X, mask) DETECT_NULL(AAAA)
void *memchr_opt(const void *str, int c, size_t len)
{
const unsigned char *src = (const unsigned char *) str;
unsigned char d = c;
while (UNALIGNED(src)) {
if (!len--)
return NULL;
if (*src == d)
return (void *) src;
src++;
}
if (!TOO_SMALL(len)) {
/* If we get this far, len is large and src is word-aligned. */
/* The fast code reads the source one word at a time and only performs
* a bytewise search on word-sized segments if they contain the search
* character. This is detected by XORing the word-sized segment with a
* word-sized block of the search character, and then checking for the
* presence of NULL in the result.
*/
unsigned long *asrc = (unsigned long *) src;
unsigned long mask = d << 8 | d;
mask |= mask << 16;
for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
mask |= mask << i;
while (len >= LBLOCKSIZE) {
if (DETECT_CHAR(CCCC, mask))
break;
asrc++;
len -= LBLOCKSIZE;
}
/* If there are fewer than LBLOCKSIZE characters left, then we resort to
* the bytewise loop.
*/
src = (unsigned char *) asrc;
}
while (len--) {
if (*src == d)
return (void *) src;
src++;
}
return NULL;
}
接著照作者的寫法逐步分析程式碼的原理
首先第一個迴圈使用到 UNALIGNED(src) 來確定是否有對齊記憶體
/* Nonzero if X is not aligned on a "long" boundary */
#define UNALIGNED(X) ((long) X & (sizeof(long) - 1))
這部份不太能理解作者的解釋，因此又自己查閱其原理。
long 所佔據的大小為 8 因此這行表示只要 x 和 7 (i.e., 0b0111) 去做 AND 運算便可確定是否未對齊。以 x = 0x1002 為例，0x1002 & 0x7 == 2 未對齊，相當於確認 x 是否為 8 的倍數(i.e., 第三位底下是否都是 0)
進到迴圈後判斷
- 第一個判別式用以判斷 len 是否為 0，若為 0 則表所有字元已經掃描過一輪，而隨著每次檢查會將其值遞減，直至迴圈條件不成立。
- 第二個判別式用以判斷當前 src 所指向字元與欲搜尋之字元 d 是否匹配。
- 最後將 src 改指向下一個字元所在位址，直到位址值符合對齊條件。
接著進到第二個條件判斷，首先判斷 if (!TOO_SMALL(len)) 當輸入字串長度 ≥ 8 時，判別式條件成立，並強制轉型 unsigned long *asrc = (unsigned long *) src;。
接著透過 or 及左移運算，使變數 mask 為欲搜尋字元 d 的重覆擴展（擴展次數會因不同機器上的 long 型別位元數而有所不同）。
unsigned long mask = d << 8 | d;
mask |= mask << 16;
for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
mask |= mask << i;
接著使用 DETECT_CHAR 及 DETECT_NULL 來檢測 c 是否出現在字串中
#define DETECT_CHAR(X, mask) DETECT_NULL((X) ^ (mask))
由於 mask 是由 c 重複擴展的 mask 因此可以先用 ^ 來確認是否有出現 c 這個字元，相同的部份則設成 0x00 再由 DETECT_NULL 來確認是否有 0x00 的存在。
接著查看 DETECT_NULL 的使用
#if LONG_MAX == 2147483647L
#define DETECT_NULL(X) (((X) - (0x01010101)) & ~(X) & (0x80808080))
#else
#if LONG_MAX == 9223372036854775807L
/* Nonzero if X (a long int) contains a NULL byte. */
#define DETECT_NULL(X) \
(((X) - (0x0101010101010101)) & ~(X) & (0x8080808080808080))
#else
#error long int is not a 32bit or 64bit type.
#endif
#endif
若系統為 32 位元則使用第二行來偵測是否有出現 NULL，若 64 位元則使用第七行，若接非則用第 9 行跳出。
以 32 位元為例，首先 x 與 0x01010101 相減，若其中某個段落為 0x00 則會變為 0xFF。接著再和 x 的取反便可留下 0x00 出現的位置 (其他不是 0x00 的部份和自己的 not 做運算會變成 0x00)， 最後再和 0x80808080 做 AND 便可識別出出現 NULL 的位置。
延伸問題2.
比較 Linux 核心原本 (與平台無關) 的實作和 memchr_opt，設計實驗來觀察隨著字串長度和特定 pattern 變化的效能影響
這部份作者僅討論要如何選定資料長度來當作樣本，並列舉出實驗所需要的數據大小，並未進行實驗，因此是可以做改進的地方。
延伸問題 3.
研讀 2022 年學生報告，在 Linux 核心原始程式碼找出 x86_64 或 arm64 對應的最佳化實作，跟上述程式碼比較，並嘗試舉出其中的策略和分析
下一步：貢獻程式碼到 Linux 核心
Phoronix 報導
同樣這個延伸問題並未完成，但也讓我好奇 linux 對於不同的硬體設備是否皆會做相對應的優化，又或者 linux 核心如何適應各種不同的硬體設備的?
