# 2024q1 Homework4 (quiz3+4)
contributed by < `millaker` >
## 第三週
### 第一題
#### 程式碼運作原理
本題運用 [Digit by digit caculation](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digit_calculation) 估計一個整數的平方根，$N^2=(a_n+a_{n-1}+...+a_m)^2$ 其中 $a_m=2^m$ 或 0。算法從 $2^n$ 依序檢查到 $2^0$ ，建構出平方根估計值 $P_m=a_0+a_1+...+a_m$。檢查的方法是比較 $P_m^2 <= N^2$，若為真則 $a_m=2^m$ 反之則為零。為了避免每次檢查需要重新計算 $P_m^2$ ，我們利用一個額外變數 $X_m = N^2 - P_m^2$ 儲存差值，並在每個回合更新。更新的大小可由以下推導得出：
$$ X_m - X_{m+1} = N^2 - P_m^2 - N^2 -P_{m+1}^2$$
移項整理後可得
$$ X_m = X_{m+1} - Y_m$$
其中
$$Y_m=P_m^2-p_{m+1}^2=2P_{m+1}a_m+a_m^2$$
在更進一步最佳化 $Y_m$ ，可以將其拆成前後兩項 $c_m$ 和 $d_m$:
$$c_m=P_{m+1}2^{m+1}$$
$$d_m=(2^m)^2$$
$$Y_m= \begin{cases}
c_m+d_m & \text{if } a_m=2^m \\
0 & \text{if } a_m=0
\end{cases}
$$
其中 $c_m$ 和 $d_m$ 可以利用以下方法更新，
$$c_{m-1} = P_m2^m= (P_{m+1}+a_m)2^m = P_{m+1}2^m + a_m2^m = \begin{cases}
c_m/2+d_m & \text{if } a_m=2^m \\
c_m & \text{if } a_m=0 \end{cases}
$$
用到$P_m=P_{m+1}+a_m$和$a_m=2^m$
$$d_{m-1}=d_m/4$$

程式碼實作中

int i_sqrt(int x)
{
    if (x <= 1) /* Assume x is always positive */
        return x;

    int z = 0;
    for (int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL); m; m >>= 2) {
        int b = z + m;
        z >>= 1;
        if (x >= b)
            x -= b, z += m;               
    }
    return z;
}

`z` 即 $c_m$ ， `m`即 $d_m$， `m` 的更新在每一回合的 `m >>= 2`， `z` 則在 `z >>= 1` 更新為 $c_{m-1}$ 並利用 `z += m` 加上當前的 $d_m$ 。
#### 取代 `__builtin_clz` 實作
用 binary search 實作 `clz`

static inline unsigned clz(uint32_t x)
{
    if (x == 0) return 32;
    int n = 0;
    if (x <= 0x0000FFFF) {
        n += 16;
        x <<= 16;
    }
    if (x <= 0x00FFFFFF) {
        n += 8;
        x <<= 8;
    }
    if (x <= 0x0FFFFFFF) {
        n += 4;
        x <<= 4;
    }
    if (x <= 0x3FFFFFFF) {
        n += 2;
        x <<= 2;
    }
    if (x <= 0x7FFFFFFF) {
        n += 1;
        x <<= 1;
    }
    return n;
}

每個 `if` 都會檢查一半的 `x` 是否有 1 ，若沒有則回傳值 `n` 便會加上和零一樣數量的數字，並將 `x` 位移至下個檢查位置，此實作的 `clz` 和 `__builtin_clz` 在輸入不等於零的情況回傳值相同。

### 第二題
此題因為輸入值範圍僅有 0 ~ 19，題目描述僅需考慮計算到小數點後第一位是精確即可，透過計算
$$1.9 \leq \frac{19}{x} \leq 1.99$$，可以得出符合的 $x$ 範圍是 $$ 9.55 \leq x \leq 10$$
從中挑選容易以二進位表達的數字 9.84 即 $\frac{128}{13}$，其中 $128 = 2^7$ , $13=2^3+2^2+2^0$。將輸入值 `tmp` 乘上 9.84 的倒數就等於除以 9.84，所以得到以下實作

q = ((((tmp >> 3) + (tmp >> 1) + tmp) << 3)) >> 7;
r = tmp - (((q << 2) + q) << 1);

第一行中括號內 `(tmp >> 3) + (tmp >> 1) + tmp) << 3)` 可以得到 $(\frac{tmp}{8}+\frac{tmp}{2}+tmp) * 8$ 再右移 7 位得到 $\frac{13}{128}$，再利用除法原理將近似的商乘以 10，程式碼中的實作對應到 `(((q << 2) + q) << 1)`，即 $(q*4+q = 5q) *2 = 10q$，最後 `tmp` 扣除 `q` 即可得到餘數。 這裡商的誤差因為前面證明，可以確定在 0 ~ 19 的範圍內都不會影響最終結果。

而原來題目中說明要額外處理被捨棄的位元，即

d0 = q & 0b1;
d1 = q & 0b11;
d2 = q & 0b111;
q = ((((n >> 3) + (n >> 1) + n) << 3) + d0 + d1 + d2) >> 7;

先假設原說明沒有寫錯字 `q` 改為 `n` ，這裏處理的方法很奇怪，若是在題目指定範圍內 0 ~ 19 則完全不需要處理，因為 `n >> 3` 在最大值 19 得出的誤差為 $(0.011)_2$ ， `n >> 1` 的誤差為 $(0.1)_2$ 兩者相加等於 $(0.111)_2$ 左移三位不會影響到最後右移 7 位的結果。

#include <stdint.h>
void divmod_10(uint32_t in, uint32_t *div, uint32_t *mod)
{
    uint32_t x = (in | 1) - (in >> 2); /* div = in/10 ==> div = 0.75*in/8 */
    uint32_t q = (x >> 4) + x;
    x = q;
    q = (q >> 8) + x;
    q = (q >> 8) + x;
    q = (q >> 8) + x;
    q = (q >> 8) + x;

    *div = (q >> 3);
    *mod = in - ((q & ~0x7) + (*div << 1));   
}

測驗題目改用其他算法，先算出 `x` 等於 $in-\frac{1}{4}in=\frac{3}{4}in$ ，再利用 `x` 得出 $\frac{3}{4}in*\frac{1}{16}+\frac{3}{4}in=\frac{102}{128}$ ，其中 $\frac{102}{128} \approx 0.7968 \approx \frac{8}{10}$ ，第 12 行可以將 $x*\frac{8}{10}*\frac{1}{8}$ 也就是向右位移三位得到近似的商，餘數則由 $in-10*q$ 得到。程式碼中 6 ~ 10 行是處理 4 5 行右移帶來的誤差，但我看了很久還是不知道怎麼解釋。 程式碼第 4 行左邊括號內 `(in | 1)` 我一樣無法看出理由，利用測試程式，我發現在輸入等於20時，有加入 `| 1` 的結果是正確的，而沒有加入的則回傳 `q:1 r:10` 的結果。

#### 對 `q` 校正
因為原本算出的 `q` 是 `in` 乘上 $\frac{102}{128} \approx 0.7968$ 和 $0.8$ 有些微偏差，實作都是使用向下位移因此可以當成無條件捨去，我們可以藉此算出有效範圍
$$
0.8x - \frac{102}{128}x \leq 1
$$
$$
x \leq 319.999...
$$
實際使用 python 測試大於 319.99 的最小正整數：

>>> 320*0.8
256.0
>>> 320*102/128
255.0

兩者的結果會相差 1，而這個偏差會隨數字增加越來越大

>>> (2**32-1)*0.8
3435973836.0
>>> (2**32-1)*102//128
3422552063
>>> 3435973836 - 3422552063
13421773

到 `UINT32_MAX` 偏差會大到 `13421773`，如果輸入值大於 319 ，則需要額外對 `q` 進行修正。

《[Hacker's Delight](http://web.archive.org/web/20180517023231/http://www.hackersdelight.org/divcMore.pdf)》中因為餘數不會大於除數太多，所以使用 `r / q` 或是同等運算的位移和相加來校正 `q`。這裡最大偏差量很大，且要避免使用除法操作，所以改用其他方法。

`q = (q >> 8) + x;` 重複做 4 次，每次都將 `x` 也是未校正前的 `q` 值加入運算。其中 `q >> 8` 等效於 $\frac{q}{256}$ ，為什麼是 256 還沒看出為什麼，先將等效的算式整理可以得到：
$$
\frac{q}{256} + q \tag{1}
$$
$$
\frac{\frac{q}{256} + q}{256} + q = \frac{q}{256^2} + (1+\frac{1}{256})q \tag{2}
$$
依序做下去會得到
$$
\frac{q}{256^3} + (1 + \frac{1}{256} + \frac{1}{256^2})q \tag{3}
$$
$$
\frac{q}{256^4} + (1 + \frac{1}{256} + \frac{1}{256^2} + \frac{1}{256^3})q \tag{4}
$$
最後整理得到
$$
(1 + \frac{1}{256} + \frac{1}{256^2} + \frac{1}{256^3} + \frac{1}{256^4})q
$$
可以看出是將原本的 `q` 加上修正量 $(\frac{1}{256} + \frac{1}{256^2} + \frac{1}{256^3} + \frac{1}{256^4})q$ ，為什麼是 256 我看了很久，忘記我們的目標是要逼近 `0.8` ，若把這幾個數字列出來看便可以知曉：
$$
0.8 = (0.CCCCCCCCCC...)_{16}
$$
$$
\frac{102}{128} = 0.796875 = (0.CC)_{16}
$$
$$
\frac{102}{128} * (1 + \frac{1}{256}) = 0.79998779296875 = (0.CCCC)_{16}
$$
$$
\frac{102}{128} * (1 + \frac{1}{256} + \frac{1}{256^2}) = 0.7999999523162842 = (0.CCCCCC00...)_{16}
$$
$$
\frac{102}{128} * (1 + \frac{1}{256} + \frac{1}{256^2} + \frac{1}{256^3}) = 0.7999999998137355 = (0.CCCCCCCC00...)_{16}
$$
$$
\frac{102}{128} * (1 + \frac{1}{256} + \frac{1}{256^2} + \frac{1}{256^3} + \frac{1}{256^4}) = 0.7999999999992724 = (0.CCCCCCCCCBFF...)_{16}
$$
到這裡我才知道 8 是為了讓 `q` 更接近 0.8 的最小位移量，若選用 7 會讓得到的 `q` 比 0.8 還要大。至於為什麼是做 4 次，我還沒想到一個合理的證明或解釋。

觀察上面做 3 次校正後的十六進位數字，可以看到已經有小數點後8位的準確度，一開始我想能不能把第四次校正省去，但實際使用 python 測試，在某些數字答案會有錯誤。原本的操作是 `q = (q >> 8) + x;` 在右移後會有部分位元被丟棄，造成經度損失，若丟棄的值累積大於 1 ，原本 $0x0.CCCCCCCC00$ 又剛好只會算到小數點後 8 位，造成 `q` 不精準的情況，所以一定得坐第四次避免這種事發生。

#### 比較 CPU 週期數量
選用的兩個程式碼版本一個為題目提供，另一個如下：

void divmod_10_noopt(uint32_t in, uint32_t *div, uint32_t *mod)
{
    uint32_t tmp = in / 10;
    *div = tmp;
    *mod = in - tmp * 10;
}

編譯命令為 `gcc -O0 mod.c`，並用 `objdump` 反組譯得到

0000000000001169 <divmod_10_noopt>:
    1169:	f3 0f 1e fa          	endbr64
    116d:	55                   	push   %rbp
    116e:	48 89 e5             	mov    %rsp,%rbp
    1171:	89 7d ec             	mov    %edi,-0x14(%rbp)
    1174:	48 89 75 e0          	mov    %rsi,-0x20(%rbp)
    1178:	48 89 55 d8          	mov    %rdx,-0x28(%rbp)
    117c:	8b 45 ec             	mov    -0x14(%rbp),%eax
    117f:	89 c2                	mov    %eax,%edx
    1181:	b8 cd cc cc cc       	mov    $0xcccccccd,%eax
    1186:	48 0f af c2          	imul   %rdx,%rax
    118a:	48 c1 e8 20          	shr    $0x20,%rax
    118e:	c1 e8 03             	shr    $0x3,%eax
    1191:	89 45 fc             	mov    %eax,-0x4(%rbp)
    1194:	48 8b 45 e0          	mov    -0x20(%rbp),%rax
    1198:	8b 55 fc             	mov    -0x4(%rbp),%edx
    119b:	89 10                	mov    %edx,(%rax)
    119d:	8b 55 fc             	mov    -0x4(%rbp),%edx
    11a0:	89 d0                	mov    %edx,%eax
    11a2:	c1 e0 02             	shl    $0x2,%eax
    11a5:	01 d0                	add    %edx,%eax
    11a7:	01 c0                	add    %eax,%eax
    11a9:	89 c1                	mov    %eax,%ecx
    11ab:	8b 45 ec             	mov    -0x14(%rbp),%eax
    11ae:	29 c8                	sub    %ecx,%eax
    11b0:	89 c2                	mov    %eax,%edx
    11b2:	48 8b 45 d8          	mov    -0x28(%rbp),%rax
    11b6:	89 10                	mov    %edx,(%rax)
    11b8:	90                   	nop
    11b9:	5d                   	pop    %rbp
    11ba:	c3                   	ret

從組合語言可以發現就算已經將最佳化關閉 `-O0` 還是沒有使用 `div` 指令，因此我改用手計算操作數量並對照指令得出序列。去除掉兩個函式皆有的 prologue 和 epilogue 以及記憶體存取指令，僅比較數值操作指令，沒有最佳化的版本分析：
| Code | Inst | Latency | Accum |
| ------------- | ---- | ------- | ----- |
| `in/10` | div | 10-13 | 11.5 (10-13) |
| `tmp*10` | mul | 3 | 14.5 (13-16) |
| `in - tmp*10` | sub | 1 | 15.5 (14-17) |

最終結果為 15.5 個週期
| Code | Inst | Latency | Accum |
| --------------------------- | ---- | ------- | ----- |
| `in \| 1` | or | 1 | 1 |
| `in >> 2` | shr | 1 | 2 |
| `(in\|1) - (in>>2)` | sub | 1 | 3 |
| `x >> 4` | shr | 1 | 4 |
| `(x>>4) + x` | add | 1 | 5 |
| `(q>>8)` | shr | 1 *4 | 9 |
| `(q>>8) + x` | add | 1 *4 | 13 |
| `q >> 3` | shr | 1 | 14 |
| `*div << 1` | shl | 1 | 15 |
| `q & ~0x7` | and | 1 | 16 |
| ` (q & ~0x7) + (*div << 1)` | add | 1 | 17 |
| `in - prev` | sub | 1 | 18 |

總共 18個週期，這是非常粗略的估算，因為觀察到每個操作都是基於前面指令的結果，所以沒有使用到 recipricol throughput 也就是一個週期 issue 一個指令，沒有多個指令同時在 EXE 階段的情況。另外 x86 中 div 指令，翻閱 x86-64 instruction set reference `DIV` 指令說明
> DIV r/m32: Unsigned divide EDX:EAX by r/m32, with
result stored in EAX := Quotient, EDX := Remainder

可以得知已經將餘數存在 EDX ，因此完全不需要再重新計算 `in - q*10`，直接存取 %edx 即可。
### 第三題

static size_t ilog2(size_t i)
{
    size_t result = 0;
    while (i >= 65536) {
        result += 16;
        i >>= 16;
    }
    while (i >= 256) {
        result += 8;
        i >>= 8;
    }
    while (i >= 16) {
        result += 4;
        i >>= 4;
    }
    while (i >= 2) {
        result += 1;
        i >>= 1;
    }
    return result;
}

題目使用二分搜尋法尋找目前 MSB 的位置來判斷是否增加 `ilog2` 的結果，第一個 `while` 檢查 MSB 是否在 31:16 位元，若為真，則代表 `ilog2` 結果至少大於 16 ，因此做相對應的操作 `result += 16` 並把 `i` 向下位移 16 格以方便後續程式碼一致操作。第二個 `while` 為檢查 是否在 15:8，第三個 `while` 檢查 7:4，最後一個 `while` 則是一個一個檢查直到 `i < 2`。

第二小題

int ilog32(uint32_t v)
{
    return (31 - __builtin_clz(v | 1));
}

因為 `__builtin_clz()` 再傳入 0 時未定義，因此需要 `| 1` 確保一定大於 0 ，而因為這裡是 count leading zero，因此不會影響正常輸入的結果。

### 第四題
從下方 `ewma_init()` 我們可以得知輸入的 `weight` 和 `factor` 都必須是 2 的冪，這是因為後方將兩者都取 `ilog2()`，之後再計算新加入的值時便可以利用位移取代原本公式的乘法。
$$ x \ll y = x * 2^y$$
$$\begin{equation}
S_{t} =
\begin{cases}
Y_0 & t = 0\\
\alpha Y_0 + (1-\alpha)S_{t-1} & t > 0\\
\end{cases}
\end{equation}$$

struct ewma *ewma_add(struct ewma *avg, unsigned long val)
{
    avg->internal = avg->internal
                        ? (((avg->internal << avg->weight) - avg->internal) +
                           (val << avg->factor)) >> avg->weight
                        : (val << avg->factor);
    return avg;
}

原來 EWMA 公式是計算 $(1-\alpha)S_{t-1}$， 題目中第四行做了不一樣的操作，若直接向左位移在減掉自己，可能會有精度損失，因此先向左位移再作相同操作得到以下數學公式:
$$(\frac{1}{\alpha}*S_{t-1}-S_{t-1})*\alpha = (1-\alpha)*S_{t-1}$$
而第 6 行，因為這裡的 EWMA 都有一個隱藏的 `factor`，所以 `val` 需要乘上 `factor`。

### 第五題

int ceil_ilog2(uint32_t x)
{
    uint32_t r, shift;

    x--;
    r = (x > 0xFFFF) << 4;                                                                                                                                    
    x >>= r;
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    shift = (x > 0x3) << 1;
    x >>= shift;
    return (r | shift | x > 1) + 1;       
}

這題實作原理和測驗三相似，不過作法稍有不同，一樣都是使用二分搜尋法，這裏不用加法 `r += 16` 改用 `r = 1 << 4` 代替，效果相同。依序從 [31:16] [15:8] [7:4] [3:2] 檢查,最後再回傳值 `| x > 1` 是檢查 [1] 的位元是否為一， 因為是算 `ceil` 所以將結果加一。這題可以使用 `|` 來計算 `r` 是因為每次加入的值位數不互相影響不會有進位的問題。

#### 改寫使 `x = 0` 回傳有意義的值
上方實作因為在計算前做了 `x--` 所以當 `x` 為零時會變成 `UINT32_MAX = 0xFFFFFFFF` 得到結果為 32。如果把 `x--` 拿掉，當輸入值是 2 的冪，例如 $2^2=4$，結果會等於 $2 + 1 = 3$，並非 `log2ceil` 的正確結果。簡單的做法就是檢查輸入是否為零，但這會破壞無分支的特性，因此需要使用其他方法改寫。

若把 `log2ceil(x)` 想成需要至少需要多少個位元才能表示 `x` 的數值，則 `log2ceil(0)` 會等於 1，使用此定義將上方程式碼 `x--` 的部分改寫為 `x -= !!x` ，利用兩次 `not` 操作將非零的數值變為一，零還是零，就可以得到上方定義的結果，且程式碼仍舊無分支。

## 第四週
### 測驗一
從 Leetcode 題目敘述中得知:
> The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

而 XOR 運算剛好符合上述要求，可以透過真值表觀察:

| XOR | 1 | 0 |
| --- | --- | --- |
| 1 | 0 | 1 |
| 0 | 1 | 0 |

若輸入想同 {0,0} 和 {1,1} 則值為零，若不同則為 1，剛好就是檢查兩個位元是否相同。將兩數字進行 XOR 後，利用 `popcount` 算出數字內有幾個位元為一就可以知道有幾個位元不同。最後需要將累加結果向右位移 1 的原因是原來的寫法會將 {i,j} 和 {j,i} 都計算一次，因此需要除以二得到正確結果。而 {i,i} 的結果因為 XOR 為零不須特別處理。

#### 改進程式碼
參考題目敘述中歸納的方法，只要算出相同位數的 1 數量，就可以得到該位數貢獻給 Hamming Distance 的值。改進實作不再存取輸入陣列 $n^2$ 次，而是只存取 $32n$ 次，依序對 32 個位元算出他的貢獻

int totalHammingDistance_it(int *nums, int numsSize)
{
    int total = 0;
    for (int i = 0; i < 32; i++) {
        int accum = 0;
        for (int j = 0; j < numsSize; j++) {
            accum += (nums[j] >> i) & 1;
        }
        total += accum * (numsSize - accum);
    }
    return total;
}

老師上課提過考慮到執行速度太快用 `gettime()` 可能無法反應真實速度，我使用 `__rdtsc()` 存取 CPU cycle count register 進行前後比較。另外，為了確保輸入資料 `arr` 已經在快取記憶體中，先進行一次計算再開始測量。

unsigned long long test_func(int *arr, int size, int (*func)(int *, int))
{
    // Warmup
    func(arr, size);
    unsigned long long start = __rdtsc();
    func(arr, size);
    unsigned long long end = __rdtsc();
    return end - start;
}

測試結果如下:

$ $ ./a.out
pop 621651614
it 1015892

測試輸入大小為 10000 時，改進的方法快原來實作的 600 倍，新的實作只有在輸入資料小於 32 時才會比原來的慢。

#### 考慮快取記憶體
稍微檢視我原本的實作尋求改進空間時，我想到若輸入資料太多，每次存取整個陣列都會造成 cache miss，若交換迴圈順序並使用 `int[32]` 陣列儲存每個位元的數量，則可以避免這個情況發生:

int totalHammingDistance_it_mem(int *nums, int numsSize)
{
    int ones[32] = {0};
    int total = 0;
    for (int i = 0; i < numsSize; i++) {
        for (int j = 0; j < 32; j++) {
            ones[j] += (nums[i] >> j) & 1;
        }
    }
    for (int j = 0; j < 32; j++) {
        total += ones[j] * (numsSize - ones[j]);
    }
    return total;
}

利用原本的測試方法因為輸入資料數量不足以置換快取記憶體內容，所以無法充分反應修改的優勢，改用更大的輸入資料比較。測試電腦為 r7-7700 L1 Cache : 512 KB，所以只需要 $\frac{512*10^3}{4} = 128*10^3$ 個 `int` 即可填滿快取記憶體。 我選用一個遠大於這個數量的 $1*10^8$ 的輸入大小做實驗:

$ ./a.out
it 10028001754
itmem 11300800924

得到的測試結果不如預期，我想的到的解釋是，因為記憶體存取的順序都是固定且很好預測的，而現在 CPU 內的 data prefetcher 都能夠有效看出這種模式並預先將需要的記憶體填入 L1 快取中，為了驗證這個猜測，使用先前 lab0-c 找到的 `perferator` 觀察 cache 使用情況。

+-----------------------+--------------------------------+
| Event                 | Count                          |
|                       | (totalHammingDistance_it)      |
+-----------------------+--------------------------------+
| cpu-cycles            | 14130703721                    |
| instructions          | 51221528813                    |
| l1d-read-accesses     | 12809871246                    |
| l1d-read-misses       | 200176481                      |
| l1d-prefetch-accesses | 199597907                      |
| cache-references      | 404837777                      |
| cache-misses          | 210397                         |
| time-elapsed          | 2.662301565s                   |
+-----------------------+--------------------------------+
+-----------------------+--------------------------------+
| Event                 | Count                          |
|                       | (totalHammingDistance_it_mem)  |
+-----------------------+--------------------------------+
| cpu-cycles            | 15551051005                    |
| instructions          | 68121105091                    |
| l1d-read-accesses     | 15651167893                    |
| l1d-read-misses       | 6384108                        |
| l1d-prefetch-accesses | 6220027                        |
| cache-references      | 12824036                       |
| cache-misses          | 9650                           |
| time-elapsed          | 3.013514068s                   |
+-----------------------+--------------------------------+

從 profiling 結果來看， cache miss 確實降低很多，但是執行時間、 CPU 週期比較多，另外也發現 `l1d-read-accesses` 數量比較多。回去更改寫法，將 `nums[j]` 先存入 `int temp` 中再降低記憶體存取次數，得到測驗結果:

+-----------------------+--------------------------------+
| Event                 | Count                          |
|                       | (totalHammingDistance_it)      |
+-----------------------+--------------------------------+
| cpu-cycles            | 14114296595                    |
| instructions          | 51103214472                    |
| l1d-read-accesses     | 12792397124                    |
| l1d-read-misses       | 200284012                      |
| l1d-prefetch-accesses | 199776937                      |
| cache-references      | 405361558                      |
| cache-misses          | 203017                         |
| time-elapsed          | 2.672375406s                   |
+-----------------------+--------------------------------+
+-----------------------+--------------------------------+
| Event                 | Count                          |
|                       | (totalHammingDistance_it_mem)  |
+-----------------------+--------------------------------+
| cpu-cycles            | 15353325068                    |
| instructions          | 52687294360                    |
| l1d-read-accesses     | 9595242080                     |
| l1d-read-misses       | 6314365                        |
| l1d-prefetch-accesses | 6230386                        |
| cache-references      | 12752291                       |
| cache-misses          | 10016                          |
| time-elapsed          | 2.943651296s                   |
+-----------------------+--------------------------------+

其中 `l1d-read-accesses` 真的降低很多，但執行時間仍然較高，有其他因素沒有被我考量到再影響結果。

#### 觀察 asm
用 `$ gcc hamming.c -O0 -c` 產生 `.o` 檔

只看軟體 C 程式碼，兩者做的操作數量是一樣的，但是由 `objdump` 觀看組合語言發現第一種作法產生 30 行的 CPU 指令，第二種考慮快取記憶體的做法產生 84 行程式碼，所以就算快取記憶體存取次數較少，第二種做法執行的 CPU 指令數量多了 2 倍以上。

### 測驗二
#### tic-tac-toe 遊戲
#### mod 7