# 2022q1 Project (cpumemory)

contributed by < [2020leon](https://github.com/2020leon) >

## 目標

- [ ] [閱讀](#閱讀論文) Ulrich Drepper 於 2007 年撰寫的論文《 [What Every Programmer Should Know About Memory](https://www.akkadia.org/drepper/cpumemory.pdf) 》(版次: 1.0)
- [ ] 嘗試[執行第六章提及的程式碼](#執行第六章提及的程式碼)
- [ ] [翻譯和校訂](#翻譯和校訂)《[每位程式開發者都該有的記憶體知識](https://sysprog21.github.io/cpumemory-zhtw/)》

## 環境

$ uname -a
Linux leon-ubuntu-20 5.13.0-44-generic #49~20.04.1-Ubuntu SMP Wed May 18 18:44:28 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   36 bits physical, 48 bits virtual
CPU(s):                          4
On-line CPU(s) list:             0-3
Thread(s) per core:              1
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           58
Model name:                      Intel(R) Core(TM) i5-3570 CPU @ 3.40GHz
Stepping:                        9
CPU MHz:                         1700.000
CPU max MHz:                     3800.0000
CPU min MHz:                     1600.0000
BogoMIPS:                        6784.21
Virtualization:                  VT-x
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        6 MiB
NUMA node0 CPU(s):               0-3

## 閱讀論文

### 6.2.1 Optimizing Level 1 Data Cache Access

6.2.1 花了很大的力氣在講述 L1d cache 對於程式速度的影響，在[實做](#矩陣乘法)過後也了解到，想要縮短程式的執行時間，勢必要了解資料在記憶體中的位置（空間局部性， spatial locality ），並且在寫程式的時候針對 L1d cache 的特性進行改善。

另外，在設計結構（ `struct` ）的時候可以藉由調整成員的順序以減少空間的浪費（如避免四位元組和八位元組的資料型態交互使用）、照宣告順序存取成員、將時常存取的成員放置於結構的開頭等。在針對大型資料結構時，為了有效利用快取，可以根據結構的使用情境將時常被存取和不常被存取的成員分開成兩個結構，如此在處理這類大型結構的陣列時可以避免將不常被存取的成員放入快取中。

除了考慮空間局部性外，對齊（ align ）也是很重要的一環，以免從記憶體搬動資料到 cache 時缺乏效率。


在動態記憶體配置的部份，即便由 `malloc` 、 `calloc` 和 `realloc` 所配置的記憶體已經針對何內建型態進行對齊，但仍然可以透過 [`posix_memalign`](https://man7.org/linux/man-pages/man3/posix_memalign.3.html) 自訂所要對齊的位元組數。

對於結構的部份，可以透過 GCC 的 `__attribute__((aligned(n)))` 進行資料的對齊。

### 6.2.2 Optimizing Level 1 Instruction Cache Access

論文列出以下幾點可盡量有效利用 L1d cache ：

1. 減少程式碼量，但需要在迴圈展開和函式內嵌之間達到平衡
2. 程式盡量線性執行
3. 合理對齊程式碼

第一點的實現除了由工程師精簡編譯前的程式碼外，大都可藉由編譯器的最佳化（ `-O2` 、 `-O3` 和 `-Os` ）來完成，而且都有不錯的效果。

第二點可以藉由 GCC 內建函式來實現將更為常用的指令搬到靠近 `if` 敘述的地方：

#define unlikely(expr) __builtin_expect(!!(expr), 0)
#define likely(expr) __builtin_expect(!!(expr), 1)

這類的程式碼在 Linux 核心經常出現。

第三點中，論文列出效果最好的程式對齊點：

1. 函式開頭
2. 只會透過 `jump` 相關指令抵達的 block
3. 在某些迴圈的開頭

前兩種可藉由加入 no-op 指令使之對齊，新增的 no-op 指令並不會被執行到，對於效能的衝擊甚小。第三種情況中，由於大部分的迴圈總是接續在其他程式碼後，在迴圈前加入的 no-op 指令便會被執行，或是藉由 `jump` 指令直達迴圈，這樣的效能衝擊可能會對對齊所省下的成本來的高。

## 執行第六章提及的程式碼

### 矩陣乘法

6.2.1 以矩陣乘法作為範例，了解到一階資料快取對於效能的影響。

首先是直觀的實做。

#define N 1024

void mul_origin(double (*a)[N], double (*b)[N], double (*c)[N])
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            for (int k = 0; k < N; k++)
                c[i][j] += a[i][k] * b[k][j];
}

所花費的時間約為 3.19 秒。但上述方法可以很明顯看到 `b` 矩陣是 cache unfriendly 的，原因是沒有有效利用到 cache 的空間局部性。因此嘗試將矩陣轉置過後再相乘。

#define N 1024

void mul_transposed(double (*a)[N], double (*b)[N], double (*c)[N])
{
    double(*d)[N] = malloc(N * sizeof(*d));
    if (!d)
        return;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            d[i][j] = b[j][i];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            for (int k = 0; k < N; k++)
                c[i][j] += a[i][k] * d[j][k];
    free(d);
}

所花費的時間約為 0.93 秒，約為第一個實做的三分之一。在上方的函式中，將乘號後方的矩陣 `b` 轉置為 `d` 後，在做乘法時，由於所取得的元素均在相鄰的位置上，所以發生 cache miss 的機率遠小於第一個實做。

最後是考慮 L1d cache 的矩陣乘法。在此 cahce line size 為 64 。

:::info
L1d cache line size 可由以下命令取得：

$ getconf LEVEL1_DCACHE_LINESIZE
64

:::

#ifndef CLS
#define CLS 64
#endif

#define SM (CLS / sizeof(double))

void mul_sub(double (*a)[N], double (*b)[N], double (*c)[N])
{
    int i, j, k, i2, k2, j2;
    double *ra, *rb, *rc;
    for (i = 0; i < N; i += SM)
        for (j = 0; j < N; j += SM)
            for (k = 0; k < N; k += SM)
                for (i2 = 0, rc = &c[i][j], ra = &a[i][k]; i2 < SM;
                     i2++, rc += N, ra += N)
                    for (k2 = 0, rb = &b[k][j]; k2 < SM; k2++, rb += N)
                        for (j2 = 0; j2 < SM; j2++)
                            rc[j2] += ra[k2] * rb[j2];
}

所花費的時間約為 0.31 秒。這次更是使還在 L1d cache 中的資料在計算完關於它的部份後才換下一個 cache line ，使得 L1d cache 發揮它最大的效益。

| Origin | Transposed | Sub Matrix |
| ---------- | ---------- | ---------- |
| 3194333615 | 931789102 | 307312426 |
| 100.0000% | 29.1701% | 9.6205% |

## 翻譯和校訂

在閱讀了《每位程式開發者都該有的記憶體知識》譯文後，除了發現內部有些尚未翻譯的原文語句外，在查閱過去的 commits 後，亦發現部份尚未完全解決的問題，因此著手修改譯文。以下列出所觀察到的問題：

- 少部份語句未翻譯
- 關於 efficient/efficiently 的中譯（[ref](https://github.com/sysprog21/cpumemory-zhtw/commit/5d68ac3f8df34c37f22c9ad82a7c49135931ae75)）
- 譯詞不統一
- core：處理器核、核（[ref](https://github.com/sysprog21/cpumemory-zhtw/commit/b3b0bc2e8fcdaeb841bfd56503e05261dd4f529e)）
- OS：作業系統（[ref](https://github.com/sysprog21/cpumemory-zhtw/commit/985bb48d278402834bb96c54ab73c10419de294e)）
- last level cache：最後一階快取（[ref](https://github.com/sysprog21/cpumemory-zhtw/commit/a2ea355ecd17d3c63e0bf519cf90c093afd73efb)）
- 部份語法

在經過修正後，已經對原 repo 發出 [PR](https://github.com/sysprog21/cpumemory-zhtw/pull/3)。