---
# System prepended metadata

title: 2020q1 Homework2 (quiz2)

---

# 2020q1 Homework2 (quiz2)
contributed by < [timmycc](https://github.com/timmycc/SSO) >

## 原題大意
> [題目](https://hackmd.io/@sysprog/linux2020-quiz2)

介紹 FB 針對頻繁的短字串處理做 SSO(Small String Optimization)，以folly::fbstring 取代 std::string，對各別大小的字串做出最適當的處理，而本測驗嘗試以 C 重現 folly::fbstring，同樣以 stack 來儲存短字串，但不同的是儲存的字串大小縮減為15 bytes，學習在特定的目的之下做出相對應的效能提升。

>AAA 和 BBB 為整數，CCC 是 operator，。Count Leading Zeros (clz) 或名 Number of Leading Zeros (nlz) 為計算 2 進位數從 MSB 往右數遇到的第一個 1 之前所有 0 的數量，因此，clz(0001010100011011) 會得到 3。GCC 內建了許多功能強大的函式，其中一項就是 __builtin_clz，注意，當參數為 0 時，結果未定義:補完正確的程式碼，使得其執行結果符合預期。

> 編譯方式: $ gcc -o xs -std=gnu11 xs.c


## 逐步理解

### 結構

可以看到結構中建立了一些 1 bit 的資訊，其中 space_left 則類似於 folly::fbstring 中表示空間的方法: 紀錄剩餘空間而非當前大小，16 bytes 中以15 bytes 來儲存字元，其餘資訊放置在剩下的1 byte 中，包含了剩餘空間、儲存在 stack 還是 heap、flag 等。

```cpp
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

typedef union {
    /* allow strings up to 15 bytes to stay on the stack
     * use the last byte as a null terminator and to store flags
     * much like fbstring:
     * https://github.com/facebook/folly/blob/master/folly/docs/FBString.md
     */
    char data[16];

    struct {
        uint8_t filler[15],
            /* how many free bytes in this stack allocated string
             * same idea as fbstring
             */
            space_left : 4,
            /* if it is on heap, set to 1 */
            is_ptr : 1, flag1 : 1, flag2 : 1, flag3 : 1;
    };

    /* heap allocated */
    struct {
        char *ptr;
        /* supports strings up to 2^54 - 1 bytes */
        size_t size : 54,
            /* capacity is always a power of 2 (unsigned)-1 */
            capacity : 6,
        /* the last 4 bits are important flags */
    };
} xs;
```

### 最後一個 byte 有什麼用?
將大小以`剩餘的空間`來表示是為了讓 stack 儲存的字串到15個字的時候，剩餘空間也會為0，包含 is_ptr 跟 flag，此時最後一個 byte (00000000, space_left, is_ptr, flag)可以表達 terminator，這樣的設計讓這個架構在16 byte 的空間中足以表達15 byte的字串以及其他資訊，再經過第二個 struct 的設計，讓我們可以儲存要的資訊又可保留前面結構中的最後一個 byte。從這邊定義的函式可以看出如何判斷目標是放在 heap 還是 stack，並由最後一個 byte 中的資料來獲取我們要的結果。

```cpp
static inline bool xs_is_ptr(const xs *x) { return x->is_ptr; }
static inline size_t xs_size(const xs *x)
{
    return xs_is_ptr(x) ? x->size : 15 - x->space_left;
}
static inline char *xs_data(const xs *x)
{
    return xs_is_ptr(x) ? (char *) x->ptr : (char *) x->data;
}
static inline size_t xs_capacity(const xs *x)
{
    return xs_is_ptr(x) ? ((size_t) 1 << x->capacity) - 1 : 15;
}
```

### 裡面有哪些功能?

AAA! 這邊 xs_new 的內容大致上就是初始化一個 xs 來放 input p，AAA 用來檢查某個東西，檢查什麼呢? 如果 len > AAA 的話，底下最明顯的一個設定 x.is_ptr = true，可以知道這邊是讓他儲存在 heap 之內，根據先前的設定可以知道，這東西大小是16個字元，因此 AAA 選 `(c) 16`。

特別的是在 malloc 給 x.ptr 的寫法給人一種眼睛為之一亮的感覺，不過這邊另外加了檢查 malloc 有沒有成功的部分，避免出現失敗後對 NULL 進行後續的操作。

```cpp
#define xs_literal_empty() \
    (xs) { .space_left = 15 }

static inline int ilog2(uint32_t n) { return 32 - __builtin_clz(n) - 1; }

xs *xs_new(xs *x, const void *p)
{
    *x = xs_literal_empty();
    size_t len = strlen(p) + 1;
    if (len > AAA) {
        x->capacity = ilog2(len) + 1;
        x->size = len - 1;
        x->is_ptr = true;
        x->ptr = malloc((size_t) 1 << x->capacity);
        if (!x->ptr) {
            perror("malloc failed");
            return NULL;
        }
        memcpy(x->ptr, p, len);
    } else {
        memcpy(x->data, p, len);
        x->space_left = 15 - (len - 1);
    }
    return x;
}
```

這邊則是讓 xs 可以依照需求成長，當需求超過 stack 儲存的範圍便換去 heap，這邊同樣有 allocation 的動作，因此同樣在 allocation 後新增檢查，確保回傳的指標不為 NULL。

```cpp
/* grow up to specified size */
xs *xs_grow(xs *x, size_t len)
{
    if (len <= xs_capacity(x))
        return x;
    len = ilog2(len) + 1;
    if (xs_is_ptr(x))
        x->ptr = realloc(x->ptr, (size_t) 1 << len);
        if (!x->ptr) {
            perror("realloc failed");
            return x;
        }
    else {
        char buf[16];
        memcpy(buf, x->data, 16);
        x->ptr = malloc((size_t) 1 << len);
        if (!x->ptr) {
            perror("malloc failed");
            return x;
        }
        memcpy(x->ptr, buf, 16);
    }
    x->is_ptr = true;
    x->capacity = len;
    return x;
}
```

這邊則是新增字串到目標頭尾

```cpp
static inline xs *xs_newempty(xs *x)
{
    *x = xs_literal_empty();
    return x;
}

static inline xs *xs_free(xs *x)
{
    if (xs_is_ptr(x))
        free(xs_data(x));
    return xs_newempty(x);
}

xs *xs_concat(xs *string, const xs *prefix, const xs *suffix)
{
    size_t pres = xs_size(prefix), sufs = xs_size(suffix),
           size = xs_size(string), capacity = xs_capacity(string);

    char *pre = xs_data(prefix), *suf = xs_data(suffix),
         *data = xs_data(string);

    if (size + pres + sufs <= capacity) {
        memmove(data + pres, data, size);
        memcpy(data, pre, pres);
        memcpy(data + pres + size, suf, sufs + 1);
        string->space_left = 15 - (size + pres + sufs);
    } else {
        xs tmps = xs_literal_empty();
        xs_grow(&tmps, size + pres + sufs);
        char *tmpdata = xs_data(&tmps);
        memcpy(tmpdata + pres, data, size);
        memcpy(tmpdata, pre, pres);
        memcpy(tmpdata + pres + size, suf, sufs + 1);
        xs_free(string);
        *string = tmps;
        string->size = size + pres + sufs;
    }
    return string;
}
```
由 macro 中可以看出 mask 操作的 index 為 uint8_t / 8，最大值為31，所以 `BBB = (a)32`。

再看第二個 macro set_bit(byte)，想像 `for (i = 0; i < trimlen; i++) set_bit(trimset[i])` 操作的過程，這部分會依序檢查 trimset，並且跟1做 inclusive or，用意在於用 uint8_t 這0~255的範圍紀錄 trimset 中出現了哪些字，比如說 trimset = "A"，則 mask[65 / 8] |= 1 << 65 % 8，即將 mask[8] 設成 0000 0010，如果 trimset = "AB"，那就是 mask[8] |= 0000 0010; mask[8] |= 0000 0100。 

從 xs_trim 中可以看出，check_bit 會對 dataptr[i] 逐一檢查，應該要用 & 來比對，所以 `CCC = (b)&`。

```cpp
xs *xs_trim(xs *x, const char *trimset)
{
    if (!trimset[0])
        return x;

    char *dataptr = xs_data(x), *orig = dataptr;

    /* similar to strspn/strpbrk but it operates on binary data */
    uint8_t mask[BBB] = {0};

#define check_bit(byte) (mask[(uint8_t) byte / 8] CCC 1 << (uint8_t) byte % 8)
#define set_bit(byte) (mask[(uint8_t) byte / 8] |= 1 << (uint8_t) byte % 8)

    size_t i, slen = xs_size(x), trimlen = strlen(trimset);

    for (i = 0; i < trimlen; i++)
        set_bit(trimset[i]);
    for (i = 0; i < slen; i++)
        if (!check_bit(dataptr[i]))
            break;
    for (; slen > 0; slen--)
        if (!check_bit(dataptr[slen - 1]))
            break;
    dataptr += i;
    slen -= i;

    /* reserved space as a buffer on the heap.
     * Do not reallocate immediately. Instead, reuse it as possible.
     * Do not shrink to in place if < 16 bytes.
     */
    memmove(orig, dataptr, slen);
    /* do not dirty memory unless it is needed */
    if (orig[slen])
        orig[slen] = 0;

    if (xs_is_ptr(x))
        x->size = slen;
    else
        x->space_left = 15 - slen;
    return x;
#undef check_bit
#undef set_bit
}
```

底下給了測試用的函式，測試輸入 foobarbar 以及 ((( + foobarbar + ))) 的結果。

```cpp
/* Memory leaks happen if the string is too long but it is still useful for
 * short strings.
 * "" causes a compile-time error if x is not a string literal or too long.
 */
#define xs_tmp(x)                                          \
    ((void) ((struct {                                     \
         _Static_assert(sizeof(x) <= 16, "it is too big"); \
         int dummy;                                        \
     }){1}),                                               \
     xs_new(&xs_literal_empty(), "" x))

#include <stdio.h>

int main()
{
    xs string = *xs_tmp("\n foobarbar \n\n\n");
    xs_trim(&string, "\n ");
    printf("[%s] : %2zu\n", xs_data(&string), xs_size(&string));

    xs prefix = *xs_tmp("((("), suffix = *xs_tmp(")))");
    xs_concat(&string, &prefix, &suffix);
    printf("[%s] : %2zu\n", xs_data(&string), xs_size(&string));

    return 0;
}
```

## 比較 xs 與 std::string 之差距

我們找出 std::string 中對應到 xs 的操作，使用兩者對隨機產生的字串做測量，分別給定四種範圍
1. 16 bytes 以內
2. 17~255 bytes
3. 256~1024 bytes 
4. 小於 1024 bytes

- [ ] 結果

## Copy-on-write 之應用

這邊另外新增一個類似於 strcpy 的函式，包含了 copy-on-write，從前面 folly::fbstring 的例子中，字串大小在超過 255 bytes 後便改由採取 CoW 的手法，而這邊我們採取同樣的策略，對大小超過 255 bytes 的字串複製時使用 CoW，當字串大小超過254時，將指標指向目標，否則放入 dest->ptr，然而完成 CoW 還需要對其他修改的函式進行相關的調整。

```cpp
xs *xs_cpy(xs *dest, xs *src) 
{
    if (xs_is_ptr(src)) {
        dest->size = src->size;
        dest->capacity = src->capacity;
        dest->is_ptr = true;
        if (src->size > 254) {
            dest->ptr = src->ptr;
        } else {
            dest->ptr = malloc((size_t) 1 << src->capacity);
            if (!dest->ptr) {
                perror("malloc failed");
                return NULL;
            }
            memcpy(dest->ptr, src->ptr, src->size + 1);
        }
    } else {
        memcpy(dest->data, src->data, xs_size(src) + 1);
        dest->is_ptr = false;
        dest->space_left = src->space_left;
    }
    return dest;
}
```
- [ ] 調整其他修改的函式
- [ ] 完成後分析增進的效能


## 建立類似 `strtok` 之函式



# Case study: linux

