contributed by <jychen0611
>
jimmy01240397
:monkey: commit e674e7b
Add multiple sets of function macros
[What?]
採納 jimmy01240397
的建議將同類型的函式寫成巨集
[Why?]
原程式碼存在重複性極高的函式,可用巨集整合之
[How?]
以下依函式類型兩兩說明
(1) q_insert_head 和 q_insert_tail
使用巨集 q_insert_base
利用 to
判別是 q_insert_head 還是 q_insert_tail 使用,若傳入 head ,則表 q_insert_head ,需使用 list_add
。反之則使用 list_add_tail
。
(2) q_remove_head 和 q_remove_tail
使用巨集 q_remove_base
利用 from
判別是 q_remove_head 還是 q_remove_tail 使用,若傳入 first ,則表 q_remove_head ,需使用 list_first_entry
。反之則使用 list_last_entry
。
(3) q_ascend 和 q_descend
使用巨集 q_scend_base
利用 dir
判別是 q_ascend 還是 q_descend 使用,若傳入 ascend ,則表 q_ascend ,需使用 strcmp(cur, t->value) >= 0
。反之則使用 strcmp(cur, t->value) <= 0
。
:monkey: commit b003cdc
Merge pull request #1 from chumytest/master
[What?]
接受 jimmy01240397
的 pull request
[Why?]
原程式碼不夠精簡,且有多餘判斷式
[How?]
以下依不同函式更動逐一說明
(1) q_delete_mid
在此無須檢查節點數量是否只有一個。若只有一個節點,則 slow 會指到這個節點,且不會進入 while 迴圈,最終會刪除 slow 所指的這個唯一的節點。
(2) q_delete_dup
新增變數 nowdel
表當前是否需刪除該節點,以簡化判斷式敘述。
使用 del
紀錄 nowdel
的先前狀態,以刪除最後一個重複節點。
(3) merge (用於 q_sort)
以 ((descend * 2) - 1) * strcmp(l->value, r->value) > 0
判斷要優先將 left 的 element 放入佇列尾端,還是將 right 的 element 放入佇列尾端。
((descend * 2) - 1)
此處理方式可使 descend 值從原本的 0/1 表示轉成 -1/+1 表示。
因此
((descend * 2) - 1)
為 +1 表 descend((descend * 2) - 1)
為 -1 表 ascendeg. 若 strcmp(l->value, r->value) > 0
(l>r) 且 ((descend * 2) - 1)
為 +1 (descend),則優先放入 left 的 element。
最後是微幅調整,將!list_empty(left)
代換成 list_empty(left)
,list_splice_tail(left, head)
也隨之替換成 list_splice_tail(right, head)
(4) q_merge
新增變數 tmphead
作為 head->next
的替代放入 list_for_each
的第二個輸入,待進入迴圈後,再將 tmphead
改為 head
。
其用意為使 node 初始化為 head->next->next
,這樣便能跳過第一個佇列,不必額外去檢查當前是否為第一個佇列。
刪除 if (list_empty(another_q->q)) continue;
不會影響程式運作,不需要做此額外判斷。
然而我在修改 commit message 時遭遇以下問題
新增的 nowdel
被系統指出範圍可以縮減,且初始化 nowdel
為 false 並無實質意義
於是我做了以下修改
:monkey: commit 7d17d45
Correct the variable
[What?]
修正變數 nowdel
的宣告方式
[Why?]
nowdel
被系統指出範圍可以縮減,且初始化 nowdel
為 false 並無實質意義
[How?]
把 nowdel
宣告在 list_for_each_safe
迴圈內
經修改後,程式可正常 push 上去,但唯獨 pull request 的 commit message 無法做修改,仍會有上述問題。 待解
用字務必精準,既然說他人不好,那就提供好的做法給同學看。 :notes: jserv
:monkey: commit 0db6def
Improve the efficiency of q_merge
[What?]
撰寫 merge_with_first_q
函式,使其他佇列能和第一個佇列兩兩合併,以改善 q_merge 效能。
[Why?]
比起直接將所有已經排序完成的鏈結串列接上再重新排序,有效能更好的解決方式。
[How?]
在 merge_with_first_q
函式中,使用佇列標頭變數 tmp_head
存放已排序的節點,其排序過程似 merge
函式,最終將排序好的節點接回第一個佇列。
Kuanch
lib/list_sort.c
的效能測量,這部分實作不困難,使用 perf
及準備小規模獨立的測試即可,可參考 q_sort 與 list_sort 效能比較,亦可透過 dudect/cpucycles.h
僅計算 cycle 數依據上述指示著手修改 queue.[ch] 和連帶的檔案,測試後用 Git 管理各項修改,要能滿足 $ make test 自動評分系統的所有項目。
- :warning: 在提交程式變更前,務必詳閱 如何寫好 Git Commit Message
- 詳閱「你所不知道的 C 語言: linked list 和非連續記憶體」並應用裡頭提及的手法,例如 pointer to pointer (指向某個指標的指標,或說 indirect pointer),讓程式碼更精簡且有效
- 參閱「2023 年 Linux 核心設計/實作課程第一次作業檢討」,留意各式細節,唯有重視小處並步步為營,方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心
q_new
:monkey: commit 0bf802e
Implement q_new
[What?] 初始化一個雙向環狀佇列 [Why?] 此功能可初始化一個標頭指標 h 以串接之後新增的節點 [How?] 宣告一個 struct list_head *h 並使用 malloc 函式分配記憶體給指標 h ,此指標可用來串街接之後新增的節點 使用巨集 INIT_LIST_HEAD 初始化指標 h
根據 C99 standard 的 malloc 描述如下:
Synopsis
Description
The malloc function allocates space for an object whose size is specified by size and whose value is indeterminate.Returns
The malloc function returns either a null pointer or a pointer to the allocated space.
:monkey: commit bf419a8
Check null pointer
[What?] 新增檢查 h 是否有成功被分配到記憶體空間 [Why?] malloc 之回傳可能為 null pointer [How?] 在呼叫 INIT_LIST_HEAD 前先檢查 h 是否為 NULL
可知 malloc 之回傳可能為 null pointer
故在呼叫 INIT_LIST_HEAD
前須先檢查是否為 NULL
q_free
:monkey: commit c3ed425
Implement q_free
[What?] 實作佇列刪除功能,並回收分配給該佇列的空間 [Why?] 使系統之後能用一個函式就刪除佇列 [How?] 遍歷佇列中所有節點釋放該空間,最後再釋放佇列標頭指標所佔空間
根據 C99 standard 的 free 描述如下:
Synopsis
Description
The free function causes the space pointed to by ptr to be deallocated, that is, made available for further allocation. If ptr is a null pointer, no action occurs. Otherwise, if the argument does not match a pointer earlier returned by the calloc, malloc, or realloc function, or if the space has been deallocated by a call to free or realloc, the behavior is undefined.Returns
The free function returns no value.
使用 list_for_each_entry_safe
巨集以逐一釋放 entry 空間
其中,list_entry
表 container_of
參考自 Linux 核心原始程式碼巨集: container_of 巨集 container_of 在 offsetof 的基礎上,擴充為「給定成員的位址、struct 的型態,及成員的名稱,傳回此 struct 的位址」
:monkey: commit c5ff2aa
Replace free() with q_release_element() on q_free
[What?] 釋放節點中 value 空間 [Why?] 原程式並無釋放節點中的字元指標 value 所佔用的空間,因此做以下修正 [How?] 以 q_release_element() 取代 free()
原程式並無釋放節點中的字元指標 value
所佔用的空間,因此做以下修正
q_insert_head
:monkey: commit a6d38b5
Implement q_insert_head, q_insert_tail
[What?]
實作新增節點到佇列的頭或尾之功能
[Why?]
使佇列能新增帶有指定字串的節點到頭尾
[How?]
先確認佇列是否存在,再嘗試分配空間給新的節點 tmp ,若分配成功則將指定字串 s 放入節點,最後利用list_add
和list_add_tail
將節點加入佇列
根據 C99 standard 的 strcpy 描述如下:
Synopsis
Description
The strcpy function copies the string pointed to by s2 (including the terminating null character) into the array pointed to by s1. If copying takes place between objects that overlap, the behavior is undefined.Returns
The strcpy function returns the value of s1.
使用 strcpy 後在 commit 時遭遇以下問題 :
根據訊息提供的 Common vulnerabilities guide for C programmers
The strcpy built-in function does not check buffer lengths and may very well overwrite memory zone contiguous to the intended destination. In fact, the whole family of functions is similarly vulnerable: strcpy, strcat and strcmp.
strcpy
strcat
strcmp
由於這些函式不會檢查緩衝區的長度,皆有可能發生相鄰記憶體區域覆寫的情形
於是改用 strncpy
來實現,更改完就能 commit 了
根據 C99 standard 的 strncpy 描述如下:
Synopsis
Description
The strncpy function copies not more than n characters (characters that follow a null character are not copied) from the array pointed to by s2 to the array pointed to by s1. If copying takes place between objects that overlap, the behavior is undefined. If the array pointed to by s2 is a string that is shorter than n characters, null characters are appended to the copy in the array pointed to by s1, until n characters in all have been written.Returns
The strncpy function returns the value of s1.
:monkey: commit 15790b1
Add allocation for new element's value
[What?] 為新增節點的value配置空間 [Why?] 由於節點中的字元指標 value 也需配置空間,才能存放字串 s ,故新增此功能 [How?] 配置 strlen(s) + 1 的空間給節點的 value,並檢查是否配置成功,若失敗則是放節點空間,並回傳 false
參考 millaker 為新增節點的value配置空間
q_insert_tail
:monkey: commit a6d38b5
Implement q_insert_head, q_insert_tail
[What?]
實作新增節點到佇列的頭或尾之功能
[Why?]
使佇列能新增帶有指定字串的節點到頭尾
[How?]
先確認佇列是否存在,再嘗試分配空間給新的節點 tmp ,若分配成功則將指定字串 s 放入節點,最後利用list_add
和list_add_tail
將節點加入佇列
q_remove_head
:monkey: commit ef95866
Implement q_remove_head, q_remove_tail
[What?]
實作從佇列頭或尾移除節點並回傳的函式
[Why?]
使節點可以從佇列頭尾移除
[How?]
先檢查佇列是否存在或是否為空,接著利用list_first_entry
或 list_last_entry
取得佇列頭尾的節點,並將節點中的字串複製給 sp,最後利用list_del
將節點從佇列移除,回傳節點
使用list_empty
檢查佇列是否為空
使用list_first_entry
取得佇列第一個節點
strncpy
不會複製最後一個字元\0
使用list_del
將該節點從佇列中移除
改成巨集後發現有以下問題
:monkey: commit 0656c4c
Modify the macro q_remove_base
[What?]新增 if (tmp && sp)
判別式到巨集 q_remove_base
[Why?]原先方式會存取到 NULL
[How?]在使用 tmp
和 sp
前先檢查是否為空
q_remove_tail
:monkey: commit ef95866
Implement q_remove_head, q_remove_tail
[What?]
實作從佇列頭或尾移除節點並回傳的函式
[Why?]
使節點可以從佇列頭尾移除
[How?]
先檢查佇列是否存在或是否為空,接著利用list_first_entry
或 list_last_entry
取得佇列頭尾的節點,並將節點中的字串複製給 sp,最後利用list_del
將節點從佇列移除,回傳節點
使用list_last_entry
取得佇列最後一個節點
q_size
:monkey: commit 42858f3
Implement function : q_size
[What?] 實作取得佇列大小的函式 [Why?] 此函數可取得佇列大小 [How?] 使用了巨集 list_for_each 走訪所有節點,並利用 len 變數紀錄節點個數
使用了巨集 list_for_each
走訪所有節點
HackMD 不是讓你張貼完整程式碼的地方,GitHub 才是!因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示),可附上對應 GitHub commit 的超連結,列出程式碼是為了「檢討」和「便於他人參與討論」,不是用來「假裝自己有付出」
q_delete_mid
:monkey: commit 093aebb
Implement q_delete_mid (first approach)
[What?]
實作刪除佇列中間節點之函式
[Why?]
使佇列能從中間移除節點
[How?]
第一個版本嘗試最簡單的方式,利用 q_size
取得佇列中間的位置,將指標移至中間刪除該節點
先嘗試最簡單的方式,利用q_size
取得佇列中間的位置,將指標移至中間刪除該節點
:monkey: commit 2808dbe
Implement approach 2 of the q_delete_mid
[What?] 提出另一個版本的方法 [Why?] 原方法需倚賴 q_size 函式來取得佇列大小,需要花一次遍歷佇列的時間,再走到佇列中間刪除節點。而新方法只需遍歷佇列一次即可。 [How?] 利用快慢指針的搭配找出中間節點 fast一次移動兩步,slow一次移動一步 當 fast 走訪完整個佇列後,slow會剛好落在佇列中間的位置
方法二利用快慢指針的搭配找出中間節點
fast
一次移動兩步,slow
一次移動一步
當 fast
走訪完整個佇列後,slow
會剛好落在佇列中間的位置
q_delete_dup
C99 Standard
Synopsis
Description
The strcmp function compares the string pointed to by s1 to the string pointed to by s2.Returns
The strcmp function returns an integer greater than, equal to, or less than zero, accordingly as the string pointed to by s1 is greater than, equal to, or less than the string pointed to by s2.
:monkey: commit fc79a87
Implement q_delete_dup
[What?]
實作刪除佇列中連續相同節點之函式
[Why?]
使佇列可移除所有連續相同的節點
[How?]
利用 list_for_each_safe
走訪每個節點,發現有重複的節點便刪除之
:monkey: commit 036b0e1
Add flag on q_delete_dup
[What?]
新增旗標del_flag
以刪除所有重複相鄰節點
[Why?]
原先我誤會題目要求,以為刪除重複相鄰節點到剩下一個即可。而題目真正的要求是要刪除所有重複相鄰節點,故作此修改
[How?]
走訪佇列節點的過程中,若發現有重複相鄰節點,則刪除其中一個,並將旗標 del_flag
設為true,以利刪除最後一個多餘節點
利用 list_for_each_safe
走訪每個節點,發現有重複的節點便刪除之
:monkey: commit c9cc2dc
Revise the q_delete_dup function
[What?]
修改 q_delete_dup 函式,解決對 null pointer 取值之錯誤
[Why?]
執行 list_for_each_entry_safe
可以走訪整個 list 但是需要注意在走訪完時 n 會指向 head,且 head 是無法透過 container_of
找到節點的,因為它沒有嵌入到結構體中,這時如果對 n 取 contain_of
會拿到 NULL 如果再做取值 n->value 會報錯 成為無效的記憶體操作。
[How?]
新增 l->next != head 條件,避免對 null pointer 取值
參考 chiangkd 新增 l->next != head
條件,避免對 null pointer 取值
執行 list_for_each_entry_safe 可以走訪整個 list 但是需要注意在走訪完時 n 會指向 head,且 head 是無法透過 container_of 找到節點的,因為它沒有嵌入到結構體中,這時如果對 n 取 contain_of 會拿到 NULL 如果再做取值 n->value 會報錯 成為無效的記憶體操作。
TODO: 撰寫為更精簡的程式碼
:monkey: commit 5ce9dc5
Revise the q_delete_dup function
[What?] 移除 q_delete_dup 中多餘程式碼 [Why?] 後來發現先前寫法在跑某些測資時會存取到 NULL 原因在於下面這段程式碼完全是多餘的
遭遇到重複節點只需多刪除最後一個節點即可,前面不管重複幾次都滿足條件 !strcmp(nl->value, nr->value) 。 進行多餘的判斷且沒使用 l->next != head 確保程式不會使用到空指標是危險的行為! [How?] 刪除上述多餘程式碼,使功能正常運作
access 的翻譯是「存取」,而非「拜訪」(visit)
後來發現上述寫法在跑某些測資時會存取到 NULL
。
原因在於下面這段程式碼完全是多餘的,遭遇到重複節點只需多刪除最後一個節點即可,前面不管重複幾次都滿足條件 !strcmp(nl->value, nr->value)
。
進行多餘的判斷且沒使用 l->next != head
確保程式不會使用到空指標是危險的行為!
更改就能穩定通過測試項目 06 了
此處是「測試項目」(item),而非「資料」,查閱辭典以理解二者的差異。
q_swap
:monkey: commit 6ccf009
Implement q_swap
[What?] 實作交換佇列中兩兩相鄰節點之功能 [Why?] 使佇列能兩兩交換相鄰節點之位置 [How?] 利用list_for_each_safe走訪佇列,每兩步進行一次左右節點交換
:monkey: commit 8003196
Consider q_size is odd
[What?] 考量節點個數是奇數時,第一個節點會和最後一個節點交換的情形 [Why?] 若節點個數是奇數,則原程式碼會讓第一個節點和最後一個節點交換 [How?] 在迴圈中加入 if (r == head) 之判斷,即時中止迴圈
:monkey: commit f2bea72
Add counter on q_swap
[What?] 加入counter紀錄當前迴圈走了幾步,偶次步才進行節點交換 [Why?] 因為題目要求第1個節點和第2個節點交換,第3和第4交換…以此類推 [How?] 迴圈中加入判斷式 if (counter % 2 == 0) 若滿足才進行交換
利用list_for_each_safe
走訪佇列,每兩步進行一次左右節點交換
並參考 vax-r,考量節點個數是奇數時,head 也會被交換的情形
:monkey: commit 5c6caea
Revise the q_swap function
[What?]
寫個簡單的 for 迴圈取代 list_for_each_safe
[Why?]
先前的寫法是錯的,原因是交換後 l 會指向右邊的節點,r 會指向左邊的節點
[How?]
以 for 迴圈將 l 指標推進,並將 l 和 r 交換位置。交換完後 l 會在右邊,因此 l 前進後可直接進行下一次的交換。
無須使用 if (counter % 2 == 0) 判斷式
上面的寫法是錯的,原因是交換後 l
會指向右邊的節點,r
會指向左邊的節點
於是我決定寫個簡單的 for 迴圈取代 list_for_each_safe
:monkey: commit 5d87af3
Implement second version of q_swap
[What?] 提出第二個方法,並盡量使用 List API [Why?] 善用 List API,可精簡程式碼,提昇程式可讀性 [How?] 利用list_del和list_add_tail 將佇列前兩個節點移出佇列,並以相反的順序放回佇列尾端。
為了善用 List API,我寫了第二個版本的 q_swap
利用list_del
和list_add_tail
將佇列前兩個節點移出佇列,並以相反的順序放回佇列尾端。
q_reverse
:monkey: commit ce7affb
Implement q_reverse
[What?] 實作將佇列節點全部調換順序的函式 [Why?] 使佇列能更改方向 [How?] 依序將佇列所有 link 指向反方向。 並發現指標 l 一旦指到最後一個節點程式便會跳出迴圈,應當再補上一次迴圈內的動作
依序將佇列所有 link 指向反方向,並發現指標l
一旦指到最後一個節點程式便會跳出迴圈,應當再補上一次迴圈內的動作
TODO: 善用 List API
q_reverseK
:monkey: commit 5b9c697
Implement q_reverseK
[What?] 實作將佇列中每 k 個節點調換順序之函式 [Why?] 使佇列能以每 k 個節點來調換順序 [How?] 利用 counter 判別當前指標l r是否在 group 的交界處 若是,則將左方 group 反向串接到右方 group 否則執行單純的指標反轉
利用 counter
判別當前指標l
r
是否在 group 的交界處
若是,則將左方 group 反向串接到右方 group
否則執行單純的指標反轉
上述寫法是錯的
:monkey: commit 13b8552
Revise the q_reverseK function
[What?]
修正 q_reverseK 函式,使功能正常。
使用 list_cut_position
, list_splice_init
完成實作,修正程式的功能,同時也精簡化程式碼
[Why?]
原先寫法有誤
[How?]
首先利用 counter 判斷當前是否需要調換前面 k 個節點順序。
接著利用list_cut_position
分出前面 k 個節點。
使用 q_reverse 函式調換 k 個節點的順序。
最後再用 list_splice_init
將 k 個節點放回佇列
於是參考 rkhuncle 使用 list_cut_position
, list_splice_init
完成實作
下圖是我對 list_cut_position
的理解
leader
為head_from
的輸入,本身並不會放入head_to list
中
使用 list_cut_position
後
q_sort
:monkey: commit b621694
Implement q_sort
[What?]
實作將佇列排序之函式,並盡量善用 List API 精簡化程式碼
[Why?]
此函式較為複雜,多使用 List API 可增加程式可讀性
[How?]
先宣告 list_head
:l
r
分別存放由list_cut_position
所分割的左右兩半佇列,接著再分別對左右兩半佇列進行 q_sort ,排序完畢後再將左右兩半進行 merge 。
以下是 merge 過程,先判別是否 descend
,再依序比較左右兩個佇列的第一個 node.value ,將較 大/小
的 node 塞入head
的尾端,當有任何佇列為空則結束迴圈,再將非空佇列加入 head
。
參考 Merge Sort – Data Structure and Algorithms Tutorials 和 linkedListSort 以了解 merge sort 的基本原理與實作方式。 subsidium 完善利用 List API,程式碼寫得精簡易讀,值得借鏡!
於是我花了30分鐘認真將 List API 的所有功能和實作細節看懂看熟,並開始撰寫 q_sort 程式碼。
先宣告 list_head
:l
r
分別存放由list_cut_position
所分割的左右兩半佇列,接著再分別對左右兩半佇列進行 q_sort ,排序完畢後再將左右兩半進行 merge 。
以下是 merge 過程,先判別是否 descend
,再依序比較左右兩個佇列的第一個 node.value ,將較 大/小
的 node 塞入head
的尾端,當有任何佇列為空則結束迴圈,再將非空佇列加入 head
。
你如何確保目前的測試已涵蓋排序演算法的最差狀況?
c 可以自己寫一個
next_permutation
,實作方式類似 leetcode 第 31 題, 過程中需要排序,考慮每次改變的區間可以發現,長度為 的區間有 個
以數字1~8為例(n=8),18765432 ⇨ 21345678 2
移動了 n-1 格,可知每當首位數字變動時,才會有數字恰移動 n-1 格,因此長度為 n-1 的變動區間有 n-1 個。
下圖是我的理解 可將變動區間的發生頻率定義成:
相當於
[1] 由 首項成立
[2] 假設 成立,則
q_ascend
:monkey: commit 7145a8b
Implement q_ascend and q_descend
[What?] 實作移除不滿足 ascend 或 descend 排列順序的節點之函式 [Why?] 依作業需求實作此功能 [How?] 由佇列尾端沿著 prev 走訪整個佇列,並利用 curMin 紀錄先前遇過的最小字串,若當前存取的節點字串大於等於curMin 則刪除該節點。
由佇列尾端沿著 prev
走訪整個佇列,並利用 curMin
紀錄先前遇過的最小字串,若當前存取的節點字串大於等於curMin
則刪除該節點。
q_descend
:monkey: commit 7145a8b
Implement q_ascend and q_descend
[What?] 實作移除不滿足 ascend 或 descend 排列順序的節點之函式 [Why?] 依作業需求實作此功能 [How?] 由佇列尾端沿著 prev 走訪整個佇列,並利用 curMax 紀錄先前遇過的最大字串,若當前拜訪的節點字串小於等於curMax 則刪除該節點。
由佇列尾端沿著 prev
走訪整個佇列,並利用 curMax
紀錄先前遇過的最大字串,若當前拜訪的節點字串小於等於curMax
則刪除該節點。
q_merge
:monkey: commit dc78edf
Implement q_merge
[What?] 實作將多個佇列合併並排序之函式 [Why?] 依作業需求實作此功能 [How?] 此函式中傳入的 head 指向此 chain 的第一個節點(queue_contex_t)。 head->next為 first_q,用來整合其他 queue 中的節點。 只需造訪整條 chain 上的節點,利用list_splice_init 將所有佇列串接到 first_q ,最後再用 q_sort 將整個佇列排序即可。
參考 25077667 畫的圖,可知每個queue_contex_t
裝有一個 queue 的 list_head
,這些queue_contex_t
串起來就形成一個 chain 。
在此函式中傳入的 head 指向此 chain 的第一個節點(queue_contex_t
)
head->next
為 first_q
,用來整合其他 queue 中的節點
只需造訪整條 chain 上的節點,利用list_splice_init
將所有佇列串接到 first_q
,最後再用 q_sort 將整個佇列排序即可。
目前 95 分,但奇怪的是我在本地端用 make test
無法通過測試項目 06,上傳到 git hub 卻通過了 ?
原來RAND
會產生隨機字串,程式在跑某些測資時會發生
Segmentation fault occurred. You dereferenced a NULL or invalid pointermake
的狀況
目前發現問題出在 q_delete_dup
!
已修正 :cactus: :cactus: :cactus:
詳見 q_delete_dup <approach 1.1>
commit 8f13b09
研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案,比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差,也該嘗試改進針對鏈結串列排序實作的效能
likely, unlikely
在list_sort.c 中,經常使用
之敘述,於是我參考 likely and unlikely macro
了解在 /include/linux/compiler.h
中存在巨集likely
unlikely
:cactus:__built_expect()
是 gcc 的內建 function,用來將 branch 的相關資訊提供給 compiler,告訴 compiler 設計者期望的比較結果,以便對程式碼改變分支順序來進行優化。
:cactus:!!(x)的用意是為了確保出來的值不是0就是1
根據c99 standard :
The controlling expression of an if statement shall have scalar type.
:cactus:使用likely
表示這段敘述(x)為 true 的機率比較大(比較常發生),告訴 compiler 將 x==ture 的對應執行程式碼接在判斷後面
:cactus: 使用unlikely
表示這段敘述(x)為 true 的機率比較小(不常發生),告訴 compiler 將 x==false 的對應執行程式碼接在判斷後面
cmp
另一個引起我注意的是 cmp 函式
void *priv
private data, opaque to list_sort(), passed to cmpstruct list_head *head
the list to sortlist_cmp_func_t cmp
the elements comparison function
The comparison function cmp must
return > 0
if a should sort after b ("a > b" if you want an ascending sort), andreturn <= 0
if a should sort before b or their original order should be preserved.- It is always called with the element that came first in the input in a, and list_sort is a stable sort, so it is not necessary to distinguish the a < b and a == b cases.
This is compatible with two styles of cmp function:
- The traditional style which returns <0 / =0 / >0, or
- Returning a boolean 0/1.
- The latter offers a chance to save a few cycles in the comparison (which is used by e.g. plug_ctx_cmp() in block/blk-mq.c).
由上敘述可知,當 cmp 回傳大於0的值表 a>b,a 應排在 b 的後面,因此這段存在 merge
中的程式可這樣解讀 :
:cactus: 若 a<=b
,則 a 先加入 tail。若 a 為空,則將整個 b 佇列接到 tail 後方
:cactus: 若 a>b
,則 b 先加入 tail。若 b 為空,則將整個 a 佇列接到 tail 後方
:monkey: commit ee5503b
Integrate the Linux kernel's lib/list_sort into lab0-c
[What?] 將 Linux 核心的 lib/list_sort 引入 lab0-c [Why?] 為了比較自己寫的 q_sort 和 Linux kernel 的 list_sort 之效能 [How?] 以下依修改檔案逐項說明
(1) 在 queue.c 中新增 list_sort 中三個函式 merge
merge_final
list_sort
,由於我先前已將某函式命名為 merge ,在此以 merge_list_sort
替代原 merge
函式。
函式內進行些微調整 :
priv
strcmp
取代 cmp
islikely
unlikely
(2) 參考 kart81604 修改 qtest.c
console_init
加入新命令 ADD_COMMAND(list_sort, "Sort queue in ascending order by list_sort", "");
do_list_sort
函式list_sort
函式Wolfgang Panny, Helmut Prodinger Algorithmica 14(4):340–354, October 1995
Wei-Mei Chen, Hsien-Kuei Hwang, Gen-Huey Chen Journal of Algorithms 30(2); Pages 423–448, February 1999
Mordecai J. Golin, Robert Sedgewick Information Processing Letters, 48(5):253–259, 10 December 1993
這篇作者提出了 queue-mergesort
的方法,並將其方法類比為 Huffman encoding
來證明其方法的 merge tree 的 external path length 為最小,推得其權重為最小,因此該 merge tree 為最佳,queue-mergesort
為最佳 mergesort 之一。
虛擬碼
示意圖
使用 perf 工具檢測效能
一開始perf_event_paranoid
權限被設為 4
command 是「命令」,而非「指令」(instruction)
可使用以下命令修改權限(-1 為權限全開)
分別對 sort / list_sort 執行相同命令,看跑完結果如何
sort
list_sort
整理成表格,可發現我寫的 q_sort 表現與 list_sort 相差不大,但這是不合理的實驗。
my sort | list sort | |
---|---|---|
task clock | 1,173.50 msec | 1,108.08 msec |
context switches | 37 | 43 |
page faults | 35,235 | 35,233 |
branches misses (core) | 19,228,387 | 19,209,980 |
branches misses (atom) | 62,259 | 2,627,089 |
參考 kart81604 將先隨機產生資料,並寫入 data.txt 中,如此兩次實驗即可共用相同輸入。
在 qtest
中新增 write
read
兩個指令,分別代表寫入 data.txt 和從中讀取資料。
:monkey: commit 2a8d392
Add the "write" and "read" commands to qtest
[what?]
在 qtest.c 中加入 do_write
do_read
兩個函式,分別代表將當前佇列節點資料寫入 data.txt 和從 data.txt 中讀取資料放入佇列
[why?]
由於實驗需以相同基準點衡量性能,故將隨機產生的資料寫入 data.txt,以利不同實驗對象讀取相同輸入
[how?]
在 qtest.c 中新增 do_write
函式,逐一將當前佇列節點資料寫進 data.txt。
新增 do_read
函式,從 data.txt 中讀取指定數量的字串,並插入當前佇列( buffer 大小設為 10)。
產生資料並寫檔
讀檔進行效能測試
q_sort
list_sort
表格
my sort | list sort | |
---|---|---|
task clock | 1,010.43 msec | 1,040.56 msec |
context switches | 37 | 38 |
page faults | 35,236 | 35,235 |
branches misses (core) | 18,212,741 | 18,072,038 |
branches misses (atom) | 2,721,285 | 1,106,266 |
random data
見方法一
descending data
my sort | list sort | |
---|---|---|
task clock | 394.22 msec | 232.44 msec |
context switches | 30 | 32 |
page faults | 35,235 | 35,236 |
branches misses (core) | 2,759,462 | 1,794,584 |
branches misses (atom) | 715,985 | <not counted> |
ascending data
my sort | list sort | |
---|---|---|
task clock | 370.47 msec | 268.25 msec |
context switches | 35 | 37 |
page faults | 35,236 | 35,239 |
branches misses (core) | 2,931,585 | 1,621,214 |
branches misses (atom) | 2,768,175 | 1,246,388 |
ascending, then 99999 random at the end
my sort | list sort | |
---|---|---|
task clock | 368.02 msec | 421.53 msec |
context switches | 31 | 38 |
page faults | 38,752 | 38,753 |
branches misses (core) | 5,185,188 | 3,837,989 |
branches misses (atom) | 47,711 | 62,375 |
ascending, then reverseK 7
my sort | list sort | |
---|---|---|
task clock | 65.35 msec | 64.16 msec |
context switches | 32 | 34 |
page faults | 3596 | 3596 |
branches misses (core) | 436,034 | 323,387 |
branches misses (atom) | 185,322 | 227,083 |
many duplicates
my sort | list sort | |
---|---|---|
task clock | 83.52 msec | 64.73 msec |
context switches | 30 | 33 |
page faults | 3,595 | 38,753 |
branches misses (core) | 880,806 | 937,747 |
branches misses (atom) | 113,522 | 137,047 |
all equal
my sort | list sort | |
---|---|---|
task clock | 49.54 msec | 60.67 msec |
context switches | 28 | 36 |
page faults | 3,595 | 3596 |
branches misses (core) | 166,327 | 57,640 |
branches misses (atom) | <not counted> | 62,937 |
翻閱統計學教科書,探討要什麼量體,才能代表樣本特徵?
中央極限定理
研讀論文〈Dude, is my code constant time?〉,解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析,達到驗證時間複雜度,需要解釋 Student's t-distribution 及程式實作的原理。
- 注意:現有實作存在若干致命缺陷,請討論並提出解決方案
- 在 oreparaz/dudect 的程式碼具備 percentile 的處理,但在 lab0-c 則無。
centered product
the two timing distributions are equql.
Welch's test
比較兩者樣本分佈差異
Kolmogorov-Smirnov
fixture.c
和 constant.c
test_const
測試常數時間的主要函式。會進行 10 次測試,每次測試會呼叫 ENOUGH_MEASURE / (N_MEASURES - DROP_SIZE * 2) + 1
次 doit
並將回傳值指派給變數 result
。
ENOUGH_MEASURE
= 10000,N_MEASURES
= 150,DROP_SIZE
= 20。result
為真,則跳出迴圈並回傳 True。doit
與 dudect_main
之比較doit (lab0-c) | dudect_main (dudect.h) |
---|---|
輸入僅有 mode ,其他參數以N_MEASURES 初始化 |
以結構體 dudect_ctx_t 做為輸入 |
執行 prepare_inputs ,初始化 input_data |
執行 prepare_inputs ,初始化 input_data |
回傳值 ret 由 measure 取得 |
執行 measure ,測量 exec_times |
執行 differentiate 和 update_statistics |
回傳值 ret 被指派為 DUDECT_NO_LEAKAGE_EVIDENCE_YET |
ret 和 report 的回傳值取 & 後再回傳 |
若為第一次執行 dudect_main ,則執行 prepare_percentiles 。否則執行update_statistics 並更新 ret 為 report 之回傳值 |
lab0-c
dudect.h
measure
之比較lab0-c | dudect.h |
---|---|
利用 mode 判別當前是否為 insert_head insert_tail remove_head remove_tail |
單一模式 |
differentiate
利用measure
取得的紀錄,計算執行時間
update_statistics
之比較lab0-c | dudect.h |
---|---|
若執行時間非負,直接執行 t 測試 | 若執行時間非負,直接執行 t 測試 |
無 | 對利用 percentiles 刪減極端值後的執行時間進行 t 測試 |
無 | 當測量值超過10000次則進行二次測試 |
report
之比較lab0-c | dudect.h |
---|---|
無輸入 | ctx 為輸入 |
prepare_percentiles
產生 percentiles
用以篩除極端值
lab0-c | dudect.h |
---|---|
doit | dudect_main |
prepare_inputs | prepare_inputs |
measure | measure |
無 | prepare_percentiles |
update_statistics | update_statistics |
report | report |
對函式輸入參數格式進行些微修改,由於原程式碼使用結構體 dudect_ctx_t
存放 exec_times 等資訊,而 lab0-c 中沒有,因此需將其作為參數輸入。
:monkey: commit e9eab10
Add the prepare_percentiles function to filter out extreme values
[What?]
針對檢測程式執行時間的程式碼進行修改,使測試程式近似原 dudect 程式
[Why?]
原測試程式無實作 prepare_percentiles
功能,可能導致極端值影響判斷
[How?]
將相關程式碼加入 fixture.c ,並對函式輸入參數格式進行些微修改。由於原程式碼使用結構體 dudect_ctx_t
存放 exec_times 等資訊,而 lab0-c 中沒有,因此需將其作為參數輸入。
修改完後發現可以通過測試項目 17
在 qtest 提供新的命令 shuffle,允許藉由 Fisher–Yates shuffle 演算法,對佇列中所有節點進行洗牌 (shuffle) 操作,需要以統計的原理來分析你的實作,探究洗牌的「亂度」
queue.c
新增 q_shuffle
函式根據 Fisher–Yates shuffle 演算法來實作洗牌 [1] 先用 q_size 取得 queue 的大小 len。 [2] 隨機從 0 ~ (len - 1) 中抽出一個數字 random,然後 old 將指向從前面數來第random 個節點,new 會指向最後一個未被抽到的節點,將 old 和 new 指向的節點的值交換,再將 len - 1。 [3] 隨著 len 大小變小,已經被抽到過,並交換值到 queue 後面的會愈來愈多,直到所有的節點都已經被抽到過,shuffle 就結束。
在 qtest.c 新增函式 q_shuffle,並新增 shuffle 命令以便呼叫 q_shuffle。
:monkey: commit 5816f1b
Add "shuffle" command
[What?] 在 qtest.c 新增函式 q_shuffle,並新增 shuffle 命令以便呼叫 q_shuffle。 [Why?] 依作業要求在 qtest 提供新的命令 shuffle ,以探究洗牌亂度。 [How?] 參考 Fisher–Yates shuffle 演算法,對佇列中所有節點進行洗牌操作。
發現我一開始的做法有誤,結果並不平均
原因出在我把 srand(time(NULL))
寫在 q_shuffle 函式中,導致srand(time(NULL))
會被重複呼叫。由於電腦指令跑很快,幾乎同時間的亂數會很多,使得重複相同亂數會很多。
當我把 srand(time(NULL))
移至主函式後,雖然分佈遍均勻了,卻又發現我寫的程式有死角,只有一半的情況會發生。
後來發現原因出在指派 new 指標時少走一次 next
,修改後問題已改善。
:monkey: commit 66d9a67
Revise "shuffle" command
[What?]
修正 q_shuffle 函式使其能正確運作,達到均勻亂數洗牌
[Why?]
原因出在我把 srand(time(NULL))
寫在 q_shuffle 函式中,導致srand(time(NULL))
會被重複呼叫。由於電腦指令跑很快,幾乎同時間的亂數會很多,使得重複相同亂數會很多。
當我把 srand(time(NULL))
移至主函式後,雖然分佈遍均勻了,卻又發現我寫的程式有死角,只有一半的情況會發生。
後來發現原因出在指派 new 指標時少走一次 next
,修改後問題已改善。
[How?]
修正 srand(time(NULL))
位置,修正 new 指派位置。
在 qtest 中執行 option entropy 1 並搭配 ih RAND 10 一類的命令,觀察亂數字串的分布,並運用「資訊與熵互補,資訊就是負熵」的觀念,設計一組新的命令或選項,得以在 qtest 切換不同的 PRNG 的實作 (可選定 Xorshift),搭配統計分析工具,比較亂數產生器 (如 Xorshift vs. 內建) 的品質
- 參見: 由大數法則理解訊息熵 (entropy) 的數學意義
- 參見: The Linux Pseudorandom Number Generator Revisited
確保 qtest 提供的 web 命令得以搭配上述佇列實作使用,目前一旦網頁伺服器啟動後,原本處理命令列操作的 linenoise 套件就無法使用,請提出改善機制
- 提示: 使用 select 系統呼叫
- 將 Linux 核心的 linux/list.h 標頭檔與
hlist
相關的程式碼抽出,成為hlist.h
,並確保後者可與 lab0-c 既有的list.h
並存,jserv/ttt 專案的zobrist.[ch]
會用到hlist.h
- 修改
qtest
程式,使其新增ttt
命令,其作用是執行與人類對弈的井字遊戲,並使用 Monte Carlo tree search (MCTS) 演算法,確保使用定點數來取代原本 jserv/ttt 的浮點數運算。- 擴充上述
ttt
命令,在qtest
引入新的option
(參照cmd>
命令提示的help
說明文字),允許使用者切換「人 vs.電腦」或「電腦 vs. 電腦」的對弈,注意後者應該採取 MCTS 以外的演算法 (也可納入你發展的演算法)。對弈的過程中,要在螢幕顯示當下的時間 (含秒數),並持續更新。- 針對
ttt
命令的「電腦 vs. 電腦」的對弈模式,參照〈並行程式設計:排程器原理〉,引入若干 coroutine (注意:不得使用 POSIX Thread,採取教材提到的實作方式),分別對應到 AI1, AI2 (具備玩井字遊戲的人工智慧程式,採取不同的演算法) 和鍵盤事件處理,意味著使用者可連續觀看多場「電腦 vs. 電腦」的對弈,當按下 Ctrl-P 時暫停或回復棋盤畫面更新 (但運算仍持續)、當按下 Ctrl-Q 時離開「電腦 vs. 電腦」的對弈,注意不該使用 (n)curses 函式庫。當離開「電腦 vs. 電腦」的對弈時,ttt
應顯示多場對弈的過程,亦即類似Moves: B2 -> C2 -> C3 -> D3 -> D4
的輸出,儘量重用現有的結構體和程式碼。 關於鍵盤事件和終端機畫面的處理機制,可參見 mazu-editor 原始程式碼和〈Build Your Own Text Editor〉。- 亂數產生器對於 MCTS 相當重要,可參照 Improving performance and efficiency of PRNG,嘗試引入其他快速的 PRNG 實作並比較 MCTS 實作獲得的效益。
- 在「電腦 vs. 電腦」的對弈模式,比照前述 load average 的計算方式,規範針對下棋 AI 的 load 機制,並運用定點數來統計不同 AI 實作機制對系統負載的使用率,整合到
qtest
輸出,開發過程中應有對應的數學分析和羅列實作考量因素。- 考慮到畫面更新不該混雜其他
printf
的訊息,可運用 GDB 進行遠端除錯。
:monkey: commit 979d357
Add header file of hash list
[What?] 新增 hlist.h 標頭檔 [Why?] 依作業要求整合 ttt 專案部份程式碼到 lab0-c [How?] 將 Linux 核心的 linux/list.h 標頭檔與 hlist 相關的程式碼抽出,成為 hlist.h,並確保後者可與 lab0-c 既有的 list.h 並存,jserv/ttt 專案的 zobrist.[ch] 會用到 hlist.h
:monkey: commit 2c249ec
Add Noughts and Crosses game command
[What?] 修改 qtest 程式,使其新增 ttt 命令 [Why?] 為了實現 AI 與人類對弈的井字遊戲 [How?] 將 jserv/ttt 專案的程式碼部分整合進 lab0-c,,使用 Monte Carlo tree search (MCTS) 演算法作為 AI 玩家,演算法仍使用浮點數運算。
UCT value
其中 代表利用,代表探索,其作用在於探詢可能的路徑,避免有更好的路徑沒被開發(可由式子中發現使用次數越少的節點 會越大,且當模擬次數越多時探索力度會稍微加大,但其加大幅度會遞減)。調整 值可改變探索與利用的比例。
four basic phases to MCTS:
Robert Love 在 Linux Kernel Development 一書論及浮點運算:
No (Easy) Use of Floating Point When using floating-point instructions kernel normally catches a trap and then initiates the transition from integer to floating point mode. Unlike user-space, the kernel does not have the luxury of seamless support for floating point because it cannot easily trap itself. Using a floating point inside the kernel requires manually saving and restoring the floating point registers. Except in the rare cases, no floating-point operations are in the kernel.
以下實驗使用 Ubuntu 24.04 LTS 進行開發
原 MCTS 程式碼在計算分數時會使用到浮點數運算,改以定點數表示之
定點數縮放因子
加法減法 : 可直接進行
乘法 : 結果要多除
除法 : 結果要多乘
自然對數
根據泰勒展開式可得
使用 frac = 1024 實作 (利於使用 bitwise)
其在 1<x<100 之表現 :
如圖可知 UCT value
的分佈多位於 0~3.5 之間,但 ln的輸入為 t (the total number of simulations that have occured after i moves)必為整數,因此不須特別考量 0<t<1 之情況。
平方根
當我把定點數 ln 和平方根運算寫入 ttt 遊戲中才發現,如果要追求極高的精度只會導致演算法下棋速率緩慢,該如何權衡精度與運算速率是一大問題。