# 2017q1 Homework5 (matrix)
constributed by <`stanleytazi`>
###### tags: `stanleytazi` `matrix-oo`
## 重現 [Matrix Multiplication using SIMD](https://hackmd.io/s/Hk-llHEyx) 實驗
在這份共筆裡探討了各種不同矩陣乘法的實作包括了
+ naive - 依照定義直接計算
+ submatrix - 把矩陣切成較小的矩陣來運算，可以運用比較多的 spatial locality 來增加 cache hit 的機率
+ SSE & AVX - 除了用 SIMD 的 intrinsic 外，也加入了 prefetch 的版本來比較效能
+ 使用 Strassen Algorithm 來做矩陣乘法
+ 討論 data alignment 對效能的影響
+ 如何產生夠亂的亂數矩陣 以及如何定義 "亂"
**[TODO]** 直接來利用這次的作業來把這篇共筆裡討論的各種實驗結合在一起吧！
## 觀察 matrix_oo
> 每次看到老師提供的 **"尚待改進"** 的作業，都覺得天呀，c語言竟然可以這樣寫
### 先來看 matrix.h
看一下程式想要提供的介面 MatrixAlgo
+ 定義了三個 methods，如此一來可以利用同一組介面但是卻使用不同的實作方式
```clike=
typedef struct {
void (*assign)(Matrix *thiz, Mat4x4);
bool (*equal)(const Matrix *l, const Matrix *r);
bool (*mul)(Matrix *dst, const Matrix *l, const Matrix *r);
} MatrixAlgo;
```
+ 但是也看到很神奇的**Mat4x4**，可以看到有 define 一個 macro 用來產生不同 size 且 是 float type 的 Matrix
+ 如果要支援不同的 (col, row) 的組合也是要利用這個 macro 嘛？
+ 目前想到的作法下面 **實作**
```clike=
#define DECLARE_MATRIX(col, row) \
typedef struct { float values[col][row]; } Mat ## col ## x ## row
DECLARE_MATRIX(3, 3);
DECLARE_MATRIX(4, 4);
```
## 實作
### 支援不同 type, size
+ 在 matrix.h 做了以下宣告
```clike=26
#define FUNC_GEN_MATRIX(type) \
static inline type **matrix_gen_##type(int rows, int cols) { \
type **matrixValue = (type **)malloc(rows * sizeof(type*)); int i;\
for (i = 0; i < rows; i++)\
*(matrixValue + i) = (type *)malloc(cols * sizeof(type));\
return matrixValue;\
}
FUNC_GEN_MATRIX(float)
FUNC_GEN_MATRIX(int)
#define NEW_MATRIXX(type, rows, cols) matrix_gen_##type(rows, cols)
```
> 要去同時更改不同的 type & size 一下子出現好多要考慮的問題
> - 以上程式宣告可以解決在 assign 分配記憶體的方式
> - 但是對於 assign 所傳入的 data的大小是還要另外考慮
> - 在原始版本 test-matrix.c 使用 designated initializer 直接宣告一個 2D-array 並設定初始值傳入 assign()，這個array 型別會是 float(*)[4] (如果是4x4)，如果要傳入其他大小的矩陣，就要另外把傳入的 data 的type 變成 float \*\*，如此一來除了解除矩陣大小 hardcode 的限制也可以在 assign 中用 subscript 的方式取用 data
```clike=
static void assign(Matrix *thiz, int rows, int cols, float **data)
{
thiz->row = rows;
thiz->col = cols;
thiz->priv = (struct naive_priv *) malloc(sizeof(struct naive_priv));
PRIV(thiz)->values = NEW_MATRIXX(float, rows, cols);
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
PRIV(thiz)->values[i][j] = data[i][j];
}
```
> + 而在 test/test-matrix.c 中給測資的方式仍然用原本的方式，只是另外在此多一層轉換後再丟入 assign() 中
> + 雖然 assign_value_f4x4() 仍是一個 hardcode 寫死，但是現在可以只透過修改測試程式來驗證不同的矩陣大小的乘法
```clike=
static void assign_value_f4x4(float **data, int rows, int cols, Mat4x4 input)
{
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
data[i][j] = input.values[i][j];
}
MatrixAlgo *matrix_providers[] = {
&NaiveMatrixProvider,
};
int main()
{
MatrixAlgo *algo = matrix_providers[0];
Matrix dst, m, n, fixed;
float **data = NEW_MATRIXX(float, 4, 4);
assign_value_f4x4(data, 4, 4, (Mat4x4) {
.values = {
{ 1, 2, 3, 4, },
{ 5, 6, 7, 8, },
{ 1, 2, 3, 4, },
{ 5, 6, 7, 8, },
},
});
algo->assign(&m, 4, 4, data);
...
}
```
## Study
老師在社團分享了幾篇文章，因為牽涉到這次會用到的記憶體管理，閱讀後簡單做個摘要以便作業使用
### [Small-Size Optimization in C](http://nullprogram.com/blog/2016/10/07/)
+ 我們在程式中很常用到較小並且只是在一小段程式中會使用到的記憶體，這些記憶體往往是以 array 型別在 stack 區段中分配來使用
+ 操作 stack 中取得的記憶體成本是比較低的(相對於從 heap 取得)
+ 可以使用 alloca() 在 stack 上取得記憶體，但是假設所需的記憶體大小超過 stack 所能分配的，程式會直接 crash 掉
+ 使用 alloca() 另外一個缺點就是 protability，在文章中另外有提到 在c99 提出的 VLA (Variable-Length Arrays) 是可以 prtable，但是同樣有記憶體不足就 crash 的問題
+ 如果不用 alloca() 或是 VLA ，那我們可以有一個比較折衷的方式，如果所需的記憶體不多，那比較小且預先分配好大小的 arrays 就可以滿足需求了，如果不夠那就再用 malloc() 去取得較大的 heap 的 memory
+ 分別舉了使用 malloc, array, 以及 caller 提供array buffer 的例子:
+ memory allocated via **malloc()**
```clike=
int
vec_simple_init(struct vec_simple *v, size_t hint)
{
assert(hint && (hint & (hint - 1)) == 0); // power of 2
v->size = hint;
v->count = 0;
v->values = malloc(sizeof(v->values[0]) * v->size);
return !!v->values;
}
```
如果使用上是比較少超過所分配的 size 且會常常 call 到這function ，那就是可以使用 stack 來分配這些記憶體來優化
+ Appling Small-Size Optimization
```clike
struct vec_small {
size_t size;
size_t count;
long *values;
long temp[16];
};
void
vec_small_init(struct vec_small *v)
{
v->size = sizeof(v->temp) / sizeof(v->temp[0]);
v->count = 0;
v->values = v->temp;
}
int
vec_small_push(struct vec_small *v, long x)
{
if (v->count == v->size) {
size_t value_size = sizeof(v->values[0]);
size_t new_size = v->size * 2;
if (!new_size || value_size > (size_t)-1 / new_size)
return 0; // overflow
// 這裡不夠用，會另外使用 malloc()來分配記憶體，等於是 worse case
void *new_values;
if (v->temp == v->values) {
/* First time heap allocation. */
new_values = malloc(new_size * value_size);
if (new_values)
memcpy(new_values, v->temp, sizeof(v->temp));
} else {
new_values = realloc(v->values, new_size * value_size);
}
if (!new_values)
return 0; // out of memory
v->size = new_size;
v->values = new_values;
}
v->values[v->count++] = x;
return 1;
}
```
+ Using a Caller-Provided buffer
``` clike
struct vec_flex {
size_t size;
size_t count;
long *values;
};
void
vec_flex_init(struct vec_flex *v, long *init, size_t nmemb)
{
assert(nmemb > 1); // we need that low bit!
assert(nmemb && (nmemb & (nmemb - 1)) == 0); // power of 2
v->size = nmemb | 1;
v->count = 0;
v->values = init;
}
long
example(long (*f)(void *), void *arg)
{
struct vec_flex v;
long buffer[16];
vec_flex_init(&v, buffer, sizeof(buffer) / sizeof(buffer[0]));
long n;
...
}
```
+ [個人想法] 這篇文章使用上有個前提就是 memory的使用是 small-size & frequently used，所以還是要看程式的應用狀況來決定是否要用 stack 來分配記憶體， 如果常常超過預先分配好的 buffer ，那也會常用 malloc()，而達不到預先想要優化的目的
## Backup
```
```
Sign in with Wallet
Connect another wallet