2024q1 Homework2 (quiz1+2)

contributed by < idoleat >

表單問題第 1 題

考慮以下程式碼

uint8_t ip = 9, *p1 = &ip;
uint32_t *p2 = (uint32_t *) p1;
printf("p2 = %d\n", *p2); 

這段程式碼會導致 undefined behavior

題目提示參見章節 6.3.2.3

6.3.2.3 Pointers
7. A pointer to an object or incomplete type may be converted to a pointer to a different object or incomplete type. If the resulting pointer is not correctly aligned for the pointed-to type, the behavior is undefined. Otherwise, when converted back again, the result shall compare equal to the original pointer. When a pointer to an object is converted to a pointer to a character type, the result points to the lowest addressed byte of the object. Successive increments of the result, up to the size of the object, yield pointers to the remaining bytes of the object.

ip 為 1 byte 對齊，而 p2 所指的 uint32_t 為 4 byte 對齊，依據規格書這並沒有正確對齊，因此為未定義行為

疑問：那如果手動將 ip padding 為 4 byte ，即 char ip[4]，這樣還會是未定義行為嗎？我們先繼續以下討論

除了以上疑問，題目給的原程式碼也違反 6.5 Expressions 中的規定：int32_t 與 ip 的 effective typeint8_t 並不 compatible。因此依據 6.2.7 Compatible type and composite type 此行為為 undefined behavior。

6.5 Expressions
7. An object shall have its stored value accessed only by an lvalue expression that has one of the following types:
— a type compatible with the effective type of the object,
— a qualified version of a type compatible with the effective type of the object,
— a type that is the signed or unsigned type corresponding to the effective type of the object,
— a type that is the signed or unsigned type corresponding to a qualified version of the effective type of the object,
— an aggregate or union type that includes one of the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union), or
— a character type.

6.2.7 Compatible type and composite type

1. Two types have compatible type if their types are the same. Additional rules for determining whether two types are compatible are described in 6.7.2 for type specifiers, in 6.7.3 for type qualifiers, and in 6.7.5 for declarators…
2. All declarations that refer to the same object or function shall have compatible type; otherwise, the behavior is undefined.

若將 ip padding 為 4 byte ，即 char ip[4]，int32_t 會與大小為 4 的 char array compatible 嗎？規格書裡沒有找到相關敘述，因此是 unspecified behavior，需要再去查閱編譯器的文件，若有相關規定那就是 implementation-defined behavior 因此這兩者依據 6.2.7 為 incompatible。以此論述接續上方提出的疑問，如此行為是 type-punning ，在 你所不知道的 C 語言：linked list 和非連續記憶體 中 WRITE_ONCE 巨集有解釋，依據規格為未定義行為，這是為了要讓編譯器有更大的彈性配合前後文做最佳化，例如可以合併對同個 char 的運算操作或是減少重複的讀取，在論及此未定義行為時會以 strict aliasing 稱呼，倘若允許了 aliasing 編譯器就必須提防最佳化帶來的錯誤行為。但是在多工環境下，這些最佳化確有可能導致讀寫事件的順序不如預期，因此可以利用 union 及 attributes 阻止最佳化。

很多概念都是環環相扣的，不可以忽略任一細節，唯有全面了解程式運作機制才能掌握自己的程式的執行方式！在社群媒體上發梗圖嘲笑欸我的程式今天能跑明天不能跑、能跑的程式就不要動啦不然一碰就壞掉修不好，或是用無限猜猜看試誤法除錯，只是彰顯自己無法對自己的程式碼負責。有時資深的 Arch Linux (或其他 DIY 風格發行版) 使用者會不小心流漏一點點優越感（例如 btw I use Arch)，是因為其完全了解他的電腦是如何運作，不用在系統出問題時到處 Google 複製貼上別人的指令來修修補補補不好

先前參加 NVIDIA 之線上測驗，有一題為

int num = 512;
char *ch = #
ch[0] = 3;
ch[1] = 2;

// 請問 `num` 值為何？

當下有疑惑這樣是否合法？現在參照規格書 6.2.3.2 ch 確實可以一次存取 1 byte 直到 int 的大小。不過在面試當下的另一題不使用乘法器達成乘法比較印象深刻，因為前一天準備時剛好在 你所不知道的 C 語言: bitwise 操作 抱佛腳抱到，不過沒有寫出最好的版本，例如如何算出當下該使用 (x << 4) - x 而非 x + (x << 1) + (x << 2) + (x << 3)

第 1 週測驗題

Quick sort

重新認識 quick sort 時的思考

• 挑 pivot 的策略？
• 移動其他元素至 pivot 的兩側，依據資料分佈決定插頭插尾？插入的時候能不能 insertion sort? 最多只比較兩次的 insertion sort?
• 都不管插入，直接一次移動 pivot 到位，也就是不動其他元素只動 pivot
  $\to$ Optimized QuickSort — C Implementation (Non-Recursive) 的作法

TODO: 在 lab0 以實驗測試想法，比較差異

• pivot 之所以為 pivot 就是到定點之後就不會再動了，例如 10 個元素中本該是第 7 大的元素經操作後就會直接待在第 7 的位置。先不論是如何搬到正確位置的，quick sort 的行為就是每個元素都會作為 pivot 被搬到正確位置。也就是「把一個元素搬到正確位置上」會做 n 次，n 為序列大小
• 「把一個元素搬到正確位置上」這件事要怎麼做呢？與其他人比一遍看 pivot 是第幾大就排第幾個（二分搜尋顯然不能用因為資料沒有排序），頗有插入排序法的味道

quick sort 關鍵在於以下三件事

• 挑選 pivot
• 切割成比 pivot 小和比 pivot 大兩部份
• 對兩部份重複以上動作

Jeff Erickson 的教科書 說 partition 顯然是

$O(n)$，但是對於最後一個層的 partition 一定是一步就做完了，有違 Big

$O$ 的定義：給定足夠大的

$n$ 時執行時間的成長趨勢。我以我的解釋重新推導 quick sort 的時間複雜度

不精確 tl;dr: pivot 若不是在頭或尾則會以二元樹的形式展開子任務執行，樹高

$log(n)$，每一層的子任務長度加總為

$n$，最後共將

$n$ 個 pivot 搬到正確位置。倘若有 pivot 選在頭或尾，則不會有兩邊兩個子任務，只有一邊，樹開始歪斜退化 (skew)，但還是要總共搬移

$n$ 個 pivot 到正確位置於是樹高開始加長，最長為

$n$，也就是退化成一直線，而每一層的子任務長度加總也還是

$n$。所以只有單一子任務與兩個子任務的比例會決定時間複雜度從

$nlogn$ 退化至

$n^2$ 的比例

經查閱 維基百科，其分析方法與我相同。不查閱最經典的教科書的理由是在我決定不看盜版書之後就被我刪了

看到是以二元樹的形式展開子任務就需要意識到，局部排序可以先做完以妥善利用 cache

運作原理與改進

首先要先找出 1. 選 pivot 的程式碼 2. 從頭與 pivot 比較，算出 pivot 應該要再哪個位置的程式碼

排序

排序是一維付加上序列位置資訊擴增二維再投影至另一維之展現

如圖

Bucket sort 即為此方法。思考若改用 virtual bucket 容納投影結果，則排序為 bucket management unit 中轉換為 physical bucket 的方法。一次處理 16 個 bucket 比較簡單，於是對 virtual bucket 4 bits (& 0xf) 作為 level 1 的排序，接下來再取 4 bits ，以已排好的 16 個buckets 為 level 2 的 unit bucket 一樣處理 16 個 bucket，假設 virtual bucket 用 int 儲存則至多 level 8。如同 page size 依場景可以選擇更大 (e.g. HPC, QEMU? 還是某個虛擬化的專案？)，可以依場景調整一次處理的 bucket 數量

void q_vbsort(struct list_head *head, bool decend)
{
    
}

先測試大小上限為 16 的純數字鏈結串列 (gist)
為了減少特殊狀況，並且讓所有 level 都共用 b16sort，即 b16sort 只負責將鍊結串列首尾相接變成一個更大的鍊結串列。level 1 需要將 list_head 用 INIT_LIST_HEAD 初始化。與以陣列為基礎的 bucket sort 不同的是，相同數值的元素會被串接起來而不是蓋過去，並且維持原本的順序，為 stable sort。

延續「排序是一維付加上序列位置資訊擴增二維再投影至另一維之展現」，其中「另一維」是由函數所定義，bucket sort 採線性維度，即認一

$y=ax+b$ blalbalbalba，完全不排序的維度 blablabla，只交換兩元素的維度

延續在 作業一 提到的想法