contributed by < MathewSu-001 >
參考Optimized QuickSort — C Implementation (Non-Recursive)以及測驗題的程式碼
上述可知以 pivot 為分隔點,比 pivot 小的值放到鏈結串列 left ;大的值放到鏈結串列 right。
分類完後,以 left -> pivot -> right 分別將鏈結開頭跟尾端存入陣列 begin 跟 end 中,因為是用堆疊 stack 的方式,會一直確保取出最大值,串接到 result 裡。
我思考後覺得可以改進的地方有兩個:
max_length
大小首先在看完程式碼後,因為 begin 跟 end 都是取鏈結串列的頭尾,所以總長度應該不超過 list 大小,所以更改程式碼如下:
參考 Linux 效能分析工具: Perf,使用perf
觀察兩者的 instruction 、 cpu cycle 、 cache miss/references。
介紹上述四種性能計數器統計信息及其含義:
before | after | |
---|---|---|
cache-misses | 2,375,967 | 957,352 |
cache-references | 21,873,934 | 21,795,217 |
instructions | 843,644,727 | 820,959,299 |
cycles | 778,685,714 | 692,183,813 |
elapsed time(s) | 0.034892 ± 0.000432 | 0.03038 ± 0.00105 |
那從數據表中,可以知道有最大的變化是 cache-misses 。參考現代處理器設計: Cache 原理和實際影響可以知道原因是出在Capacity misses(空間性失誤):
如果有一個 64KB 的陣列需要重複存取,因為陣列大小遠大於 cache 大小,所以沒辦法全部放入 cache 。第一次存取陣列發生的 cache misses 全都是 compulsory misses 。但之後存取陣列發生的 cache misses 全都是 capacity misses ,這時的 cache 已存滿,容量不足以儲存全部的資料。
決定 pivot 從哪裡取得也是很重要的因素。考慮一個已經排序好的數列,在每次選擇的 pivot 都會是最小或最大值,這種情況下,快速排序的效能將退化為最壞的時間複雜度,即 。
接下來我就遇到 perf top 出現問題:
根據 Linux 效能分析工具: Perf裡所提到,推測原因應該是我重開機後有更新到 kernel 。所以現在我來紀錄修復過程。
在編譯過程中,安裝相依的套件出現的錯誤:
可以根據Minimal requirements to compile the Kernel去看說電腦哪些相依套件沒有安裝到,另外比較大問題是是缺少 libtraceevent
函式庫
安裝完後編譯就成功了~
最後將編譯好後的 perf 掛接到 /usr/bin/perf
裡就可以重新運作了
merge
function在 merge 函式裡,會先初始化宣告head
,以及間接指標tail
指向head
的位址。
通過 cmp 函式比較兩個鏈表節點的值。因為是用間接指標,所以 tail = a 這個指令會讓head
去指向 a1 ,然後將tail
指向 a->next 的位址,a 指向 a 的下一個節點。
再利用 cmp 函式比較兩個鏈表節點的值。因為tail
為間接指標,所以會更動 a1->next 指向 b1,這樣就會 a1 與 b1 相接 ,然後將tail
指向 b1->next 的位址,b 指向 b 的下一個節點。
如此一來降低記憶體開銷 : 只會對 2 個 runs 中,其範圍重疊的部份進行合併,額外空間只需要配置二個要合併的部份中跟較小的那一部份元素數量的記憶體。
find_run
functionfind_run
(某些程式碼已省略)find_run
這個函式的用途就是去尋找連續的遞減或遞增數列,讓該數列成為一個 run。這邊以圖解的方式來說明遞減數列,遞增數列原裡差不多就不多贅述。
在 do while 迴圈裡就是將 list 指向的節點指派到 prev 鏈結串列,然後重新比較下兩個是否有符合遞減的條件。
當 list 與 next 的條件不再符合時,就將 list 和 prev 掛接在一起完成 reverse。並且宣告一個 result 的 head 為該 run 的開端;next 為 run 的尾端的下一個節點(方便在找下一個 run)。
接著,timsort 將檢視已找到的 runs 中,是否有存在可以合併的 runs,這也是 timsort 一個顯著特點,它會在分割過程中進行合併,以維持合併的平衡。
將 timsort 合併進 lob0-c 當中,運行 perf 後的結果如下
首先比較運算時間(四捨五入到小數點第三位)(單位 : s)
q_sort | timsort | |
---|---|---|
第一次 | 0.884 | 0.846 |
第二次 | 0.989 | 0.985 |
第三次 | 0.926 | 1.072 |
第四次 | 0.891 | 0.953 |
第五次 | 0.892 | 0.863 |
平均值 | 0.916 | 0.878 |
使用perf 觀察兩者的 instruction 、 cpu cycle 、 cache miss/references
q_sort | q_listsort | |
---|---|---|
cache-misses | 54,910,492 | 48,025,172 |
cache-references | 89,689,860 | 70,943,655 |
instructions | 4,914,653,177 | 4,665,065,530 |
cycles | 6,515,988,823 | 6,657,494,108 |
elapsed time(s) | 1.3629 ± 0.0272 | 1.4029 ± 0.0476 |
以 105. Construct Binary Tree from Preorder and Inorder Traversal的題目作為例子,首先會遍歷 inorder 的所有值,並以Linux 核心的 hash table 實作篇中的 Division method 作為找尋 key 的方法。
僅將部分圖畫出:
由前序可知哪個節點在上面 (越前面的越上面)、而由中序可知哪個節點靠左(越前面的越左邊),於是可得知前序的第一個元素一定是 root 的值,且該元素對應到中序後,左邊的值就在左邊,右邊的值就在右邊。
所以dfs
函式所做的事就是找 preorder 的開端值,是位在 inorder 的哪個位置上,左邊的陣列與右邊的陣列就分別不斷遞迴dfs
函式,直到二原樹畫完。
find
函式所做的事便是要找到位在 inorder 的哪個位置上,因此會利用hlist_for_each
,去遍歷同一個 hash_key 找到相同值,回傳 on->idx。
使用 Multiplication Method ,且設定 A = golden ratio 時, 此雜湊函數稱為 Fibonacci hashing,且 key 經此函數轉換得到的 index 相當分散,減少碰撞次數。
首先要先了解LRUCache
的結構是長怎樣。裡面包含:
根據146. LRU Cache,push
的功能為:
Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
所以在程式碼分成了兩個區塊:
透過hlist_for_each
來遍歷 hhead[hash] ,若 key 本來就存在就更新值,並且將該 LRUNode->link 移到 dhead 佇列開端。
如果 capacity 滿了,提取出 dhead 佇列尾端(最近最少使用的 key)重新放到佇列尾端,修改 key 、 value為新的組合,hhead[hash]也是同樣步驟。
根據146. LRU Cache,get
的功能為:
Return the value of the key if the key exists, otherwise return -1.
所以程式碼的話就是用hlist_for_each
來遍歷 hhead[hash],將該 LRUNode->link 移到 dhead 佇列開端,且 return LRUNode->value。
在解讀主要函式find_nth_bit
時,對於small_const_nbits
的用途抱有很大的疑惑。
從定義上來看,是必須要滿足:
那麼__builtin_constant_p
的用途是甚麼呢?根據6.61 Other Built-in Functions Provided by GCC
You can use the built-in function to determine if the expression is known to be constant at compile time and hence that GCC can perform constant-folding on expressions involving that value. The argument of the function is the expression to test. The expression is not evaluated, side-effects are discarded. The function returns the integer 1 if the argument is known to be a compile-time constant and 0 if it is not known to be a compile-time constant. Any expression that has side-effects makes the function return 0. A return of 0 does not indicate that the expression is not a constant, but merely that GCC cannot prove it is a constant within the constraints of the active set of optimization options.
__builtin_constant_p
是 GCC 提供的內建函式,用於在編譯時判斷表達式是否是一個常數。如果參數被證明是編譯時常數,函式返回整數 1,如果不能確定是編譯時常數,則返回 0。
當 BITS_PER_LONG
為 64(64-bit),輸出一個可以用來取回最後 nbits
的 bit mask。
假設 nbits
為 3,BITS_PER_LONG
為 16:
-(nbits) = (-3) = 0xFD
-(nbits) & (BITS_PER_LONG - 1) = 0xFD & (16-1) = 0xFD & 0xF = 0xD
(~0UL >> (-(nbits) & (BITS_PER_LONG - 1))) = (0xFF >> (0xD)) = (0xFFFF >> 13) = 0x7
也就是可以取回最後 3 個 bit 的 mask