--- tags: linux2022 --- # 2022q1 Homework1 (quiz1) contributed by < [`qwe661234`](https://github.com/qwe661234) > [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz1) ## 測驗一 Two Sum ### Hash Table Structure ![](https://i.imgur.com/5FQZ6Lo.png) hash table bucket 以 non-circular doubly-linked list 來儲存 * hlist_head: 指向 bucket list 的第一個節點 * hlist_node: bucket list 中的節點 `map_t` * bits: hash table 的 size. * ht: array of hlist_head ```c struct hlist_head { struct hlist_node *first; }; struct hlist_node { struct hlist_node *next, **pprev; }; typedef struct { int bits; struct hlist_head *ht; } map_t; ``` ### map_init Create hash table ```c #define MAP_HASH_SIZE(bits) (1 << bits) map_t *map_init(int bits) { map_t *map = malloc(sizeof(map_t)); if (!map) return NULL; map->bits = bits; map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits)); if (map->ht) { for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) (map->ht)[i].first = NULL; } else { free(map); map = NULL; } return map; } ``` ### container_of 給定結構體成員的位址, 回推該結構體的起始位置 reference: https://hackmd.io/@sysprog/linux-macro-containerof ```c #define container_of(ptr, type, member) \ ({ \ void *__mptr = (void *) (ptr); \ ((type *) (__mptr - offsetof(type, member))); \ }) ``` ### hash function ```c #define GOLDEN_RATIO_32 0x61C88647 static inline unsigned int hash(unsigned int val, unsigned int bits) { /* High bits are more random, so use them. */ return (val * GOLDEN_RATIO_32) >> (32 - bits); } ``` ### hash key * key: value of array element * data: array index ```c struct hash_key { int key; void *data; struct hlist_node node; }; ``` ### find_key 由於不同的 key value 經過 hash funciton 後可能得到一樣的 value, 所以經過 hash 後需要到對應的 bucket 中尋找 `node->key == key` 的 node 並回傳 ```c static struct hash_key *find_key(map_t *map, int key) { struct hlist_head *head = &(map->ht)[hash(key, map->bits)]; for (struct hlist_node *p = head->first; p; p = p->next) { struct hash_key *kn = container_of(p, struct hash_key, node); if (kn->key == key) return kn; } return NULL; } ``` ### map_get 在 hash table 中尋找對應 key value 的 node ```c void *map_get(map_t *map, int key) { struct hash_key *kn = find_key(map, key); return kn ? kn->data : NULL; } ``` ### map_add 一開始會在 hash table 中尋找對應 key value 的 node, 若已存在就不重複加入 若不存在, 先配置記憶體給 new node 並設好 key 與 data, 接著以 hash funciton 得到的 value 去找出 bucket 對應的 `hlist_head`,`first` 為 bucket 中的第一個 node (或是 NULL), 接下來的操作其實就是把原本的 `first` 接在 new node 後面, 把 new node 變成 `first`. ```graphviz digraph structs { rankdir="LR" node[shape=record]; struct1 [label="0|<1>1|2|3|4|5|..."] node[shape=record]; struct2 [shape=record, label="{first|{<p>pprev|<n>next}}"]; node[shape=record]; struct3 [label= "{new node|{<p>pprev|<n>next}}"]; struct1:1 -> struct2; struct2:p -> struct1:1; struct2:n -> NULL; } ``` ```graphviz digraph structs { rankdir="LR" node[shape=record]; struct1 [label="0|<1>1|2|3|4|5|..."] node[shape=record]; struct2 [shape=record, label="{<f>first|{<p>pprev|<n>next}}"]; node[shape=record]; struct3 [label= "{<f>new node|{<p>pprev|<n>next}}"]; struct1:1 -> struct3:f; struct2:p -> struct3:n; struct3:n -> struct2:f struct3:p -> struct1:1 struct2:n -> NULL; } ``` :::info 1. AAA = `n->next = first` 將 new node 的 next 指向原本的 `first` 2. BBB = `n->pprev = &h->first` 將 new node 的 pprev 指向此 bucket 的 hlist_head ::: ```c void map_add(map_t *map, int key, void *data) { struct hash_key *kn = find_key(map, key); if (kn) return; kn = malloc(sizeof(struct hash_key)); kn->key = key, kn->data = data; struct hlist_head *h = &map->ht[hash(key, map->bits)]; struct hlist_node *n = &kn->node, *first = h->first; n->next = first; if (first) first->pprev = &n->next; h->first = n; n->pprev = &h->first; } ``` ### map_deinit 清除 hash table ```c void map_deinit(map_t *map) { if (!map) return; for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) { struct hlist_head *head = &map->ht[i]; for (struct hlist_node *p = head->first; p;) { struct hash_key *kn = container_of(p, struct hash_key, node); struct hlist_node *n = p; p = p->next; if (!n->pprev) /* unhashed */ goto bail; struct hlist_node *next = n->next, **pprev = n->pprev; *pprev = next; if (next) next->pprev = pprev; n->next = NULL, n->pprev = NULL; bail: free(kn->data); free(kn); } } free(map); } ``` ### main funciton 1. 首先建立 hash table 並配置 memory 給 return array 2. 接著 iterate array nums 3. 尋找 key vlaue 為 target - nums[i] 的 node 是否有在 hash table 中 * 找到就將 return array 的第一跟第二個 element 設為這兩個值的 array index, returnSize 設為 2 並 return * 找不到就建立 new node, key 為 nums[i], data 為 array index, 放入 hash table 中 4. 如果 nums 中任兩個 element 相加都不為 target, 則 returnSize = 0 ```c int *twoSum(int *nums, int numsSize, int target, int *returnSize) { map_t *map = map_init(10); *returnSize = 0; int *ret = malloc(sizeof(int) * 2); if (!ret) goto bail; for (int i = 0; i < numsSize; i++) { int *p = map_get(map, target - nums[i]); if (p) { /* found */ ret[0] = i, ret[1] = *p; *returnSize = 2; break; } p = malloc(sizeof(int)); *p = i; map_add(map, nums[i], p); } bail: map_deinit(map); return ret; } ``` ## Hash funciton Hash funciton: hash function 的功能是用來將 key 值轉換成對應的 index ### **Perfect function** 當所有的 key value 經過 hash funciton 轉換後, 得到 index 都不一樣時, 我們稱此 hash funciton 為 **perfect funciton**。 **Perfect funciton** 可以做到完美的 1-to-1, 也就是一組 key 對應到一組 value。 假如 hash function 的時間複雜度是 O(1), 這樣我們僅僅只需要時間複雜度 O(1) 的時間就可以查找到 hash table 中的資料。 但實際上 **perfect funciton** 很難做到, 我們不知道 key value 的 range 有多大, 所以不知道 bucket 的數量要多少才能滿足 1-to-1, 如果 hash table size 很大, 但其中有很多空間都沒有使用到也會造成不必要的浪費。由於多個 key value 可能對應到同一個 index, 所以一個 index 會對應到一個可以存數筆 data 的 bucket。 綜合以上, 我們只能透過設計 hash function, 使其盡可能接近 **perfect funciton**。 ### Hash function 考慮因素 #### 1. 計算所需的時間複雜度要低 希望 hash funciton 計算的時間複雜度為 O(1)。 #### 2. Collision 減少 Collision 是指不同的 key value 對應到相同的 index, collision 越少越接近 **perfect funciton**。 #### 3. 避免 Clustering 現象 Clustering 是指某些 bucket 存放很多筆資料, 而某些 bucket 存放的很少, 應該盡量讓 bucket 存放的資料筆數平衡, 否則容易造成 `Overflow`, 這樣會造成存取效率變差。 `Overflow` 是指 bucket 的記憶體空間滿了, 需要刪除一筆資料才能存入新的資料, `Overflow` 發生時, 決定哪一筆資料要被刪除也是重要的議題。 ### 常見 hash function 作法 #### 1. Division method h(k) = k % N 以 mod 運算後的餘數作為 index, 由於 key 值得範圍無法得知, 所以如何挑選適合的 N 很關鍵。 #### 2. Mid-square h(k) = $bits_{i,i + r - 1}(k^2)$ 將 key 值平方後, 取其 bit 第 $i$ ~ $i + r - 1$ 位, 得到的數字範圍會是 0 ~ $2^{r - 1}$, 所以 bucket 數量為 $2^r$ 即可。 例如: key value = 6, $6^2 = 36$, 假設 i = 2, r = 3, 所以取其 bit 第 2 ~ 4 位 所以將 $36_{10}$ = $100100_2$, 取第 2 ~ 4 位得 $010_2$, 所以 index = $2_{10}$。 #### 3. Folding addition 先將 key value 切割成片段後相加, 亦可以對相加後的結果做其他運算 例如: key value = 3823749374, 將此 value 每三個數字分成一段 382 | 374 | 937 | 4, 再將這四個數字相加 index = 382 + 374 + 937 + 4 = 1697 可以進一步對 1697 進行其他運算例如: mod, 反轉... #### 4. Multiplication Method 由於大部分的情況下, 我們不知道 key value 的範圍以及分佈情形, 這樣的情形適用 `Multiplication Method` `Multiplication Method` 步驟: ![](https://raw.githubusercontent.com/alrightchiu/SecondRound/master/content/Algorithms%20and%20Data%20Structures/HashTable%20series/Intro/f8.png) key value 乘上 constant A -> 取小數點部分 -> 再乘上 m -> 再取整數部分的一系列步驟讓 hash function 能夠儘量把更多的 key value 中的 bit 納入考慮而增加隨機性。 (原因參考[這篇](http://alrightchiu.github.io/SecondRound/hash-tableintrojian-jie.html#dm)) K: key value A: a constant, 且 0 < A < 1 m: bucket 數量, 且 m = $2^p$ ## Linux hash function 在 linux 的 [hash.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/hash.h) 中, hash funciton 的設計是使用上面所提到的 `Multiplication Method`, 但上面提到的 hash funciton 應該是要長得像 $h(K) = \lfloor m * (KA - \lfloor KA \rfloor) \rfloor$ 這個樣子, 但在 [hash.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/hash.h) 中卻用到了 bit-shifting 的方式, 這是由於上述的 funciton 與 $h(K) = K * 2^w * A >> (w - p)$ 是等價的, 而且 bit-shifting 的效率比較好, 所以以這種方式來實作。 K: key value A: a constant, 且 0 < A < 1 m: bucket 數量, 且 m = $2^p$ $w$: 一個 word 有幾個 bit ### 為什麼兩個 function 等價 我們假設一個 word 是 8 個 bit, 將 KA 的結果以 8 bit 整數配上 8 bit 浮點數表示 ```graphviz graph structs { node[shape=record]; struct1 [label="0|0|0|0|0|1|0|1"] node[shape=point] dot node[shape=record]; struct2 [label="1|1|1|0|1|0|0|0"] } ``` 根據 $h(K) = \lfloor m * (KA - \lfloor KA \rfloor) \rfloor$, 我們只需要 KA 的浮點數部分, 也就是後面的 8 個 bits, 再假設 m 是 8 = $2^3$, 所以乘上 m, 所以以上步驟等同於將前8個 bit 清除再往左移三位 ```graphviz graph structs { node[shape=record]; struct1 [label="0|0|0|0|0|1|1|1"] node[shape=point] dot node[shape=record]; struct2 [label="0|1|0|0|0|0|0|0"] } ``` 最後做下高斯只留下整數部分 ```graphviz graph structs { node[shape=record]; struct1 [label="0|0|0|0|0|1|1|1"] node[shape=point] } ``` 而這樣的操作等同於 KA 的結果先左移 8 位, 這樣前面 8 個 bit 為 KA 結果的浮點數部分, 依照前面的操作我們知道浮點數部分其實只要留下前 p 個 bit, 所以要右移 (w - p) 個 bit KA ```graphviz graph structs { node[shape=record]; struct1 [label="0|0|0|0|0|1|0|1"] node[shape=point] dot node[shape=record]; struct2 [label="1|1|1|0|1|0|0|0"] } ``` K * $2^w$ * A, 乘上 $2^w＄$ 等同於左移 8 個 bit ```graphviz graph structs { node[shape=record]; struct1 [label="1|1|1|0|1|0|0|0"] node[shape=point] dot node[shape=record]; struct2 [label="0|0|0|0|0|0|0|0"] } ``` 接著右移 (w - p), 也就是 8 - 3 = 5 個 bit, 因為在 linux 的實用中是用 uint, 所以只會留下整數部分 ```graphviz graph structs { node[shape=record]; struct1 [label="0|0|0|0|0|1|1|1"] node[shape=point] } ``` ### linux 程式碼 我們擷取 32 bit 的 hash funciton 的程式碼 (64 bit 的 hash funciton 邏輯相同, 只是 word size 為 64) source: [hash.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/hash.h) #### 程式碼解釋 * GOLDEN_RATIO_32: A * $2^{32}$ 後的結果 * __hash_32_generic(u32 val) * val: key value K * 這個 function 做的事情是算出 $K * 2^w * A$ 的結果 * hash_32(u32 val, unsigned int bits) * val: key value K * bits: 其實就是 p, $2^{bits}$ = bucket 數量 * 這個 function 做的事情是將 `__hash_32_generic(u32 val)` 算出的結果 $K * 2^w * A$ 右移 (32 - p) 因此, val * GOLDEN_RATIO_32 >> (32 - bits) $\equiv$ K * A * $2^w$ >> (w - p) ```c #define GOLDEN_RATIO_32 0x61C88647 #ifndef HAVE_ARCH__HASH_32 #define __hash_32 __hash_32_generic #endif static inline u32 __hash_32_generic(u32 val) { return val * GOLDEN_RATIO_32; } static inline u32 hash_32(u32 val, unsigned int bits) { /* High bits are more random, so use them. */ return __hash_32(val) >> (32 - bits); } ``` ### GOLDEN_RATIO 至於 A 為什麼使用 [golden ratio](https://zh.wikipedia.org/wiki/%E9%BB%84%E9%87%91%E5%88%86%E5%89%B2%E7%8E%87), A = $(\sqrt{5} - 1) / 2$ = 0.6180339887..., 這個數字是由 [Donald Knuth](https://en.wikipedia.org/wiki/Donald_Knuth) 所建議的, 在這份 [hunter college 的課程講義](http://www.compsci.hunter.cuny.edu/~sweiss/course_materials/csci335/lecture_notes/chapter05.pdf) 中有提出實驗結果圖, 其中當 A = [golden ratio](https://zh.wikipedia.org/wiki/%E9%BB%84%E9%87%91%E5%88%86%E5%89%B2%E7%8E%87) 時, 此 hash function 稱為 `Fibonacci hashing`, 且 key value 經此 funciton 轉換得到的 index 是相當分散的, 意即 Collision 很低。 ![](https://i.imgur.com/TU1DpWk.png) ### 比較 golden ratio 與非 golden ratio 這邊挑選了4個不同的數字作為 A * $2^{32}$, 並紀錄對 key value 0 ~ 1500 做 `hash_32(key value, 10)` 的結果 1. 0x61C88647 2. 0x80000000 3. 0x12345678 4. 0x54061094 圖的 x 軸是 key value, y 軸是 `hash_32(key value, 10)` 計算出的值 ![](https://i.imgur.com/kP2RoI9.png =50%x)![](https://i.imgur.com/BFgUtcA.png =50%x) ![](https://i.imgur.com/xEmZWP7.png =50%x)![](https://i.imgur.com/X1D9qBi.png =50%x) 由實驗個果圖可發現, golden ratio 作為 A 結果是最均勻分散的, 另外結果也證明 A 的值的對於 Collision 有很大的影響, 例如 A * $2^{32}$ = 0x80000000 時, 0 ~ 1500 只有兩種可能, 不僅每兩個數字就發生一次 Collision, 由於 data 只會存放於兩個 bucket, 因此 Cluster 程度相當嚴重。 ### Reference: * https://meteorv.dev/Data-Structure/hashing/#Collision-Overflow-%E7%9A%84%E8%99%95%E7%90%86%E6%96%B9%E6%B3%95 * http://alrightchiu.github.io/SecondRound/hash-tableintrojian-jie.html#dm * https://www.cs.hmc.edu/~geoff/classes/hmc.cs070.200101/homework10/hashfuncs.html * http://www.cs.nthu.edu.tw/~wkhon/ds/ds12/lecture/lecture18.pdf * http://www.compsci.hunter.cuny.edu/~sweiss/course_materials/csci335/lecture_notes/chapter05.pdf ## 測驗二 Remove Duplicates from Sorted List II :::info `COND1` = `COND2` = `head->next && head->val == head->next->val` ::: 邏輯是將值不重複的 node 的 next 指向下一個值不重複的 node, 忽略中間所有值重複的 node 先檢查 next node 是否存在, 接著檢查 next node 的值是否與 current node 的值重複。 遇到重複會進入 `while` loop 直到 next node 與 current node 的值不重複, 對 next node 做遞迴, 唯有值不重複的 node 才會被回傳 ```c #include <stddef.h> struct ListNode { int val; struct ListNode *next; }; struct ListNode *deleteDuplicates(struct ListNode *head) { if (!head) return NULL; if (head->next && head->val == head->next->val) { /* Remove all duplicate numbers */ while (head->next && head->val == head->next->val) head = head->next; return deleteDuplicates(head->next); } head->next = deleteDuplicates(head->next); return head; } ``` ### 非遞迴版本: 邏輯與遞迴版本類似, 以指標的指標操作可以省去檢查 current node 是否為 head #### `*cur = (*cur)->next` 與 `cur = &(*cur)->next`差異 `*cur = (*cur)->next`: 將 head or 前一個 node 的 next 指向位置改為 next node `cur = &(*cur)->next`: iterate next, 將 cur 設為 next node ```c #include <stddef.h> struct ListNode { int val; struct ListNode *next; }; struct ListNode *deleteDuplicates(struct ListNode *head) { struct ListNode **cur; cur = &head; while (*cur) { if ((*cur)->next && (*cur)->val == (*cur)->next->val) { while ((*cur)->next && (*cur)->val == (*cur)->next->val) *cur = (*cur)->next; *cur = (*cur)->next; } else { cur = &(*cur)->next; } } return head; } ``` ## circular doubly-linked list 改寫 ### doubly-linked list structure Doubly-linked list and its value is integer. ```c struct list_head { struct list_head *prev; struct list_head *next; }; typedef struct { int value; struct list_head list; } element_t; ``` ### 迭代 (iterative) version 由於 list_head 不會變, 所以不用回傳 list_head 由於 safe 會保存 next node, 所以直接刪除當前節點, `while` loop 終止時, current node 會指向一串存在重複值 node list 中的最後一個 node, 所以 `while` loop 結束後要刪除 current node ```c void deleteDuplicates(struct list_head *head) { if (!head) return; struct list_head *cur, *safe; list_for_each_safe (cur, safe, head) { if (list_entry(cur, element_t, list)->value == list_entry(safe, element_t, list)->value) { while(safe != head && list_entry(cur, element_t, list)->value == list_entry(safe, element_t, list)->value) { list_del(cur); cur = safe; safe = safe->next; } list_del(cur); } } } ``` ### 遞迴 (recursive) version 如果 current node 有重複, 先遞迴 next node, 遞迴返回後再刪除 current node, 考慮到一串存在重複值的 node list 中的最後一個 node, 所以要檢查與 previous node 的值是否相同. ```c void deleteDuplicates(struct list_head *cur, struct list_head *head) { if(cur == head) return; if ((cur->next != head && list_entry(cur, element_t, list)->value == list_entry(cur->next, element_t, list)->value) || (cur->prev != head && list_entry(cur, element_t, list)->value == list_entry(cur->prev, element_t, list)->value)) { deleteDuplicates(cur->next, head); list_del(cur); } deleteDuplicates(cur->next, head); } ``` ## 測驗三 [LeetCode 146. LRU Cache](https://leetcode.com/problems/lru-cache/) [Least recently used (LRU)](https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)) 是一種 cache 的置換機制, 主要是當 cache 記憶體已滿, 將最近最少使用的一筆資料與新資料替換, 這樣的機制是為了降低 cache miss rate, 在這題中要替換的是使用時間距離目前最遠的那筆資料。 ### Cache Data Structure 在 cache 的實作類似測驗一的 hash table, hheads[index] 會指向對應此 index 的 bucket, 而 bucket 是以 circular doubly-linked list 來實作。 除了 hheads array 之外, 還有另外一個 dhead, 會指向一條用來紀錄的 circular doubly-linked list, 這邊紀錄的是 LRUNode 的使用情況, 最近使用的 node 會被擺在越前面, 越之前使用的 node 會被擺在越後面, 所以要替換時, 會選擇這一條 list 中最後面的 node 來做替換。 Cache 中的 node 和 dhead 所指向的 list 中的 node 是同一份。 ```c struct list_head { struct list_head *prev; struct list_head *next; }; ``` capacity: cache 容量, 即可存放的 data 筆數 count: data 目前存放了多少筆 data ```c typedef struct { int capacity, count; struct list_head dhead, hheads[]; } LRUCache; ``` hlink 用來連接 cache 中的 bucket, dlink 則是用來連接紀錄 node 使用情形的 list。 ```c typedef struct { int key, value; struct list_head hlink, dlink; } LRUNode; ``` ### lRUCacheCreate Create LRU cache, 並初始化 dhead and hhead array。 這邊的 `sizeof(*obj)` 印出來是 24, 代表的是 count(4 bytes) + capacity(4 bytes) + dhead(16 bytes) 的空間, 另外的 `capacity * sizeof(struct list_head)` 則是配置給 hheads array 的空間。 ```c LRUCache *lRUCacheCreate(int capacity) { LRUCache *obj = malloc(sizeof(*obj) + capacity * sizeof(struct list_head)); obj->count = 0; obj->capacity = capacity; INIT_LIST_HEAD(&obj->dhead); for (int i = 0; i < capacity; i++) INIT_LIST_HEAD(&obj->hheads[i]); return obj; } ``` ### lRUCacheFree :::info MMM1 = list_for_each_entry_safe ::: dhead 所指向的 list 中代表目前存在 cache 中的所有 node, 所以將這條 list 中的所有 node 釋放等同於釋放 cache, 用 `list_for_each_entry_safe` 是因為有移除 node, 所以要先紀錄下一個 node 位置。 ```c void lRUCacheFree(LRUCache *obj) { LRUNode *lru, *n; list_for_each_entry_safe (lru, n, &obj->dhead, dlink) { list_del(&lru->dlink); free(lru); } free(obj); } ``` ### lRUCacheGet :::info MMM2 = list_for_each_entry ::: key 經過 hash funciton 後, 得到對應的 index, 再以此 index 找到對應的 bucket, 由於 不同的 key 經過 hash function 可能得到相同的 index, 所以要從 bucket 中所有的 node 找到 `node>key == key` 的 node。 ```c int lRUCacheGet(LRUCache *obj, int key) { LRUNode *lru; int hash = key % obj->capacity; list_for_each_entry (lru, &obj->hheads[hash], hlink) { if (lru->key == key) { list_move(&lru->dlink, &obj->dhead); return lru->value; } } return -1; } ``` ### lRUCachePut :::info MMM3 = list_for_each_entry MMM4 = list_last_entry **MM4 的正確答案給 list_for_each_entry, 但應該是 list_last_entry, 如果是 list_for_each_entry 參數對不上** ::: key 經過 hash funciton 後, 得到對應的 index, 再以此 index 找到對應的 bucket, 接著到該 bucket 中找 `node->key == key` 的 node。 1. 有找到: 將 value 更新, 並將該 node 移到用來記錄使用情形的 list 中的第一個, 因為這個 node 當前被使用到。 2. 沒找到: 如果找不到代表需要新增 node 到 cache 中, 此時要檢查 cache 記憶體是否滿了。 * cache 記憶體已滿, 這邊的做法是先找到用來記錄使用情形的 list 中的最後一個 node, 因為這個 node 的使用時間是距離目前最遠的, 接著把他從 cache 和用來記錄使用情形的 list 中移除, 但是沒有 free 掉, 而是用同一份記憶體空間, 只是將其 key 和 value 更新, 從新放入 cache 中對應的 bucket 和用來記錄使用情形的 list 中。 * cache 記憶體還有剩餘空間的話, 則配置記憶體給新的 node 並設定好 key 和 value, 放入 cache 中對應的 bucket 和用來記錄使用情形的 list 中。 ```c void lRUCachePut(LRUCache *obj, int key, int value) { LRUNode *lru; int hash = key % obj->capacity; list_for_each_entry (lru, &obj->hheads[hash], hlink) { if (lru->key == key) { list_move(&lru->dlink, &obj->dhead); lru->value = value; return; } } if (obj->count == obj->capacity) { lru = list_last_entry(&obj->dhead, LRUNode, dlink); list_del(&lru->dlink); list_del(&lru->hlink); } else { lru = malloc(sizeof(LRUNode)); obj->count++; } lru->key = key; list_add(&lru->dlink, &obj->dhead); list_add(&lru->hlink, &obj->hheads[hash]); lru->value = value; } ``` ### Test fucntion 測試 `lRUCacheCreate` 是否有成功 ```c bool testLRUCacheCreate(LRUCache *cache) { if(!cache) return false; return true; } ``` 在 lRUCachePut 後測試 cache 是否有新增或更新該 key 所對應的 value。 ```c bool testCacheGet(LRUCache *cache, int key, int rightvalue) { if(!cache) { printf("cache is NULL"); return false; } int target = lRUCacheGet(cache, key); if(target != rightvalue) return false; return true; } ``` ## 改進 觀察程式碼可以發現這邊所使用的 hash function 是 division method, 也就是直接把 key mod cache capacity, 可是者樣的作法可能導致 collision 和 cluster。 例如: 假設 cache capacity 是 10, 而插入的 key value pair 是 (1, 1), (11, 11), (21, 21), (31, 31), (41, 41), 經過 hash funciton `key mod 10` 後, 這五個 node 得到的 index 都是 1, 而且這 5 個 node 都會接在 `hheads[1]` 之後, 因而導致存取效率變差。 我們可以考慮將 hash funciton 改成在 hash.h 中的 `hash_32`, 並比較改變前後的執行時間。 ### 實驗 本次實驗的 capacity 為 128 = $2^{7}$, bits = 7 #### hash_function_1 ```c int hash = key % obj->capacity(128); ``` #### hash_funciton_2 ```c int hash = hash_32(key, bits) % 128; ``` ```c #define GOLDEN_RATIO_32 0x61C88647 static inline u32 __hash_32_generic(u32 val) { return val * GOLDEN_RATIO_32; } static inline u32 hash_32(u32 val, unsigned int bits) { /* High bits are more random, so use them. */ return __hash_32(val) >> (32 - bits(7)); } ``` ### 實驗步驟 取一個隨機整數, 接著到 cache 中尋找, 如果沒找到就將 key 和 value 都設為此隨機整數並加入 cache 中, 重複 n 次 ( n 從 0 ~ 2000000 )。 ```c int main(int argc, char** argv) { for(int size = 0; size <= 20000000; size+= 100000) { LRUCache *cache = lRUCacheCreate(128); int rand_num; clock_t start, end; start = clock(); srand(time(NULL)); for(int i = 0; i < size; i++) { rand_num = rand(); if(!lRUCacheGet(cache, rand_num)) lRUCachePut(cache, rand_num, rand_num); } end = clock(); printf("%d %lf\n", size, (end - start) / (double)(CLOCKS_PER_SEC) * 1000); lRUCacheFree(cache); } } ``` ### 實驗結果 實驗結果圖顯示這兩個 hash function 在效能上的表現並無明顯差異 ![](https://i.imgur.com/6nGLiw8.png) ### 分析原因 我對亂數經過 hash_function 後得到的 index 紀錄並作圖, 結果圖為對 2000 個亂數做 hash funciton 後得到的 index, 對比兩張圖可發現, 其實兩個 hash function 對亂數計算後, 產生的結果分佈狀況差不多, 故推論其為效能無明顯差異的原因。 ![](https://i.imgur.com/6C9OJQ1.png) ![](https://i.imgur.com/iln1OJZ.png) ## 測驗四 [LeetCode 128. Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence/description/) ### Data Structure 這題的 data structure 實作類似測驗一的 hash table, heads[index] 會指向對應此 index 的 bucket, 而 bucket 是以 circular doubly-linked list 來實作。 ```c struct list_head { struct list_head *prev; struct list_head *next; }; struct seq_node { int num; struct list_head link; }; ``` ### find hash table 的 hash function 是 abs(key) % size, size 是 input array 的大小, function `find` 就是在 hash table 中尋找是否存在 key = num 的 node。 ```c static struct seq_node *find(int num, int size, struct list_head *heads) { struct seq_node *node; int hash = num < 0 ? -num % size : num % size; list_for_each_entry (node, &heads[hash], link) { if (node->num == num) return node; } return NULL; } ``` ### longestConsecutive 這個 function 拆成 3 個部分來看 #### part1 建立 hash table 並初始化 ```c int hash, length = 0; struct seq_node *node; struct list_head *heads = malloc(n_size * sizeof(*heads)); for (int i = 0; i < n_size; i++) INIT_LIST_HEAD(&heads[i]); ``` #### part2 interate input array 並為 array 中的數字建立 node 加入對應的 bucket 中。 假設 inpur array = [98,1,3,2], size = 6 圖中的 head 分別有 prev 指向 bucket 的最後一個 node 和 next 指向 bucket 的第一個 node。 ```graphviz digraph structs { rankdir="LR" node[shape=record]; ht [label="0|<1>1|<2>2|<3>3|4|5"] node[shape=record]; node1 [shape=record, label="{<f>1|{<p>pprev|<n>next}}"]; node[shape=record]; node2 [label= "{<f>2|{<p>pprev|<n>next}}"]; node3 [label= "{<f>3|{<p>pprev|<n>next}}"]; node98 [label= "{<f>98|{<p>pprev|<n>next}}"]; node1:p -> ht:1; node1:n -> ht:1; node3:p -> ht:3; node3:n -> ht:3; node2:p -> ht:2; node2:n -> node98; node98:p -> node2:n; node98:n -> ht:2 } ``` ```c for (int i = 0; i < n_size; i++) { if (!find(nums[i], n_size, heads)) { hash = nums[i] < 0 ? -nums[i] % n_size : nums[i] % n_size; node = malloc(sizeof(*node)); node->num = nums[i]; list_add(&node->link, &heads[hash]); } } ``` #### part3 iterate input array 中的所有 element, 對於每一個 element 都去 hash table 找其左半邊連續數字是否存在在 hash table 中, 再搜尋其右半邊。在查找的過程中, 會把走訪過的 node 移除, 避免重複走訪的情形。 例如: 當前 iterate 到的 element 是 5, 他就會先走 4 是否存在 hash table 中, 存在就 `len++`, 接著找 3, 直到該 key 在 hash table 找不到, 接著找 6, 7 ..., 找到做 `len++`, 找不到就結束, 繼續 iterate 下一個 element。 :::info LLL = --left RRR = ++right ::: ```c for (int i = 0; i < n_size; i++) { int len = 0; int num; node = find(nums[i], n_size, heads); while (node) { len++; num = node->num; list_del(&node->link); int left = num, right = num; while ((node = find(--left, n_size, heads))) { len++; list_del(&node->link); } while ((node = find(++right, n_size, heads))) { len++; list_del(&node->link); } length = len > length ? len : length; } } ``` #### 完整 funciton ```c int longestConsecutive(int *nums, int n_size) { int hash, length = 0; struct seq_node *node; struct list_head *heads = malloc(n_size * sizeof(*heads)); for (int i = 0; i < n_size; i++) INIT_LIST_HEAD(&heads[i]); for (int i = 0; i < n_size; i++) { if (!find(nums[i], n_size, heads)) { hash = nums[i] < 0 ? -nums[i] % n_size : nums[i] % n_size; node = malloc(sizeof(*node)); node->num = nums[i]; list_add(&node->link, &heads[hash]); } } for (int i = 0; i < n_size; i++) { int len = 0; int num; node = find(nums[i], n_size, heads); while (node) { len++; num = node->num; list_del(&node->link); int left = num, right = num; while ((node = find(LLL, n_size, heads))) { len++; list_del(&node->link); } while ((node = find(RRR, n_size, heads))) { len++; list_del(&node->link); } length = len > length ? len : length; } } return length; } ``` ### 改進之處 原本的 fucntion `longestConsecutive` 在查找後將 node 從 hash table 中移除, 但移除後並未釋放記憶體, 以及在 funciton 結束後並未將配置給 heads 的記憶體釋放, 因此會造成 **memory leak**。 ### 測試 我們以執行以下程式碼並透過 `Valgrind` 分析。 ```c int main(int argc, char** argv) { int a[10] = { 0, 3, 7, 2, 5, 8, 4, 6, 0, 1 }; printf("Longest Consecutive Sequence = %d\n", longestConsecutive(a, 10)); return 0; } ``` #### 分析結果 * `indirectly lost` 中的 1 個 blocks 是我們配置給 array of heads, 我們配置 10 個 `struct list_head`, 而一個 `struct list_head` 需要 16 bytes 的空間。 * `definitely lost` 是我們配置給 node 的空間, 我們總更配置了 9 個 node (key = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9), 但奇怪的地方是 `struct list_head` 需要 16 bytes, 而 `int` 需要 4 個 bytes, 總共只需 20 個 bytes, 為何印出卻是 24 個 bytes? 透過 `offsetof(struct seq_node, link)` 可以發現, link 的位移量是 8 而不是預期中的 4, 這邊推測是 memory alignment 所導致這樣的結果。 ![](https://i.imgur.com/Ixr7lF8.png) 為了驗證, 我們可以在 `struct seq_node` 的後方加上, 讓結構體的成員實際排列和空間佔用跟程式碼順序一致, 再次印出 `offsetof(struct seq_node, link)` 的結果, 可以發現結果為 4, 驗證我們的推測是正確的。 ```c struct seq_node { int num; struct list_head link; } __attribute__((packed)); ``` ##### reference: https://hackmd.io/@sysprog/linux-macro-containerof #### 改進程式碼 在移除 node 之後, 將 node 記憶體釋放, 並在走訪完每個 node 後將配置給 head 的記憶體釋放。 ```c int longestConsecutive(int *nums, int n_size) { int hash, length = 0; struct seq_node *node; struct list_head *heads = malloc(n_size * sizeof(*heads)); for (int i = 0; i < n_size; i++) INIT_LIST_HEAD(&heads[i]); for (int i = 0; i < n_size; i++) { if (!find(nums[i], n_size, heads)) { hash = nums[i] < 0 ? -nums[i] % n_size : nums[i] % n_size; node = malloc(sizeof(node)); node->num = nums[i]; list_add(&node->link, &heads[hash]); } } for (int i = 0; i < n_size; i++) { int len = 0; int num; node = find(nums[i], n_size, heads); while (node) { len++; num = node->num; list_del(&node->link); free(node); int left = num, right = num; while ((node = find(--left, n_size, heads))) { len++; list_del(&node->link); free(node); } while ((node = find(++right, n_size, heads))) { len++; list_del(&node->link); free(node); } length = len > length ? len : length; } } free(heads); return length; } ``` #### 分析結果 解決 memory leak 問題 ![](https://i.imgur.com/TbjPHj9.png) ### 以 Linux 核心風格的 hash table 重新實作 ```c #include <stddef.h> #include <stdlib.h> #include <stdio.h> struct hlist_node { struct hlist_node *next, **pprev; }; struct hlist_head { struct hlist_node *first; }; typedef struct { int size; struct hlist_head *ht; } map_t; struct hash_key { int key; struct hlist_node node; }; map_t *map_init(int size) { map_t *map = malloc(sizeof(map_t)); if (!map) return NULL; map->size = size; map->ht = malloc(sizeof(struct hlist_head) * size); if (map->ht) { for (int i = 0; i < size; i++) (map->ht)[i].first = NULL; } else { free(map); map = NULL; } return map; } #define container_of(ptr, type, member) \ ({ \ void *__mptr = (void *) (ptr); \ ((type *) (__mptr - offsetof(type, member))); \ }) static struct hash_key *find_key(map_t *map, int key) { int hash = key < 0 ? -key % map->size : key % map->size; struct hlist_head *head = &(map->ht)[hash]; for (struct hlist_node *p = head->first; p; p = p->next) { struct hash_key *kn = container_of(p, struct hash_key, node); if (kn->key == key) return kn; } return NULL; } void map_add(map_t *map, int key) { struct hash_key *kn = find_key(map, key); if (kn) return; kn = malloc(sizeof(struct hash_key)); kn->key = key; int hash = key < 0 ? -key % map->size : key % map->size; struct hlist_head *h = &map->ht[hash]; struct hlist_node *n = &kn->node, *first = h->first; n->next = first; if (first) first->pprev = &n->next; h->first = n; n->pprev = &h->first; } void map_del_node(struct hlist_node *n) { struct hlist_node *next = n->next, **pprev = n->pprev; *pprev = next; if (next) next->pprev = pprev; n->next = NULL, n->pprev = NULL; } int longestConsecutive(int *nums, int n_size) { int length = 0; struct hash_key *node; map_t *map = map_init(n_size); for (int i = 0; i < n_size; i++) { if (!find_key(map, nums[i])) { map_add(map, nums[i]); } } for (int i = 0; i < n_size; i++) { int len = 0; int num; node = find_key(map, nums[i]); while (node) { len++; num = node->key; map_del_node(&node->node); free(node); int left = num, right = num; while ((node = find_key(map, --left))) { len++; map_del_node(&node->node); free(node); } while ((node = find_key(map, ++right))) { len++; map_del_node(&node->node); free(node); } length = len > length ? len : length; } } free(map->ht); free(map); return length; } ```
Last changed by  
 
陳彥甫
727

Read more

實作 Thread package

contributed by < qwe661234 >

10/8/2023
Cache Coherency & I/O ordering

在多處理器的機器上，每個 CPU 都有自己的 cache，以彌補 CPU 和主記憶體(Main memory) 之間較慢的存取速度，當一個特定資料首次被特定的 CPU 讀取時，此資料顯然不存在於該 CPU 的 cache 中 (即 cache miss)，意味著 CPU 需要自主記憶體中讀取資料 (為此，CPU 通常要等待數百個 cycle)，此資料最終將會存放於 CPU 的 cache 中，這樣後續就能直接自 cache 上快速存取，不需要再透過主記憶體。因為每個 CPU 上的 cache 資料是 private 的，因此在進行寫入操作時，會造成其他 CPU 上的 cache 資料不一致的問題。

10/2/2023
CO Final

(15pt) 1. Assume there is no forwarding in a 5-stage pipline processor 1 (1) (5pt) Please indicate all the potential hazards in the following instruction sequence ? xori x1, x1, 2 addi x6, x5, -4 lw x10, 8(x6) add x5, x6, x6 sub, x2, x2, x1 Ans: addi && lw (2.5pt)

6/8/2023
New EBB Strategy

考量到 JIT 中 codegen 以及 compilation 的 overhead 過高，我們需要讓一個 EBB 含有更多的指令，理想是希望將一整個 loop body 涵蓋在一個 EBB 中。 我們參考 rvemu， rvemu 先將 block 以 unconditional jump 作切分，接著將其 block 中所有 branch taken 會走到的 block 都涵蓋進來，一個 block 含有大量的指令且有好的效能表現。 我們的新策略也是希望一個 block 中含有大量的指令，所以我們 trace 整個 control flow graph 並把 trace 過的 block 都涵蓋進來。 control flow graph 的終點有兩種情形，一種是 unconditional jump，而另一個則是遇到 back edge，也就是指向已經 trace 過的節點，下圖展示一個簡單的 EBB 案例。 過去的策略我們是直接指向某個 block 的 ir，一旦 block 被 cache 置換掉，EBB 就會變小。過去的另一個策略是用 memcpy，然而頻繁的 memcpy 成本過高，導致效能沒有很好的提昇。於是我們選用成本較低的 instruction fetch & decode，將 trace 到的 block 使用 instruction fetch & decode 存到 EBB 中，這個作法也不用擔心其他 block 被 cache 置換掉使 EBB 變小的問題。 另外，過去 EBB 有兩種版本，一種是 for interpter 而另一種是 for JIT 的，這導致作 JIT 時還要重新 extend 一次，現在則統一一種版本。 original EBB vs new EBB 指令數量

5/10/2023
Read more from 陳彥甫
Published on HackMD