Try   HackMD

2020q1 Homework3 (quiz4)

contributed by < OscarShiang >

tags: linux2020

測試環境

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

作業要求

  • 重新回答測驗題
  • 解釋測驗 1 程式運作的原理，改寫為更精簡且等效的程式碼;
  • 考慮到 alignment 和 word size，改寫為執行效率更高的程式碼;
  • 在 Linux 核心原始程式碼找出逐 bit 進行資料複製的程式碼，並解說相對應的情境;
  • 解釋測驗 2 程式運作的原理，比照 quiz2 進行效率分析;
  • 指出測驗 2 所述實作的限制並提出改進方案;
  • 參照 folly::fbvector 文件和對應原始程式碼，以測驗 2 程式為基礎，實作 vector 經典操作

測驗 1

題目分析

首先 KK1 是在剛進入 bitcopy 函式的地方，根據 read_lhs, read_rhs 與 source 位移的操作可以判斷 _read & 7 的目的在於計算 _read % 8 的數值，因為如果除數是

2n 時，可以利用將變數與
2n−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 後，可以把程式碼簡化為下列形式：

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

bitsize = (_count > 8) ? 8 : _count; 這樣的敘述可換為 bitwise operation

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

已成功實作 bitwise operation 的版本
Oscar[color= orange]

使用 perf 測量分支數量

$ sudo perf record \
-e branch-misses:u,branch-instructions:u \
-F 30000 ./bitcopy

$ sudo perf report

原始版本的測量結果如下所列

Available samples
432 branch-misses:u
1K branch-instructions:u

改寫的版本測量如下

Available samples
261 branch-misses:u
859 branch-instructions:u

從結果可以看到減少了許多的分支

接下來進行實驗測量簡化後的版本與原始版本的差異
實驗的結果如下圖（以排除干擾因素）

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

從實驗結果可以看出因為去除了多餘的判斷，所以在執行上可以減少許多為了判斷特定情況而花費的時間，在 bitcopy 的數量為

8000 時可以減少大約
1μs 的時間

測驗 2

題目分析

VV1 是位在 NEXT_POWER_OF_2 的 macro 之中，該 macro 在實作的就是計算大於給定 s 中最小的 2 的次方，如果符合 VV1 的條件，就直接回傳回去，如果不符合 VV1 的條件，則利用 __builtin_clzl 來計算

所以從程式碼中得知 VV1 是在判斷給定的 s 是否為 2 的次方，而其所使用的技巧就是如果 s 是一個 2 的次方的話，其在二進位的表示上就會是：

010000002 這種的形式，而 s - 1 就會是
001111112 ，表示將兩者進行 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 的宣告

#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 的宣告中

#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 的問題產生，所以在實作中加入檢查邊界的判斷

#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() 停止程式

Assertion failed: (vec1.size > 0), function main, file vector.c, line 171.
[1]    16207 abort      ./vector

vec_pos 造成的記憶體存取問題

因為在 vec_pos 的實作如下列

#define vec_pos(v, n) vec_data(v)[n]  /* lvalue */

因為其並未實作出檢查邊界，所以在 n 超出 v.size 時會存取到未使用的元素空間或是 n < 0 時會產生分預期的行為。

使用函式將取值與 assert 包裝起來：

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 將回傳回來的位址轉型後取值

#define vec_pos(v, n) *(__typeof__(v.buf[0]) *) __vec_pos(&v, n, vec_elemsize(v))  /* lvalue */

測試超出邊界的呼叫

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 來觸發編譯時期的錯誤

#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 的判斷

#define SAFE_TYPE(type) (strcmp(#type, "void") && strcmp(#type, "void *"))

原本想要使用 _Generic 來實作，但是發現 _Generic 不能接受型態作為參數使用，所以改以 macro 字串化的特性來實作 SAFE_TYPE

宣告一個元素型態為 void 的 vector 來進行測試

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

確認其在編譯時期會導致錯誤

$ 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 ，所以利用 memmove 來避免未定義行為的發生

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 實作介面：

#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 類似，但是因為不用考慮超過容量的問題，所以只需要將給定位置之後的元素向前位移即可

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 的介面

#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 週測驗題
  2. folly::fbvector
Last changed by 
 
Oscar Shiang
0
546

Read more

Interesting Facts of Pthread

It may exit immediately if we replace line 24 with return 0.

Feb 25, 2024
OS HW1: Benchmark Your Computer Black Box

學號: F74076124 姓名: 向景亘 系級: 資訊 111 開發環境 OS: Ubuntu 20.04 CPU: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz CPU cores: 4 Memory: 16 GB Programming Language: C11, gcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0

May 7, 2023
程式設計(二) Lab 3 講解

lab3 A 部分 題目說明 根據從 file.in 讀入的資料，將最重的 5 隻牛的體重加總起來輸出 使用 fstream 使用前需要在原始碼的上方加上 #include &lt;fstream&gt; 利用 constructor 進行開檔或是利用 member function 的形式開啟檔案 open 函式的參數形式是 open(filename, open_mode)

May 7, 2023
Qt Graphics 系列介紹

常見 QGraphics 系列元件介紹與使用示範

May 7, 2023
Read more from Oscar Shiang
Published on HackMD