# 2020q3 Homework4 (quiz4)
###### tags: `sysprog2020`
## Question
[quiz4](https://hackmd.io/@sysprog/2020-quiz4)
## Test1
```c=1
int hammingDistance(int x, int y) {
return __builtin_popcount(x ^ y);
}
```
### 運作原理
* 因為每一個 bit 都是獨立的，所以列出一個 bit 的 hamming distance 的真值表即可發現， hamming distance 和 hamming weight (x ^ y) 等價
* | x | y | hamming weight(x ^ y) | hamming distance |
|---|---|-----------------------|------------------|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
* Popcount 研究: 參考 [詳解二進位數中 1 的個數](http://github.tiankonguse.com/blog/2014/11/16/bit-count-more.html) 中的作法，假設要計算 32-bit unsigned int 的1 的個數：
* gcc 內建函數 __builtin_popcount
```cpp
// built-in gcc extension
uint32_t popcount_gcc(uint32_t x)
{
return __builtin_popcount(x);
}
```
* 逐個位計算法：最簡單的方法，但即使全部的位元都是 0，還是要處理所有的位元
```cpp
// naive method 1
uint32_t popcount_naive_1(uint32_t x)
{
uint32_t mask = 1 << 31;
uint32_t count = 0;
for (int i = 0; i < 32; i++) {
if ((x & mask) != 0)
count++;
mask = mask >> 1;
}
return count;
}
```
* 借位法：利用減法借位的性質，如果有 n 個位元是 1 則 while 循環 n 次
```cpp
// naive method 2
uint32_t popcount_naive_2(uint32_t x)
{
uint32_t n = 0;
while (x) {
n++;
x &= x - 1;
}
return n;
}
```
* 分而治之法 （一次計算2個 bit 的版本）
```cpp
// divide and conquer (2-ver)
uint32_t popcount_div_2(uint32_t x)
{
uint32_t mask[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF,
0x0000FFFF};
for (int i = 0, j = 1; i < 5; i++, j <<= 1) {
x = (x & mask[i]) + ((x >> j) & mask[i]);
}
return x;
}
```
* 分而治之法 （一次計算3個 bit 的版本）
```cpp
// divide and conquer (3-ver)
uint32_t popcount_div_3(uint32_t x)
{
unsigned int threeBitSum =
x - ((x >> 1) & 0xdb6db6db) - ((x >> 2) & 0x49249249);
return ((threeBitSum + (threeBitSum >> 3)) & 0xc71c71c7) % 63;
}
```
* 分而治之法 （fast mod）
```cpp
const uint32_t D = 63;
#define M ((uint64_t)(UINT64_C(0xFFFFFFFFFFFFFFFF) / (D) + 1))
/* compute (n mod d) given precomputed M */
uint32_t quickmod(uint32_t n)
{
uint64_t quotient = ((__uint128_t) M * n) >> 64;
return n - quotient * D;
}
// divide and conquer (3-ver)
uint32_t popcount_div_3_fast(uint32_t x)
{
unsigned int threeBitSum =
x - ((x >> 1) & 0xdb6db6db) - ((x >> 2) & 0x49249249);
return quickmod((threeBitSum + (threeBitSum >> 3)) & 0xc71c71c7);
}
```
* 實驗1：比較兩個最簡單的方法『逐個位計算法(naive_1)』和『借位法(naive_2)』
* 
* | | naive_1 | naive_2 |
|---------|---------|---------|
| mean | 522.08 | 148.63 |
| std dev | 100.16 | 70.77 |
* 從平均數來看『逐個位計算法(naive_1)』比『借位法(naive_2)』快上約3.5倍，且標準差更小，故借位法較佳
* 實驗2：比較 `Divide-And-Conquer` 的方法『分而治之法(2-bit)』和『分而治之法(3-bit)』
* 
* | | 2-bit | 3-bit |
|---------|--------|-------|
| mean | 86.53 | 61.07 |
| std dev | 485.53 | 84.98 |
* 分而治之法(3-bit) 有更快的平均時間以及更小的標準差，故分而治之法(3-bit)較佳
* 實驗3：比較分而治之法(3-bit)中，取餘數所使用的 mod 函數的區別，比較 `jemalloc` 所使用的快速 mod 方法和一般的 mod 方法
* 
* | | gcc | 2-bit | 3-bit | 3-bit(fast mod) |
|---------|-------|--------|-------|-----------------|
| mean | 26.55 | 86.53 | 61.07 | 61.13 |
| std dev | 19.02 | 485.53 | 84.98 | 78.82 |
* 使用 fast mod 和使用一般的取餘數方法花費的時間差不多，可能是編譯器有做最佳化
* fast mod 的時間會在 60 ~ 100 cycles 之間跳動，不清楚原因
* 總整理：所有測試的方法整理如下，所有方法都經過驗證以確保正確性
* | | gcc | naive_1 | naive_2 | 2-bit | 3-bit | 3-bit(fast mod) |
|---------|-------|---------|---------|--------|-------|-----------------|
| median | 26 | 520 | 147 | 83 | 59 | 55 |
| mean | 26.55 | 522.08 | 148.63 | 86.53 | 61.07 | 61.13 |
| std dev | 19.02 | 100.16 | 70.77 | 485.53 | 84.98 | 78.82 |
* 綜合考慮所有方法，速度排名如下：gcc builtin >>> 3-bit ~ 3-bit(fast mod) >>> 2-bit >>> naive_2 >>> naive_1
### 延伸問題
* [LeetCode 477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/)
* 最直接的作法是為用兩個 for loop 計算所有可能的組合的 hamming distance 但會超時
* 想法：逐個 bit 檢查 bit
* 研讀錯誤更正碼簡介及抽象代數的實務應用，摘錄其中 Hamming Distance 和 Hamming Weight 的描述並重新闡述，舉出實際的 C 程式碼來解說
* **(7,4) Hamming Code 的數學結構**
* 定義二進位的加法跟乘法
* 二進位的加法（就是XOR）
* | | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
* 二進位的乘法
* | | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
* 二進位的版本，就跟實數運算再取 modulo 2 的結果相同
* (7,4) Hamming Code 可以使用文氏圖具象化
* 
* 其中編號 1 ~ 4 的區域分別填入要傳輸的 4 bits 資料，編號 5 ~ 7 的區域則根據『在 A,B,C 圓圈內的 1 的個數要為偶數』這項規則分別填入 0 或 1 當作容錯碼
* 將 4 bits 的資料加上 3 bits 的容錯碼經過傳輸後，可以糾正 1 bit 的錯誤
* 根據『二進位的加法跟乘法』，以及『在 A,B,C 圓圈內的 1 的個數要為偶數』所定義的 **(7,3) Hamming Code** 線性方程組
* $$\begin{array}{rcrcrc@{\qquad}l}
x_1 + x_2 + x_3 + x_5 &= 0 \\
x_1 + x_2 + x_4 + x_6 &= 0 \\
x_1 + x_3 + x_4 + x_7 &= 0 \\
\end{array}$$
* 以上的方程組可以寫成以下的矩陣
* $$ Hx = \begin{bmatrix}
1 & 1 & 1 & 0 & 1 & 0 & 0 \\
1 & 1 & 0 & 1 & 0 & 1 & 0 \\
1 & 0 & 1 & 1 & 0 & 0 & 1\\
\end{bmatrix} \times
\begin{bmatrix}
x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \\
\end{bmatrix} = 0
$$
* $\forall x \in C \mid Hx = 0, \ x \in N(H)$ 根據 **Sylvester 維度定理** $rank(H) + nullity(H) = 7$ 故 $nullity(H) = 4$
* $C = span\left\{ \begin{matrix}
\begin{bmatrix}
1 \\ 0 \\ 0 \\ 0 \\
\end{bmatrix}
\begin{bmatrix}
0 \\ 1 \\ 0 \\ 0 \\
\end{bmatrix}
\begin{bmatrix}
0 \\ 0 \\ 1 \\ 0 \\
\end{bmatrix}
\begin{bmatrix}
0 \\ 0 \\ 0 \\ 1 \\
\end{bmatrix}
\end{matrix}
\right\}$ 有 $2^4=16$ 種 codewords
* 令 $y = x + e$ 為經過傳輸通道的錯誤訊息，$Hy = Hx + He$ 是編碼過後的訊息 $\because x \in N(H),\ Hy = He$
* 因為 $Hy$ 是已知所以可以經由解 $He=Hy$ 知道 e 是多少，$He=Hy$ 可能有無限多組解，通常取 1 的個數最少的那一個，也就是錯的個數最少。因為在一般的情況下會錯的機率比較小, 不會錯的機率比較大。
* **Hamming distance** 為比較兩個向量有幾個 bit 不同
* Minimum distance: 在這個編碼中，任意兩個不同的向量的 hamming distance 的最小值
* **Hamming weight** 為一個向量不是零的地方有幾個 (population count)
* Minimum weight：在這個編碼中，所有不為0的向量的 hamming weight 的最小值
* 如果利用上面二進位加法（等同於 bit-wise XOR ）的定義，兩個向量的 hamming distance 等於兩向量做 bit-wise XOR 的 hamming weight
* 對於線性碼來說，$d_{min}(C) = w_{min}(C)$, C 的 minimum distance 等於 minimum weight
* (7,3) hamming code 的向量是 $\forall x,\ x \in N(H)$，這個編碼的 minimum distance = minimum weight = 3
* 如果一個編碼要改正 t 個錯誤，則他的 minimum distance 至少需要 2t+1 所以 (7,3) hamming code 的 minimum distance 為 3 最多只能改正1個錯誤
* 搭配閱讀 Hamming codes, Part I 及 Hamming codes, Part II，你可適度摘錄影片中的素材，但應當清楚標註來源
* 研讀 Reed–Solomon error correction，再閱讀 Linux 核心原始程式碼的 lib/reed_solomon 目錄，抽離後者程式碼為單獨可執行的程式，作為 ECC 的示範。
## Test2
```c=1
#include <stdlib.h>
typedef struct {
int **parent;
int max_level;
} TreeAncestor;
TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize)
{
TreeAncestor *obj = malloc(sizeof(TreeAncestor));
obj->parent = malloc(n * sizeof(int *));
int max_level = 32 - __builtin_clz(n) + 1;
for (int i = 0; i < n; i++) {
obj->parent[i] = malloc(max_level * sizeof(int));
for (int j = 0; j < max_level; j++)
obj->parent[i][j] = -1;
}
for (int i = 0; i < parentSize; i++)
obj->parent[i][0] = parent[i];
for (int j = 1;; j++) {
int quit = 1;
for (int i = 0; i < parentSize; i++) {
obj->parent[i][j] = obj->parent[i][j + -1] == -1
? -1
: obj->parent[obj->parent[i][j - 1]][j - 1];
if (obj->parent[i][j] != -1) quit = 0;
}
if (quit) break;
}
obj->max_level = max_level - 1;
return obj;
}
int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)
{
int max_level = obj->max_level;
for (int i = 0; i < max_level && node != -1; ++i)
if (k & (1 << i))
node = obj->parent[node][i];
return node;
}
void treeAncestorFree(TreeAncestor *obj)
{
for (int i = 0; i < obj->n; i++)
free(obj->parent[i]);
free(obj->parent);
free(obj);
}
```
* `AAA = int **parent`
* `BBB = -1`
* `CCC = 1 << i`
* 運作原理
* 延伸問題:
解釋上述程式碼運作原理，指出可改進的地方，並實作對應的程式碼;
在 treeAncestorCreate 函式內部，若干記憶體被浪費，請撰寫完整測試程式碼，並透過工具分析;
在 LeetCode 1483. Kth Ancestor of a Tree Node 提交你的實作，你應該要在 C 語言項目中，執行時間領先 75% 的提交者;
## Test3
```c=1
#define MSG_LEN 8
static inline bool is_divisible(uint32_t n, uint64_t M) {
return n * M <= M - 1;
}
static uint64_t M3 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1;
static uint64_t M5 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 5 + 1;
int main(int argc, char *argv[]) {
for (size_t i = 1; i <= 100; i++) {
uint8_t div3 = is_divisible(i, M3);
uint8_t div5 = is_divisible(i, M5);
unsigned int length = (2 << div3) << div5;
char fmt[MSG_LEN + 1];
strncpy(fmt, &"FizzBuzz%u"[(MSG_LEN >> KK1) >> (KK2 << KK3)], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");
}
return 0;
}
```
* `KK1 = div 5`
* `KK2 = div 3`
* `KK3 = 2`
* 運作原理
* 延伸問題
解釋上述程式運作原理並評估 naive.c 和 bitwise.c 效能落差
避免 stream I/O 帶來的影響，可將 printf 更換為 sprintf
分析 Faster remainders when the divisor is a constant: beating compilers and libdivide 一文的想法 (可參照同一篇網誌下方的評論)，並設計另一種 bitmask，如「可被 3 整除則末位設為 1」「可被 5 整除則倒數第二位設定為 1」，然後再改寫 bitwise.c 程式碼，試圖運用更少的指令來實作出 branchless;
參照 fastmod: A header file for fast 32-bit division remainders on 64-bit hardware
## Test4
```c=1
#include <stdint.h>
#define ffs32(x) ((__builtin_ffs(x)) - 1)
size_t blockidx;
size_t divident = PAGE_QUEUES;
blockidx = offset >> ffs32(divident);
divident >>= ffs32(divident);
switch (divident) {
CASES
}
```
* 運作原理
* 延伸問題
解釋程式運算原理，可搭配 Microsoft Research 的專案 snmalloc 來解說;
對應的原始程式碼 src/mem/sizeclass.h
練習 LeetCode 51. N-Queens，應選擇 C 語言並善用上述的 __builtin_ffs，大幅降低記憶體開銷;
Sign in with Wallet
Connect another wallet