2020q3 Homework11 (quiz 11)

contributed by < JimmyLiu0530 >

tags: 進階電腦系統理論與實作

測驗1: Vector

考慮到一個針對空間處理最佳化的 vector 實作

支援以下操作:

• vec_push_back: 新增元素至 vector 的尾端，必要時會進行記憶體重新配置;
• vec_pop_back(): 刪除 vector 最尾端的元素;

每個 vector 都有兩個重要的屬性:

• 容量 (capacity) : 是這個 vector 擁有的空間。
• 長度 (size): 實際儲存了元素的空間大小。capacity 永遠不小於 size。

使用示範:

int main()
{
    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);
    printf("capacity(vec1)=%zu, capacity(vec2)=%zu\n", vec_capacity(vec1),
           vec_capacity(vec2));
    printf("pos(vec2,2)=%d\n", vec_pos(vec2, 2));

#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)

    display(vec1);
    vec_push_back(vec1, 0.0);
    display(vec1);
    vec_push_back(vec1, 1.1);
    display(vec1);
    vec_push_back(vec1, 2.2);
    display(vec1);
    vec_push_back(vec1, 3.3);
    display(vec1);
    vec_push_back(vec1, 4.4);
    display(vec1);
    vec_push_back(vec1, 5.5);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);

    return 0;
}

預期輸出:

pos(vec2,0)=13, pos(vec2,1)=42
capacity(vec1)=4, capacity(vec2)=128
pos(vec2,2)=88
stack
0.00 stack
0.00 1.10 stack
0.00 1.10 2.20 stack
0.00 1.10 2.20 3.30 stack
0.00 1.10 2.20 3.30 4.40 heap
0.00 1.10 2.20 3.30 4.40 5.50 heap
0.00 1.10 2.20 3.30 4.40 heap
0.00 1.10 2.20 3.30 heap
0.00 1.10 2.20 heap
0.00 1.10 heap
0.00 heap
heap

本體的實作程式如下:

#include <stddef.h>
#include <stdio.h>                           
#include <stdlib.h>
#include <string.h>

/* vector with small buffer optimization */

#define STRUCT_BODY(type)                                                  \
    struct {                                                               \
        size_t size : 54, on_heap : 1, capacity : 6, flag1 : 1, flag2 : 1, \
            flag3 : 1;                                                     \
        type *ptr;                                                         \
    }

#define NEXT_POWER_OF_2(s) \
    VV1                    \
        ? s                \
        : (size_t) 1 << (64 - __builtin_clzl(s)) /* next power of 2 */

#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 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))

static NON_NULL void vec_free(void *p)
{
    STRUCT_BODY(void) *s = p;
    if (s->on_heap)
        free(s->ptr);
}

static inline int ilog2(size_t n)
{
    return 64 - __builtin_clzl(n) - ((n & (n - 1)) == 0);
}

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;
        }
    }
}

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);
    }
}

請補完程式碼。

參閱 你所不知道的C語言：技巧篇 以得知 GCC extension: attribute cleanup 使用技巧。

程式說明

從 main 開始看，首先，line 3-4 建立兩個 vector，vec1 跟 vec2，其中 vec1 的 capacity 為 4，vec2 的 capacity 為 2。這邊是 4 的原因其實是因為當初在建立 vector 時，到底要配多大的空間給這個 vector 是取決於 NEXT_POWER_OF_2(s)。在 NEXT_POWER_OF_2(s) 希望配置一個大於等於 s 的最小 2 的冪次方，舉例來說，s = 3，則配置 4。因此，VV1 為 (s & (s - 1)) == 0。

接著，line 8 欲在 vec2 尾端新增元素 88，但因為 vec2 已經滿了，所以若要新增元素，則觸發 reallocation。

line 9 呼叫 vec_reserve(vec2, 100)，一樣會配置 2 的冪次方的空間給 vec2，只是在於這裡是因為函式 ilog2 ，因此 vec2 的 capacity 變成 128。

接下來，不斷地插入元素到 vec1 尾端，並觀察它的變化。我們發現在插入第 5 個元素 (即 4.4) 時，由於 vec1 已滿，所以會出觸發 reallocation，使得原本存於 stack 的 vec1，變成存於 heap 中。
插入完後，改成不斷從 vec1 尾端刪除元素，並觀察。先看 vec_pop_back(v)，因為刪除元素不會影響該 vector 的 capacity，只會影響 size，因此，VV2 為 v.size -= 1。再來，vec1 也不會因為元素個數的減少，改回存於 stack 中，所以我們可以看到經過一連串的刪除，vec1 都仍存於 heap。

延伸問題

1. 指出上述實作的限制並提出改進方案;

2. 參照 folly::fbvector 文件和對應原始程式碼，以上述程式為基礎，實作 vector 經典操作

補充1: GNU extension 的應用

1. __attribute__: 使編譯器在編譯時期作特殊的處理或是檢查。依照處理的對象主要分成三種:
   • function attribute: 針對 函式
   • variable attribute: 針對 變數
   • type attribute: 針對 struct 或 union

以此題為例:

#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__}};
    ...

在第 8 行，宣告完一個 union name 後，緊接的就是一個 type attribute，代表賦予這個 name 特定的性質，而這個性質就是當程式執行結束時，會自動的釋放當初在 heap 占用 (即動態配置) 的記憶體，不需手動釋放。

能賦予的性質有很多，像這邊也有針對 函式 賦予性質的例子: __attribute__((nonnull))。此性質是說這個函式的 augment 不應該是一個 null pointer，但如果是的話，compiler 就會發出警告。

2. __VA_ARGS__: Variadic Macros
   一樣舉上面那個例子，簡單來說，__VA_ARGS__ 就等同於 macro v 的那些不定引數(即 …)

補充2: Preprocessor 的應用

連結