# 2020q1 Homework2 (quiz2)
contributed by < `pingsutw` >
> 重新回答[第 2 周測驗題](https://hackmd.io/@sysprog/linux2020-quiz2)
## 解題思路
`xs_new` 分別依據 `len` 大小，來判斷新的字串要存 heap or stack, 當字串大於 16 時，資料存在 heap，所以這邊 `AAA` 代表 16
```cpp
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);
memcpy(x->ptr, p, len);
} else {
memcpy(x->data, p, len);
x->space_left = 15 - (len - 1);
}
return x;
}
```
`BBB = 32` 因為 char 0~255 分別代表不同字元，mask 每單位代表 8 個字元 `8*32 = 256`, 每個 bit 分別代表 char 不同字元
`CCC = &` 因為 mask 裡的每個 bit 代表要刪除的字元，跟 mask 裡的每個 bit 做 ＆，如果是0代表沒有找到符合的字元，反之刪除此字元
```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
}
```
## 延伸問題
- [x] 解釋上述程式碼運作原理，並提出改進方案，可善用 GDB 追蹤和分析;
- [x] 以上述程式碼為基礎，提供字串複製 (應考慮到 CoW) 和類似 strtok 功能的函式實作;
- [ ] 設計實驗，確認上述字串處理最佳化 (針對空間效率) 帶來的效益，應考慮到 locality of reference;
- [ ] 在 Linux 核心原始程式碼中，找出類似手法的 SSO 或 CoW 案例並解說;
### `xs_copy`
字串在 stack 時，複製 string 到 dest，當字串存在 heap 時，有指針指向 src的 data，避免在大字串額外的記憶體複製
- cow (Copy on write)
加一個 int pointer 表示 refernece count, refcnt = NULL, 代表沒有其他指標指向同一快記憶體空間 ptr，反之 > 1 代表有 1 個以上同時指向同一個記憶體空間
```cpp
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 */
int *refcnt;
};
```
```cpp
xs *xs_copy(xs *dest, xs *src) {
if (xs_is_ptr(src)) {
printf("Data on heap\n");
dest->is_ptr = true;
dest->ptr = src->ptr;
dest->size = xs_size(src);
if (!src->refcnt) {
dest->refcnt = src->refcnt = (int *)malloc(sizeof(int));
*(dest->refcnt) = 1;
} else {
dest->refcnt = src->refcnt;
*(dest->refcnt) += 1;
}
} else {
printf("Data on stack\n");
memcpy(dest->data, src->data, 16);
dest->is_ptr = false;
dest->space_left = 15 - xs_size(src);
}
return dest;
}
```
測試
1. 先做 concat 讓 string 存在 heap 裡
2. copy string，此時不會新增一段新的記憶體空間，而是指標指向 string 的位址
3. 對 copy string 做 trim 此時才會新增新的記憶體空間，並對字串進行修改，可發現記憶體位址跟 string 已經不一樣了
```cpp
xs copy;
string = *xs_tmp("foobarbar");
prefix = *xs_tmp("(((((");
suffix = *xs_tmp(")))))");
xs_concat(&string, &prefix, &suffix);
xs_copy(©, &string);
printf("\nBefore trim\n");
printf("[%s], %2zu\n", xs_data(&string), xs_size(&string));
printf("[%s], %2zu\n", xs_data(©), xs_size(©));
printf("string %p\ncopy %p\n", xs_data(&string), xs_data(©));
xs_trim(©, "\n ");
printf("\nAfter trim\n");
printf("[%s], %2zu\n", xs_data(©), xs_size(©));
printf("string %p\ncopy %p\n", xs_data(&string), xs_data(©));
```
輸出結果
```
Before trim
[(((((foobarbar)))))], 19
[(((((foobarbar)))))], 19
string 0x55555555a6a0
copy 0x55555555a6a0
After trim
[(((((foobarbar)))))], 19
string 0x55555555a6a0
copy 0x55555555a6f0
```
### `xs_strtok`
- 將字串分割成一個個片段, x 欲被分解的字串, delim 分隔的字串(符號), 用 `strspn` 找出分解後的字串的起始點，`strpbrk` 找出分解後的字串的的終點，並設為 `\0` 代表字串
- `lastToken` 代表下一個分解後的字串的起始點
```cpp
char *xs_strtok(xs *x, const char *delim) {
char static *lastToken = NULL;
char *tmp = NULL;
char *str = NULL;
if ( x == NULL ) {
str = lastToken;
if (str == NULL)
return NULL;
} else {
str = xs_data(x);
str += strspn(str, delim);
}
/* Find end of segment */
tmp = strpbrk(str, delim);
if (tmp) {
*tmp = '\0';
lastToken = tmp + 1;
} else {
lastToken = NULL;
}
return str;
}
```
測試
```cpp
char delim[8] = "- ", *tmp;
string = *xs_tmp("foo-bar-bar");
printf("\nBefore xs_strtok \n");
printf("[%s], %2zu\n", xs_data(&string), xs_size(&string));
printf("delim = %s\n", delim);
printf("%s\n", xs_strtok(&string, delim));
while(tmp = xs_strtok(NULL, delim))
printf("%s\n", tmp);
```
輸出結果
```
Before xs_strtok
[foo-bar-bar], 11
delim = -
foo
bar
bar
```
## 程式優化
:::warning
TODO (Kevin) 重新測量，把 outlier 去除
:::
- 優化前, 分別測量一百萬次，再取平均
測試
```cpp
struct timespec start, stop;
double t1 = 0, t2 = 0;
int times = 1000000;
xs string = *xs_tmp("\n foobarbar \n\n\n");
xs prefix = *xs_tmp("((("), suffix = *xs_tmp(")))");
for(int i = 0; i < times; i++){
clock_gettime(CLOCK_MONOTONIC, &start);
xs_trim(&string, "\n ");
clock_gettime(CLOCK_MONOTONIC, &stop);
t1 += diff_in_ns(start, stop);
}
printf("[%s] : %2zu\n", xs_data(&string), xs_size(&string));
for (int i = 0; i < times; i++){
clock_gettime(CLOCK_MONOTONIC, &start);
xs_concat(&string, &prefix, &suffix);
clock_gettime(CLOCK_MONOTONIC, &stop);
t2 += diff_in_ns(start, stop);
}
printf("[%s] : %2zu\n", xs_data(&string), xs_size(&string));
printf("trim : %.10lf ns concat : %.10lf ns\n", t1/times, t2/times);
```
輸出結果
```
[foobarbar] : 9
[(((((((((((((((((((((((()))] : 21
trim : 67.6565360000 ns concat : 83.8203580000 ns
```
## 參考資料
<s>
- [size_t strspn(const char *str1, const char *str2)](http://tw.gitbook.net/c_standard_library/c_function_strspn.html)
- [char *strpbrk(const char *str1, const char *str2)](http://tw.gitbook.net/c_standard_library/c_function_strpbrk.html)
</s>
:::danger
關於 C 標準函式庫的參考資料，務必以 Linux man page 為主，方可知道語言規範和實作的議題。避免閱讀第 N 手材料
:notes: jserv
:::
<s>- [C 語言:typedef 的用法](https://magicjackting.pixnet.net/blog/post/65865174)
</s>
:::danger
改為查閱 C 語言規格書！
:notes: jserv
:::
- https://github.com/facebook/folly
###### tags: `sysprog2020`
Sign in with Wallet
Connect another wallet