Swift Array Capacity 變化之謎
yllan陳涵宇問了這個問題:
從 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擴充的行為呢?
延伸討論
- 使用不同尺寸的元素(Int8、Int16、Int32、Int)會導致不同的 capacity 變化 pattern,可以試試看能不能預測。
- 解釋為什麼和 OEIS A033484 這個數列有關係。
- malloc 和 OS 的記憶體管理的關係為何?其實 malloc 是 application level 的 library,有點像是二房東,和 OS 挖一塊記憶體過來以後,就自行分配。
- 為何 malloc 要這樣設計,不是你要多少就給多少,減少浪費?可以自行實作 malloc() 看看,也可以仔細研究 libmalloc 的做法。