2023q1 Homework2 (quiz2)

contributed by < Korin777 >

測驗三

size_t swar_count_utf8(const char *buf, size_t len)
{
    const uint64_t *qword = (const uint64_t *) buf;
    const uint64_t *end = qword + len >> 3;

    size_t count = 0;
    for (; qword != end; qword++) {
        const uint64_t t0 = *qword;
        const uint64_t t1 = ~t0;
        const uint64_t t2 = t1 & 0x04040404040404040llu;
        const uint64_t t3 = t2 + t2;
        const uint64_t t4 = t0 & t3;
        count += __builtin_popcountll(t4);
    }

    count = ((len >> 3) << 3) - count;
    count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0;

    return count;
}

• 與原本的 count_utf8 相比 ， swar_count_utf8 充分利用處理器暫存器一次檢查 8 個 byte
• 先計算出 continuation byte 的數量，再與字串所佔的 bytes 相減即為 utf-8 字元數
• 當字串所佔 bytes 不是 8 的倍數，在透過 count_utf8 補齊剩餘的 utf-8 字元

效能比較

github

• 測試資料為隨機生成的 utf-8 字元
• 綠色為原本的實作，紫色則為加入 SWAR 技巧的實作，直覺上執行時間應該會快 8 倍左右，實際上卻快了12倍以上

測驗四

從輸出可以觀察到符合的樣式為左邊皆為 1 右邊皆為 0 的 bit pattern e.g. 1100

bool is_pattern(uint16_t x)
{
    const uint16_t n = -x;
    return (n ^ x) < x;
}

考慮以下三種情況：

1. 當 x 符合，-x ^ x 一定會將最低位的 1 改為 0，使他比 x 小
   e.g. 若 x =
   ${110}_2$，則
   ${010}_2$ ^
   ${110}_2$ =
   ${100}_2$
2. 當 x 不符合， -x ^ x 一定會將最高位 1 及次高位 1 中間的 0 改為 1，使他比 x 大
   e.g. 若 x =
   ${101}_2$，則
   ${011}_2$ ^
   $101$ =
   ${110}_2$
3. 當 x 為 0，-x ^ x 仍為 0

題目連結