為什麼你應該幫 Rust Vector 加上初始容量
You can find the English version at Maximizing Rust Vector Efficiency: Why Initial Capacity Tricks Work.
前言
在比較高階的程式語言裡中通常都會提供 Growable 的 Array 型別，像 C++ 跟 Rust 的 Vector、Go 的 Slice 或是 JS 的 Array 都可以可以變動長度，並且提供 push 跟 pop 的功能用來增加、刪掉 element，簡單來說就是加強版的 Array
因為各語言 Growable Array 的內部實作都大同小異，所以這篇文章講的也不限於 Rust Vector，只是我剛好最近在寫 Rust 所以用 Rust Vector 做範例。如果你不太熟悉 Rust 也沒關係（寫 Rust 的人真的好少 😢），看看以下這個範例就會明白 Rust 的 Vector 怎麼用了
為什麼 Vector 可以一直長大
如果你寫過 C 這類比較低階的程式語言，就會知道分配記憶體時一定要指定一個長度。所以 Vector 這種 Growable Array 為了提供 push 的功能，一定要事先分配更多空間
以 [1, 2, 3] 的例子來說，Vector 可能會先分配 6個整數的空間（Capacity），然後在前三格放 [1, 2, 3]
之後再跑 vec.push(4) 時就可以把 4 擺在後面，不用再重新分配記憶體
但因為一開始只分配了 6 個整數的空間，若繼續 push 下去那些容量遲早會被用完。所以當 Vector 已經沒有空間而我又要 push 時，Rust 就會重新分配一段兩倍大的記憶體，並且把目前 Vector 內的內容都複製過去
所以當我執行 vec.push(7) 後 Vector 的容量就會變成 12，這時又有五格空間。如果過一陣子又 push 滿了，那就再分配一段兩倍大的記憶體、把內容複製過去
小範例：double
了解 Vector 的擴充機制後來看這個小範例 double，他的功能是產生一個新的 Vector，裡面的值都是原本 Vector 的兩倍，譬如說 [1,2,3] 變成 [2,4,6]
目前的實作是用 Vec::new() 宣告一個新的 vec2 之後，把 vec 內的元素每個都乘二 push 進去新的 vec2 裡面
這樣做有什麼問題嗎 🤔
剛在上面有提到 Vector 在分配記憶體時會預留一些空間，但如果容量不夠了就會重新分配一段 兩倍大 的記憶體，並且把資料複製到新的位置
所以如果要 double 長度為一萬的 Vector，那就必須 進行一萬次 push，在這一萬次 push 的過程中可能會一直超出預留的容量，所以 Vector 為了擴充容量必須不斷重新分配記憶體、複製 Vector 的內容，導致這一萬次 push 需要花更多時間
改良版 double
因為不斷的分配記憶體、複製內容很費工，所以 Rust 也提供了另一個初始化 Vector 的方式：Vec::with_capacity(cap)，有了它就可以幫 Vector 設定初始容量。如果可以在一開始就預留足夠的容量，那即便之後一直 push 也不需要再搬動內容，效率自然比較高
第二個版本跟原版的 double 幾乎一樣，唯一的不同就是把第一行的 Vec::new() 改成 Vec::with_capacity(vec.len())，也就是把初始容量設為原本 vec 的長度，畢竟 double 過後的 Array 一定會跟原本一樣長，這樣就不怕超出容量，可以一直 push 一直 push（感覺好開心XD）
效能比較
理論上預留 capacity 一定會讓速度更快，但到底快多少呢？我實際用 double 跟 double2 分別去跑長度為十萬的 Array，為了避免誤差所以我跑了一千次做加總
得到的結果第一版本的 double 大概需要 273 ms，而改良後的 double2 只需要 107 ms，算起來 double2 大概快了 2.5 倍左右（改一行扣就可以加速這麼多，還不快改嗎XD），而且這是在 release 模式下進行編譯，所以應該很接近實際結果
結論
回到這篇的主題，你現在應該知道為什麼要幫 Rust Vector 加上初始容量了
如果你能確定 Vector 最後會放幾個元素，像例子中 double 之後的 Vector 一定跟原本一樣長，那就可以善用初始容量讓 push 更快。如果無法得知確切數量，但你知道 至少 會放幾個，那也可以設定初始容量讓擴充的次數變少
另外如果你不是寫 Rust 的也沒關係，其實各語言裡面都有類似的初始化方式，像 Go 的 make([]T, len, cap) 跟 Java 的 new ArrayList<T>(cap)，所以重點在於理解 Vector 的擴充機制、知道什麼時候該設初始容量，語法的話查一下就有了
最後的最後提醒一下，雖然幫 Vector 加上初始容量可以讓 push 更快，但對整個程式來講影響可能非常小。如果想要 大幅 提升整個應用程式的效能，那還是要從架構、IO Model、演算法等等方面下手，光是把 Vec::new() 改成 Vec::with_capacity(cap) 是沒有用的 😂
