# 2020q1 Homework3 (quiz4)
contributed by < `OscarShiang` >
###### tags: `linux2020`
## 測試環境
```shell
$ cat /etc/os-release
NAME="Ubuntu"
VERSION="18.04.4 LTS (Bionic Beaver)"
$ cat /proc/version
Linux version 5.3.0-40-generic (buildd@lcy01-amd64-024)
(gcc version 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1))
```
## 作業要求
- [x] 重新回答測驗題
- [x] 解釋測驗 1 程式運作的原理，改寫為更精簡且等效的程式碼;
- [ ] 考慮到 alignment 和 word size，改寫為執行效率更高的程式碼;
- [ ] 在 Linux 核心原始程式碼找出逐 bit 進行資料複製的程式碼，並解說相對應的情境;
- [x] 解釋測驗 2 程式運作的原理，比照 [quiz2](https://hackmd.io/@sysprog/BJXNYx5NL) 進行效率分析;
- [x] 指出測驗 2 所述實作的限制並提出改進方案;
- [x] 參照 [folly::fbvector](https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md) 文件和對應原始程式碼，以測驗 2 程式為基礎，實作 vector 經典操作
## 測驗 1
### 題目分析
首先 `KK1` 是在剛進入 `bitcopy` 函式的地方，根據 `read_lhs`, `read_rhs` 與 `source` 位移的操作可以判斷 `_read & 7` 的目的在於計算 `_read % 8` 的數值，因為如果除數是 $2^n$ 時，可以利用將變數與 $2^n - 1$ 進行 AND 運算取得餘數，所以根據 `uint8_t *dest = _dest + (_write / 8);` 可以得知
> `KK1` = `7`
根據 `KK2` 所在的位置可以知道，`KK2` 是用來表示當前迴圈所處理的 bit 的個數，所以根據迴圈中與 bit 計算有關的 `bitsize = (_count > 8) ? 8 : _count;` 就可以知道
> `KK2` = `bitsize`
### 程式運作原理
首先我們可以先從函式的參數開始了解：
1. `*_dest`: 目標的起始位址
2. `_write`: 寫入位置的位移量
3. `*_src`: 複製對象的起始位址
4. `_read`: 讀取位置的位移量
5. `_count`: 要複製的位元數量
在函式之中，因為我們要複製的位元不一定是剛好與位元組對齊，所以需要考慮到我們要複製的位元可能會需要位移才能放進 `data` 中，所以我們需要計算 `read_lhs` 與 `read_rhs` ，並在執行複製的時候將位元利用位移並向左對齊，方便之後貼上到 `dst` 指標所指向位元中。
而在執行貼上的時候，因為 `dst` 原本可能也有自己的資料，所以我們需要透過，`write_mask` 將多餘的位元利用遮罩消除。在將 `data` 寫入 `dst` 時，也要考慮到位移的問題，所以利用 `write_lhs` 與 `write_rhs` 將 `data` 對齊 `dst` 寫入的 `offset`，並將資料寫入，最後根據寫入的位元數，更新 `_count` 的數值，重複執行直到 `_count` 歸零就表示位元複製結束
### 改寫程式碼
根據原始的實作，每次的 while 迴圈都要重新判斷 `read_lhs`, `read_rhs` 等等變數的數值，但是其中包含太多針對特定情況的處理。
在去除針對特定情況的 `if-else` 後，可以把程式碼簡化為下列形式：
```cpp
void bitcpy(void *_dest, /* Address of the buffer to write to */
size_t _write, /* Bit offset to start writing to */
const void *_src, /* Address of the buffer to read from */
size_t _read, /* Bit offset to start reading from */
size_t _count)
{
...
while (_count > 0) {
// read data
data = (*source++ << read_lhs) | (*source >> read_rhs);
size_t prep = (_count & 8) >> 3, filter = 8 - _count;
bitsize = (_count & ((-filter - pre) >> 31) + (8 & (filter >> 31));
data &= read_mask[bitsize];
// write data
mask = read_mask[write_lhs];
*dest++ = (*dest & mask) | (data >> write_lhs);
*dest &= write_mask[bitsize - write_rhs];
*dest |= (data << write_rhs);
_count -= bitsize;
}
}
```
:::warning
`bitsize = (_count > 8) ? 8 : _count;` 這樣的敘述可換為 bitwise operation
:notes: jserv
:::
> 已成功實作 bitwise operation 的版本
> [name= Oscar][color= orange]
使用 `perf` 測量分支數量
```shell
$ sudo perf record \
-e branch-misses:u,branch-instructions:u \
-F 30000 ./bitcopy
$ sudo perf report
```
原始版本的測量結果如下所列
```shell
Available samples
432 branch-misses:u
1K branch-instructions:u
```
改寫的版本測量如下
```shell
Available samples
261 branch-misses:u
859 branch-instructions:u
```
從結果可以看到減少了許多的分支
接下來進行實驗測量簡化後的版本與原始版本的差異
實驗的結果如下圖（以排除干擾因素）
從實驗結果可以看出因為去除了多餘的判斷，所以在執行上可以減少許多為了判斷特定情況而花費的時間，在 bitcopy 的數量為 $8000$ 時可以減少大約 $1 \mu s$ 的時間
## 測驗 2
### 題目分析
`VV1` 是位在 `NEXT_POWER_OF_2` 的 macro 之中，該 macro 在實作的就是計算大於給定 s 中最小的 2 的次方，如果符合 `VV1` 的條件，就直接回傳回去，如果不符合 `VV1` 的條件，則利用 `__builtin_clzl` 來計算
所以從程式碼中得知 `VV1` 是在判斷給定的 s 是否為 2 的次方，而其所使用的技巧就是如果 s 是一個 2 的次方的話，其在二進位的表示上就會是： $01000000_2$ 這種的形式，而 s - 1 就會是 $00111111_2$ ，表示將兩者進行 AND 運算時將會得到 0 的結果，所以在這題中：
> `VV1` = `(s & (s - 1)) == 0`
而 `VV2` 的判斷上，因為`VV2` 的位置位於 `pop_back` 的 macro 中。vector 的 size 為目前元素的個數，而 `capacity` 則是最大容量，所以根據 `pop_back` 要將元素刪除的需求，`VV2` 應該為
> `VV2` = `v.size -= 1`
### 程式運作原理
在測驗 2 中，由於使用下列 macro 實作 vector 的宣告
```cpp
#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])
```
所以在使用 `v(type, size, name, ...)` 時，編譯器就會根據輸入的參數展開 macro，達到自訂內部元素資料型態的功能
在 `STRUCT_BODY` 的宣告中
```cpp
#define STRUCT_BODY(type) \
struct { \
size_t size : 54, on_heap : 1, capacity : 6, flag1 : 1, flag2 : 1, \
flag3 : 1; \
type *ptr; \
}
```
採用了類似 `folly::string` 的實作方式，所以可以達到在小容量時使用 stack 儲存資料，大容量時使用 heap 儲存資料的功能。
而較為特別的是因為 `v` 本身可以傳入多個參數，所以使用 `__VA_ARGS__` 來取得在 `name` 之後的參數，並將他們存入 `buf` 之中
`__attribute_((cleanup(vec_free)))` 的用法則是設定該變數在程式結束時會呼叫綁定的函式 `vec_free` 釋放記憶體空間
### 實作的限制與修改
#### vec_pop_back 邊界檢查
在原始的實作中， `vec_pop_back` 就是將 vector 的 `size` 直接減一，讓其不會在 `display` 的時候被印出，但是這樣的實作因為沒有檢查邊界，有可能會導致記憶體 `BAD_ACCESS` 的問題產生，所以在實作中加入檢查邊界的判斷
```cpp
#define vec_pop_back(v) \
assert(v.size > 0); \
v.size -= 1;
```
根據 `assert` 在 `Linux Programmer's Manual` 中的定義
> The assert() macro tests the given expression and if it is false, the calling process is terminated. **A diagnostic message is written to stderr and the abort(3) function is called, effectively terminating the program.**
我們可以使用定義於 `assert.h` 的 `assert` 進行檢查，在使用 `vec_pop_back` 會超出邊界時，呼叫 `abort()` 停止程式
```shell
Assertion failed: (vec1.size > 0), function main, file vector.c, line 171.
[1] 16207 abort ./vector
```
#### vec_pos 造成的記憶體存取問題
因為在 `vec_pos` 的實作如下列
```cpp
#define vec_pos(v, n) vec_data(v)[n] /* lvalue */
```
因為其並未實作出檢查邊界，所以在 `n` 超出 `v.size` 時會存取到未使用的元素空間或是 `n < 0` 時會產生分預期的行為。
使用函式將取值與 `assert` 包裝起來：
```cpp
static NON_NULL void *__vec_pos(void *vec, size_t n, size_t elemsize)
{
union {
STRUCT_BODY(void);
struct {
size_t filler;
char buf[];
};
} *v = vec;
assert(n >= 0 && n < v->size);
uint8_t *data = (uint8_t *)(v->on_heap) ? v->ptr : v->buf;
return data + (n * elemsize);
}
```
參考 `__vec_push_back` 與 `__vec_reserve` 的實作，將 `__vec_pos` 的回傳值定義為 `void *` ，並使用 macro 將回傳回來的位址轉型後取值
```cpp
#define vec_pos(v, n) *(__typeof__(v.buf[0]) *) __vec_pos(&v, n, vec_elemsize(v)) /* lvalue */
```
測試超出邊界的呼叫
```shell
Assertion failed: (n >= 0 && n < v->size), function __vec_pos, file vector.c, line 106.
[1] 19023 abort ./vector
```
完成實作邊界的檢查
#### 檢查 vector 元素的宣告型態
因為在 vector 中不能夠存入像是 `void` 或是 `void *` 的資料型態，所以我們可以利用 `_Static_assert` 來觸發編譯時期的錯誤
```diff
#define v(t, s, name, ...) \
+ _Static_assert(SAFE_TYPE(t), "unsupported type of element"); \
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]);
```
在 macro 中加入 `_Static_assert` ，接著定義 `SAFE_TYPE` 的判斷
```cpp
#define SAFE_TYPE(type) (strcmp(#type, "void") && strcmp(#type, "void *"))
```
原本想要使用 `_Generic` 來實作，但是發現 `_Generic` 不能接受型態作為參數使用，所以改以 macro 字串化的特性來實作 `SAFE_TYPE`
宣告一個元素型態為 `void` 的 vector 來進行測試
```cpp
int main()
{
v(void, 2, vec0); // declare a vector with element type void
v(float, 3, vec1);
v(int, 2, vec2, 13, 42);
printf("pos(vec2,0)=%d, pos(vec2,1)=%d\n", vec_pos(vec2, 0),
vec_pos(vec2, 1));
vec_push_back(vec2, 88);
vec_reserve(vec2, 100);
...
return 0;
}
```
確認其在編譯時期會導致錯誤
```shell
$ gcc vector.c -o vector
vector.c:146:5: error: static_assert failed due to requirement 'strcmp("void", "void")' "unsupported type of element"
v(void, 2, vec0);
^~~~~~~~~~~~~~~~
```
### 實作 vector 經典操作
#### insert 實作
因為在實作 `vec_insert` 的時候會需要調整與移動元素的位置，所以我使用 `string.h` 的 `memmove` 來進行實作，因為根據 `Linux Programmer's Manual` 的描述
> The memmove() function copies len bytes from string src to string dst. **The two strings may overlap**; the copy is always done in a non-destructive manner.
但是如果使用 `memcpy` 而 `dst` 與 `src` 如果重疊，則是 [undefined behavior](http://man7.org/linux/man-pages/man3/memcpy.3.html) ，所以利用 `memmove` 來避免未定義行為的發生
```cpp
static NON_NULL void __vec_insert(void *restrict vec,
void *restrict e,
size_t pos,
size_t elemsize,
size_t capacity)
{
union {
STRUCT_BODY(char);
struct {
size_t filler;
char buf[];
};
} *v = vec;
assert(pos < v->size);
char *data;
if (v->on_heap) {
if (v->size == capacity)
v->ptr = realloc(v->ptr, elemsize * (size_t) 1 << ++v->capacity);
data = v->ptr;
} 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;
data = v->ptr;
} else
data = v->buf;
}
memmove(&data[(pos + 1) * elemsize], &data[pos * elemsize],
(v->size++ - pos) * elemsize);
memcpy(&data[pos * elemsize], e, elemsize);
}
```
因為在使用 `vec_insert` 的時候有可能會導致容量不足，所以需要依照情況調整容量，之後將給定 `pos` 之後的所有元素向後位移一個單位，最後將元素複製到指定位置上
接著利用 macro 實作介面：
```cpp
#define vec_insert(v, e, p) \
__vec_insert(&v, &(__typeof__(v.buf[0])[]){e}, p, vec_elemsize(v), \
vec_capacity(v));
```
#### erase 實作
在 `vec_erase` 的實作上也與 `vec_insert` 類似，但是因為不用考慮超過容量的問題，所以只需要將給定位置之後的元素向前位移即可
```cpp
static NON_NULL void __vec_erase(void *restrict vec,
size_t pos,
size_t elemsize)
{
union {
STRUCT_BODY(char);
struct {
size_t filler;
char buf[];
};
} *v = vec;
assert(pos >= 0 && pos < v->size);
char *data;
if (v->on_heap)
data = v->ptr;
else
data = v->buf;
memmove(&data[pos * elemsize], &data[(pos + 1) * elemsize],
elemsize * (--v->size - pos));
}
```
建立 `vec_erase` 的介面
```cpp
#define vec_erase(v, p) __vec_erase(&v, p, vec_elemsize(v))
```
### 效能分析
接下來針對 `push_back`, `insert` 與 `erase` 分析 C++ STL vector 與我們實作版本的花費時間差異
在 `push_back` 中，因為 C++ 版本的 std::vector 有使用記錄 tail 的指標 `vector::end()` ，所以可以在常數時間完成。而我們的版本則因為有記錄 vector 長度，所以也可以實作出常數時間甚至比 `vector::push_back` (from C++ STL) 還高效率的 函式
圖中的高峰是因為兩者 `push_back` 在根據 vector 的容量在調整
兩個版本的 `insert` 的實作差異如下
可以看到因為需要將資料向後位移，元素的大小與花費時間呈正相關
從結果可以看到，因為越接近 tail 在 `erase` 的時候需要搬運的元素也較少，所以花費時間與 `erase` 的位置呈負相關
而從上述的情況都可以看出 C 實作出來的 vec 在 `push_back`, `insert` 與 `erase` 執行的效率上都較 C++ STL 的 vector 好
## 參考資料
1. [2020q1 第 4 週測驗題](/@sysprog/linux2020-quiz4)
2. [folly::fbvector](https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md)
Sign in with Wallet
Connect another wallet