# 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$$
程式碼實作中
```c
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`
```c
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，所以得到以下實作
```c
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 的範圍內都不會影響最終結果。
而原來題目中說明要額外處理被捨棄的位元，即
```c
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 位的結果。
```c=
#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 週期數量
選用的兩個程式碼版本一個為題目提供，另一個如下：
```c
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 即可。
### 第三題
```c
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`。
第二小題
```c
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}$$
```c=
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`。
### 第五題
```c
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 個位元算出他的貢獻
```c
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` 已經在快取記憶體中，先進行一次計算再開始測量。
```c
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]` 陣列儲存每個位元的數量，則可以避免這個情況發生:
```c
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
Sign in with Wallet
Connect another wallet