Swift Array Capacity 變化之謎

陳涵宇問了這個問題：

從 Swift 原始碼的確可看到，Swift Array 如果容量不足了，的確會倍增（double, ×2）容量。至少以上列出來的 capacity 在 32 以前的確都是遵守這個規則的。那後來到底發生什麼事呢？要了解 Array 擴充的行為，你要知道兩件事：

Array 所花費的記憶體不只要存 Elements，還有本身的額外開銷

如果你仔細去追，會發現 Array 的設計，底層儲存其實是由叫做 _ContiguousArrayStorage<T> 的東西來負責的（以下簡稱CAS）。

當 Array 要擴大容量時，會去要一塊至少放得下目前容量×2的 CAS。

這個 Builtin.allocWithTailElems_1(CAS<Element>.self, realMinimumCapacity._builtinWordValue, Element.self) 到底在做什麼事呢？我猜，他是說我要 allocate 一個 CAS，然而不止如此，我還要求 CAS 右邊要能放得下 realMinimumCapacity 這麼多個元素。

Allocate 記憶體時，不是要多少就給多少

不知你是否注意過，有些檔案明明很小，在硬碟上卻佔了比較大的容量：

這看似浪費空間，其實是在效率上做出取捨。

記憶體也一樣，當你 malloc(1) 的時候，實際上配給你的空間不是真的只有 1byte，而是會取一個最小基本單位——在這裡我們稱為 quantum。macOS 使用的 libmalloc 設計，會按照需求大小，使用不同尺寸的 quantum。當你要 malloc 的記憶體在 1KB 以下，會使用 16bytes quantum；超過 1KB，就會使用 0.5KB 的 quantum；再大到某個程度（我實測是32KB，但網路上查有不同的說法），就會直接使用 page size 4KB。（這邊講的只是某種實作細節並非真理，不同家的 malloc 可能有不同考量而選擇不同的策略，例如 jemalloc / tcmalloc，甚至就連 libmalloc 本身好像也會按照機器有多少記憶體、CPU 而採用不同策略）

當你要 allocate 一塊 20 bytes 的記憶體，malloc 實際上會割 32 bytes 給你，多出來的 12 bytes 就浪費了。當你要 allocate 1025 bytes，實際上會割給你 1024 + 512 bytes。

黑箱揭曉

綜合以上兩點，當我們 allocate 一塊記憶體時，malloc() 實際上會以 quantum size 為最小單位，割出足夠大的空間給你用，平時多出來的就是浪費了。然而 CAS 考量到，既然 malloc 有可能多割，反正我後面浪費的空間可以拿來放更多 elements，就按照真正割出的尺寸來計算 capacity 能放多少。

回到原題，在此我們就可以來計算 Swift Array 的 capacity 行為了。

Given CAS overhead = 32bytes, String = 16 bytes,

count 0→ 1, request (32 + 16) bytes, allocated 48 bytes (16 bytes quantum), capacity = (48 - 32)/16 = 1

count 1→ 2, request (32 + 16*2) bytes, allocated 64 bytes (16 bytes quantum), capacity = (64 - 32)/16 = 2

...

count 32→33, request (32 + 16*32*2) = 1056 bytes, allocated 1536 bytes (512 bytes quantum), capacity = (1536 - 32)/16 = 94

count 94→95, request (32 + 16*94*2) = 3040 bytes, allocated 3072 bytes (512 bytes quantum), capacity = (3072 - 32)/16 = 190

count 190→191, request (32 + 16*190*2) = 6112 bytes, allocated 6144 bytes (512 bytes quantum), capacity = (6144 - 32)/16 = 382

count 382→383, request (32 + 16*382*2) = 12256 bytes, allocated 12288 bytes (512 bytes quantum), capacity = (12288 - 32)/16 = 766

count 766→767, request (32 + 16*766*2) = 24544 bytes, allocated 24576 bytes (512 bytes quantum), capacity = (24576 - 32)/16 = 1534

count 1534→1535, request (32 + 16*1534*2) = 49120 bytes, allocated 49152 bytes (4096 bytes quantum), capacity = (49152 - 32)/16 = 3070

如何？是不是完美預測了Array擴充的行為呢？

延伸討論

1. 使用不同尺寸的元素（Int8、Int16、Int32、Int）會導致不同的 capacity 變化 pattern，可以試試看能不能預測。
2. 解釋為什麼和 OEIS A033484 這個數列有關係。
3. malloc 和 OS 的記憶體管理的關係為何？其實 malloc 是 application level 的 library，有點像是二房東，和 OS 挖一塊記憶體過來以後，就自行分配。
4. 為何 malloc 要這樣設計，不是你要多少就給多少，減少浪費？可以自行實作 malloc() 看看，也可以仔細研究 libmalloc 的做法。