HackMD
2020q1 Homework2 (quiz2)
contributed by < timmycc >
原題大意
介紹 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 等。
#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 中的資料來獲取我們要的結果。
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 進行後續的操作。
#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。
/* 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;
}
這邊則是新增字串到目標頭尾
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)&。
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 + ))) 的結果。
/* 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 的操作，使用兩者對隨機產生的字串做測量，分別給定四種範圍
- 16 bytes 以內
- 17~255 bytes
- 256~1024 bytes
- 小於 1024 bytes
- 結果
Copy-on-write 之應用
這邊另外新增一個類似於 strcpy 的函式，包含了 copy-on-write，從前面 folly::fbstring 的例子中，字串大小在超過 255 bytes 後便改由採取 CoW 的手法，而這邊我們採取同樣的策略，對大小超過 255 bytes 的字串複製時使用 CoW，當字串大小超過254時，將指標指向目標，否則放入 dest->ptr，然而完成 CoW 還需要對其他修改的函式進行相關的調整。
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;
}
- 調整其他修改的函式
- 完成後分析增進的效能
