---
# System prepended metadata

title: 2020q3 Homework11 (quiz11)
tags: [進階電腦系統理論與實作]

---

---
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 去檢查)。
:::
