contributed by < cwl0429 >
linux2022
q_new
: 建立新的「空」佇列;q_free
: 釋放佇列所佔用的記憶體;q_insert_head
: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);q_insert_tail
: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);q_remove_head
: 在佇列開頭 (head) 移去 (remove) 給定的節點;q_release_element
: 釋放特定節點的記憶體空間;q_size
: 計算目前佇列的節點總量;q_delete_mid
: 移走佇列中間的節點,詳見 LeetCode 2095. Delete the Middle Node of a Linked Listq_delete_dup
: 在已經排序的狀況,移走佇列中具備重複內容的節點,詳見 LeetCode 82. Remove Duplicates from Sorted List IIq_swap
: 交換佇列中鄰近的節點,詳見 LeetCode 24. Swap Nodes in Pairsq_reverse
: 以反向順序重新排列鏈結串列,該函式不該配置或釋放任何鏈結串列節點,換言之,它只能重排已經存在的節點;q_sort
: 以遞增順序來排序鏈結串列的節點,可參閱 Linked List Sort 得知實作手法;list.h
中的 INIT_LIST_HEAD
將 next 和 prev 指向 head 本身並且回傳 head,否則回傳 NULL 表示配置失敗list_for_each_entry_safe
找到 queue 中的每個 element 並釋放list_for_each_entry
,是因為在迭代的過程中會將 element 刪除,list_for_each_entry
沒有對 node 做保護,若隨意刪除節點,將會無法找到下一個 node用通順的漢語書寫。
element_t *e
,若是無法配置則回傳 falselist_add
將 e->list 加入 queue 的開頭並回傳trueq_insert_head
判斷式,當 queue 尚未被建立時,不能插入節點,應回傳 falseq_insert_head
相似,唯一差別在於 e->list 加入的位置list_add_tail
將 e->list 加入 queue 的 tailq_insert_head
一樣問題list_first_entry
取得 queue 的第一個 elementlist_del
將該節點移出
list_del
只有將 link 斷開,以下為list.h
註解:qtest.c
中 do_remove
會主動將 \0 填入字串的末端q_remove_head
雷同,只差在移除 head->next 還是 head->prevlab0-c
作業說明,目前還沒想到更好的寫法Floyd's tortoise and hare
演算法在本課程中,「核心」一定指 OS kernel,你該避免濫用該詞彙。附上必要的參考資訊。
list_move
將當前 node 插入 node->next 的 nextlist_for_each_safe
q_reverse
沒有寫好,導致有 link 連接錯誤,想說試試 list_move
的方式實作,便成功通過測資q_size
改寫成反方向 traverse 後,才發現 merge 結束時 queue size 已經不對,代表 q_sort
只有正確地連接順向的 nodel
的 l->prev
沒接到q_reverse
實作方式會通過測資的原因在於 list_move
串接了遺漏的 link,使 queue 在經過 reverse 後能正確地 free根據 Scottk 網友在 stackoverflow 的說明,似乎是 strcmp 會建立一個 assembler file - strcmp-avx2.S,但由於傳進去的 pointer 為 NULL pointer,導致它無法創建該檔案,但可能要找到更多證據來支持這項論述
請愛用 GDB 排除問題。
strcmp
不能接受 NULL 值,所以要使用一段判斷式跳脫迴圈,避免 safe->value = NULL 傳入 strcmp
__attribute__
用途根據 gcc 的說明,__attribute__
能指定變數、函式參數及結構等等的屬性
The keyword
__attribute__
allows you to specify special properties of variables, function parameters, or structure, union, and, in C++, class members. This__attribute__
keyword is followed by an attribute specification enclosed in double parentheses. Some attributes are currently defined generically for variables. Other attributes are defined for variables on particular target systems. Other attributes are available for functions (see Function Attributes), labels (see Label Attributes), enumerators (see Enumerator Attributes), statements (see Statement Attributes), and for types (see Type Attributes). Other front ends might define more attributes (see Extensions to the C++ Language).
其中在 list_sort.c 用到 function attribute,其能幫助編譯器最佳化及更正確地檢查 code 是否出錯
In GNU C and C++, you can use function attributes to specify certain function properties that may help the compiler optimize calls or check code more carefully for correctness. For example, you can use attributes to specify that a function never returns (noreturn), returns a value depending only on the values of its arguments (const), or has printf-style arguments (format).
譬如 list_sort.c 用到不少 nonnull attribute,能指定函式的哪些參數不能為 NULL pointers,以下方例子來說, nonnull(2,3,4)
函式第二到四的參數不能為 NULL pointers,也就是 cmp, a, b 這三個參數
Merge 方式
list_sort.c 使用了兩種 merge 函式
宣告兩個變數 * head
及 ** tail
利用 cmp 比較 a b 大小,若是小於或相等則選擇 a 為下一個 node,用來確保 sort stability
將 a 放入 tail 指向的地址,也就是 head 的地址
將 tail 指向的地址改為 &a->next
將 a 指到 a->next
接著重複此過程,不斷地將 a or b 串接起來
直到 a or b 為 NULL,便將非 NULL 的 list 串到 *tail 指到的地址
在操作之後
cmp(priv, a, b) > 0
,則將上列操作 a, b 對調即可和 merge 的差異為,merge_final 會將所有的 list->prev 串接至正確的 node
將 tail->next 串接至 b 後,再把後續的 b->prev 串接完成
需要注意的地方為以下部分:
!++count
: 由於 count 為 u_int8,代表在 count 遞增至 255 前,傳入 unlikely
的數值皆為 0
!++count
為 1unlikely
是一個巨集,定義在 compiler.h
,定義內容如下:
# define unlikely(x) __builtin_expect(!!(x), 0)
!!(x)
用途是使任何變數在兩次 not 後,剩下 0 或 1 兩種可能unlikely
的回傳值為實際上 !!(!++count)
的結果unlikely
會影響編譯器的 branch prediction,表示在該 if 條件下的 code,較不常被執行,進而將此段 code 擺到較為後方的位置至於為何需要比較相同的數值呢 ? 根據 merge_final
內的註解 :
/*
* If the merge is highly unbalanced (e.g. the input is
* already sorted), this loop may run many iterations.
* Continue callbacks to the client even though no
* element comparison is needed, so the client's cmp()
* routine can invoke cond_resched() periodically.
*/
cmp(priv, b, b)
是為了定期喚醒 cond_resched
,使得 cpu 的資源能被短暫釋放
但為何呼叫 cmp
能連帶觸發 cond_resched
,目前還沒搞懂
list_sort
首先來看 list_sort
的註解
* This mergesort is as eager as possible while always performing at least 2:1 balanced merges.
得知此 mergesort 的實作方式,是希望被 merge 的 sublists size 比例至少為 2 : 1 (較大的為較小的兩倍以上)
* Given two pending sublists of size 2^k, they are merged to a size-2^(k+1) list as soon as we have 2^k following elements.
* Thus, it will avoid cache thrashing as long as 32^k elements can fit into the cache. Not quite as good as a fully-eager bottom-up mergesort, but it does use 0.2n fewer comparisons, so is faster in the common case that everything fits into L1.
常見的 merge sort 會在遇到兩個大小為 的 list 時將其 merge,但 linux 的 merge sort 只有在兩個大小為 的 list 位於 pending 且再遇到一個 的 list 時,才會將 pending 中的兩個 的 list merge。若是此 的 list 能放入 cache,則可避免 cache thrashing 發生
* The merging is controlled by "count", the number of elements in the pending lists. This is beautifully simple code, but rather subtle.
* Each time we increment "count", we set one bit (bit k) and clear bits k-1 .. 0. Each time this happens (except the very first time for each bit, when count increments to 2^k), we merge two lists of size 2^k into one list of size 2^(k+1).
* This merge happens exactly when the count reaches an odd multiple of 2^k, which is when we have 2^k elements pending in smaller lists, so it's safe to merge away two lists of size 2^k.
* After this happens twice, we have created two lists of size 2^(k+1), which will be merged into a list of size 2^(k+2) before we create a third list of size 2^(k+1), so there are never more than two pending.
* The number of pending lists of size 2^k is determined by the state of bit k of "count" plus two extra pieces of information:
- The state of bit k-1 (when k == 0, consider bit -1 always set), and Whether the higher-order bits are zero or non-zero (i.e.is count >= 2^(k+1)).
裡面提到 count 是控制放入 pending 的 list 數量,會根據當前 count 而有不同效果,共有六種狀態 :
* There are six states we distinguish. "x" represents some arbitrary
* bits, and "y" represents some arbitrary non-zero bits:* 0: 00x: 0 pending of size 2^k; x pending of sizes < 2^k
* 1: 01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
* 2: x10x: 0 pending of size 2^k; 2^k + x pending of sizes < 2^k
* 3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
* 4: y00x: 1 pending of size 2^k; 2^k + x pending of sizes < 2^k
* 5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
* (merge and loop back to state 2)
接著來看實際程式碼
for (bits = count; bits & 1; bits >>= 1)
likely(bits)
和 merge_final
中提到的 unlikely
相似,都能藉由此巨集幫助編譯器最佳化Risheng1128
所作的研讀 Linux 核心原始程式碼 list_sort建立完 pending 後,此時 pending 內是由小到大排列完成的 sublists,剩下就是把 pending 內的所有 sublists 進行合併
最後將 list 內的 prev links 串起,便完成此 sort
list_sort
引入將 list_sort.c
及 list_sort.h
放入專案中,並將遺失定義的巨集補進 list_sort.h
內
新增 cmd 的 option : list_sort
用來決定要使用 linux 的 sort 或 自己實作的 sort
先設計一個自動測試檔 trace-18-compare.cmd
使用大小為 的資料進行排序
結果如下:
可以發現 my sort 的 delta time 約為 linux sort 的 2.1 倍
接著嘗試利用 perf 進行 mergesort 效能分析
我將兩種 sort 各跑 5 次,perf 會將結果作平均
linux sort
my sort
list_sort() |
q_sort() |
|
---|---|---|
cache-misses | 143,081,730 | 132,646,439 |
cache-references | 240,861,121 | 245,083,976 |
instructions | 3,262,443,609 | 3,263,356,237 |
cycles | 5,017,161,434 | 7,717,237,980 |
我發現 cache-misses, cache-references 及 instruction,兩者的表現接近,但在比較 cycles 時,my sort 比起多了 27 億個 cycles,差異不小
看懂 Fisher-Yates shuffle,想法如下:
將 shuffle 加入 console_int()
內
便能利用 shuffle 命令將 queue 隨機洗混,操作如下: