# 2020q1 Homework3 (quiz4)
contributed by < [`KYG-yaya573142`](https://github.com/KYG-yaya573142/bitcpy) >
> [第 4 週測驗題](https://hackmd.io/@sysprog/linux2020-quiz4)
## 測驗 1
### 解題思路
首先觀察函式參數及開頭宣告的變數
```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)
{
uint8_t data, original, mask;
size_t bitsize;
size_t read_lhs = _read & 7;
size_t read_rhs = 8 - read_lhs;
const uint8_t *source = _src + (_read / 8);
size_t write_lhs = _write & KK1;
size_t write_rhs = 8 - write_lhs;
uint8_t *dest = _dest + (_write / 8);
...
}
```
`bitcpy` 允許開發者對指定的記憶體區域，逐 bit 進行資料複製，而從註解可以知道 `_read` 是寫入地址以 bit 為單位的 offset，觀察第 9~11 行
* `_read & 7` 會將 `read_lhs` 的數值侷限在 0~7
* `read_rhs = 8 - read_lhs` 代表 `read_lhs` 與 `read_rhs` 的總和一定是 8
* `*source = _src + (_read / 8)` 代表當 offset 超過 8 bits 時，會先以 byte 為單位移動 `*source` 來讓 offset 的數字維持在 8 以內
* 綜合上述三點，在 `*source` 指向的 byte 中
* `read_lhs` 為 offset 的大小
* `read_rhs` 為此 byte 資料中扣除 offset 部分後剩餘的大小
* 第 12~14 行 `_write` 相關的部分邏輯同上，對應寫入的位置與 offset，因此 KK1 應填入 7
觀察主 `while` 迴圈的上半部
```cpp
while (_count > 0) {
data = *source++;
bitsize = (_count > 8) ? 8 : _count;
if (read_lhs > 0) {
data <<= read_lhs;
if (bitsize > read_rhs)
data |= (*source >> read_rhs);
}
if (bitsize < 8)
data &= read_mask[bitsize];
...
_count -= KK2;
}
...
```
* 這段程式碼的作用是將資料從 `*source` 讀進 `data` 這個 buffer
* `data` 和 `*source` 的資料型態是 `uint8_t`，代表一次讀取的資料為 1 byte
* `bitsize` 代表最後需要寫入的 bit 總量，而一次迴圈我們只處理 1 byte
* 因此 KK2 應填入 `bitsize`
* `read_lhs` 代表讀取的 offset，因此亦可理解為從 `*source` 讀取的 byte 中
* `read_lhs` 代表不需要的 bit 數量
* `read_rhs` 代表需要的 bit 數量
* `data <<= read_lhs` 將不需要的 bit 移除，並將需要的資料移動到 `data` 的開頭，即只留下長度共 `read_rhs` 的資料
* 因此 `bitsize > read_rhs` 代表現有的資料不足需求，需再從下個 byte 讀取資料並接在 `data` 已有資料的後面
* 以 `_read = 5` `_count = 6` 為例，根據上述程式碼可知此時 `read_lhs = 5`
```graphviz
digraph data {
node [shape=record]; //default node style
offset [label="offset"]
next [label=" {{b1|b2|b3|b4|b5}|read_lhs}|{{<offset> b6|b7|b8}|read_rhs}", xlabel="+1 B"];
source [label=" {{a1|a2|a3|a4|a5}|read_lhs}|{{<offset> a6|a7|a8}|read_rhs}", xlabel="source "];
{rank=same;next source}
offset -> source:offset
}
```
* 由於總共需要讀取 `bitsize = 6` 個 bit 的內容，需再從下個 byte 讀取資料並接在已有資料的後面，最終 `data` 內容如下
```graphviz
digraph data {
node [shape=record]; //default node style
data [label=" a6|a7|a8|b1|b2|b3|b4|b5", xlabel="data "];
}
```
* 最後只會寫入 `bitsize` 個 bit，這代表 `data` 中開頭 `bitsize` 個 bit 以外的資料是 dummy data，須使用 `read_mask[bitsize]` 遮罩掉 dummy data，以上例來說 dummy data 就是 b4 與 b5 這兩 bit 的資料
* `write_mask` 則是用於寫入時，寫入的 bit 數量以外的資料是需要保存的原始資料，因此用 `write_mask`
```cpp
...
static const uint8_t read_mask[] = {
0x00, /* == 0 00000000b */
0x80, /* == 1 10000000b */
0xC0, /* == 2 11000000b */
0xE0, /* == 3 11100000b */
0xF0, /* == 4 11110000b */
0xF8, /* == 5 11111000b */
0xFC, /* == 6 11111100b */
0xFE, /* == 7 11111110b */
0xFF /* == 8 11111111b */
};
static const uint8_t write_mask[] = {
0xFF, /* == 0 11111111b */
0x7F, /* == 1 01111111b */
0x3F, /* == 2 00111111b */
0x1F, /* == 3 00011111b */
0x0F, /* == 4 00001111b */
0x07, /* == 5 00000111b */
0x03, /* == 6 00000011b */
0x01, /* == 7 00000001b */
0x00 /* == 8 00000000b */
};
...
```
接著觀察主 `while` 迴圈的下半部
```cpp
...
original = *dest;
if (write_lhs > 0) {
mask = read_mask[write_lhs];
if (bitsize > write_rhs) {
*dest++ = (original & mask) | (data >> write_lhs);
original = *dest & write_mask[bitsize - write_rhs];
*dest = original | (data << write_rhs);
} else {
if ((bitsize - write_lhs) > 0)
mask = mask | write_mask[8 - (bitsize - write_lhs)];
*dest++ = (original & mask) | (data >> write_lhs);
}
} else {
if (bitsize < 8)
data = data | (original & write_mask[bitsize]);
*dest++ = data;
}
...
```
* 這個部分程式碼的目的是將資料從 `data` 寫入至目的地 `*dest`
* `write_lhs` 為寫入的 offset，因此 `write_rhs` 代表 `*dest` 指向的那個 byte 中可以被寫入的 bit 數量
* 整體的邏輯和讀取資料至 `data` 類似，但需要特別處理被寫入處 `*dest` 的原始資料，使寫入範圍外的資料不變
* `write_lhs` 的部分永遠是原始資料
* 若 `bitsize > write_rhs`，代表需要繼續寫入資料至下一個 byte
* 若 `bitsize < write_rhs`，代表寫入的資料後面還會接著共 `8 - write_lhs - bitsize` 個 bit 的原始資料
* `write_mask` 主要是用在這個部分，只要使用 `original & write_mask[write_lhs + bitsize]` 就可以保留接在尾端的原始資料
* 原本的寫法應該有錯，`write_mask[8 - (bitsize - write_lhs)]` 應該要寫成 `write_mask[write_lhs + bitsize]` 才對
### 改寫為更精簡且等效的程式碼
原本的寫法有幾個可以改善的部分，如
* 使用太多 `if` 進行判斷，例如原本 `read_mask` 和 `write_mask` 的宣告就有包含當參數為 0 的 mask，無須再用 `if` 進行判斷是否為 0
* 部分程式行數具有相同的邏輯但寫法不一致，導致較難理解
* 針對複製的 bit 數量很大時進行優化，此時會先不斷以 `bitsize = 8` 執行迴圈的內容，最後再處理尾段不足 8 bits 的資料，因此可以去除大部分的 `if` 判斷
* `read_mask` 和 `write_mask` 互為 bitwise NOT 的關係，可用 `write_mask[n] = ~read_mask[n]` 代替
```cpp
...
//write_mask[n] = ~read_mask[n]
for (size_t count = _count >> 3; count > 0; count--) {
/* read data from source in to buffer */
data = *source++;
data = data << read_lhs | (*source >> read_rhs);
/* write data into dest */
original = *dest & (read_mask[write_lhs]);
*dest++ = original | (data >> write_lhs);
*dest = (*dest >> write_lhs) | (data << write_rhs);
}
_count &= 7;
data = *source++;
data = (data << read_lhs | (*source >> read_rhs)) & read_mask[_count];
original = *dest & (read_mask[write_lhs] | ~read_mask[write_lhs + _count]);
*dest++ = original | (data >> write_lhs);
if (_count > write_rhs)
*dest = (*dest & ~read_mask[_count - write_rhs]) | (data << write_rhs);
...
```
最後使用原本題目中的程式碼驗證，輸出結果無誤
### 效能差異
實驗的程式碼如下
```cpp
static uint8_t output[800], input[800];
int main(int _argc, char **_argv)
{
memset(&input[0], 0xFF, sizeof(input));
for (int bit = 1; bit < 6000; bit++) {
struct timespec t_start, t_end;
memset(&output[0], 0x00, sizeof(output));
clock_gettime(CLOCK_MONOTONIC, &t_start);
bitcpy(&output[0], 5, &input[0], 3, bit); /* original method */
clock_gettime(CLOCK_MONOTONIC, &t_end);
long long t1 = (long long)(t_end.tv_sec * 1e9 + t_end.tv_nsec)
- (long long)(t_start.tv_sec * 1e9 + t_start.tv_nsec);
memset(&output[0], 0x00, sizeof(output));
clock_gettime(CLOCK_MONOTONIC, &t_start);
bitcpy_rewrite(&output[0], 5, &input[0], 3, bit); /* mymethod */
clock_gettime(CLOCK_MONOTONIC, &t_end);
long long t2 = (long long)(t_end.tv_sec * 1e9 + t_end.tv_nsec)
- (long long)(t_start.tv_sec * 1e9 + t_start.tv_nsec);
printf("%d %lld %lld\n", bit, t1, t2);
}
}
```
* 複製的 bit 長度為 0~6000
* 使用與 [fibdrv 作業](https://hackmd.io/BZjwYw1FQ1O0NPY5kIS7VQ#Linux-%E6%95%88%E8%83%BD%E5%88%86%E6%9E%90%E7%9A%84%E6%8F%90%E7%A4%BA)一樣的方法降低干擾
實驗結果如下
* 相較於題目中的寫法，我改寫後的方法可以節省約 33% 的時間
由於更動的部分主要是去除大量的 `if`，我嘗試使用 `perf` 來分析 branch 的差異
```shell
sudo perf stat --repeat 5 -e branch-instructions:u,branch-misses:u ./test
```
* 原本的寫法
```
Performance counter stats for './test' (5 runs):
15,934,530 branch-instructions:u ( +- 0.00% )
9,913 branch-misses:u # 0.06% of all branches ( +- 0.12% )
0.025568 +- 0.000629 seconds time elapsed ( +- 2.46% )
```
* 我改寫的方法
```
Performance counter stats for './test' (5 runs):
2,417,277 branch-instructions:u ( +- 0.00% )
8,614 branch-misses:u # 0.36% of all branches ( +- 0.21% )
0.018744 +- 0.000560 seconds time elapsed ( +- 2.99% )
```
可以清楚的看到，無論在 branch-instructions:u 還是 branch-misses:u 都有明顯的改善
### 在 Linux 核心原始程式碼找出逐 bit 進行資料複製的程式碼，並解說相對應的情境 (待補)
## 測驗 2
### 解題思路
```cpp
#define NEXT_POWER_OF_2(s) \
VV1 \
? s \
: (size_t) 1 << (64 - __builtin_clzl(s)) /* next power of 2 */
```
* 從註解可以知道目的是找出最接近且大於等於 s 的 $2^n$
* 以 2 進位思考，$2^n$ 代表全部的 bit 只會有一位被設置為 1，此時將此數值減 1 會產生具有共 n - 1 位全部都是 1 的 2 進位數字，也只有此時會符合 `(s & (s - 1)) == 0`
* 因此 VV1 應填入 `(s & (s - 1)) == 0`
```cpp
static inline int ilog2(size_t n)
{
return 64 - __builtin_clzl(n) - ((n & (n - 1)) == 0);
}
```
* 用來計算 $log_2(n)$
* `64 - __builtin_clzl(n)` 代表代入的數字如果不是 $2^n$ 會無條件進位，如果代入的數字已經是 $2^n$ 則無需再進一位，用 `((n & (n - 1)) == 0)` 來扣回去
接著從使用示範觀察 vector 的使用方式
```cpp
v(float, 3, vec1);
v(int, 2, vec2, 13, 42);
```
查看相關的定義來了解 vector 實作的資料結構
```cpp
#define STRUCT_BODY(type) \
struct { \
size_t size : 54, on_heap : 1, capacity : 6, flag1 : 1, flag2 : 1, \
flag3 : 1; \
type *ptr; \
}
#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])
```
* `#define STRUCT_BODY(type)` 實現了讓 vector 可以在宣告時使用不同資料型態的功能
* `#define v(t, s, name, ...)` 是實現 vector 宣告的核心，vector 本質上是 `union`，定義內容的方式和[第二周測驗題](https://hackmd.io/@sysprog/linux2020-quiz2)中以 C 語言重寫 [folly::fbstring](https://github.com/facebook/folly/blob/master/folly/FBString.h) 的程式碼非常相似
* 前 8 bytes 會用來記錄 `size` `capacity` `flag`，所以後面的 `size_t filler` 是用來避免此區域內容遭到複寫
* 初始記憶體空間使用 stack，最大的可用空間為 `NEXT_POWER_OF_2(s)`
* `name` 是這個 vector 物件的名稱，同時結尾用 `{.buf = {__VA_ARGS__}}` 來根據輸入的參數初始化物件的內容
* `__VA_ARGS__` 是 [Variadic Macros](https://gcc.gnu.org/onlinedocs/cpp/Variadic-Macros.html)，對應到 `v(t, s, name, ...)` 中的 `...`，用來實現讓參數數量可以變動的功能
* `__attribute__` 是 [Attribute Syntax](hhttps://gcc.gnu.org/onlinedocs/gcc-3.2/gcc/Attribute-Syntax.html#Attribute%20Syntax)，在這裡用來於宣告物件時加上特定的屬性
* 從 [Common Variable Attributes](https://gcc.gnu.org/onlinedocs/gcc-3.2/gcc/Variable-Attributes.html#Variable%20Attributes) 可以知道 `cleanup(vec_free)` 的作用為當 vector 變數超出 scope 時會自動呼叫 `vec_free`
* 相關的用法可參閱[ 你所不知道的C語言：技巧篇 ](https://hackmd.io/@sysprog/c-trick)以及 [Implementing smart pointers for the C programming language](https://snai.pe/posts/c-smart-pointers)
* `name.size` 是 vector 中已有資料的數量
* `__typeof__` 的用法可參閱 [Referring to a Type with typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html)
* `(__typeof__(name.buf[0])[]` 宣告一個資料型態跟 `name.buf[0]` 一樣的陣列，並且用後面的數值 `{0, __VA_ARGS__}` 進行初始化
* 當宣告 vector 時沒有輸入任何參數，這個陣列會變成 [Arrays of Length Zero](https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html)，`{0, __VA_ARGS__}` 的 0 就是為了避免這個情況發生
* `name.capacity` 是 vector 中可容納的資料數量上限
* `sizeof(name.buf[0])` 是 buf 中一個內容的大小
* `sizeof(name.buf)` 是整個 buf 的大小
```cpp
#define vec_size(v) v.size
#define vec_capacity(v) \
(v.on_heap ? (size_t) 1 << v.capacity : sizeof(v.buf) / sizeof(v.buf[0]))
#define vec_data(v) (v.on_heap ? v.ptr : v.buf) /* always contiguous buffer */
#define vec_elemsize(v) sizeof(v.buf[0])
#define vec_pos(v, n) vec_data(v)[n] /* lvalue */
#define vec_reserve(v, n) __vec_reserve(&v, n, vec_elemsize(v), vec_capacity(v))
#define vec_push_back(v, e) \
__vec_push_back(&v, &(__typeof__(v.buf[0])[]){e}, vec_elemsize(v), \
vec_capacity(v))
#define vec_pop_back(v) (void) (VV2)
/* This function attribute specifies function parameters that are not supposed
* to be null pointers. This enables the compiler to generate a warning on
* encountering such a parameter.
*/
#define NON_NULL __attribute__((nonnull))
```
* `vec_size` `vec_capacity` `vec_data` `vec_elemsize` `vec_pos` 這幾個 macro 都是用來取用對應的資料
* `vec_reserve` 和 `vec_push_back` 是為了讓相關的函式使用起來更直覺的 wrapper，相對應的函式實作後面會討論
* `__attribute__((nonnull))` 會讓函式追加代入的參數不能是 null pointer 的屬性，詳見 [Declaring Attributes of Functions](https://gcc.gnu.org/onlinedocs/gcc-3.4.3/gcc/Function-Attributes.html)
* `vec_pop_back` 的意義是將 vector 中最後的元素去除，`size` 代表的是 vector 內含有的資料數量，因此 VV2 應填入 `v.size -= 1`
```cpp
static NON_NULL void vec_free(void *p)
{
STRUCT_BODY(void) *s = p;
if (s->on_heap)
free(s->ptr);
}
```
* 如果 vector 有使用 heap，需 `free` 掉使用的部分
```cpp
#define vec_reserve(v, n) __vec_reserve(&v, n, vec_elemsize(v), vec_capacity(v))
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;
}
}
}
```
* 變更指定的 vector 讓其至少具有能涵蓋 n 筆資料的 capacity，如果索求量沒有超過原本 capacity，就不進行變動
* 須注意此函式內用的區域變數 `*v` 內定義的資料型態是 `char`，所以在 `malloc` 與 `realloc` 空間時需再乘 `elemsize`
* 這種做法是為了讓 vector 的資料能使用任意資料型態
```cpp
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);
}
}
```
* 將資料存在 vector 末端
* 如果空間不夠，就先擴張空間
* 原本在 heap 上就使用 `realloc` 改變空間
* 原本在 stack 上就 `malloc` 空間然後把資料複製過去
另外，在測試的程式碼中有一個這樣的用法
```cpp
#define display(v) \
do { \
for (size_t i = 0; i < vec_size(v); i++) \
printf("%.2f ", vec_pos(v, i)); \
puts(v.on_heap ? "heap" : "stack"); \
} while (0)
```
* 如果要在 macro 中使用多個 statement，單純用 `{}` 框起來在 macro 展開後會造成語法錯誤，因此可用 `do {} while (0)` 來滿足這個需求
### 上述實作的限制並提出改進方案
#### `vec_pop_back`
```diff
-#define vec_pop_back(v) (void) (v.size -= 1)
+#define vec_pop_back(v) (void) (v.size -= !!v.size)
```
* 原本的寫法如果在 `v.size = 0` 時會引發 Segmentation fault (core dumped)，改寫後可避免此狀況發生
#### `vec_pos(v, n)`
```diff
-#define vec_pos(v, n) vec_data(v)[n] /* lvalue */
+#define vec_pos(v, n) *(__typeof__(v.buf[0]) *) _vec_pos(&v, n, vec_elemsize(v))
```
```cpp
static NON_NULL void *_vec_pos(void *vec,
size_t n,
size_t elemsize)
{
union {
STRUCT_BODY(char);
struct {
size_t filler;
char buf[];
};
} *v = vec;
assert(v->size > n);
return (void *)
((v->on_heap ? v->ptr : v->buf) + n * elemsize);
}
```
* 一樣是原本的寫法沒有檢查邊界，但比較麻煩的地方是 vector 的資料型態不固定，如果直接在 macro 中使用 `assert` 檢查邊界，又會導致 `vec_pos` 沒辦法直接當成 `printf` 的參數使用
* 最後想到可以先回傳 `void *` 然後再於 macro 中使用 [`__typeof__`](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 來轉換到對應的型態
* 整體寫法類似 `vec_reserve` 中 wrapper 的寫法
#### `v(t, s, name, ...)`
```diff
#define v(t, s, name, ...) \
+ _Static_assert(strncmp(#t, "void", 4), "error type"); \
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])[]){__VA_ARGS__} ) / \
sizeof(name.buf[0]); \
name.capacity = sizeof(name.buf) / sizeof(name.buf[0])
```
* 原本的寫法可以允許 `t` 是 `void*`，而且會成功編譯
* `void` 不用特別處理，因為 `t buf[NEXT_POWER_OF_2(s)]` 的部分就會導致編譯錯誤 `error: declaration of ‘buf’ as array of voids`
* 參考[第 2 周測驗題](https://hackmd.io/@sysprog/linux2020-quiz2)使用 [_Static_assert](https://en.wikichip.org/wiki/c/static_assertion)
* `_Static_assert` 中要求只能使用 constant expression 來進行判斷，但一開始想不到如何使用 constant expression 來判斷字串，查詢後發現可以用 `strncmp`
* 原因是 gcc 有將它列入 [Built-in Functions](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)，所以可以在 compile time 的時候 evaluate
* `strncmp` 只比對前 4 字元是為了同時檢查 `void *` 和 `void*` 這兩種型態
### Memory Handling
[folly::fbvector](https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md) 一開始就提到配置動態記憶體大小使用的 growth factor 會影響效能，其中 2 是一個不建議的數值，因為任何新配置的記憶體大小一定會大於之前配置過的記憶體的總和，造成 vector 無法重新利用曾經配置的空間。這點可以由下式驗證，例如欲配置的空間大小是 $2^4$ 時，過去已配置的空間總和是 $2^5 - 1$
$2^0 + 2^1 + 2^2 + 2^3 + ... 2^n = 2^{n+1} - 1$
最理想的方案是使用與 allocator 相同的策略，如此一來可以有最佳的使用效率，但單純使用 `realloc` 沒辦法達成，所以 folly::fbvector 才會使用 jemalloc。
:::warning
很重要的發現！在後續的作業 (如 `kcalc` 及 `kecho`) 可運用客製化的 memory allocator
:notes: jserv
:::
#### 使用 1.5 作為 growth factor 的輔助函式
嘗試使用 1.5 作為 growth factor，這裡以資料筆數做為計算的依據，而不是使用實際配置的記憶體大小，會這麼決定有幾個原因
* 不是每個數字都適合成為記憶體大小，例如說 91 bytes
* 可以用一套一樣的邏輯管理不同資料型態的 vector
* 程式碼的更動比較少
在實做更動以前，須先完成相關的輔助函式
```cpp
#define FACTOR 1.5
#define CHUNK_SIZE 4
static inline float ilog_factor(float n) /* log1.5(n) = log2(n)/log2(1.5)*/
{
return ceilf(log2f(n)/log2f(FACTOR));
}
```
* 根據容量計算最接近的 capacity 比較麻煩，無法像以 2 為底進行計算時單純使用 bitwise shift
* 根據 $log_{1.5}(n) = \frac{log_{2}(n)}{log_{2}(1.5)}$ 進行計算，並嘗試全部都用標準函式庫來實作
* 最大可用資料數量為 $chunk\ size\times1.5^{capacity}$ (我選定的初始 chunk size 為 4 筆資料)
```cpp
#define vec_capacity(v) __vec_capacity(&v)
static size_t inline __vec_capacity(void *vec)
{
union {
STRUCT_BODY(char);
struct {
size_t filler;
char buf[];
};
} *v = vec;
if (v->on_heap) {
return (size_t) (pow(1.5, v->capacity) * CHUNK_SIZE);
}
return CHUNK_SIZE;
}
```
* 原本的 `vec_capacity` 沒辦法直接以 macro 的方式寫，改以函式寫
* 單純只是要算得數字沒問題，但要兼顧速度就非常困難，牽涉到浮點數的運算，運算成本一定會增加
以 `CHUNK_SIZE = 4` `FACTOR = 1.5` 為例，修改後的資料筆數會以如下方式成長
```
4 6 9 13 20 30 45 ...
```
#### 驗證數值正確性
用以下程式碼驗證，結果無誤
```cpp
int main(int _argc, char **_argv)
{
for (int i = 4; i < 4097; i++) {
int capacity = ilog_factor((float)i/CHUNK_SIZE);
int full_size = (size_t) (pow(1.5, capacity) * CHUNK_SIZE);
assert(i <= full_size);
//printf("input: %d capacity: %d full size: %d\n", i, capacity, full_size);
}
}
```
#### 計算數字的速度差異
實際比對以 1.5 與 2 做為 growth factor 時，計算 capacity 以及最大可用容量時的時間
```cpp
#define FACTOR 1.5
#define CHUNK_SIZE 8.0
int main(int _argc, char **_argv)
{
struct timespec t_start, t_end;
int result = 0;
for (int i = 4; i < 4097; i++) {
clock_gettime(CLOCK_MONOTONIC, &t_start);
result = ilog2(i); /* original method */
//result = 1 << result;
clock_gettime(CLOCK_MONOTONIC, &t_end);
long long t1 = (long long)(t_end.tv_sec * 1e9 + t_end.tv_nsec)
- (long long)(t_start.tv_sec * 1e9 + t_start.tv_nsec);
clock_gettime(CLOCK_MONOTONIC, &t_start);
result = ilog_factor((float)i/CHUNK_SIZE); /* mymethod */
//result = (size_t) (pow(1.5, result) * CHUNK_SIZE);
clock_gettime(CLOCK_MONOTONIC, &t_end);
long long t2 = (long long)(t_end.tv_sec * 1e9 + t_end.tv_nsec)
- (long long)(t_start.tv_sec * 1e9 + t_start.tv_nsec);
printf("%d %lld %lld\n", i, t1, t2);
}
return 0;
}
```
* `ilog_facor` 的計算時間約為 `ilog2` 的 2 倍
* `pow(1.5, capacity)` 的時間約為 `1 << capacity` 的 3~4 倍
* 以 `pow` 計算次方值為常數時間，比用遞迴的方式好
#### 修改 growth factor 為 1.5 (待補)
原本宣告 vector 的 macro 中是使用 `t buf[NEXT_POWER_OF_2(s)]` 來設置最初在 stack 占用的空間，我改為固定以 `CHUNK_SIZE = 4` 作為起始大小，主要是現階段以固定 chunk size 的實作比較簡單
```diff
#define v(t, s, name, ...) \
_Static_assert(strncmp(#t, "void", 4), "error type"); \
union { \
STRUCT_BODY(t); \
struct { \
size_t filler; \
- t buf[NEXT_POWER_OF_2(s)]; \
+ t buf[CHUNK_SIZE]; \
}; \
} 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])
+ name.capacity = 0
```
會動到記憶體配置的 `__vec_push_back` 與 `__vec_push_back` 也須做相對應的更動
```diff
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)));
+ v->ptr = realloc(v->ptr, elemsize * (size_t)
+ (pow(1.5, (v->capacity = ilog_factor((float) n / CHUNK_SIZE))) * CHUNK_SIZE));
} else {
void *tmp =
- malloc(elemsize * (size_t) 1 << (v->capacity = ilog2(n)));
+ malloc(elemsize * (size_t)
+ (pow(1.5, (v->capacity = ilog_factor((float) n / CHUNK_SIZE))) * CHUNK_SIZE));
memcpy(tmp, v->buf, elemsize * v->size);
v->ptr = tmp;
v->on_heap = 1;
}
}
}
```
```diff
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);
+ v->ptr = realloc(v->ptr, elemsize * (size_t)
+ (pow(1.5, ++v->capacity) * CHUNK_SIZE));
memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
} else {
if (v->size == capacity) {
void *tmp =
- malloc(elemsize * (size_t) 1 << (v->capacity = capacity + 1));
+ malloc(elemsize * (size_t) (pow(1.5, ++v->capacity) * CHUNK_SIZE));
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);
}
}
```
### 實作 vector 經典操作 (待補)
###### tags: `linux 2020`
Sign in with Wallet
Connect another wallet