# 2020q3 Homework2 (quiz2) contributed by < `eecheng87` > ###### tags: `進階電腦系統應用2020` ## 測驗 1 若要檢查是否為 ASCII，只需要看 most significant 的 bit 是否為 1，另外本題是把 8 個 8 bits 的字元合成 64 bits 的資料。所以該選 `0x8080808080808080` ### 延伸問題 先來確認一下一次檢查 64 bits 是否會比較快，結果當然是沒錯！`is_ascii` 為改善後的版本： ![](https://i.imgur.com/32pDS2g.png) 接著透過 SSE4.2 提供的 intrinsic 來和 `is_ascii` 比較效能，後者為考題第二個實做版本。 在這就不解釋 SSE 的基本操作(基本知識可參考[這](https://www.csie.ntu.edu.tw/~r89004/hive/sse/page_1.html))，只紀錄如何逐步達成要求。本次使用 SSE4.2 的 `_mm_cmpistrm` 來達成需求。`_mm_cmpistrm` 的原形為 `__m128i _mm_cmpistrm (__m128i a, __m128i b, const int imm8)`，當中 `a` 是想找的字元，而 `b` 是被找的來源，那 `imm8` 就是調整各種模式的地方（這裡須注意的是 `imm8` 在呼叫的時候就要給定值，不能用變數代替） 首先我們先處理前兩個參數，該如何把字串轉成 `__m128i`，這裡使用 `_mm_loadu_si128` 來達成要求，所以使用方式如下： ```cpp const __m128i a = _mm_loadu_si128((const __m128i *)target); ``` 這裡值得注意的是，將 `char*` 轉成 `__m128i` 有兩種方式，以上是 unalign 版本，比較方便。宣告完字串就可以轉了。反之，若使用 `_mm_load_si128` 的話，轉型前的字串必須對齊 16 bits。所以需要做一些前處理： ```cpp int ierr = posix_memalign((void **)&a, 16, 16 * sizeof(char)); if (ierr != 0) { fprintf(stderr, "Memory allocation failure."); exit(EXIT_FAILURE); } ... strcpy(a, FILTER_SET); ``` 先配置一塊對齊好的記憶體，再填入字元，如此一來就能使用 `_mm_load_si128`。 當然，若載入的資料已經對齊了，會比較快（unalign loaded 會比對齊好的多一條指令）。對應的實驗可參可[這裡](https://stackoverflow.com/questions/20259694/is-the-sse-unaligned-load-intrinsic-any-slower-than-the-aligned-load-intrinsic-o)，結論是 align load 會快百分之五，算是蠻少的。之所以會這麼說是因為接下來的實驗： 倘若 align load 比較好，那何嘗不用此法？因為還需要額外的處理，所以接著要來比較是否值得花時間來額外處理，來達到效能提昇。分別用載入對齊資料 (`_mm_loadu_si128`) 和載入非對齊資料 (`_mm_load_si128`) 後做 `_mm_cmpistrm` 的效能差異，以下將兩種版本的收尋包成函式： ```cpp unsigned ucmpistrm(const char *target, const char *in) { /* load data which is unaligned */ const __m128i ma = _mm_loadu_si128((const __m128i *)target); const __m128i mb = _mm_loadu_si128((const __m128i *)in); const unsigned mask = _mm_cvtsi128_si32(_mm_cmpistrm( ma, mb, _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ANY | _SIDD_BIT_MASK)); return mask; } unsigned alcmpistrm(const char *target, const char *in) { /* load data which is alread aligned */ const __m128i ma = _mm_load_si128((const __m128i *)target); const __m128i mb = _mm_load_si128((const __m128i *)in); const unsigned mask = _mm_cvtsi128_si32(_mm_cmpistrm( ma, mb, _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ANY | _SIDD_BIT_MASK)); return mask; } ``` 接著設計實驗，為了避免干擾，所以分開執行： ```cpp if (strcmp(argv[1], "align") == 0) { for (int i = 0; i < EXPTIME; i++) { clock_gettime(CLOCK_REALTIME, &t1); strcpy(a, FILTER_SET); strcpy(b, INPUT_SET); alcmpistrm(a, b); clock_gettime(CLOCK_REALTIME, &t2); printf("%ld\n", get_elapse(t1, t2)); } } else { for (int i = 0; i < EXPTIME; i++) { clock_gettime(CLOCK_REALTIME, &t1); ucmpistrm(FILTER_SET, INPUT_SET); clock_gettime(CLOCK_REALTIME, &t2); printf("%ld\n", get_elapse(t1, t2)); } } ``` 以上可以看到，在使用對齊版本的 `cmp` 時還需要呼叫兩次 `strcpy` 來填入對齊的記憶體，所以會產生 overhead。 實驗結果： ![](https://i.imgur.com/SzYJgFX.png) 可以發現堅持使用叫快的載入對齊並不是在每種狀況下都適合。所以接下來的實做將使用非對齊載入。 以下比較用 SSE 的 intrinsic 和傳統 branch 來檢查字串是否有特定符號： ```cpp #define FILTER_SET ",.?!" #define INPUT_SET "ff$j@ufhvaiubviu" bool valid_notation(const char *in) { for (int i = 0; i < 16; i++) { if (in[i] == ',' || in[i] == '.' || in[i] == '!' || in[i] == '?') { return true; } } return false; } ... int main(){ for (int i = 0; i < EXPTIME; i++) { clock_gettime(CLOCK_REALTIME, &t1); ucmpistrm(FILTER_SET, INPUT_SET); clock_gettime(CLOCK_REALTIME, &t2); printf("%ld ", get_elapse(t1, t2)); clock_gettime(CLOCK_REALTIME, &t1); valid_notation(INPUT_SET); clock_gettime(CLOCK_REALTIME, &t2); printf("%ld ", get_elapse(t1, t2)); } return 0; } ``` 比較用 SSE 加速後成果： ![](https://i.imgur.com/y2VWPWq.png) 明顯看出 SSE 的確加速 到目前為止，我在 `imm8` 中使用的設定是 `_SIDD_CMP_EQUAL_ANY`，但是這就有一個很大的缺點。倘若我們要篩選的集合很大，如：想檢查是否含 a\~zA\~Z，那這樣可能就要分好幾個 `__m128i` 了。但是其實不用，在 `imm8` 中還有提供一個好用的設定 `_SIDD_CMP_RANGES`。從原始碼可以看出如何使用： ```cpp 1: // ranges IntRes1 := 0 FOR i := 0 to UpperBound FOR j := 0 to UpperBound IntRes1[i] := IntRes1[i] OR (BoolRes.word[i].bit[j] AND BoolRes.word[i].bit[j+1]) j += 2 ENDFOR ENDFOR ``` 也就是說如果今天想要檢查是否含 a~z，那就要把 `a` 填成 `{'a','z'}`。而其他的部份則同上，不須改動。 下面的圖是看看 `imm8` 用 `FOR_ANY` 和 `RANGE` 是否有差，結果是沒差的： ![](https://i.imgur.com/ZPWFci2.png) 最後則是改寫考題的 `is_ascii`，使用考題提供的一次比較 64 位元的 `is_ascii` 和使用 SSE4.2 intrinsic 加速後的 `is_ascii`： ```cpp bool is_ascii(const char str[], size_t size) { if (size == 0) return false; int i = 0; while ((i + 8) <= size) { uint64_t payload; memcpy(&payload, str + i, 8); if (payload & 0x8080808080808080) return false; i += 8; } while (i < size) { if (str[i] & 0x80) return false; i++; } return true; } bool is_ascii_sse(const char str[], size_t size) { char range_set[16]; memset(range_set, 0, strlen(range_set)); range_set[0] = 0; range_set[1] = 127; __m128i ma; __m128i mb = _mm_loadu_si128((const __m128i *)&range_set[0]); unsigned mask; if (size == 0) return false; int i = 0; while ((i + 16) <= size) { ma = _mm_loadu_si128((const __m128i *)(str + i)); mask = _mm_cvtsi128_si32(_mm_cmpistrm( ma, mb, _SIDD_UBYTE_OPS | _SIDD_CMP_RANGES | _SIDD_BIT_MASK)); i += 16; } while (i < size) { if (str[i] & 0x80) return false; i++; } return true; } ``` 實驗方式是拿一個長度 10000 的字串來檢查，為了避免 cache 干擾，每個 iterate 都產生新的字串。並且生成的字串都為 ASCII（這樣才不會檢查到一半就跳出 function，而是跑完整條字串） ```cpp for (int i = 0; i < EXPTIME; i++) { for (int i = 0; i < LEN; i++) { str[i] = 'A' + (rand() % 26); } clock_gettime(CLOCK_REALTIME, &t1); (void)is_ascii(str, sizeof(str)); clock_gettime(CLOCK_REALTIME, &t2); printf("%ld ", get_elapse(t1, t2)); clock_gettime(CLOCK_REALTIME, &t1); (void)is_ascii_sse(str, sizeof(str)); clock_gettime(CLOCK_REALTIME, &t2); printf("%ld\n", get_elapse(t1, t2)); } ``` 實驗結果： ![](https://i.imgur.com/TPT7vn5.png) 符合預期，SSE 的加速效果顯著。 ## 測驗 2 這題原理是先判斷(透過 `mask`)是數字或是英文，如果是的話結果加 9。 仔細來說的話 `letter = in & MASK` 剛好利用 `afAF` 在第 2 個 bit 都是 1 的特性，來分辨數字或字母。 接著若是字母的話要再加上 9。(將 `letter` 透過 bitwise 變成 9，再次巧妙避開 branch) ## 測驗 3 由 [/div.h](https://github.com/jemalloc/jemalloc/blob/dev/src/div.c) 推導的結論，`quotient` 可以被改寫成: $$ \left\lfloor{\left\lceil\frac{2^k}{d}\right\rceil \times \frac{n}{2^k}} \right\rfloor $$ 由於 $\frac{n}{2^k} < 1$，且 $n < 2^{64}$，所以 k 為 64。 此外 $\left\lceil\frac{2^k}{d}\right\rceil$ 可以改寫成 $\frac{2^k + r}{d}$。($r = (-2)^k mod\ d$) 所以接著就是比對 $\frac{2^{64} + r}{d}$ 和 `((uint64_t)(UINT64_C(XXX) / (d) + 1))` 如果 `r` 為正會 overflow，所以要找負的值。加上 `r` 為 mod d 後的結果，所以不能大於 d。接著比對選項，發現只能選 `0xFFFFFFFFFFFFFFFF` 註: 改寫後的 floor 可以拿掉是因為最後 shift 64 捨去掉小數點了。而 ceil 可以拿掉是因為 $\frac{2^{64}-1}{d}$ 捨去掉小術後，有再加 1。 ## 測驗 4 $M \times n$ 表示 $\frac{n}{d}$ 的小數部分，而要檢查是否整除，即看小數部分是否為零即可，但考慮到最高精準度的問題，將條件設為小於 $\frac{1}{d}$。 ## 測驗 5 先解 `VV1`，透過註解得知，`(*chunk & PACKED_BYTE(VV1)) == 0` 是用來決定是否為 ASCII，那就和測驗 1 一樣，檢查 8 bits 的 most significant bit。另外 `PACKED_BYTE` 是將 8 bits 的值重複 8 次變成 64 bits 的資料。所以本題要選 `0x80`。 可以透過背景知識知道，如果大寫要轉小寫，只需要對其做 XOR 32。所以可以猜測 `mask` 應該為 32。接著這裡使用了一個巧妙的方式來判斷 `chunk` 是否在 A~Z 之間。 ```cpp 0,0 1,0 1,1 A Z ``` 可以觀察到只有在 A~Z 之間，`A` 和 `Z` 才會相異。如果在範圍內，則 8 bits 應為 `1xxxxxxx` 。然後和 `10000000` 做 `&` 再 shift，剛好就使 `mask` 成 32。 ## 測驗 6