郭育軒

@yxguo

Joined on Jun 6, 2019

  • Pointer to Pointer Pointer to pointer 有一個很重要的應用 - 更改變數的 life time : 因為C裡面的函式都是 ==call by value==,可以說在 function 裡面操作的 parameter 都是原始 object 的「複本」,出了function後原本object的value還是不會改變。 因此很多時候我們必須寫func(&var)傳入 object 的地址,讓 function 內部可以更改原始 object 的內容。 舉例來說,如果是一個linked list要刪除head,有兩種做法 list = list_del_head(list); list_del_head(&list); 但是第一種作法很麻煩,因為你需要每次都去更新你的linked list的指標。 而第二種做法就可以很好的==實現ADT(Abstract Data Type)== - 你可以不用管function裡面的實作細節,你只需要知道「list變數中紀錄的head被刪除了」這個結果。
     Like 1 Bookmark
  • 你可能沒想過的 Memory malloc有可能不成功,即便回傳valid pointer也不一定能用! 因為當我們 malloc() 的時候,記憶體預設是允許==overcommit==的,如果記憶體實際有32MB,但你可以malloc遠超32MB。 但這可能會導致非常糟糕的結果 - 宣告時沒事,但真去操作時卻會把任意 process 殺掉。 alloc 給 valid pointer不要太高興,等你要開始用的時候搞不好作業系統給個 OOM。簡單來說就是一張支票,能不能拿來開等到兌現才知道 OOM Killer (Out-Of-Memory Killer),他會在沒有記憶體不夠用時會被喚醒,並砍掉一些 process 以釋放記憶體給你用。 但你無法確定到底哪些會被砍,甚至連你自己都會被砍。 所以也有人認為這個從 overcommit 到 OOM Killer 的機制根本就是個Bug mlock : mlock要求(不一定會被O.S接受)特定記憶體區塊常駐於此,而不會被置換 ( swap out ) 到硬碟的/swap裡面。
     Like  Bookmark
  • 編碼發展過程 符號與值 ↓ 一補數 改良 - 電路設計簡單 去掉了「符號」的表示位元,也就代表不需要有獨立電路將MSB分開來判斷,因而簡化電路 任何減法運算都可以替換成另一種形式的加法運算 => 不需要專門設計「減法器」,也不需要執行減法那繁瑣的借位運算
     Like  Bookmark
  • symbol : 人類可以看懂得自對應到一個記憶體位址 程式通常不會直接操控記憶體,而是操控虛擬記憶體,虛擬記憶體才會再 mapping 到實體記憶體空間。 而這些虛擬記憶體的單元就稱為==MMU==,Memory Managment Unit : 基本觀念 : 每個function都對應到一個記憶體上的地址 通常function call都是==有來有回== ( 雖然也有例外 ),比如 funcA() -> funcB()。 那當function B執行完後,他必須想辦法回到原本的function A裡面,並接續原本中斷的地方繼續執行下去。這也就代表在離開A前往B之前,需要先將原本的一些data記錄下來,比如 : return address、argument、variable(畢竟B已經離開A的生命週期),而這些資料就會統整放在記憶體的stack裡面,稱為一個==stack frame== brk、sbrk(program break) : 改變程式data在記憶體的空間。 ==malloc/free==實際上就是用sbrk做的。
     Like  Bookmark
  • 作業要求 從 課程簡介和注意須知, 第 1 週測驗題 選出你感興趣的 3 個題組進行作答,並且回答附帶的「延伸問題」 應當包含 課程簡介和注意須知 的 Page 9 到 Page 16 裡頭的 C 語言程式設計議題 比照 課前測驗參考解答: Q1 和 對 Linked List 進行氣泡排序 的模式來撰寫共筆,需要詳細分析自己的想法、參閱的材料 (包含 C 語言規格書的章節),以及==進行相關實驗== 閱讀 第一週課程進度 所有材料,記錄所見所聞並提問,若有不能理解的部分,請標註出來。善用 HackMD 的語法 :::info 和 ::: 標註你的提問 :::info 像是這樣標註提問
     Like  Bookmark
  • contributed by < yxguo2536 > 課程簡介和注意須知 C 語言: 指標篇 C 語言: 函式呼叫篇 解讀計算機編碼 C 語言: 記憶體管理、對齊及硬體特性篇
     Like  Bookmark
  • --- tags: sysprog --- # 2019q3 Homework5 (quiz5) contributed by < `rageNami` `yxguo2536` > ## 測驗 `1` ### [Quotient Filters](https://en.wikipedia.org/wiki/Quotient_filter) 請詳細觀看 San Diego State University 的 Rob Edwards 教授的解說影片: [Counting Quotient Filters](https://youtu.be/oMFHkuVoF70) (可開字幕)。 一般的 Bloom filter 存在以下問題: * The inability to delete items * Poor scaling out of RAM * The inability to resize dynamically * The inability to count the number of occurrences of each item, especially with
     Like  Bookmark
  • --- tags: sysprog --- # 2019q3 Homework5 (quiz7) contributed by < `yxguo2536` > ### 測驗 `1` 考慮貌似簡單卻蘊含實作深度的 [FizzBuzz](https://en.wikipedia.org/wiki/Fizz_buzz) 題目: * 從 1 數到 n,如果是 3的倍數,印出 "Fizz" * 如果是 5 的倍數,印出 "Buzz" * 如果是 15 的倍數,印出 "FizzBuzz" * 如果都不是,就印出數字本身 直覺的實作程式碼如下: (`naive.c`) ```cpp #include <stdio.h> int main() { for (unsigned int i = 1; i < 100; i++) { if (i % 3 == 0) printf("Fizz"); if (i % 5 == 0) printf("Buzz"); if (i % 15 == 0) printf("FizzBuzz");
     Like  Bookmark
  • --- tags: sysprog --- # 2019q3 Homework5 (dict) contributed by < `yxguo2536` > ## 使用 test_common.c 統合 test_ref.c 和 test_cpy.c 以 `diff test_ref.c test_cpy.c` 比較 `test_ref.c` 和 `test_cpy.c` 之間的差別: 1. output 檔案不同 ```c 20c20 < #define BENCH_TEST_FILE "bench_ref.txt" --- > #define BENCH_TEST_FILE "bench_cpy.txt" ``` ```c 77c74 < output = fopen("ref.txt", "a"); --- > output = fopen("cpy.txt", "a"); ``` 2. error 訊息不同,但此處應該是 test_ref.c 原本寫錯了。 ```c 45c45 < fprintf(stderr, "error: file
     Like  Bookmark
  • --- tags: sysprog --- # 2019q3 Homework3 (list) ## Merge Sort 實做與效能分析 根據理論分析,我們知道在平均狀況下,Merge Sort 與 Quick Sort 的表現差不多,而 Insertion Sort 的表現會比前兩者差: | 排序法 | 最佳 | 平均 | 最差 | | ---------- | ---------- | --------- | --------- | | insert sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | | Quick Sort | $O(nlgn)$ | $O(nlgn)$ | $O(n^2)$ | | Merge Sort | $O(nlgn)$ | $O(nlgn)$ | $O(nlgn)$ | 而以亂數產生的 linked list 數列做排序實驗,也確實呈現出同樣的趨勢 ![](https://i.imgur.com/MeKaDcZ.png) 但光看
     Like  Bookmark
  • --- tags: sysprog --- # 2019q3 Homework2 (quiz2) contributed by < `yxguo2536` > ## 測驗6 延伸測驗 `5`,實作 branchless 的 `popcnt` 並附上對應的程式原理解說。 :::success 延伸問題: 1. 指出 `popcnt` 的應用場景; 2. 在 Linux 核心程式碼找出具體用法並解析; ::: --- ### 原理 參考 [Hamming weight - Wikipedia](https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation) 的範例: :::danger 用 HackMD 內建的表格語法改寫下方 :notes: jserv ::: <table> <thead> <tr> <th>Expression</th> <th>Binary</th> <th>Decimal</th> <th>Comment
     Like 3 Bookmark
  • --- tags: sysprog --- # 2019q3 Homework1 (lab0) contributed by < `yxguo2536` > ## 實驗環境 作業系統 : Ubuntu 18.04.3 gcc 編譯器 :gcc 7.4.0 ## 實做 根據 C Programming Lab 要求,修改 queue.c 的以下 function和 queue.h 的 資料結構: 1. typedef struct queue_t 2. q_new 3. q_free 4. q_insert_head 5. q_insert_tail 6. q_remove_head 7. q_size 8. q_reverse ### sturct queue_t 原本的 queue_t 為 : ```clike typedef struct { list_ele_t *head; } queue_t; ``` 而後為了實做 $O(1)$ 的 q_insert_tail 和 q_size,增加了2個成員 : ```clike typedef struct {
     Like  Bookmark