---
tags: 進階電腦系統理論與實作
---
# 2020q3 Homework11 (quiz11)
contributed by < `RinHizakura` >
> [第 11 週測驗題](https://hackmd.io/@sysprog/2020-quiz11)
> [GitHub](https://github.com/RinHizakura/vector)
## 測驗 `1`
:::info
內容搬運自之前在測驗題 [quiz4](https://hackmd.io/@RinHizakura/B17sUnk4v) 時所記錄
:::
### 實作原理
#### `v`
```c=
#define v(t, s, name, ...) \
union { \
STRUCT_BODY(t); \
struct { \
size_t filler; \
t buf[NEXT_POWER_OF_2(s)]; \
}; \
} name __attribute__((cleanup(vec_free))) = {.buf = {__VA_ARGS__}}; \
name.size = sizeof((__typeof__(name.buf[0])[]){0, __VA_ARGS__}) / \
sizeof(name.buf[0]) - 1; \
name.capacity = sizeof(name.buf) / sizeof(name.buf[0])
```
* 在 Union 中有兩種 struct。一種是透過 `STRUCT_BODY` 定義的。一種是有一個 `size_t` 的成員 `filter`，和 `NEXT_POWER_OF_2(s)` 大小的 `t` 型態 array。
* 根據 [cleanup (cleanup_function)](https://gcc.gnu.org/onlinedocs/gcc/Common-Variable-Attributes.html) `__attribute__((cleanup(vec_free)))` 會在變數離開 stack 時自動呼叫 `vec_free`。
* 根據 [Variadic Macros](https://gcc.gnu.org/onlinedocs/cpp/Variadic-Macros.html)，把 `name` 以後的參數對應到 `__VA_ARGS__`，用來初始化 `buf` 裡的內容。
* `size` 計算 vector 目前儲存的數量，透過 `(__typeof__(name.buf[0]))` 得到 buf 的型別，再用此型別去建立一個成員有 `{0, __VA_ARGS__}` 的 literal，則 vector 大小即是這個 literal 需要的儲存空間除以單個元素的儲存空間再減 1(扣掉 0)
* 需要多放一個 0，是避免沒有 `__VA_ARGS__` 時 buf[0] 不會出錯
* `capacity` 是 vector 可以容納的數量
#### `STRUCT_BODY`
這個 macro 用來宣告 struct 結構，其中 `type` 是結構中 pointer 的型態。前面的 size_t 則是透過在 [C 語言：bit-field](https://hackmd.io/@RinHizakura/Hk1CYv1kv/%2F5B7s4KiaQOmS0Ud6Px6Cww) 提到的技巧，把 `size_t` 的 64 位元分配給不同的 struct member。
```c=
#define STRUCT_BODY(type) \
struct { \
size_t size : 54, on_heap : 1, capacity : 6, flag1 : 1, flag2 : 1, \
flag3 : 1; \
type *ptr; \
}
```
#### `NEXT_POWER_OF_2(s)`
```c=
#define NEXT_POWER_OF_2(s) \
VV1 \
? s \
: (size_t) 1 << (64 - __builtin_clzl(s)) /* next power of 2 */
```
求出比 `s` 大且最接近 `s` 的 2^n 次方(n 為整數)。因此 `VV1 = (d)(s & (s - 1)) == 0` (可以參閱 [C 語言：數值系統篇](https://hackmd.io/9tGfpJtLTwyyOzDvlyJS2w?view#x-amp-x---1--0))，如果 s 本身就是 2^n 次方則直接是 s，否則透過 `64 - __builtin_clzl` 求出 s 從左邊數來第 1 個 1 在哪，位移那個量可以得到所求。
#### `NON_NULL`
```c=
#define NON_NULL __attribute__((nonnull))
```
[__attribute__((nonnull))](https://www.keil.com/support/man/docs/armcc/armcc_chr1359124976631.htm) 告訴編譯器這個 function 不能接受 NULL pointer，否則會在編譯時期產生警告。
#### `vec_free`
```c=
static NON_NULL void vec_free(void *p)
{
STRUCT_BODY(void) *s = p;
if (s->on_heap)
free(s->ptr);
}
```
檢查 vector 是否是用 heap 來儲存，是的話要透過 free 來釋放。
#### `vec_size`
```c=
#define vec_size(v) v.size
```
如你所見，不解釋。
#### `vec_capacity`
```c=
#define vec_capacity(v) \
(v.on_heap ? (size_t) 1 << v.capacity : sizeof(v.buf) / sizeof(v.buf[0]))
```
檢查 vector 是否額外使用 heap 儲存資料，如果是，$2^{v.capacity}$ 為實際的容量大小，否則就是 `sizeof(v.buf) / sizeof(v.buf[0]))`。
#### `vec_data`
```c=
#define vec_data(v) (v.on_heap ? v.ptr : v.buf) /* always contiguous buffer */
```
針對是否使用 heap 存取的 member 不同。
#### `vec_elemsize`
```c=
#define vec_elemsize(v) sizeof(v.buf[0])
```
如你所見。
#### `vec_pos`
```c=
#define vec_pos(v, n) vec_data(v)[n] /* lvalue */
```
用來取 vector 的第 n 個值
#### `vec_reserve`
```c=
#define vec_reserve(v, n) __vec_reserve(&v, n, vec_elemsize(v), vec_capacity(v))
```
#### `__vec_reserve`
```c=
static NON_NULL void __vec_reserve(void *vec,
size_t n,
size_t elemsize,
size_t capacity)
{
union {
STRUCT_BODY(void);
struct {
size_t filler;
char buf[];
};
} *v = vec;
if (n > capacity) {
if (v->on_heap) {
v->ptr = realloc(v->ptr,
elemsize * (size_t) 1 << (v->capacity = ilog2(n)));
} else {
void *tmp =
malloc(elemsize * (size_t) 1 << (v->capacity = ilog2(n)));
memcpy(tmp, v->buf, elemsize * v->size);
v->ptr = tmp;
v->on_heap = 1;
}
}
}
```
透過 heap 擴大 vector 的 capacity
#### `ilog2`
```c=
static inline int ilog2(size_t n)
{
return 64 - __builtin_clzl(n) - ((n & (n - 1)) == 0);
}
```
求出 k，k 滿足比 n 大且最接近的 $2^k$(k 為整數)
#### `vec_push_back`
```c=
#define vec_push_back(v, e) \
__vec_push_back(&v, &(__typeof__(v.buf[0])[]){e}, vec_elemsize(v), \
vec_capacity(v))
```
#### `__vec_push_back`
```c=
static NON_NULL void __vec_push_back(void *restrict vec,
void *restrict e,
size_t elemsize,
size_t capacity)
{
union {
STRUCT_BODY(char);
struct {
size_t filler;
char buf[];
};
} *v = vec;
if (v->on_heap) {
if (v->size == capacity)
v->ptr = realloc(v->ptr, elemsize * (size_t) 1 << ++v->capacity);
memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
} else {
if (v->size == capacity) {
void *tmp =
malloc(elemsize * (size_t) 1 << (v->capacity = capacity + 1));
memcpy(tmp, v->buf, elemsize * v->size);
v->ptr = tmp;
v->on_heap = 1;
memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
} else
memcpy(&v->buf[v->size++ * elemsize], e, elemsize);
}
}
```
push 進一個元素，必要的時候要增加 capacity。
#### `vec_pop_back`
```c=
#define vec_pop_back(v) (void) (VV2)
```
拿出一個元素，所以 `VV2 = ( a )v.size -= 1`
### 實作限制與改進方案
#### `vec_pop_back`
```c=
#define vec_pop_back(v) assert(v.size > 0); v.size -= 1
```
原本的 `vec_pop_back` 僅僅是把 `size -= 1`，對於空的 vector 的 pop 應該要反映出問題，因此修改為此。
#### `vec_pos`
透過 assert 檢查超出邊界的存取，詳細請參閱前面的 Github 連結。
#### `v`
透過 [Static Assertion](https://en.wikichip.org/wiki/c/static_assertion) 避免初始化 void 型別的 vector，需注意到 static assertion 的檢查只能接受 [Constant Expressions](https://www.cs.auckland.ac.nz/references/unix/digital/AQTLTBTE/DOCU_066.HTM) 而不能執行 function，不過我們可以透過 GCC builtin 來完成字串比對。
```c=
_Static_assert(__builtin_strncmp(#t, "void", 4), "error type");
```
詳情請參閱 Github。
#### 記憶體配置
在 [folly::fbvector](https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md) 提到記憶體配置原則的重要性。當 vector 需要更多空間時，一次 malloc(realloc) 要重新要多少空間是很關鍵的議題，如果要的太少，會導致頻繁呼叫 malloc 產生的時間成本，但是如果要的太多又會有空間浪費的問題。
空間的成長幅度稱為 growth factor，在原始程式中，growth factor 為 2，也就是當空間不足時，就把 heap 空間擴大成兩倍。但是在文章中指出此設計不好的地方。假如初始一塊大小為 C 的空間，則 growth factor = k，下一次需要的空間是原本的 K 倍：
$C$, $C * k$, $C * k^2$, $C * k^3$, ...
在 k = 2 的狀況下，因為 $C$ + $C * k$ + $C * k^2$ + ... $C * k^{n-1}$ < $C * k^n$ 恆成立，因此每次重新配置的空間都比之前配置過的總和大，導致每一次配置就真的需要多要記憶體，而沒辦法重新利用之前配置的空間(如果新的所需空間總和小於之前，則有機會從 pool 裡拿出之前配置的空間來使用就足夠)。
需注意到 allocator 實際上是怎麼分配會影響到實作的策略，不過 k = 2 不論如何都是理論上最差的選擇。而 fbvector 與 jemalloc 搭配，使用 growth factor 1.5 得到最佳效能。
- [ ] 研究如何設計使用者定義的 allocator，搭配記憶體的配置策略得到更佳的效能
### 實現經典 vector 操作
#### `front` / `back`
```c=
#define vec_front(v) vec_pos(v, 0)
#define vec_back(v) vec_pos(v, v.size-1)
```
透過 `vec_pos` 去存取也可以確保錯誤使用時(例如空 vector 時用 `vec_front`)被 assert 擋下來。
#### `insert`
C++ 中的 insert 根據參數功能會有點差異，其中最基本的功能是可以把指定的 element `e` 插入到 `p` 位置。
```c=
#define vec_insert(v, p, e) \
do { \
assert(p >= 0 && p < v.size); \
__typeof__(v.buf[0]) __tmp; \
for (int i = 0; i < (signed) v.size; i++) { \
if (i == p) { \
__tmp = vec_pos(v, i); \
vec_pos(v, i) = e; \
} else if (i > p) { \
__typeof__(v.buf[0]) __t; \
__t = __tmp; \
__tmp = vec_pos(v, i); \
vec_pos(v, i) = __t; \
} \
} \
vec_push_back(v, __tmp); \
} while (0)
```
```c=
#define vec_insert_n(v, p, n, e) \
do { \
assert(p >= 0 && p < v.size); \
assert(n > 0); \
__typeof__(v.buf[0]) *__tmp = \
malloc(sizeof(__typeof__(v.buf[0])) * (v.size - p)); \
int cnt = 0; \
for (int i = 0; i < (signed) v.size; i++) { \
if (i >= p) { \
__tmp[cnt++] = vec_pos(v, i); \
} \
} \
for (int i = 0; i < (signed) v.size - p; i++) \
vec_pop_back(v); \
vec_reserve(v, v.size + n + cnt); \
for (int i = 0; i < n; i++) \
vec_push_back(v, e); \
for (int i = 0; i < cnt; i++) \
vec_push_back(v, __tmp[i]); \
free(__tmp); \
} while (0)
```
作法稍微有點暴力，尤其是 `vec_insert_n`，可以實作出相同效果的方法有許多種，需要考量到效率去做改進。
:::warning
雖然用 macro 可以減少轉型，讓對 vector 的操作比較簡單，不過也因此如果認真要做 assert 可以有很多需要檢查的(在 int 的 vector 插入 float element? `vec_insert_n` 如果 insert 的數量是 float?)。如果要增加實用性的話，需要對這些層面去改善(真的 assert 去檢查？或者換成 function 型式讓 compiler 去檢查)。
:::
Sign in with Wallet
Connect another wallet