# SOO
:::warning
前情提要
[Facebook](https://www.facebook.com/groups/system.software2022/posts/2081326045382128/)
[微中子的貼文](https://tigercosmos.xyz/post/2022/06/c++/smallvec/)
:::
SSO and SOO 我相信大家都不陌生，詳細可以看 Mes 鄭教授的[這篇介紹](https://hackmd.io/@Mes/Miner_Magic_SSO)。不過對於[微中子的貼文鏡像](http://archive.today/Aw9tT)中的測試方式第一眼我是有疑慮的
這邊有幾點需要考慮：
1. [物件可不可以被優化，而搬到迴圈之外？](#物件可不可以被優化，而搬到迴圈之外？)
2. [如何在 stack 上生成 array ？](#如何在stack上生成array？)
3. [更好的 SSO 評估方式](#更好的SSO評估方式)
> 有點抱歉中英文沒有加空白鍵，讀起來有一點點痛苦，這是為了要實現 href 讓你方便直接跳到那個 tag
## 物件可不可以被優化，而搬到迴圈之外？
假定你已經熟悉這優化，也知道 RAII，我們就直接來看組語吧！
[Godbolt](https://godbolt.org/z/q8xs49Tsx)
先看 C++
```cpp=
template <typename T, size_t N = 10>
class SmallVec
{
public:
SmallVec() = default;
void push_back(T const & value)
{
if(cur < N)
m_data[cur++] = value;
else
m_v.push_back(value);
}
private:
std::vector<T> m_v;
std::array<T, N> m_data;
size_t cur = 0;
};
```
對照抽取的部份 asm
```asm=
.L19:
mov QWORD PTR [rsp+80], 0
xor eax, eax
xor r14d, r14d
xor ebp, ebp
xor r15d, r15d
xor ebx, ebx
jmp .L15
.L39:
lea rdx, [rax+1]
mov QWORD PTR [rsp+80], rdx
mov DWORD PTR [rsp+40+rax*4], ebx
.L3:
add ebx, 1
cmp ebx, 10
je .L14
.L40:
mov rax, QWORD PTR [rsp+80]
.L15:
mov r12, r14
sub r12, rbp
cmp rax, 9
jbe .L39
cmp r14, r15
je .L4
mov DWORD PTR [r15], ebx
add ebx, 1
add r15, 4
cmp ebx, 10
jne .L40
.L14:
test rbp, rbp
je .L16
mov rsi, r12
mov rdi, rbp
call operator delete(void*, unsigned long)
sub r13, 1
jne .L19
```
注意到 .L14 這邊就是 dtor，可以明顯看到我們確實讓他在 .L15 的 Line 26 mov DWORD PTR [r15], ebx 把資料般到 r15 之後，如過超出迴圈範圍，會跳到 .L14 呼叫 dtor
我們把他加上一個 std::vector 作為 member，這樣當 sv 需要被解構的時候必須要去解構 std::vector，這樣就無法被 compiler 化簡 dtor。
所以我們得到 std::vector 跟 SmallVec 效能相似的結果
而效能比 std::vector 好，我認為是分支比較少的關係，因為我們可以觀察到：
sv 的 push_back 相當簡單，只有一個分支而後就可以搬動資料
```asm=
.L19:
mov QWORD PTR [rsp+80], 0
xor eax, eax
xor r14d, r14d
xor ebp, ebp
xor r15d, r15d
xor ebx, ebx
jmp .L15
.L71:
lea rdx, [rax+1]
mov QWORD PTR [rsp+80], rdx
mov DWORD PTR [rsp+40+rax*4], ebx
```
而，std::vector 的 push_back 分支處理就比較多次：
```asm=
.L31:
mov r12, r14
sub r12, r15
cmp rbx, r14
jne .L74
movabs rcx, 2305843009213693951
mov rax, r12
sar rax, 2
cmp rax, rcx
je .L75
cmp rbx, r15
mov edx, 1
cmovne rdx, rax
add rax, rdx
jc .L25
test rax, rax
jne .L76
xor r9d, r9d
xor r14d, r14d
xor r13d, r13d
.L27:
mov DWORD PTR [r13+0+r12], ebp
lea rbx, [r13+4+r12]
test r12, r12
jg .L77
test r15, r15
jne .L29
.L30: # Loopping
add ebp, 1
mov r12, r9
mov r15, r13
cmp ebp, 10
jne .L31
```
觀察到 .L31 的邊界檢查以及移動邊界，分支失敗多次對效能是很有傷害的。
所以，即便 vector 的仍快取在 page table 上，也會有相較於純 array 1.5 倍的邊界負擔。
## 如何在stack上生成array？
[Godbolt](https://godbolt.org/z/Y8aj4Wcqs)
首先我們看到 Line 10:
```asm=
main:
push r15
mov eax, 3735928495
push r14
push r13
push r12
movabs r12, 2305843009213693950
push rbp
push rbx
sub rsp, 104
mov QWORD PTR [rsp+24], rax
lea r13, [rsp+56]
mov rbp, r13
```
對應的 Cpp 是：
```cpp=
constexpr int K = 10;
namespace {
template <typename T, size_t N = 10>
class SmallVec
{
public:
explicit SmallVec(size_t size);
void push_back(T const & value);
T operator[](size_t index);
private:
T *m_head = nullptr;
size_t m_size = 0;
size_t m_capacity = N;
std::array<T, N> m_data;
};
};
```
104 是被 alignment 優化的，優化 stack 往上增長以 8 的倍數做考量(因為是 64-bit)。我們可以明顯看到 sub rsp, 104 就是推移 stack pointer 104 byte 預留給這個 array 跟 member data。
### Array 的運作方式
如上是直接推移 stack pointer 沒有對 memory 做額外的 allocation，基本上跟 [alloca](https://man7.org/linux/man-pages/man3/alloca.3.html) 等價。
而 std::vector 每次都會去 heap allocation 所以會有微中子這篇的結果：
### 迴圈與函式呼叫
會有這議題是因為 sv 物件生命週期在迴圈的 scpoe 當中，所以我們期待要將 sv 物件在迴圈離開(或重入)的時候解構。但是這個 sv 物件的 stack 上成員其實是可以重複利用的，所以在 -fcombine-stack-adjustments (-O1 就有) 開啟的情況下，是可以將個一個 sv 物件的 array reference 到 stack 上 array。
而且迴圈不會推動 stack 的指標，所以這邊在建構及解構 sv 物件的時後，頂多是洗掉 array 中的值，也不會將 array re-allocation 去推動 stack pointer。
所以這觀念有點像 tail-recursion，用跳躍的方式去執行重複步驟，而不用額外推 stack 保存狀態。
### 有一點奇怪的測試結果
考慮到上面是把 array 放在 stack 上，所以比反覆 malloc 在 heap 效能好，那麼我們把 array 放在 heap 上，同時也把 vector 的 reserve 打開(減少 space doubling 的誤差)。
這樣兩個效能應該要近似：
確實是有點相似，但是為什麼 std::unique_ptr<std::array<T, N>> 會比 std::vector 還要差呢？
我還沒有好的解釋，std::unique_ptr 除了搬到 heap 上，應該是沒有其他 overhead 才對，歡迎告訴我。(其實我還沒去看 asm，但是我想可以從 asm 看出 std::unique_ptr 的問題)
## 更好的SSO評估方式
因為重點是小物件的分配可以放在 stack 上，然而 stack 是 fixed length 的，即便你跨越這個 function stack 預期的空間使用，你還是有可能會遇到超出 stack page 的 stack overflow，所以我們設計一個包裝 (wrapper) 用來包裝 array 跟 vector，然後跟指標指向 vector 比較，以減少 RAII dtor 對效能的衝擊。
> 其實我覺得 RAII 是好東西，但是對於最極度的優化(最佳化)，是需要調整的。
上面用 std::unique_ptr 把 array 搬到 heap 是一個方式，這樣可以「控制變因」，讓兩個比較都有經過經過 heap 上相同的解構次數。
但是，更好的測定方式是將造成干擾的變因移除，不是加入干擾。
所以我們把 vector 搬到迴圈外，然後在迴圈內使用 clear 而不是 dtor，這樣可以有效的移除 dror 在迴圈結束的後，造成的衝擊。
### 保留 std::unique_ptr 與 std::vector 的比較
```cpp=
static void SmallVector(benchmark::State& state) {
for (auto _ : state) {
SmallVec<int> sv; // 使用 inline memory
for(int i = 0 ; i < K; i++) {
sv.push_back(i);
}
}
}
BENCHMARK(SmallVector);
static void StdVector(benchmark::State& state) {
std::vector<int> v;
v.reserve(K); // 分配新的 Heap 記憶體
for (auto _ : state) {
v.clear();
for(int i = 0 ; i < K; i++) {
v.push_back(i);
}
}
}
BENCHMARK(StdVector);
```
我們可以看到這樣 vector 就顯著的比原本好多了，可見如我們預期主要影響因子是 dtor。
### 把 dtor 都消除，比較都在 heap 上的結果
可以看到 std::vector<> 的處理似乎比較好，但是原因尚未清楚。
看起來 mov 0xc(%rsp),%eax 是把 i 複製到 array 當中，花上了 50% 的效能
#### 把 O3 改為 O2
我對 O3 的魔法不清楚， [GNU 文件](https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html) 上面提到：
> -fgcse-after-reload
-fipa-cp-clone
-floop-interchange
-floop-unroll-and-jam
-fpeel-loops
-fpredictive-commoning
-fsplit-loops
-fsplit-paths
-ftree-loop-distribution
-ftree-partial-pre
-funswitch-loops
-fvect-cost-model=dynamic
-fversion-loops-for-strides
但是究竟是什麼激進的提示，讓 compiler 可以作到上面化簡，不清楚。
## 定長治百病
既然上面結果這樣，我們就可以嘗試把 std::unique_ptr 移除，讓 SOO 保留在 stack 上。也不要有動態長度。
我們得到這樣的結果。太棒了，SOO 讓物件搬到 stack，這樣完全消除了容器的 overhead。
:::success
看到這精美的效能優勢，
Yes, 有極致的效能就是身心舒暢。
:::
Sign in with Wallet
Connect another wallet