2024q1 Homework2 (quiz1+2)

contributed by < MathewSu-001 >

第一周測驗1

程式碼理解

參考Optimized QuickSort — C Implementation (Non-Recursive)以及測驗題的程式碼

node_t *p = pivot->next;
pivot->next = NULL;
    
while (p) {
    node_t *n = p;
    p = p->next;
    list_add(n->value > value ? &right : &left, n);
}

上述可知以 pivot 為分隔點,比 pivot 小的值放到鏈結串列 left ;大的值放到鏈結串列 right。







%0



Node1

2



Node2

3



Node1->Node2





Node3

1



Node2->Node3





Node4

4



Node5

7



Node6

5



Node5->Node6





left
left



left->Node1





pivot
pivot



pivot->Node4





right
right



right->Node5





begin[i] = left;
end[i] = list_tail(&left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right);

left = right = NULL;
i += 2;

分類完後,以 left -> pivot -> right 分別將鏈結開頭跟尾端存入陣列 begin 跟 end 中,因為是用堆疊 stack 的方式,會一直確保取出最大值,串接到 result 裡。

延伸問題

我思考後覺得可以改進的地方有兩個:

  • 更改max_length大小
  • 決定 pivot 從哪裡取得

首先在看完程式碼後,因為 begin 跟 end 都是取鏈結串列的頭尾,所以總長度應該不超過 list 大小,所以更改程式碼如下:

void quick_sort(node_t **list) {
  int n = list_length(list);
  int value;
  int i = 0;
-    int max_level = 2 * n;
-    node_t *begin[max_level], *end[max_level];
+  // int max_level = 2 * n;
+  node_t *begin[n], *end[n];

參考 Linux 效能分析工具: Perf,使用perf 觀察兩者的 instruction 、 cpu cycle 、 cache miss/references。
介紹上述四種性能計數器統計信息及其含義:

  • cache-misses: CPU 核心的快取未命中次數。表示在執行程式時,CPU 試圖訪問快取中不存在的數據或指令的次數。
  • cache-references: CPU 核心的快取參考次數。表示 CPU 試圖訪問快取的次數,無論訪問是否成功。
  • instructions: CPU 核心的指令執行數量。
  • cpu cycle: CPU 執行程式的總時鐘周期數。
$perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./qsort
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 都會是最小或最大值,這種情況下,快速排序的效能將退化為最壞的時間複雜度,即

O(n2)

perf 執行錯誤解決

接下來我就遇到 perf top 出現問題:

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

根據 Linux 效能分析工具: Perf裡所提到,推測原因應該是我重開機後有更新到 kernel 。所以現在我來紀錄修復過程。
在編譯過程中,安裝相依的套件出現的錯誤:

BUILD:   Doing 'make -j20' parallel build
Warning: Kernel ABI header differences:
  diff -u tools/include/uapi/sound/asound.h include/uapi/sound/asound.h
  diff -u tools/arch/x86/include/asm/cpufeatures.h arch/x86/include/asm/cpufeatures.h
  diff -u tools/arch/arm64/include/asm/cputype.h arch/arm64/include/asm/cputype.h
Makefile.config:465: No libdw DWARF unwind found, Please install elfutils-devel/libdw-dev >= 0.158 and/or set LIBDW_DIR
Makefile.config:470: No libdw.h found or old libdw.h found or elfutils is older than 0.138, disables dwarf support. Please install new elfutils-devel/libdw-dev
Makefile.config:612: No sys/sdt.h found, no SDT events are defined, please install systemtap-sdt-devel or systemtap-sdt-dev
Makefile.config:698: Warning: Disabled BPF skeletons as clang (clang) is missing
Makefile.config:810: slang not found, disables TUI support. Please install slang-devel, libslang-dev or libslang2-dev
Makefile.config:857: Missing perl devel files. Disabling perl scripting support, please install perl-ExtUtils-Embed/libperl-dev
Makefile.config:1021: No libcap found, disables capability support, please install libcap-devel/libcap-dev
Makefile.config:1093: No libbabeltrace found, disables 'perf data' CTF format support, please install libbabeltrace-dev[el]/libbabeltrace-ctf-dev
Makefile.config:1158: libpfm4 not found, disables libpfm4 support. Please install libpfm4-dev
Makefile.config:1176: *** ERROR: libtraceevent is missing. Please install libtraceevent-dev/libtraceevent-devel or build with NO_LIBTRACEEVENT=1.  Stop.
make[1]: *** [Makefile.perf:261: sub-make] Error 2
make: *** [Makefile:70: all] Error 2

可以根據Minimal requirements to compile the Kernel去看說電腦哪些相依套件沒有安裝到,另外比較大問題是是缺少 libtraceevent函式庫

sudo apt install libtraceevent-dev  # Debian/Ubuntu 系統

安裝完後編譯就成功了~

最後將編譯好後的 perf 掛接到 /usr/bin/perf 裡就可以重新運作了

$sudo ln -s /path/linux-6.8/tools/perf/perf /usr/bin/perf

第一周測驗2

timsort.c程式碼理解

  • merge function
static struct list_head *merge(void *priv,
                               list_cmp_func_t cmp,
                               struct list_head *a,
                               struct list_head *b)
{
    struct list_head *head;
    struct list_head **tail = &head;

    for (;;) {
        /* if equal, take 'a' -- important for sort stability */
        if (cmp(priv, a, b) <= 0) {
            *tail = a;
            tail = &a->next;
            a = a->next;
            if (!a) {
                *tail = b;
                break;
            }
        } else {
            *tail = b;
            tail = &b->next;
            b = b->next;
            if (!b) {
                *tail = a;
                break;
            }
        }
    }
    return head;
}

在 merge 函式裡,會先初始化宣告head,以及間接指標tail指向head的位址。







structs



structa

a1

1



structb

a2

3



structa:n1->structb:n2





structd

b1

2



structe

b2

4



structd:n4->structe:n5





structadptr

&(&head)

tail



structptr

&head

head



structadptr:adptr->structptr:nw





structc

a3

5



structb:n2->structc:n3





a
a



a->structa:A





b
b



b->structd:D





通過 cmp 函式比較兩個鏈表節點的值。因為是用間接指標,所以 tail = a 這個指令會讓head去指向 a1 ,然後將tail指向 a->next 的位址,a 指向 a 的下一個節點。







structs



structa

a1

1



structb

a2

3



structa:n1->structb:n2





structd

b1

2



structe

b2

4



structd:n4->structe:n5





structadptr

&a1.next

tail



structptr

&head

head



structptr:name->structa:A





structc

a3

5



structb:n2->structc:n3





a_list
a



a_list->structb:B





b
b



b->structd:D





再利用 cmp 函式比較兩個鏈表節點的值。因為tail為間接指標,所以會更動 a1->next 指向 b1,這樣就會 a1 與 b1 相接 ,然後將tail指向 b1->next 的位址,b 指向 b 的下一個節點。







structs



structadptr

&b1.next

tail



structptr

&head

head



structa

a1

1



structptr:name->structa:A





structd

b1

2



structa:n1->structd:n4





structb

a2

3



structc

a3

5



structb:n2->structc:n3





structe

b2

4



structd:n4->structe:n5





a
a



a->structb:B





b
b



b->structe





如此一來降低記憶體開銷 : 只會對 2 個 runs 中,其範圍重疊的部份進行合併,額外空間只需要配置二個要合併的部份中跟較小的那一部份元素數量的記憶體。

  • find_run function
    再來解釋find_run(某些程式碼已省略)
static struct pair find_run(void *priv,
                            struct list_head *list,
                            list_cmp_func_t cmp)
{
    size_t len = 1;
    struct list_head *next = list->next, *head = list;
    struct pair result;

    if (cmp(priv, list, next) > 0) {
        /* decending run, also reverse the list */
        struct list_head *prev = NULL;
        do {
            len++;
            list->next = prev;
            prev = list;
            list = next;
            next = list->next;
            head = list;
        } while (next && cmp(priv, list, next) > 0);
        list->next = prev;
    } else {
        /* ascending run, delete */
    }
    head->prev = NULL;
    head->next->prev = (struct list_head *) len;
    result.head = head, result.next = next;
    return result;
}

find_run這個函式的用途就是去尋找連續的遞減或遞增數列,讓該數列成為一個 run。這邊以圖解的方式來說明遞減數列,遞增數列原裡差不多就不多贅述。







%0



Node1

5



Node2

4



Node1->Node2





Node3

1



Node2->Node3





Node4

2



Node3->Node4





Node5

3



Node4->Node5





head
head



head->Node1





next
next



next->Node2





prev
prev



list
list



list->Node1





在 do while 迴圈裡就是將 list 指向的節點指派到 prev 鏈結串列,然後重新比較下兩個是否有符合遞減的條件。







%0



Node1

5



Node2

4



Node3

1



Node2->Node3





Node4

2



Node3->Node4





Node5

3



Node4->Node5





head
head



head->Node2





next
next



next->Node3





prev
prev



prev->Node1





list
list



list->Node2





當 list 與 next 的條件不再符合時,就將 list 和 prev 掛接在一起完成 reverse。並且宣告一個 result 的 head 為該 run 的開端;next 為 run 的尾端的下一個節點(方便在找下一個 run)。







%0



Node1

5



Node2

4



Node2->Node1





Node3

1



Node3->Node2





Node4

2



Node5

3



Node4->Node5





head
head



head->Node3





next
next



next->Node4





list
list



list->Node3





result.head
result.head



result.head->Node3





result.next
result.next



result.next->Node4





接著,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

$perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./qtest -f ./traces/trace-test-listsort.cmd 
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

第二周測驗1

解釋程式碼運作

105. Construct Binary Tree from Preorder and Inorder Traversal的題目作為例子,首先會遍歷 inorder 的所有值,並以Linux 核心的 hash table 實作篇中的 Division method 作為找尋 key 的方法。
僅將部分圖畫出:







G


cluster_4

hash_key 4


cluster_2

hash_key 0


cluster_3

hash_key 3



hash

hash table

0

1

2

3

4



hn4

15

pprev

next



hash:f0->hn4





hn2

3

pprev

next



hash:f3->hn2





hn5

9

pprev

next



hash:f4->hn5





null1
NULL



null2
NULL



null4
NULL



hn4:s->hash:f0





hn3

20

pprev

next



hn4:next->hn3





hn3:next->null1





hn3:s->hn4:s





hn2:next->null2





hn5:s->hash:f4





hn5:next->null4





由前序可知哪個節點在上面 (越前面的越上面)、而由中序可知哪個節點靠左(越前面的越左邊),於是可得知前序的第一個元素一定是 root 的值,且該元素對應到中序後,左邊的值就在左邊,右邊的值就在右邊。

static struct TreeNode *dfs(int *preorder,
                            int pre_low,
                            int pre_high,
                            int *inorder,
                            int in_low,
                            int in_high,
                            struct hlist_head *in_heads,
                            int size)
{
    if (in_low > in_high || pre_low > pre_high)
        return NULL;

    struct TreeNode *tn = malloc(sizeof(*tn));
    tn->val = preorder[pre_low];
    int idx = find(preorder[pre_low], size, in_heads);
    tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
                   in_low, idx - 1, in_heads, size);
    tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,
                    idx + 1, in_high, in_heads, size);
    return tn;
}

所以dfs函式所做的事就是找 preorder 的開端值,是位在 inorder 的哪個位置上,左邊的陣列與右邊的陣列就分別不斷遞迴dfs函式,直到二原樹畫完。

struct hlist_node *p;
int hash = (num < 0 ? -num : num) % size;
hlist_for_each (p, &heads[hash]) {
    struct order_node *on = list_entry(p, struct order_node, node);
    if (num == on->val)
        return on->idx;
}

find函式所做的事便是要找到位在 inorder 的哪個位置上,因此會利用hlist_for_each,去遍歷同一個 hash_key 找到相同值,回傳 on->idx。

  • 程式碼可改進之處
    根據Linux 核心的 hash table 實作,設計雜湊函數使其盡可能接近 perfect function,讓查找 hash table 中的資料時間複雜度為
    O(1)
    ,是關鍵要素。

使用 Multiplication Method ,且設定 A = golden ratio 時, 此雜湊函數稱為 Fibonacci hashing,且 key 經此函數轉換得到的 index 相當分散,減少碰撞次數。

第二周測驗2

解釋程式碼運作

首先要先了解LRUCache的結構是長怎樣。裡面包含:

  • capacity: 該 cache 可存取的量
  • count: 計算已經存取幾個 LRUNode
  • dhead: 連結所有 LRUNode->link,用來判斷當 capacity 滿時,需要 evict 哪個 LRUNode
  • hhead: 用來快速尋找 LRUNode 的 key 與 value






structs


cluster_1

LRUCache


cluster_2

LRUNode



struct1

capacity



struct2

count



struct3

dhead



struct3->struct3


prev



link1

prev

next



struct3->link1


next



struct4

hhead[0]

hhead[1]

...

hhead[capacity - 1]



node1

a

pprev

next



struct4:s->node1





struct5

key=0



struct6

value



根據146. LRU Cachepush的功能為:

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.

所以在程式碼分成了兩個區塊:

  1. Update the value of the key if the key exists.
int hash = key % obj->capacity;
struct hlist_node *pos;
hlist_for_each (pos, &obj->hhead[hash]) {
    LRUNode *c = list_entry(pos, LRUNode, node);
    if (c->key == key) {
        list_move(&c->link, &obj->dhead);
        cache = c;
    }
}

透過hlist_for_each來遍歷 hhead[hash] ,若 key 本來就存在就更新值,並且將該 LRUNode->link 移到 dhead 佇列開端。

  1. If capacity is full, evict the least recently used key; otherwise, add the key-value pair to the cache.
if (obj->count == obj->capacity) {
    cache = list_last_entry(&obj->dhead, LRUNode, link);
    list_move(&cache->link, &obj->dhead);
    hlist_del(&cache->node);
    hlist_add_head(&cache->node, &obj->hhead[hash]);
} else {
    cache = malloc(sizeof(LRUNode));
    hlist_add_head(&cache->node, &obj->hhead[hash]);
    list_add(&cache->link, &obj->dhead);
    obj->count++;
}

如果 capacity 滿了,提取出 dhead 佇列尾端(最近最少使用的 key)重新放到佇列尾端,修改 key 、 value為新的組合,hhead[hash]也是同樣步驟。

根據146. LRU Cacheget的功能為:

Return the value of the key if the key exists, otherwise return -1.

所以程式碼的話就是用hlist_for_each來遍歷 hhead[hash],將該 LRUNode->link 移到 dhead 佇列開端,且 return LRUNode->value。

int lRUCacheGet(LRUCache *obj, int key)
{
    int hash = key % obj->capacity;
    struct hlist_node *pos;
    hlist_for_each (pos, &obj->hhead[hash]) {
        LRUNode *cache = list_entry(pos, LRUNode, node);
        if (cache->key == key) {
            list_move(&cache->linkI, &obj->dhead);
            return cache->value;
        }
    }
    return -1;
}

第二周測驗3

解釋程式碼運作

static inline unsigned long find_nth_bit(const unsigned long *addr,
                                           unsigned long size,
                                           unsigned long n)
{
    if (n >= size)
        return size;

    if (small_const_nbits(size)) {
        unsigned long val = *addr & GENMASK(size - 1, 0);

        return val ? fns(val, n) : size;
    }

    return FIND_NTH_BIT(addr[idx], size, n);
}

在解讀主要函式find_nth_bit時,對於small_const_nbits的用途抱有很大的疑惑。

#define small_const_nbits(nbits) \
    (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)

從定義上來看,是必須要滿足:

  1. 搜索的位元的最大數量小於等於64
  2. size 必須為正數
  3. 要滿足 __builtin_constant_p(?)

那麼__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。

#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))

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