# 2023q1 Homework1 (lab0) contributed by < `SPFishcool` > ## 開發環境 ```shell $ neofetch --stdout OS: Ubuntu 22.04.1 LTS x86_64 Host: GL552VW 1.0 Kernel: 5.15.0-60-generic Uptime: 13 hours, 20 mins Packages: 1877 (dpkg), 9 (snap) Shell: bash 5.1.16 Resolution: 1920x1080 DE: GNOME 42.5 WM: Mutter WM Theme: Adwaita Theme: Yaru [GTK2/3] Icons: Yaru [GTK2/3] Terminal: gnome-terminal CPU: Intel i5-6300HQ (4) @ 3.200GHz GPU: Intel HD Graphics 530 GPU: NVIDIA GeForce GTX 960M Memory: 3626MiB / 11868MiB $ gcc -v Thread model: posix Supported LTO compression algorithms: zlib zstd gcc version 11.3.0 (Ubuntu 11.3.0-1ubuntu1~22.04) ``` ## lab0 資料架構認識 ### list_head - list_head 負責作為鏈結串列將其 entry 串連在一起，其為 Circular Doubly-linked list 類型 :::warning 注意書寫: doubly-linked list，連字號的位置在 doubly 和 linked 之間。 :notes: jserv ::: ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; subgraph cluster_0 { head [label="{<prev>prev|<next>next}"]; color=invis; label=list_head } } ![](https://i.imgur.com/8XRDf8u.png) ``` - list_head架構圖 :::warning 使用 Graphviz 製圖並嵌入到 HackMD 頁面。 :notes: jserv 收到！正在改進中！ ::: - list_head的struct為： ```c struct list_head { struct list_head *prev; struct list_head *next; }; ``` ### element_t - `element_t` 為佇列儲存 value，內部有 `list_head` 架構的 list 能夠將所有 `element_t` 串接起來 ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; subgraph cluster_0 { value [label="{*value}"]; list [label="list", shape=plaintext] head [label="{<prev>prev|<next>next}"]; label=element_t; } } ``` - element_t 架構圖 - element_t 的 struct 為： ```c typedef struct { char *value; struct list_head list; } element_t; ``` - 因此 lab0 實做的佇列結構會是 ![](https://i.imgur.com/2NomHmV.png) ### queue_chain_t - 在執行 [qtest.c](https://github.com/SPFishcool/lab0-c/blob/master/qtest.c) 時，會先 create 一個 `queue_chain_t` 結構的物件，其功用類似上述佇列結構的 **head**，目的是每當 `q_new` 一個新的佇列時會將新的佇列利用 list_add_tail 加入到 `queue_chain_t` 鏈結串列的最後面。 >![](https://i.imgur.com/96FnpoC.png) >queue_chain_t 架構圖，size 為佇列的數量 ```c typedef struct { struct list_head head; int size; } queue_chain_t; ``` ### queue_contex_t - `queue_contex_t` 在紀錄每一條佇列的資訊，`*q` 為 pointer of queue head，`size` 是佇列裡面 element_t 的數量，`chain` 為與其他 `queue_contex_t` 串連的 `list_head`。 >![](https://i.imgur.com/80aWxMq.png) >queue_contex_t架構圖 ```c typedef struct { struct list_head *q; struct list_head chain; int size; int id; } queue_contex_t; ``` - 再加入 `queue_chain_t` 其完整佇列架構就完成了！ >![](https://i.imgur.com/NuEJyGr.png) >queue 為上圖的紅色虛線部份 ## lab0 開發過程 ### q_new `q_new()` 會先配置 `list_head` 大小的記憶體位置，接下來判斷是否配置成功，最後 `INIT_LIST_HEAD(new)` 會將這個 node 接回自己（成為 Doubly-linked list 型態）。 ![](https://i.imgur.com/Qvdzk6d.png) ```c struct list_head *q_new() { struct list_head *new = malloc(sizeof(struct list_head)); // check if space allowed if (!new) return NULL; INIT_LIST_HEAD(new); return new; } ``` ### q_free `q_free()` 從 `head->next` (第一個有entry的節點)開始釋放，直到回到 head 最後釋放 head 節點。 ```c void q_free(struct list_head *l) { if (!l) return; struct list_head *indirect = l->next; struct list_head *tmp = NULL; while (indirect != l) { tmp = indirect; indirect = indirect->next; q_release_element(list_entry(tmp, element_t, list)); } free(l); } ``` ### q_insert_head / q_insert_tail 兩者可以使用 [list.h](https://github.com/SPFishcool/lab0-c/blob/master/list.h) 中的 `list_add` 與 `list_add_tail` 將 `element_t` 內的list加入鏈結串列中。 ```c bool q_insert_head(struct list_head *head, char *s) { if (!(head && s)) return false; element_t *new_ele = malloc(sizeof(element_t)); if (!new_ele) return false; new_ele->value = (char *) malloc(strlen(s) * sizeof(char) + 1); if (!new_ele->value) { free(new_ele); return false; } strncpy(new_ele->value, s, strlen(s) + 1); // struct list_head *new_node = (new_ele -> list); list_add(&new_ele->list, head); return true; } ``` ### q_remove_head/q_remove_tail remove 只有將 element_t 的串列節點從佇列中移除並沒有釋放其空間，因此只需要將其 next 與 prev 連接起來即可移除。 ```c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; struct list_head *indirect = head->next; //or head->prev (q_remove_tail) list_del(indirect); element_t *ele = list_entry(indirect, element_t, list); if (sp) { strncpy(sp, ele->value, bufsize-1); *(sp+bufsize-1) = '\0'; } return ele; } ``` ### q_size `q_size` 則從 `head->next` 開始計算這條佇列的 `element_t` 數量，並且回傳 `i` (count 後的結果) ```c int q_size(struct list_head *head) { if (!head) return -1; struct list_head *indirect = head->next; int i = 0; while (indirect != head) { i++; indirect = indirect->next; } return i; } ``` ### q_delete_mid 因為佇列是 doubly-linked list 結構，因此可以使用左右指標（最左和最右可以快速找到），其原理是每一迴圈 `left_node` 往右走一步，`right_node` 往左走一步，直到兩指標相遇（奇數 element）或相鄰（偶數 element）時 right_node 就是我們要找的節點。 優點：跟快慢指標相比，迴圈節省了一半的次數（僅限 Circular Doubly-linked list）。 ![](https://i.imgur.com/m7wqbwr.png) ```c bool q_delete_mid(struct list_head *head) { while(!head || list_empty(head)) return false; struct list_head *left_node = head->next; struct list_head *right_node = head->prev; while ((left_node->next != right_node) && (left_node != right_node)) { left_node = left_node->next; right_node = right_node->prev; } list_del(right_node); q_release_element(list_entry(right_node, element_t, list)); return true; } ``` ### q_delete_dup `q_delete_dup` 這個 question 我紀錄此次和前次的比較紀錄，而受到「判決」的節點為 `indirect->prev`(目前指到的節點的前一個節點) - `cmp`：`indirect` 與 `indirect->prev` 的比較結果 - `prev_cmp`：`indirect->prev` 與 `indirect->prev->prev` 的比較結果 ![](https://i.imgur.com/5lbM3Lc.png) 不管是 `cmp` 還是 `prev_cmp` 只要為 0 都代表著**中間這個節點的 value 與前後節點重複**，必刪除！ ```c bool q_delete_dup(struct list_head *head) { if (!head || list_empty(head)) return false; struct list_head *indirect = (head->next)->next; element_t *prev_ele = NULL; element_t *current_ele = NULL; int cmp = -1, prev_cmp = -1; while (indirect != head) { prev_ele = list_entry(indirect->prev, element_t, list); current_ele = list_entry(indirect, element_t, list); cmp = strcmp(prev_ele->value, current_ele->value); if (cmp == 0 || prev_cmp == 0) { list_del(indirect->prev); q_release_element(prev_ele); } prev_cmp = cmp; indirect = indirect->next; } if (cmp == 0) { list_del(indirect->prev); q_release_element(current_ele); } return true; } ``` ### q_swap `q_swap` 只要將佇列內的 element 兩兩交換即可，因此只需要使用 [list.h](https://github.com/SPFishcool/lab0-c/blob/master/list.h) 中的 `list_move` 把自己搬到 `next` 後面即可 ```c void q_swap(struct list_head *head) { if (!head || list_empty(head)) return; struct list_head *indirect = head->next; while (indirect != head && indirect->next != head) { list_move(indirect, indirect->next); indirect = indirect->next; } } ``` ### q_reverse 這裡則是使用 pointer to pointer 紀錄第一個 element 節點內的 next 位址（`&head->next->next`），在每次迴圈中將 `next` 指到的節點利用 `list_move` 移到 `head` 前面直到 `next` 指向的位置為 `head` 為止。 ```c void q_reverse(struct list_head *head) { if (!head || list_empty(head)) return; struct list_head **indirect = &((head->next)->next); while (*indirect != head) list_move(*indirect, head); } ``` ### q_reverseK `q_reverseK` 其原理與 `q_reverse` 相似，但因為如果後面個數不足 k 個則不做 reverse，因此我的作法是先讓一個指標邊走邊數，數到第 k 個後，再將後面的節點一一搬到前面來，因此如果走完一圈沒有數到 k 個，剩下的節點就不會動到。 ```c void q_reverseK(struct list_head *head, int k) { if (!head || list_empty(head)) return; struct list_head **indirect = &(head->next); struct list_head *current = head->next; struct list_head *tmp = NULL; int i = 1; while (current != head) { if (i % k == 0) { tmp = current; while (*indirect != tmp) { list_move(tmp->prev, current); current = current->next; } indirect = &((current)->next); } current = current->next; i++; } } ``` ### q_sort 參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)merge_sort寫法。 原先想法是要維持 doubly-linked list 的結構去設計，但當我要 `malloc` 新的 head 來接分割後的子串列時遇到`ERROR:Calls to malloc disallowed`，因此決定將 circular 斷開將最後一個 node 的`prev`指向`NULL`才進行`mergesort`並且在排序後將排序過後的串列重新接上 head。 ```c void q_sort(struct list_head *head) { if (!head || list_empty(head)) return; struct list_head *start = head->next; struct list_head *tail = head->prev; tail->next = NULL; struct list_head *sorted_list = merge_sort(start); head->next = sorted_list; struct list_head *cur = head; while (cur->next) { cur->next->prev = cur; cur = cur->next; } cur->next = head; head->prev = cur; } ``` ```c struct list_head *mergeList(struct list_head *l1, struct list_head *l2) { struct list_head *head = NULL; struct list_head **current = &head; while (l1 && l2) { if (strcmp(list_entry(l1, element_t, list)->value, list_entry(l2, element_t, list)->value) >= 0) { *current = l2; l2 = l2->next; } else { *current = l1; l1 = l1->next; } current = &((*current)->next); } *current = (struct list_head *) ((__intptr_t) l1 | (__intptr_t) l2); return head; } ``` ```c struct list_head *merge_sort(struct list_head *head) { if (!head || head->next == NULL) return head; struct list_head *slow = head; for (struct list_head *fast = head->next; fast && fast->next; fast = fast->next->next) { slow = slow->next; } struct list_head *list2 = slow->next; slow->next = NULL; return mergeList(merge_sort(head), merge_sort(list2)); } ``` ### q_descend `q_descend` 若是 `prev` 方向有比自己小的節點則這些小的節點都要 delete 掉，直到遇到下一個比自己大的節點，則移動到下一個節點(`prev`) ```c int q_descend(struct list_head *head) { if (!head || list_empty(head)) return 0; struct list_head *current = head->prev; struct list_head *cur_prev = current->prev; while (cur_prev != head) { if (strcmp(list_entry(current, element_t, list)->value, list_entry(cur_prev, element_t, list)->value) > 0) { list_del(cur_prev); q_release_element(list_entry(cur_prev, element_t, list)); } else { current = current->prev; } cur_prev = current->prev; } int len = q_size(head); return len; } ``` ### q_merge 在 [qtest.c](https://github.com/SPFishcool/lab0-c/blob/master/qtest.c) 裡執行`q_merge`其程式碼為 ```c len = q_merge(&chain.head); ``` 這個 chain 其實就是 `queue_chain_t` 結構，所以得知輸入的資料為 `queue_chain_t` 內的 `head` 元素因此我們可以很簡單的拜訪所有佇列再使用[list.h](https://github.com/SPFishcool/lab0-c/blob/master/list.h)中的 `list_splice_init` 從第二個佇列到最後一個一一串在 ~~`id=0`~~ 目前第一個 `queue_contex_t->q` 的串列內。 ```c int q_merge(struct list_head *head) { if(!head || list_empty(head)) return 0; else if(list_is_singular(head)) return list_entry(head->next, queue_contex_t, chain)->size; queue_contex_t *target = list_entry(head->next, queue_contex_t, chain); queue_contex_t *que = NULL; list_for_each_entry (que, head, chain) { if (que == target) continue; list_splice_init(que->q, target->q); target->size = target->size + que->size; que->size = 0; } q_sort(target->q); return target->size; } ``` ## 目前 queue.c 靜態與動態評分 ### make test - score: 95/100 - problem: q_insert 系列程式時間複雜度非 constant time ### make valgrind - score: 94/100 - problem: Test of malloc failure on new 測試未通過 - reason：在 `qtest` 執行結束未妥善釋放其程式所配置的記憶體所導致 - solved: 在研讀[Valgrind + 自動測試程式](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-b#%E4%BB%A5-Valgrind-%E5%88%86%E6%9E%90%E8%A8%98%E6%86%B6%E9%AB%94%E5%95%8F%E9%A1%8C)後發現大部分的test其實都在記憶體配置上出現問題，例如： ```bash ==104151== 128,000 bytes in 2,000 blocks are still reachable in loss record 4 of 6 ==104151== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==104151== by 0x10F110: test_malloc (harness.c:133) ==104151== by 0x10F645: q_insert_tail (queue.c:72) ==104151== by 0x10C62B: do_it (qtest.c:312) ==104151== by 0x10DDFA: interpret_cmda (console.c:181) ==104151== by 0x10E3AF: interpret_cmd (console.c:201) ==104151== by 0x10E7B0: cmd_select (console.c:610) ==104151== by 0x10F09C: run_console (console.c:705) ==104151== by 0x10D1EC: main (qtest.c:1223) ``` 而上述 problem 的錯誤為： ```bash ==104070== 160 bytes in 5 blocks are possibly lost in loss record 3 of 3 ==104070== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==104070== by 0x10CBCE: do_new (qtest.c:145) ==104070== by 0x10DDFA: interpret_cmda (console.c:181) ==104070== by 0x10E3AF: interpret_cmd (console.c:201) ==104070== by 0x10E7B0: cmd_select (console.c:610) ==104070== by 0x10F09C: run_console (console.c:705) ==104070== by 0x10D1EC: main (qtest.c:1223) ``` 在這情況下我決定先嘗試解決比較輕的問題，解決過程如下： - 檢查 queue.c 是否有哪一個功能沒有完全 free 空間 - 檢查 script 資料夾內的 cmd 檔案，發現沒有此問題的腳本都有執行 free。 - 開始檢查 [qtest.c](https://github.com/SPFishcool/lab0-c/blob/master/qtest.c) 的退出程式發現： ```c static bool q_quit(int argc, char *argv[]) { return true; report(3, "Freeing queue"); if (current && current->size > BIG_LIST_SIZE) set_cautious_mode(false); if (exception_setup(true)) { struct list_head *cur = chain.head.next; while (chain.size > 0) { queue_contex_t *qctx, *tmp; tmp = qctx = list_entry(cur, queue_contex_t, chain); cur = cur->next; q_free(qctx->q); free(tmp); chain.size--; } } ``` 發現 `do_quit` 第一行程式碼即 `return true` 表示下方程式完全沒有走過，註解掉後重新 `make valgrind` 所有問題都解決了。 ## 研讀 Linux 核心原始程式碼的 lib/list_sort.c 在 linux 核心原始程式碼內的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 所作的 sort 為 **Merge Sort** ，但這裡面的 Merge Sort 跟我們以前認識的 Merge Sort 不同。 在 `list_sort` 內有 3 個 Function - `merge` - `merge_final` - `list_sort` 而走訪 linked list 時會使用 count 會計算目前走訪到的節點數量，一旦走訪數量走到 $2^k$ 數量時不執行 `merge`，反之就會執行 merge。其流程如下 1. 一開始 `list` 從 `head->next` 開始，而 `pending` 起始為 `NULL`，`count` 起始為 `0`，linked list 最後指向 `NULL`。 2. 迴圈開始，宣告 `**tail`指向 `pending` 的位址。 3. 會先計算 `count` 是否為 $2^k-1$ ，如果是，跳到 "7."。 4. 準備 `merge` ，將 `a = *tail`、`b = a->prev`，執行 `merge(priv, cmp, b, a);` 5. `merge` 會有一個 `**tail` 紀錄前一次比較最小的節點的 `next` 位址，每一次比較會把 `*tail` 指向較小的節點，**其實就是一般的merge，這裡就把 `next` 拿來做 merge 的主要 link。** 6. merge return 為 merge 後的第一個節點（最小）存入 `a` ，將目前的 `a->prev` 重指成 `b->prev`，藉由 `*tail` 把 `pending` 指向 `a`（merge 起始節點）。 7. 將 `list->prev` 指向 `pending`，`list` 往前一步， `panding = list->prev`， 把 `pending->next` 指向 `NULL`。 8. 若 `list` 還沒走完，回到 "2." 9. merge 剩下還沒 merge 起來的 pending list。 10. 最後 `merge_final` 把 merge 完的 list 將其 `prev` 連接起來。 看完 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 發現他並沒有特別做 divide 而是走訪過程一一將 `next` 斷開並且把 `next` 當成執行 merge 動作時走訪的 link，比較「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)」所提及的遞迴與非遞迴，此做法省去 divide 這一部份，也沒有使用 stack 有 Max Depth 的限制。 ## 引入 lib/list_sort.c 到 lab0-c 專案 - 在 [qtest.c](https://github.com/SPFishcool/lab0-c/blob/master/queue.c) 新增 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 三條 finction 和引入 [list_sort.h](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h) 內宣告設定 - 參考[lab 0:Valgrind + 自動測試程式](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-b)中的 qtest 直譯器實作，使用 `ADD_COMMAND` 新增剛才加入的 `list_sort`， 再依照檔案裡的 `do_sort` 新增 `do_list_sort` ```c ADD_COMMAND(list_sort, "Sort queue in ascending order by list_sort", ""); ``` - 製作分析準備 ### 利用 perf 分析 `list_sort` 與自己做的 `q_sort` 效能比較 參考 [linhoward0522 開發紀錄 (lab0)](https://hackmd.io/@linhoward/lab0-2023#2023q1-Homework1-lab0) 使用 perf 分析其效能，在 [traces/trace-15-perf.cmd](https://github.com/SPFishcool/lab0-c/blob/master/traces/trace-15-perf.cmd) 有三筆資料來測試排序，因此我們可以依照這個檔案自製用來測試的 cmd 檔。 ``` . ├── RAND-1000000-list.cmd ├── RAND-1000000-q.cmd ├── RAND-100000-list.cmd ├── RAND-100000-q.cmd ├── RAND-10000-list.cmd ├── RAND-10000-q.cmd ├── RAND-1000-list.cmd └── RAND-1000-q.cmd ``` `q` : `q_sort` `list` : `list_sort` 接下來是試做 `shell scripts` ```bash #!/bin/bash # q_sort for i in ./traces/perf_traces/RAND-*-q.cmd do perf stat --repeat 5 -o "${i%.cmd}"-report -e cache-misses,branches,instructions,context-switches ./qtest -v 0 -f "$i" done #list_sort for i in ./traces/perf_traces/RAND-*-list.cmd do perf stat --repeat 5 -o "${i%.cmd}"-report -e cache-misses,branches,instructions,context-switches ./qtest -v 0 -f "$i" done ``` - `q_sort` | #node | cache-misses | branches | instructions | context-switch | | ------- | ------------ | ----------- | ------------ | -------------- | | 1000 | 3469 | 77,9884 | 516,0401 | 0 | | 10000 | 3,3403 | 621,9374 | 4305,8950 | 0 | | 100000 | 543,0532 | 6326,2119 | 4,3295,3471 | 0 | | 1000000 | 7491,5547 | 4,6974,1917 | 31,6153,3055 | 10 | - `list_sort` | #node | cache-misses | branches | instructions | context-switch | |-------|--------------|----------|--------------|-----------------| |1000|2489|77,7798|519,9240|0| |10000|4,1257|614,2028|4329,3845|0| |100000|439,1922|6258,0696|4,3642,0292|3| |1000000|5824,6891|4,6028,3507|31,6579,3448|9| 可以看到節點數增多，效能差異越大，雖然 RAND 會導致偶爾會讓 `list_sort` 效能看起來跟 `q_sort` 差不多甚至更差，但時間上還是 `list_sort` 略勝一籌。 ## 在 [qtest.c](https://github.com/SPFishcool/lab0-c/blob/master/qtest.c) 新增 `shuffle` 命令 作業要求為使用「Fisher–Yates shuffle」完成 `shuffle`，其原理就是從最後一個節點開始，隨機選取前面的節點與其交換，交換完後再往前一格完成前面敘述的事情直到第二張牌為止。 ```c for (int i = len-1;i > 0;i--) { //random 1~i int count = rand() % i; struct list_head *node = head->next; for (int j=1; j < count;j++) node = node->next; swap(tail, node); tail = node->prev; } ``` 跟設定 `list_sort` 一樣，新增 `do_shuffle` 與 `ADD_COMMAND` ```c ADD_COMMAND(shuffle, "shuffle queue.", ""); ``` 接下來統計剛設計出來的 `shuffle` 亂度 參考 [L01: lab0 亂數+論文閱讀](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-d) 中的測試程式並載入 [Makefile](https://github.com/SPFishcool/lab0-c/blob/master/Makefile) 執行指令 ```makefile shuffle_check: qtest scripts/shuffle_test.py scripts/shuffle_test.py ``` 執行結果： ![](https://i.imgur.com/6nFK4rS.png) 依照 4 個數字的亂數來看，分佈差距大約在 $\pm1.2\%$ ，學生突然想到如果數字在多一點的話分佈會不會變化比較大，因此我將數字加到 6 個，而 6 個數字的排列組合比 4 個數字多出 30 倍，因此也將次數增加到 30000000 次。 執行結果： ![](https://i.imgur.com/MgJ8VzX.png) 在這張圖最少次為 41081，最多次為 42281，幅度有稍微增加，但沒有特別明顯。 ## 使用 entropy 觀察亂數 在認識 entropy 之前，對 entropy 的唯一認知就是機器學習中計算 loss 值的方式 `cross entropy`，發現其中的含意與 entropy 也有一些關係，但知道了「entropy 與亂數產生的資訊量成反比」還是覺得對 entropy 有點抽象，因此我打算從 qtest.c 裡的指令 `option entropy 1` 與 `ih RAND 10` 找出關於 entropy 的蛛絲馬跡，最後發現 [shannon_entropy.c](https://github.com/SPFishcool/lab0-c/blob/master/shannon_entropy.c) 裡的 `shannon_entropy` 實作了以下 entropy 公式。 $-\sum^{n}_{i=1} p(x_i)\log_2{p(x_i)}$ ```c for (uint32_t i = 0; i < BUCKET_SIZE; i++) { if (bucket[i]) { uint64_t p = bucket[i]; p *= LOG2_ARG_SHIFT / count; entropy_sum += -p * log2_lshift16(p); } } entropy_sum /= LOG2_ARG_SHIFT; return entropy_sum * 100.0 / entropy_max; ``` 這裡除了使用 bucket 計算每一個字元的熵值，而且使用 `LOG_ARG_SHIFT` 預計算的常數來避免使用浮點數增加計算時間。
Last changed by  
 
SPFishcool
500

Read more

4/16 一對一問題回復

linux 核心的 list_sort 實作考量 在 linux 核心的 list_sort 使用 buttom-up merge sort 實作排序，buttom-up 與 top-down 的差異在於 buttom-up 少了 partition 這一步驟。 此作法可以省去 recursive 和 stack 的使用（會佔用大量記憶體的寫法，並且會較常去 catch 記憶體更新 cache 內容） 其效能比較根據如下（q_sort 為 lab0-c 實作之排序）： q_sort#nodecache-missesbranchesinstructionscontext-switch1000346977,9884516,04010100003,3403621,93744305,89500100000543,05326326,21194,3295,3471010000007491,55474,6974,191731,6153,305510 list_sort#nodecache-missesbranchesinstructionscontext-switch1000248977,7798519,92400100004,1257614,20284329,38450100000439,19226258,06964,3642,0292310000005824,68914,6028,350731,6579,34489

5/8/2023
2023q1 Homework6 (quiz6)

contributed by < SPFishcool > 開發環境 $ neofetch --stdout fico@fico-mac ------------- OS: Arch Linux ARM aarch64 Host: Apple MacBook Air (13-inch, M2, 2022) Kernel: 6.2.0-asahi-11-1-edge-ARCH Uptime: 16 hours, 7 mins

4/27/2023
2023q1 Homework3 (fibdrv)

contributed by < SPFishcool > 開發環境 $ neofetch --stdout fico@fico-mac ------------- OS: Arch Linux ARM aarch64 Host: Apple MacBook Air (13-inch, M2, 2022) Kernel: 6.1.0-asahi-2-2-ARCH Uptime: 12 mins

3/20/2023
2023q1 Homework2 (quiz2)

contributed by < SPFishcool > 測驗一 運作原理 程式裡 next_pow2(x) 要找出最接近且大於等於 x 的 2 的冪次方的值。 在改寫程式裡，有著幾行類似下方的程式碼。 x |= x >> 1; 這會讓 x 右移一位並將 1 set 到原本的 x 上，例如： 00100000 變成 00110000、 00100110 變成 00110111。

3/13/2023
Read more from SPFishcool
Published on HackMD