# 2021q1 Homework3 (quiz3)
contributed by < `WayneLin1992` >
###### tags: `linux2021`
## 延伸問題
- [x] 解釋運作原理，並提出改進方案
- [x] 提供字串複製的函式實作
- [ ] 設計實驗，確認上述字串處理最佳化
- [ ] 將 string interning 機制整合，提出最佳化的字串處理工具函式庫
- [ ] 在 Linux 核心碼中，找出 SSO 或 CoW 案例並解說
## 題目理解
### 理解結構
[fbstring](https://github.com/facebook/folly/blob/master/folly/docs/FBString.md) 目的要達到緊湊的記憶體佈局，確保有相對的空間可以存大量的字串，之後再對 CoW 而不是使用複製將其中字串進行複製， stack 對 cache 較為友善。
`xs` 定義 16個字元組
* 字串長度小於或等於 15 個位元組，則放在 stack
* 字串長度大於或等於 16 個位元組，則放在 heap (透過 malloc 系統呼叫配置所需字串大小)
* ptr 為 8位元
* size 為 54
* capacity 定義為 6 其中有4存 flag
#### `xs struct`
```cpp
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, is_large_string : 1, flag2 : 1, flag3 : 1;
};
/* heap allocated */
struct {
char *ptr;
/* supports strings up to 2^MAX_STR_LEN_BITS - 1 bytes */
size_t size : MAX_STR_LEN_BITS,
/* capacity is always a power of 2 (unsigned)-1 */
capacity : 6;
/* the last 4 bits are important flags */
};
} xs;
```
:::info
`union` 不同於一般的 `struct` 他會存取最大 member ，意思就是不配置所有 member 空間。
實驗:
```cpp
typedef union {
struct {
int member[10],
a : 1,
c : 1;
};
struct {
char* st;
};
} foo;
struct __moo {
struct {
int member[10],
a : 1,
c : 1;
};
struct {
char* st;
};
};
typedef struct __moo moo;
int main(){
printf("moo: %d \n", sizeof(moo));
printf("foo: %d \n", sizeof(foo));
}
```
>moo: 56
>foo: 48
可以觀察到 `moo` 和 `foo` 差 8 bytes，差在 `char*` 。
當假如想存取一個 `foo->member[1]` 時又想存取後 `foo->st` 時會發生什麼?
```cpp
int main(){
foo *t = malloc(sizeof(foo));
t->member[1] = 10;
printf("member[1]: %d \n", t->member[1]);
char i = 'h';
t->st = &i;
printf("member[1]: %d \n", t->member[1]);
printf("pointer to char in the st: %c", *(t->st));
}
```
>member[1]: 10
>member[1]: 0
>pointer to char in the st: h
由此可以看出，在 `union` 的作用下，只能存取其中一個 member ，所以 fbstring 就是字串只能存在 stack 或 heap 中，這也反應為什麼 struct 中為什麼要有類似的 member 如 `size` 及 `space_left`。
思考 struct bit-field 是否會存在? 畢竟就算字串存入 heap 中還是要先詢問 `is_ptr` 才知道。
實驗
```cpp
int main(){
foo *t = malloc(sizeof(foo));
t->a = 1;
t->c = 0;
printf("a : %d \n", t->a);
printf("c : %d \n", t->c);
char i = 'h';
t->st = &i;
printf("a : %d \n", t->a);
printf("c : %d \n", t->c);
}
```
>a : -1
>c : 0
>a : -1
>c : 0
是不會變得，因為 bit-field 存在 memory 地址比 `char*` 高，所以不會互相影響。
:::
```graphviz
digraph fbstring {
node [shape=record];
rankdir=LR;
union [label="<f0> data|<f3> |<f4>"];
data [label="<f0> data[0] |<f1> data[1]|... |<f2> data[15]"]
filler [label="<f0> filler|space_left : 4 bits|<f1> is_ptr : 1 bit|<f2>s_large_string : 1 bit|flag2 : 1 bit|flag3 : 1 bit"]
ptr [label="<f0> ptr|<f1> size : 54 bits|<f2> capacity : 6 bits"]
filler1 [label="<f0> filler[0]|<f3> filler[1]|<f4> filler[2]|...|<f5> filler[14]"]
union:f3->filler:f0;
union:f4->ptr:f0;
filler:f0->filler1:f0;
union:f0->data:f0
}
```
#### `xs_data`
```cpp
static inline char *xs_data(const xs *x)
{
if (!xs_is_ptr(x))
return (char *) x->data;
if (xs_is_large_string(x))
return (char *) (x->ptr + OFF);
return (char *) x->ptr;
}
```
`xs_data` function 目的:尋找字串所在位置。
假如字串不在 data 中就會從 heap 中找，而 heap 中又有4 bytes 存入 reference count 因為可以推測出 `OFF` = `4`
#### `ilog2`
```cpp
static inline int ilog2(uint32_t n) { return LLL; }
```
`ilog2` function 目的:log~2~n 將會 return 次方項
可以使用 clz 指令可從 MSB 開始計算0的數量，並用32 - clz 代表從 LSB 計算到最高出現1的位置，但是次方項跟位置不相同次方向從0開始計算但數量由1開始計算，所以需要再減1 e.g. `32 - clz(0000 0000 0000 0000 1000 0000 0000 1000)` = 16，`ilog(32776)` = 15。
`LLL` = `32 - __builtin_clz(n) - 1`
#### `xs_allocate_data`
```cpp
static void xs_allocate_data(xs *x, size_t len, bool reallocate)
{
/* Medium string */
if (len < LARGE_STRING_LEN) {
x->ptr = reallocate ? realloc(x->ptr, (size_t) 1 << x->capacity)
: malloc((size_t) 1 << x->capacity);
return;
}
/* Large string */
x->is_large_string = 1;
/* The extra 4 bytes are used to store the reference count */
x->ptr = reallocate ? realloc(x->ptr, (size_t)(1 << x->capacity) + 4)
: malloc((size_t)(1 << x->capacity) + 4);
xs_set_refcnt(x, 1);
}
```
`xs_allocate_data` function 目的: 由字串長度判斷是否需要 reallocate 空間
`reallocate` 設定為1時，代表需要重新分配，所以 `malloc` 新的空間。
`1 << x->capacity` 代表配置的大小。
當 `is_large_string` = 1 時，就要將 offset 4 bytes 給 reference count。
#### `xs_ _refcnt`
```cpp
static inline void xs_set_refcnt(const xs *x, int val)
{
*((int *) ((size_t) x->ptr)) = val;
}
static inline void xs_inc_refcnt(const xs *x)
{
if (xs_is_large_string(x))
++(*(int *) ((size_t) x->ptr));
}
static inline int xs_dec_refcnt(const xs *x)
{
if (!xs_is_large_string(x))
return 0;
return --(*(int *) ((size_t) x->ptr));
}
static inline int xs_get_refcnt(const xs *x)
{
if (!xs_is_large_string(x))
return 0;
return *(int *) ((size_t) x->ptr);
}
```
`xs_set_refcnt` : long_string 所 offset 4 bytes 是給 int 存取 reference count。
`xs_inc_refcnt` : reference count + 1。
`xs_dec_refcnt` : reference count - 1。
`xs_get_refcnt` : 取得 reference count
#### `xs_tmp`
```cpp
#define xs_tmp(x) \
((void) ((struct { \
_Static_assert(sizeof(x) <= MAX_STR_LEN, "it is too big"); \
int dummy; \
}){1}), \
xs_new(&xs_literal_empty(), x))
```
`xs_tmp` macro 目的: 初始化，並將 x 寫入 xs struct 中。
#### `xs_literal_empty`
```cpp
#define xs_literal_empty() \
(xs) { .space_left = 15 }
```
`xs_literal_empty` macro 目的: 初始化，並將 `space_left` = 15 。
#### `xs_new`
```cpp
xs *xs_new(xs *x, const void *p)
{
*x = xs_literal_empty();
size_t len = strlen(p) + 1;
if (len > NNN) {
x->capacity = ilog2(len) + 1;
x->size = len - 1;
x->is_ptr = true;
xs_allocate_data(x, x->size, 0);
memcpy(xs_data(x), p, len);
} else {
memcpy(x->data, p, len);
x->space_left = 15 - (len - 1);
}
return x;
}
```
`xs_new` function 目的:創造新的xs。
要由想存入內部的 string 長度來判斷出要存在 stack 中還是存入 heap 當中，xs struct 可以知道 stack 可以存15字元，因此 `NNN` = `16`。
#### `xs_trim`
```cpp
xs *xs_trim(xs *x, const char *trimset)
{
if (!trimset[0])
return x;
char *dataptr = xs_data(x), *orig = dataptr;
if (xs_cow_lazy_copy(x, &dataptr))
orig = dataptr;
/* similar to strspn/strpbrk but it operates on binary data */
uint8_t mask[32] = {0};
#define check_bit(byte) (CCC)
#define set_bit(byte) (SSS)
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
}
```
`xs_trim` function 目的:將對應到的字元進行刪減。
`set_bit(trimset[i])` set bit 要將我們要對應的字元存入 mask 當中，竟然要存入 `|` or 及 `=` 是要被使用的，因此`SSS` = `mask[(uint8_t) byte / 8] |= 1 << (uint8_t) byte % 8` 而 check bit 將是用 mask 對 byte 檢查是否有指定 bit ，所以將使用 `&` 因此 `SSS` = `mask[(uint8_t) byte / 8] & 1 << (uint8_t) byte % 8`
#### `xs_cow_lazy_copy`
```cpp
static bool xs_cow_lazy_copy(xs *x, char **data)
{
if (xs_get_refcnt(x) <= 1)
return false;
/* Lazy copy */
xs_dec_refcnt(x);
xs_allocate_data(x, x->size, 0);
if (data) {
memcpy(xs_data(x), *data, x->size);
/* Update the newly allocated pointer */
*data = xs_data(x);
}
return true;
}
```
`xs_cow_lazy_copy` function 目的: 將 data 進行複製 至 x 中。
但 is_large_string 才會設置 reference count `if (xs_get_refcnt(x) <= 1)` 代表 is_large_string 才能使 `xs_cow_lazy_copy` 作用。
#### `xs_grow`
```cpp
xs *xs_grow(xs *x, size_t len)
{
char buf[16];
if (len <= xs_capacity(x))
return x;
/* Backup first */
if (!xs_is_ptr(x))
memcpy(buf, x->data, 16);
x->is_ptr = true;
x->capacity = ilog2(len) + 1;
if (xs_is_ptr(x)) {
xs_allocate_data(x, len, 1);
} else {
xs_allocate_data(x, len, 0);
memcpy(xs_data(x), buf, 16);
}
return x;
}
```
`xs_grow` 字串從 stack 轉換至 heap
`x->is_ptr = true` ，但後面 `if(xs_is_ptr(x))` 就會不會存在 `else` 的情況，所以 `is_ptr` 不管本來是 `1` 還是 `0->1` 都會重新配置空間。
#### `xs_concat`
```cpp
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);
xs_cow_lazy_copy(string, &data);
if (size + pres + sufs <= capacity) {
memmove(data + pres, data, size);
memcpy(data, pre, pres);
memcpy(data + pres + size, suf, sufs + 1);
if (xs_is_ptr(string))
string->size = size + pres + sufs;
else
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;
}
```
`xs_concat` 將 `prefix` 及 `suffix` 寫入 `string` 中
:::info
[bit-field](https://hackmd.io/@sysprog/c-bitfield) 筆記
```cpp
bool is_one(int i) { return i == 1; }
int main() {
struct { signed int a : 1; } obj = { .a = 1 };
puts(is_one(obj.a) ? "one" : "not one");
return 0;
}
```
> not one
`puts()` 為 `int puts(const char *str)` 可以將char 直接顯示並且會附帶 `\n` 使其自動換行。
原本 signed int 需要 4 byte 存取，`signed int a : 1;` 代表由 1 bit 來表示， `.a = 1` 表示 a 的 1 bit 裡面存 1 ，又因 signed bit 只能表示 `0` 或 `-1` ，這裡 1 代表 `-1` 的意思，所以結果為 not one 。
```cpp
/*
* Force a compilation error if condition is true, but also produce a
* result (of value 0 and type size_t), so the expression can be used
* e.g. in a structure initializer (or where-ever else comma expressions
* aren't permitted).
*/
#define BUILD_BUG_ON_ZERO(e) (sizeof(struct { int:(-!!(e)); }))
```
macro 檢查是否有 compilation error
* `-!!(e)` 對e做兩個 `NOT` 代表其中 `true` 時 `e = 0` ， 反之 false `e = -1` 。
```cpp
struct foo {
int a : 3;
int b : 2;
int : 0; /* Force alignment to next boundary */
int c : 4;
int d : 3;
};
int main() {
int i = 0xFF;
struct foo *f = (struct foo *) &i;
printf("a=%d\nb=%d\nc=%d\nd=%d\n", f->a, f->b, f->c, f->d);
return 0;
}
```
> a=-1
> b=-1
> c=0
> d=-2
查看一下 address of a b c d ， a b 在 `(int *) 0x61fe14` ， c d 在 `(int *) 0x61fe18` 所以 c d 產生 undefind behavior (UB) 每次執行出來的值都會有所不同， `int : 0` 被稱為 unnamed bit-field 代表此空間沒有 bit-field package 了，所以 c d就會讀取下一個空間。
```graphviz
digraph fbstring {
node [shape=record];
foo [label="0x61fe14|0|0|0|0|0|0|0|1|1|1|<f5>1|<f4>1|<f3>1|<f1>1|<f0>1"];
a->foo:f0;
a->foo:f1;
a->foo:f3;
b->foo:f4;
b->foo:f5;
foo1 [label="0x61fe18|0|0|0|0|0|0|0|<f8>0|<f7>1|<f6>1|<f5>0|<f4>0|<f3>0|<f1>0|<f0>0"]
c->foo1:f0;
c->foo1:f1;
c->foo1:f3;
c->foo1:f4;
d->foo1:f5;
d->foo1:f6;
d->foo1:f7;
}
```
:::
#### 實際行為與可改進空間
可以觀察到 `filler` 和 `data` 存取相同的內容，代表可以改進。
觀察到 `size` 怪異，看 `xs_size`
```cpp
static inline size_t xs_size(const xs *x)
{
return xs_is_ptr(x) ? x->size : 15 - x->space_left;
}
```
可以了解到當存入 stack 時 `size` 要用 `15 - x->space_left` 所以 `"\n foobarbar \n\n\n"` `size` = `15` 。
### 改進程式
#### `xs` struct 改寫
將 data 從 struct 中刪去，並把存入 data 改存入 filler。
```graphviz
digraph fbstring {
node [shape=record];
rankdir=LR;
union [label="<f3> |<f4>"];
filler [label="<f0> filler|space_left : 4 bits|<f1> is_ptr : 1 bit|<f2>s_large_string : 1 bit|flag2 : 1 bit|flag3 : 1 bit"]
ptr [label="<f0> ptr|<f1> size|<f2> capacity: 6 bits"]
filler1 [label="<f0> filler[0]|<f3> filler[1]|<f4> filler[2]|...|<f5> filler[14]"]
union:f3->filler:f0;
union:f4->ptr:f0;
filler:f0->filler1:f0;
}
```
>[foobarbar] : 9
>[(((foobarbar)))] : 15
#### 改寫 `xs_grow`
因為 else 將不會被執行到，觀察到使用 `xs_grow` 部分，為 `xs_concat` 中， `tmps` 將會一直保持著 `xs_is_ptr(tmps)` == 0 ， 狀態所以 `else` 完全沒使用的，還有 `ptr->is_large_string` 情況需要考慮。
```cpp
xs tmps = xs_literal_empty();
xs_grow(&tmps, size + pres + sufs);
```
```cpp
xs *xs_grow(xs *x, size_t len)
{
char buf[16];
if (len <= xs_capacity(x))
return x;
if (!xs_is_ptr(x))
memcpy(buf, x->filler, 16);
/* from stack to heap */
if(len < LARGE_STRING_LEN){
x->is_ptr = true;
x->capacity = ilog2(len) + 1;
if (xs_is_ptr(x)) {
xs_allocate_data(x, len, 1);
}
/* from is_ptr to is_large_string*/
}else{
x->is_ptr = true;
x->is_large_string = true;
x->capacity = ilog2(len) + 1;
xs_allocate_data(x, len, 1);
}
return x;
}
```
>[foobarbar] : 9
>[sssssssssssssssssssssssssssssssswwwwwwwwwwwwaaaaasssssssssssssssssssssssssssssssswwwwwwwwwwwwaaaaasssssssssssssssssssssssssssssssswwwwwwwwwwwwaaaaasssssssssssssssssssssssssssssssswwwwwwwwwwwwaaaaasssssssssssssssssssssssssssssssswwwwwwwwwwwwaaaaafoobarbarxxxxxxx)))))))] : 268
>reference count : 1
## 提供字串複製的函式實作
### copy on write 解釋
有效的利用記憶體空間，"duplicate" or "copy" ， "duplicate" 不進行修改，所以不需要使用新的資源，當要對字串進行修改時，就需要對字串進行 "copy" 將字串進行複製，並將其中 reference count 也要對應進行加減。
#### `xs_cow_copy`
對於 `is_large_string` 字串，進行 duplicate ，並修改 reference count ，而 `is_ptr` 及 stack 字串將直接複製。
```cpp
xs* xs_cow_copy_long(xs* src){
xs* dest = malloc(sizeof(xs));
if(!xs_is_ptr(src)){
*dest = *src;
}else if(src->is_large_string){
dest->capacity = src->capacity;
dest->size = src->size;
dest->is_large_string = src->is_large_string;
xs_inc_refcnt(src);
dest->ptr = src->ptr;
}else{
dest->is_ptr = src->is_ptr;
dest->size = src->size;
size_t len = xs_size(src) + 1;
xs_allocate_data(dest, len, 0);
char *dest_data = malloc(len*sizeof(char));
strncpy(dest_data, xs_data(src), len);
dest->ptr = dest_data;
}
return dest;
}
```
>test on the stack
[foobarbar] : 9
[foobarbar] : 9
000000000061FD90 : 000000000061FD80
test on the heap
[Wayne is a smart, kind and friendly man ] : 40
[e is a smart, kind and friendly man ] : 40
0000000000A815B0 : 0000000000A81640
test is large string
[sssssssssssssssssssssssssssssssswwwwwwwwwwwwaaaaasssssssssssssssssssssssssssssssswwwwwwwwwwwwaaaaasssssssssssssssssssssssssssssssswwwwwwwwwwwwaaaaasssssssssssssssssssssssssssssssswwwwwwwwwwwwaaaaasssssssssssssssssssssssssssssssswwwwwwwwwwwwaaaaaWayne is a smart, kind and friendly man ] : 285
[sssssssssssssssssssssssssssssssswwwwwwwwwwwwaaaaasssssssssssssssssssssssssssssssswwwwwwwwwwwwaaaaasssssssssssssssssssssssssssssssswwwwwwwwwwwwaaaaasssssssssssssssssssssssssssssssswwwwwwwwwwwwaaaaasssssssssssssssssssssssssssssssswwwwwwwwwwwwaaaaaWayne is a smart, kind and friendly man ] : 285
0000000000741680 : 0000000000741680
對於 `is_large_string` 要 write 時就要將字串進行 copy 並將字串進行修改，要注意必須 offset 4 bytes 為了寫入 reference count。
```cpp
bool xs_cow_write_long(xs*src, char *data){
if(!xs_is_large_string(src))
return false;
if(strlen(data) < LARGE_STRING_LEN)
return false;
char* data2 = malloc(strlen(data)*sizeof(char)+4);
memcpy(data2+4,data, strlen(data));
data2[strlen(data)+4] = '\0';
src->ptr = data2;
xs_set_refcnt(src, 1);
src->size = strlen(data);
return true;
}
```
>[aaaassssssssssssssssssssssssssssssssssssssssssssswwwwwwwwwwwwaaaaasssssssssssssssssssssssssssssssswwwwwwwwwwwwaaaaasssssssssssssssssssssssssssssssswwwwwwwwwwwwaaaaasssssssssssssssssssssssssssssssswwwwwwwwwwwwaaaaasssssssssssssssssssssssssssssssswwwwwwwwwwwwaaaaa] : 262
reference count 1
:::info
[Optimize string use: a case study](https://www.oreilly.com/content/optimize-string-use-case-study/)
1. 靜態分配比動態分配，來的快，而且靜態分配在結束時，會自動 free 掉。
2. 動態分配空間給字串，成本相當高，為了讓字串可以接受修改變動，所以一般會動態配置 power of two 的空間給字串，但這也造成不必要的浪費。
3. CoW雖然降低動態配置，但因為每次都要需要改動 reference count 會使成本變高，在 C++11 就取消 CoW 方式。
嘗試優化程式
`remove_ctrl`
```cpp
std::string remove_ctrl(std::string s) {
std::string result;
for (int i=0; i<s.length(); ++i) {
if (s[i] >= 0x20)
result = result + s[i];
}
return result;
}
```
整體執行 24.8 ms
`remove_ctrl_mutating`
```cpp
std::string remove_ctrl_mutating(std::string s) {
std::string result;
for (int i=0; i<s.length(); ++i) {
if (s[i] >= 0x20)
result += s[i];
}
return result;
}
```
將程式改成 += 減少不必要的複製，使整體速度上升x13倍， 1.72 ms
`remove_ctrl_ref_args`
```cpp
std::string remove_ctrl_ref_args(std::string const& s) {
std::string result;
result.reserve(s.length());
for (int i=0; i<s.length(); ++i) {
if (s[i] >= 0x20)
result += s[i];
}
return result;
}
```
const 提取 string，而非複製，提升8%，執行時間1.6ms
`remove_ctrl_ref_args_it`
```cpp
std::string remove_ctrl_ref_args_it(std::string const& s) {
std::string result;
result.reserve(s.length());
for (auto it=s.begin(),end=s.end(); it != end; ++it) {
if (*it >= 0x20)
result += *it;
}
return result;
}
```
將字串引用執行時間縮短為 1.04ms。
`remove_ctrl_cstrings`
```cpp
void remove_ctrl_cstrings（char * destp，char const * srcp，size_t size）{
for（size_t i = 0; i <size; ++ i）{
if（srcp [i]> = 0x20）
* destp ++ = srcp [i];
}
* destp = 0;
}
```
c style string 使執行時間縮短為 0.15ms，因為 c style string 有優秀的 cache locality 尤其在大量使用時，更是優異。
除了可以在語法上優化，還能在演算法、編譯器選擇、資料庫的選擇 (folly::fbstring) ，都是能改進著手的地方，但是最後還是要從速度、方便性和安全性中，取得平衡點。
:::
## 設計實驗，確認上述字串處理最佳化
### 測試建立字串 `std::string` `xs`
建立 50 組字串，每組字串長度範圍是 256 到 300，所以這裡是測試 heap 部分，`xs` 主要存入 `char *` 再保存到 `xs->ptr` 最終釋放 `xs` 配置空間，`std::string` 則透過 `string` 來操作字串。
實作如下
[xs testbench](https://github.com/WayneLin1992/linux20201_week3/blob/main/teststringc.c)
[std::string testbench](https://github.com/WayneLin1992/linux20201_week3/blob/main/tetstringcpp.cpp)
- [ ] `xs`
```shell
==5081== HEAP SUMMARY:
==5081== in use at exit: 0 bytes in 0 blocks
==5081== total heap usage: 54 allocs, 54 frees, 31,648 bytes allocated
==5081==
==5081== All heap blocks were freed -- no leaks are possible
```
- [ ] `std::string`
```shell
==4373== HEAP SUMMARY:
==4373== in use at exit: 0 bytes in 0 blocks
==4373== total heap usage: 9 allocs, 9 frees, 91,698 bytes allocated
==4373==
==4373== All heap blocks were freed -- no leaks are possible
```
測試 stack ，50組字串，每組字串有8~13個字母， c 存入 `xs->filler` 並 free `xs` ， cpp 存入 `string` 。
stack 方面 `xs` 和 `std::string` 執行時間上沒有差距，但可以看出在 記憶體配置 方面， `xs` 可以更好的利用空間，但 `string` 會一次提取大的空間，
- [ ] `xs`
```shell
==3456== HEAP SUMMARY:
==3456== in use at exit: 0 bytes in 0 blocks
==3456== total heap usage: 5 allocs, 5 frees, 9,150 bytes allocated
==3456==
==3456== All heap blocks were freed -- no leaks are possible
```
- [ ] `std::string`
```shell
==3469== HEAP SUMMARY:
==3469== in use at exit: 0 bytes in 0 blocks
==3469== total heap usage: 5 allocs, 5 frees, 90,032 bytes allocated
==3469==
==3469== All heap blocks were freed -- no leaks are possible
```
觀察 heap `xs` 的 cache misses 和 `std::string` cache misses
- [ ] `xs`
```shell
Performance counter stats for './teststringc' (6 runs):
31,850 cache-misses # 33.310 % of all cache refs ( +- 2.96% )
95,618 cache-references ( +- 1.11% )
1,341,525 instructions # 0.89 insn per cycle ( +- 0.49% )
1,500,931 cycles ( +- 4.25% )
21,306 L1-dcache-load-misses ( +- 1.88% )
0.0016249 +- 0.0000927 seconds time elapsed ( +- 5.70% )
```
- [ ] `std::string`
```shell
Performance counter stats for './tetstringcpp' (6 runs):
50,560 cache-misses # 26.400 % of all cache refs ( +- 2.68% )
191,516 cache-references ( +- 0.74% )
3,650,056 instructions # 1.19 insn per cycle ( +- 0.17% )
3,059,521 cycles ( +- 3.27% )
43,775 L1-dcache-load-misses ( +- 1.81% )
0.00378 +- 0.00124 seconds time elapsed ( +- 32.89% )
```
:::info
查看 std::string 所分配的 string.capacity() 空間，發現到一開始配置277之後遇到較長的字串，277是因為 testbench 第一行字串為277長度 ，就會配置兩倍的容量554這方面 `xs` 會直接配置 power of 2 的容量，所以會配置512來保存256~300的字串。
>277
277
554
554
觀察 `xs` 的記憶體分配狀況
其中 `xs_allocate` peak 在 516 為 512 bytes 給字串 和 4 給 reference count
`main` 為 getline 寫成 `char*` 空間為 300 bytes
`fopen@@` 為 fopen 所消耗
觀察 `std::string`的記憶體配置狀況
`???` 為初始化動態連結 ld-init.c (圖中橘色部分)
`__fopen` 為 fopen 所消耗
`std::string` 為可分為兩部份 一個是 `getline` 將檔案字串存入 `string str` 中，另一部份就是將 `str` 寫入 `string file_contents` 中 各自為 8KB，共 16KB 。
總結：
1. 由此可以知道 `std::string` 和 `xs` 在建立字串中兩者執行時間上沒有明顯優劣
2. `std::string` 有更多的 member 要存取導致所消耗記憶體空間較大，也就是說 `xs` 有效的節省空間
參考資料：
[cpp std::string](http://www.cplusplus.com/reference/string/string/)
:::
### 測試 `concat` `trim` `cow`
建立 50 組字串的三個文字檔案，
第一個文字檔:每組字串長度範圍是 256 到 300 字母為'a'。
第二個文字檔:每組字串長度範圍是 8 到 13 字母為'b'。
第三個文字檔:每組字串長度範圍是 5 到 8 字母為'c'。
分別存入 `xs` 中，然後使用 `concat` 將其中合併，之後使用 `trim` 將 'c' 修剪掉，在使用 `cow_copy` duplicate，在使用 `cow_write` 將字串修改。
`std::string` 則透過 `string` 來操作字串，使用 + 將字串合併， 要注意 `trim` 在 `std::string` 中沒有相關實作，所以需要額外增加函數， duplicate 後再使用修改。
- [ ] `xs`
其中可以注意到 `xs_allocate` 的部分，在新 malloc 空間卻又沒有將原本的空間 free 掉。
- [ ] `std::string`
### 思考
[Locality of reference](https://en.wikipedia.org/wiki/Locality_of_reference)
:::info
cache-friendly code:
Spatial locality:資料存取在附近的位置
Temporal locality:讓資料能重複使用
Branch locality:減少跳躍指令的使用
觀察上面建立 `xs` 和 `std::string` 中的 cache-misses
- [ ] `xs`
```shell
Performance counter stats for './teststringc' (6 runs):
31,850 cache-misses # 33.310 % of all cache refs ( +- 2.96% )
95,618 cache-references ( +- 1.11% )
1,341,525 instructions # 0.89 insn per cycle ( +- 0.49% )
1,500,931 cycles ( +- 4.25% )
21,306 L1-dcache-load-misses ( +- 1.88% )
0.0016249 +- 0.0000927 seconds time elapsed ( +- 5.70% )
```
- [ ] `std::string`
```shell
Performance counter stats for './tetstringcpp' (6 runs):
50,560 cache-misses # 26.400 % of all cache refs ( +- 2.68% )
191,516 cache-references ( +- 0.74% )
3,650,056 instructions # 1.19 insn per cycle ( +- 0.17% )
3,059,521 cycles ( +- 3.27% )
43,775 L1-dcache-load-misses ( +- 1.81% )
0.00378 +- 0.00124 seconds time elapsed ( +- 32.89% )
```
尤其中 cache-misses 和 instructions 經過計算後知道 cache misses 的比例，不能只比較 cache misses 的數量，因此
`xs`: 31,850 cache-misses/1,341,525 instructions = 2.3%
`std::string`: 50,560 cache-misses/3,650,056 instructions = 1.3%
因此可以知道在建立字串部分， `std::string` 表現比 `xs` 好。
觀察 copy on write 部份
- [ ] `xs`
```shell
Performance counter stats for './testcow' (6 runs):
32,869 cache-misses # 30.139 % of all cache refs ( +- 4.18% )
109,060 cache-references ( +- 2.08% )
1,570,834 instructions # 1.00 insn per cycle ( +- 1.42% )
1,563,503 cycles ( +- 4.78% )
23,669 L1-dcache-load-misses ( +- 3.93% )
0.001758 +- 0.000274 seconds time elapsed ( +- 15.57% )
```
- [ ] `std::string`
```shell
Performance counter stats for './testcppcow' (6 runs):
55,682 cache-misses # 26.654 % of all cache refs ( +- 2.03% )
208,904 cache-references ( +- 0.69% )
3,796,018 instructions # 1.19 insn per cycle ( +- 0.19% )
3,189,342 cycles ( +- 2.24% )
47,729 L1-dcache-load-misses ( +- 0.47% )
0.00860 +- 0.00590 seconds time elapsed ( +- 68.63% )
```
`xs`: 在 cache misses 及 執行時間都有較好的表現
`std::string`: 在 指令方面有較好的表現
使用 gdb 觀察其中的差距， `std::string` `&str` 的位置 (std::__cxx11::string *) 0x62f5f0 而存放字串的位置 0x54640 'a' 將 str 複製 (std::__cxx11::string *) 0x62f590 存放字串的位置 0x54640 'a'，而 stack 時字串存放的位置 `&prefix` (std::__cxx11::string *) 0x62f5d0 其中字串位置 0x62f5e0 ， 而將 prefix 進行複製 `&file_prefix` (std::__cxx11::string *) 0x62f570 而字串位置為 0x62f580。
觀察其中字串位置變化
總結:
1. 短字串一樣是將整個 `struct` 進行複製而短字串也會存入 `struct` 當中。
2. 長字串一樣是 CoW 將 `struct` 複製，並使用指標，指向字串位置。
這方面 `xs` 和 `std::string` 是相同的。
參考資料:
[what is a "cache-friendly code"](https://stackoverflow.com/questions/16699247/what-is-a-cache-friendly-code)
:::
## 整合 string interning
:::info
TODO:
:::
Sign in with Wallet
Connect another wallet