2020 第四週測驗

--- title: 2020 第四週測驗 tags: _核心設計 breaks: true --- # 2020q1 Homework3 (quiz4) contributed by < [babysuse](https://github.com/babysuse) > [toc] ## 測驗 1 內容參見 [測驗題](https://hackmd.io/@sysprog/linux2020-quiz4#%E6%B8%AC%E9%A9%97-1) 對照 [程式碼 (附行號)](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/bitcpy.c) ### 簡而言之 - ==[KK1](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/bitcpy_commented.c#L19) = ?== 由 16、17 行 `read_lhs` 和 `read_rhs` 對照 19、20 行 `write_lhs` 和 `write_rhs`，讀多少寫多少，可以判斷 KK1 是 ==7==。 - ==[KK2](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/bitcpy_commented.c#L86) = ?== 由 47、49、77 行可以得知，`_count` 是要 copy 的 bits 長，而最多一次讀寫 8 bits，所以可以判斷 KK2 是一次讀寫的單位長 ==`bitsize`== ### 詳解程式碼及運作原理對照 [程式碼 (含註解)](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/bitcpy_commented.c) 看半天看沒很懂，圖解就一目了然，假設 - `offset = 2` - `_count = 43` (也就是跑了 6 次 iterations，而最後一次剩 `_count` 剩 3 bits)，運作原理大致如下 (數字代表第幾次的 iteration) |\_src / \_dest 1|\_src / \_dest 2|...|\_src / \_dest 6| |:-:|:-:|:-:|:-:| |<table><tr><td colspan="2" align="center"> offset </td><td colspan="6" align="center"> rhs </td></tr><tr><td>X</td><td>X</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr></table> | <table><tr><td colspan="2" align="center"> lhs </td><td colspan="6" align="center"> rhs </td></tr><tr><td>1</td><td>1</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td></tr></table> | <table><tr><td colspan="2" align="center"> lhs </td><td colspan="6" align="center"> ... </td></tr><tr><td>2</td><td>2</td><td>...</td></tr></table> | <table><tr><td colspan="2" align="center"> lhs </td><td colspan="6" align="center"> rhs </td></tr><tr><td>5</td><td>5</td><td>6</td><td>6</td><td>6</td><td>X</td><td>X</td><td>X</td></tr></table> :::danger 改用 Graphviz 製圖，參見: https://renenyffenegger.ch/notes/tools/Graphviz/examples/index HackMD 支援 Graphviz 語法，請多利用 :notes: jserv ::: 以下挑出對我而言比較費解的部份 - [16 行](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/bitcpy_commented.c#L16)用 bitwise operator `_read & 7` 來取代檢查式 `_read % 8`。由於 `uint8_t` 的關係，每個 element 只有 8 bits，所以每個 element 的 offset 最大允許到 7 位為止。 - 這裡的 offset 分成兩的部份，由於 uint8_t - rightmost 3 bits 的是 element 中的 bitwise 的 offset - 剩餘的以 8 為單位，就是 element-wise 的 offset 這就區分了 [16 行和 18 行](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/bitcpy_commented.c#L16#L18)，以及 [19 行和 21 行](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/bitcpy_commented.c#L19#L21)將 offset 的位元分開來操作差異了 - [17 行](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/bitcpy_commented.c#L17)由於 `uint8_t` 的關係，這裡的實作方式為一次最多讀寫 8 bits (也就是一個 element)，所以如上面示意圖 - lhs 寬度相當於 `offset` - rhs 寬度就等於 `8 - offset` - 緊接著兩個 `mask` - [24 行](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/bitcpy_commented.c#L24)的 `read_mask` 有兩個功能 - 在讀取 `_src` 的最後一個 iteration 時 (也就是 \_count 可能不足 8 時)，只需要讀取指定剩餘的 bits 數，像是 [62 行](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/bitcpy_commented.c#L62)。 - 在寫入 `_dest` 的 rhs 的時候用來保留 lhs 的部份，並清空 rhs 的部份，像是 [67 行](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/bitcpy_commented.c#L67)的 `mask`。 - [37 行](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/bitcpy_commented.c#L37)的 `write_mask` 主要功能就是 - 在寫入 `_dest` 的 lhs 的時候清空 lhs 的部份，並保留下一個 rhs 的部份，像是 [72 行](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/bitcpy_commented.c#L72)。 - 在寫入 `_dest` 的最後一次 iteration 時 (也就是 `_count` 可能不足 `_dest` 的 rhs 時)，用來保留最後不足 rhs 的部份，像是 [77 行](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/bitcpy_commented.c#L77)。 - 最後就是讀寫的部份了 - 從 [50 行到 63 行](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/bitcpy_commented.c#L50&#L63) 是讀取 `_src` - 從 [65 行到 83 行](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/bitcpy_commented.c#L50&#L63) 是寫入 `_dest` 基本上就是對照示意圖以及以上和程式碼註解說明去運作這裡就不再贅述。唯一的疑惑在於 [75、76 行從](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/bitcpy_commented.c#L75&#L76)註解掉的兩行看半天其實不能理解 mask 為甚麼要這樣設。就算最後一次的 iteration `bitsize` 不足 rhs，那反正就是繼續從 rhs 往下填就對了，跟 lhs 的寬度有甚麼關係？好比如果說到了最後一個 iteration 時，假設 - 第 N 個 iteration - `bitsize = 3` - offset (也就是 `lhs`) 為 4，那如下所示 <table> <tr> <td colspan="4" align="center"> lhs </td> <td colspan="3" align="center"> rhs </td> <td> one bit left (reserved) </td> </tr> <tr align="center"> <td>N-1</td><td>N-1</td><td>N-1</td><td>N-1</td><td>N</td><td>N</td><td>N</td><td>X</td> </tr> </table> 直接按照原本的 mask (`read_mask[write_lhs]` 也就是 (11110000)~2~ ) 就行，後面標為 X 的 bits 就算是要保留的話，那按我的理解 mask 應該設成如 [77 行](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/bitcpy_commented.c#L77)這樣。而這個問題在[這位同學](https://hackmd.io/@Hsuhaoxiang/quiz4#%E7%A8%8B%E5%BC%8F%E9%81%8B%E4%BD%9C%E5%8E%9F%E7%90%86)最後有先被提出，和我的想法一樣在於，我們的測資比較單純，而這個判斷式是針對一些比較特別的狀況才看得出來的功能。 ### 改寫: 等價、精簡、高效 - 首先，這是一個 bitwise 的操作，第一個讓我想到的方法是先把整個 `dest` 做 alignment，再直接複製，再移回去。只是 - 論及精簡層面，在撰寫過程中發現光是先將 `dest` 和 `source` 給對齊，篇幅就快要和原本的演算法一樣長； - 加上效能改進角度來考量，跟原本的相比，雖然複製過程中會減少許多判斷式和 element-wise 的操作，但畢竟原方法的迴圈只 traverse 一次，而這個方法複製加上兩次位移足足 traverse 了三次，所以作罷。 - 第二種方法，如果很直觀地想要直接複製就會遇到 `dest` 和 `source` 的 offset 沒對上的問題。 - 我想到的和這位[這位同學](https://hackmd.io/@eecheng/SyOd56BBI#%E6%94%B9%E5%96%84-bit-copy-%E7%9A%84%E6%95%88%E8%83%BD)提出了的方法類似，就是將頭尾不滿 8 bits 的狀況獨立出來處理，關鍵在 `_read - _write` 這個 `offset`。 - 第三種方法，還有想到單就原本的演算法去做精簡如同[這位同學](https://hackmd.io/@oscarshiang/linux_quiz4#%E6%94%B9%E5%AF%AB%E7%A8%8B%E5%BC%8F%E7%A2%BC)。 :::danger 應提及同學的 ID，不要只是「這位同學」。同時你該發布訊息給這兩位同學，透過修改共筆或留言。 :notes: jserv ::: - 以上兩位同學的實作都有缺陷，好比第一位沒有處理在 `_count` 很小的情況，和第二位好比在 `source` 已經到最後一個 element 的時候，`data = (*source++ << read_lhs) | (*source >> read_rhs);` 會有問題等。但暫時都還沒有實作出任何一個正確的版本，完成後補上。 ### 尋找在 linux 核心中類似應用情境我在 [linux 核心程式碼: drivers/video/fbdev/amifb.c](https://elixir.bootlin.com/linux/latest/source/drivers/video/fbdev/amifb.c#L2598) 中找到了有趣的應用情境，在最新版本的 linux 核心中實作的 bitcpy。這個 [fbdev](https://en.wikipedia.org/wiki/Linux_framebuffer) 的 fb 是 framebuffer 的縮寫，用來直接操作顯示卡中[影像記憶體](https://zh.wikipedia.org/wiki/VRAM) [(video memory)](https://en.wikipedia.org/wiki/Dynamic_random-access_memory#Graphics_RAM) 的 [video frame](https://en.wikipedia.org/wiki/Film_frame)，使得顯示圖像不需要透過 [overhead](https://en.wikipedia.org/wiki/Overhead_(computing)) 比較大的 [X Window System](https://en.wikipedia.org/wiki/X_Window_System)，而且是無關乎硬體，尤其是在主控台應用程式 (Console Application) 中。使用到 [`bitcpy(size_t *dst, int dst_idx, const size_t *src, int src_idx, uint32_t n)`](https://elixir.bootlin.com/linux/latest/source/drivers/video/fbdev/amifb.c#L2598) 的地方有 - [`copy_one_line(...)`](https://elixir.bootlin.com/linux/latest/source/drivers/video/fbdev/amifb.c#L3207) 應用在 - [`amifb_copyarea(...)`](https://elixir.bootlin.com/linux/latest/source/drivers/video/fbdev/amifb.c#L3242) 就是用來更新 virtual address 上圖像資料的位址。 - [`expand_one_line(...)`](https://elixir.bootlin.com/linux/latest/source/drivers/video/fbdev/amifb.c#L3306) 被使用在 - [`amifb_imageblit(...)`](https://elixir.bootlin.com/linux/latest/source/drivers/video/fbdev/amifb.c#L3336) 就是拿來將圖像資料寫入 virtual address 中。 ## 測驗 2 內容參見 [測驗題](https://hackmd.io/@sysprog/linux2020-quiz4#%E6%B8%AC%E9%A9%97-2) 對照 [程式碼 (附行號)](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/vector.c) ### 解析 - ==[VV1](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/vector.c#L17) = ?== - macro 望文生義，就是要擴充 capacity，也就是相對於 size 為實際內容大小，capacity 是事先預支好的空間，並以 2 的指數成長，所以需要是 2 的指數。 - 這裡的檢查方式是用 bitwise operator 的方式，若 `s` 是 2 的指數的話，那二進位就是 (1000...0)~2~ 的樣子；最快的檢驗方式就是跟 `s - 1` (也就是 (0111...1)~2~) 作 `&`，檢查是否 ==`s & (s - 1) == 0`==。如果不是的話，那才去尋找下一個 2 的指數。 - ==[VV2](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/vector.c#L48) = ?== - 這題是觀念題，檢驗分別對 size 和 capacity 功能，如上述說明 - 由於 `pop_back` 是從末端取出 element，所以是 ==`v.size -= 1`== ### 運作原理 & 改進方案進入主題前先介紹幾個 gcc 提供的 function 和 keyword - `int __builtin_clzl (unsigned long)` - 同 `int __builtin_clz (unsigned int x)`，顧名思義就是 count leading zero - ??? implementation ??? - `__attribute__` - 根據[官方文檔](https://gcc.gnu.org/onlinedocs/gcc-3.3.6/gcc/Function-Attributes.html) > The keyword `__attribute__` allows you to specify special attributes when making a declaration. This keyword is followed by an attribute specification inside double parentheses. > [color=lightblue] - 這些額外的 attribute 一方面多一層編譯器的檢查，一方面可以幫助編譯器優化函數呼叫 - 這份程式中，有兩處用到 `__attribute__` 關鍵字 - [28行](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/vector.c#L28) 的 `__attribute__((cleanup(vec_free)))` - `cleanup` 是一個 [variable attribute](https://gcc.gnu.org/onlinedocs/gcc/Common-Variable-Attributes.html)，也可以寫成 `__cleanup__` - 簡單說就是 c 語言中用來設定 out of scope 的 exception handler - [54行](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/vector.c#L54) 的 `NON_NULL __attribute__((nonnull))` - `nonnull` 是一個 [attribute of functions](https://gcc.gnu.org/onlinedocs/gcc-4.7.2/gcc/Function-Attributes.html) - 用來檢查參數不為 null pointer - 最後一個是最熟悉的陌生人，[21 行的變數宣告](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/vector.c#L21#L31) `__VA_ARGS__`，稱為 [Variadic Macros](https://gcc.gnu.org/onlinedocs/cpp/Variadic-Macros.html) - 宣告函式有任意數量的參數，在最初的 hello world 程式中的 `printf(str, args...)` 就是以這種方式宣告的 - 在 C99 之前，C++ 定義的寫法是 `args...`， - C99 之後支援以下寫法 - `printf(str...)` - `printf(str, args...)` - `printf(str, __VA_ARGS__)` 在閱讀程式碼的過程中，發現原來 C 也可以透過 macro 來實現類似 C++ 的 template 或是 overloading 這種脫離型態來避免 duplicate code 的問題，好比說 [8 行](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/vector.c#L8)用來定義 `struct` 和 [21 行](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/vector.c#L21)用來宣告 `union` 的變數。然而，與此同時也萌生了以下問題 - 由於是用 macro 來定義，在預處理器階段就把他們都處理掉了，所以就缺乏像是在編譯器階段或是函式中可以檢查的各種狀況，好比像是[這位仁兄](https://stackoverflow.com/a/1571702)的論述，有時優點同時也是缺點 - macro 和 inline function 第一個差別，macro 雖然好處在於相對於 function 的參數逐項 evaluate，而 macro 只有使用到的「參數」才會，以此省去不必要的 evaluate，但這個假設是建立在不會出現不合法的值時才會成立。 - 再來就是數值型態的問題，雖然 macro 看似可以超脫型態的限制，但同時也少的編譯器的型態檢查。 - 再來就是在維護和協作的部份，和在 ***Effective C++*** 中有提過的 ***"Prefer `const` and `inline` to `#define`"*** 類似，在於編譯器的錯誤會針對預處理器寫入的地方來回報，而不會像變數或函式那樣明確指出錯誤。好比說有個 `#define NUMBER 0` 在某些地方成為的不合法的值而出現編譯錯誤，編譯器不會指出是 `NUMBER` 而是 `0`，增加了除錯的難度。而整份程式演算法的部份基本上實作了 C++ `std::string` 中，用來縮減 capacity 的 `reserve()` 和用來新增 element 的 `push_back()`。在 [folly::FBVector 的文件中](https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md) 就有提起了 C++ STL 中的資料結構存在最致命的問題，每當事先分配好的 capacity 不夠時，都是 2 的指數在成長。針對這一點，文中提出兩種思考層面 - 首先針對演算法本身的問題，提出調整這個成長因子，太小會導致頻繁索取記憶體，太大又解決不了問題，作者提出折衷取 1.5。 - 而針對這題我的觀點是，畢竟還有尚未使用的 bit field (3 bits)，就可以拿來做動態調整。好比說第一次從 stack 轉為 heap 就一樣乘 2，下一次開始記數改乘 1.8、1.6、1.4，最低定在 1.4 或是 1.2 (這樣只需要 2 bits 的計數器就夠了)，畢竟記憶體浪費的問題是隨著資料量增加才開始變得嚴重的。 - 第二個切入點由 [`jemalloc()`](http://jemalloc.net/) 取代 `realloc()` 或是 `malloc()`。在索取記憶體的時候，設定一個門檻值 (文中舉例 1M)，超過 1M 就不再以指數成長，改為等差級數，每次最多增加 512K。 - 文中針對 reallocation 這個步驟還提出了令一個優化上的問題在於包含 C++ STL 在內的 allocator 不支援 in-place 的 reallocation，變成必須要 allocate 新的空間，複製，再釋放。 ### 效能測試這邊的對照組我用上面提到的 1.5 來取代 2 ，作為資料結構指數成長的底數，[程式碼對照](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/vector_improved.c) #### 原版記憶體使用狀況這邊使用了 gdb 來觀察，以及 linux 函式庫中的 `size_t malloc_usable_size (void *ptr);` ，對應[測試程式碼](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/vector_improved.c#L145-L183)，過程如下 - 當 size = 1,000 時， ```shell (gdb) info locals ... vect = {{size = 1000, on_heap = 1, capacity = 10, ... ... (gdb) x &vect 0x7fffffffdbf0: 0x000003e8 (gdb) print malloc_usable_size(vect.ptr) $1 = 4104 ``` - 0x3e8 就是 1000，如同 size 所紀錄的 - 當 size = 10,000 時， ```shell (gdb) info locals ... vect = {{size = 10000, on_heap = 1, capacity = 14, ... ... (gdb) x &vect 0x7fffffffdbf0: 0x00002710 (gdb) print malloc_usable_size(vect.ptr) $2 = 65544 ``` - 0x2710 依舊如同 size 所紀錄的 10000 - 前一次根據 `capacity = 10`，可使用的 heap size 理當為 2^10 (1024)，在乘上 `sizeof(int)` 大約是 2^12 (4096)；同樣情形，這次可使用的 heap size 理當為 $2^{14}$ (16384)，加上 int 大小約莫是 $2^{16}$ (65536)，後續也又這種跟理論上有誤差的狀況，尤其隨著資料結構成長的愈大，誤差愈明顯。 - 這個問題根據[這位仁兄](https://stackoverflow.com/a/44581328)所述，底層實作過程中可能會因為 alignment 而配置大於指定大小的記憶體空間。 :::danger 為何 int 大小約莫是 $2^{16}$ (65536) ? :notes: jserv ::: - 當 size = 100,000 時， ```shell (gdb) info locals ... vect = {{size = 100000, on_heap = 1, capacity = 17, ... ... (gdb) x &vect 0x7fffffffdbf0: 0x000186a0 (gdb) print malloc_usable_size(vect.ptr) $3 = 528368 ``` - 0x186a0 = 100000 - 2^17 = 131072，加上 int 大小 2^19 = 524288 - 誤差 4120 bytes - 當 size = 1,000,000 時， ```shell (gdb) info locals ... vect = {{size = 1000000, on_heap = 1, capacity = 20, ... ... (gdb) x &vect 0x7fffffffdbf0: 0x000f4240 (gdb) print malloc_usable_size(vect.ptr) $4 = 4198384 ``` - 0xf4240 = 1000000 - 2^20 = 1048576，加上 int 大小 2^22 = 4194304 - 誤差 4080 bytes #### 改版記憶體使用狀況 - 當 size = 1,000 時， ```shell (gdb) info locals ... vect = {{size = 1000, on_heap = 1, capacity = 18, ... ... (gdb) x &vect 0x7fffffffdbf0: 0x000003e8 (gdb) print malloc_usable_size(vect.ptr) $1 = 5912 ``` - `x &vect` 正如理論上的相同 - \[ 1.5^18 ] - 1 = 1477，加上 int 大小是 5908 - 這邊用高斯符號表示，但是實作是用 `(size_t)` 所以會少一 - 這邊應該是有點 bug 所以沒有正確分配 - 當 size = 10,000 時， ```shell (gdb) info locals ... vect = {{size = 10000, on_heap = 1, capacity = 23, ... ... (gdb) x &vect 0x7fffffffdc00: 0x00002710 (gdb) print malloc_usable_size(vect.ptr) $2 = 44888 ``` - \[ 1.5^18 ] - 1 = 11222，加上 int 大小是 44888 剛好 - 當 size = 100,000 時， ```shell (gdb) info locals ... vect = {{size = 100000, on_heap = 1, capacity = 29, ... ... (gdb) x &vect 0x7fffffffdbf0: 0x000186a0 (gdb) print malloc_usable_size(vect.ptr) $3 = 511984 ``` - \[ 1.5^29 ] - 1 = 127834，加上 int 大小是 511336 - 當 size = 1,000,000 時， ```shell (gdb) info locals ... vect = {{size = 1000000, on_heap = 1, capacity = 35, ... ... (gdb) x &vect 0x7fffffffdbf0: 0x000f4240 (gdb) print malloc_usable_size(vect.ptr) $4 = 5824496 ``` - \[ 1.5^35 ] - 1 = 1456109，加上 int 大小是 5824436 - 這一筆測資跟節省記憶體開銷的預服不符，明顯大了一點。其實可以看得出來，由於碰巧 1.5 的指數離 1M 最近的 \[ 1.5^34 ] - 1 = 970739 比較小，所以多乘了一次 #### 原版測試時間 ![](https://i.imgur.com/OYWO4NN.png) #### 改版測試時間 ![](https://i.imgur.com/cdVXd9r.png) - 承襲 size 和 capacity 這種預先分配，capacity 以指數的身份來紀錄的機制，這邊是簡單用遞迴的方式來實作 [`factor_power(size_t capacity)`](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/vector_improved.c#L36)，所以相對於原本的 bitwise operator `<<` 時間複雜度為 $O(1)$，[`factor_power(size_t capacity)`](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/vector_improved.c#L36) 的時間複雜度是 $O(log\ N)$，從實驗也可以明顯看得出耗時是原本的將近 25 倍。 - 目前可以想到比較好的解法是把 `capacity` 這個 field 獨立出來直接紀錄 1.5 的指數，以小小的空間作為 overhead 來換取 $O(1)$ 的時間複雜度。 #### 結論 - 綜觀來看，如果把改版記憶體使用狀況的最後一筆測資列入少數按例看來 (畢竟這種情況不管今天底數為何都是難免的)，改版後確實減少了不少記憶體的浪費，尤其很多時候其實大部份 double 上去的記憶體空間是沒有用到的。 - 從測試時間的角度來看，最一開始會選擇以 2 為底數就是因為實作上可以使用 bitwise operator `<<` 和 `>>`，加上 bit field 可以算是最精簡的實作策略。如果要再去計較記憶體使用上的最佳化的話，感覺付出一些空間或時間上的代價是不可避免的。 - 由於這次測資只到 1M 個 elements，所以 [`jemalloc`](https://github.com/jemalloc/jemalloc) 就不再加進來實驗了。 ### 參照 folly::fbvector 文件和原始程式碼實作經典操作對照 C++ 的 std::vector 算是應有盡有，就再少了個針對特定位置操作的 [`insert()`](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/vector_extended.c#L131-L164) 和 [`erase()`](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/vector_extended.c#L166-L179)，還有 [`empty()`](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/vector_extended.c#L54) 清空。 [測試程式碼參見](https://github.com/babysuse/Quiz-C_Programming_Lab/blob/master/wk4_2020/vector_extended.c#L186-L209)。如同預期輸出結果如下 ``` 1 6 stack 1 5 6 heap 1 4 5 6 heap 1 3 4 5 6 heap 1 2 3 4 5 6 heap 2 3 4 5 6 heap 2 4 5 6 heap 2 4 6 heap heap ``` - 由於第一次如果是使用 stack 的話，都是以 2 的指數來宣告，而這邊第一次就是 2 的指數 (2^1 = 2)，所以下一次再要的時候直接進到 heap。