CFArray的歷史淵源及實(shí)現(xiàn)原理
在 iOS 開發(fā)中，NSArray 是一個(gè)很重要的數(shù)據(jù)結(jié)構(gòu)。尤其 TableView 中的數(shù)據(jù)緩存與更新， NSArray 來(lái)緩存數(shù)據(jù)以及對(duì)于顯示數(shù)據(jù)的修改操作。而在 Core Foundation 中 CFArray 與 NSArray 相互對(duì)應(yīng)，這引起了筆者對(duì) Core Foundation 和 Foundation 庫(kù)中的原生數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)產(chǎn)生興趣，所以來(lái)研究一下。
CFArray 歷史淵源
NSArray 和 CFArray 是 Toll-Free Bridged 的，在 opensource.apple.com 中， CFArray 是開源的。這更有助于我們的學(xué)習(xí)與研究。在 Garan no Dou 大神之前在做個(gè)人工具庫(kù)的時(shí)候，曾經(jīng)研究過(guò) CFArray 的歷史淵源和實(shí)現(xiàn)手段，在閱讀此文之前可以參考一下前輩的優(yōu)秀博文。
Array 這篇 2005 年的早期文獻(xiàn)中，最早介紹過(guò) CFArray ，并且測(cè)試過(guò)其性能水平。它將 CFArray 和 STL 中的 Vector 容器進(jìn)行了性能對(duì)比，由于后者的實(shí)現(xiàn)我們可以理解成是對(duì) C 中的數(shù)組封裝，所以在性能圖上大多數(shù)操作都是線性的。而在 CFArray 的圖中，會(huì)發(fā)現(xiàn)很多不一樣的地方。
上圖分析可以看出， CFArray 在頭插、尾插插入時(shí)候的效率近乎常數(shù)，而對(duì)于中間元素的操作會(huì)從小數(shù)據(jù)的線性效率在一個(gè)閥值上突然轉(zhuǎn)變成線性效率，而這個(gè)躍變灰不由得想起在 Java 8 當(dāng)中的 HashMap 的數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)變方式。
在 ObjC 的初期，CFArray 是使用 deque 雙端隊(duì)列 實(shí)現(xiàn)，所以會(huì)呈現(xiàn)出頭尾操作高效，而中間操作成線性的特點(diǎn)。在容量超過(guò) 300000 左右時(shí)(實(shí)際應(yīng)該是 262140 = 2^18 )，時(shí)間復(fù)雜度發(fā)生陡變。在源代碼中，閥值被宏定義為 __CF_MAX_BUCKETS_PER_DEQUE ，具體代碼可以見 CF-550-CFArray.c (2011 年版本)：
- if (__CF_MAX_BUCKETS_PER_DEQUE futureCnt) {
- // 創(chuàng)建 CFStorage 引用
- CFStorageRef store
- // 轉(zhuǎn)換 CFArray 為 Storage
- __CFArrayConvertDequeToStore(array);
- store = (CFStorageRef)array->_store;
- }
可以看到，當(dāng)數(shù)據(jù)超出閥值 __CF_MAX_BUCKETS_PER_DEQUE 的時(shí)候，會(huì)將數(shù)據(jù)結(jié)構(gòu)從 CFArray 轉(zhuǎn)換成 CFStorage 。 CFStorage 是一個(gè)平衡二叉樹的結(jié)構(gòu)，為了維護(hù)數(shù)組的順序訪問(wèn)，將 Node 的權(quán)值使用下標(biāo)完成插入和旋轉(zhuǎn)操作。具體的體現(xiàn)可以看 CFStorageInsertValues 操作。具體代碼可以查看 CF-368.18-CFStorage.c 。
在 2011 年以后的 CF-635.15-CFArray.c 版本中， CFArray 取消了數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換這一功能。或許是為了防止大數(shù)據(jù)時(shí)候二叉樹建樹的時(shí)間抖動(dòng)問(wèn)題從而取消了這一特性。直接來(lái)看下數(shù)據(jù)結(jié)構(gòu)的描述：
- struct __CFArrayDeque {
- uintptr_t _leftIdx; // 自左開始下標(biāo)位置
- uintptr_t _capacity; // 當(dāng)前容量
- };
- struct __CFArray {
- CFRuntimeBase _base;
- CFIndex _count; // 元素個(gè)數(shù)
- CFIndex _mutations; // 元素抖動(dòng)量
- int32_t _mutInProgress;
- __strong void *_store;
- };
從命名上可以看出 CFArray 由單一的雙端隊(duì)列進(jìn)行實(shí)現(xiàn)，而且記錄了一些容器信息。
C 數(shù)組的一些問(wèn)題
C 語(yǔ)言中的數(shù)組，會(huì)開辟一段連續(xù)的內(nèi)存空間來(lái)進(jìn)行數(shù)據(jù)的讀寫、存儲(chǔ)操作。另外說(shuō)一句，數(shù)組和指針并不相同。有一種被很多教材書籍上濫用的說(shuō)法：一塊被 malloc 過(guò)的內(nèi)存空間等于一個(gè)數(shù)組。這是錯(cuò)誤的。最簡(jiǎn)單的解釋，指針需要申請(qǐng)一個(gè)指針區(qū)域來(lái)存儲(chǔ)(指向)一塊空間的起始位置，而數(shù)組(的頭部)是對(duì)一塊空間起始位置的直接訪問(wèn)。另外想了解更多可以看 Are pointers and arrays equivalent in C? 這篇博文。
C 中的數(shù)組最顯著的缺點(diǎn)就是，在下標(biāo) 0 處插入時(shí)，需要移動(dòng)所有的元素(即 memmove() 函數(shù)的原理)。類似的，當(dāng)刪除***個(gè)元素、在***個(gè)元素前插入一個(gè)元素也會(huì)造成 O(n)復(fù)雜度的操作 。然而數(shù)組是常讀寫的容器，所以 O(n) 的操作會(huì)造成很嚴(yán)重的時(shí)間開銷。
當(dāng)前版本中 CFArray 的部分實(shí)現(xiàn)細(xì)節(jié)
在 CF-855.17 中，我們可以看到當(dāng)前版本的 CFArray 的實(shí)現(xiàn)。文檔中對(duì) CFArray 有如下的描述：
CFArray 實(shí)現(xiàn)了一個(gè)可被指針順序訪問(wèn)的緊湊容器。其值可通過(guò)整數(shù)鍵(索引下標(biāo))進(jìn)行訪問(wèn)，范圍從 0 至 N-1，其中 N 是數(shù)組中值的數(shù)量。稱其緊湊 (compact) 的原因是該容器進(jìn)行刪除或插入某個(gè)值的時(shí)候，不會(huì)再內(nèi)存空間中留下間隙，訪問(wèn)順序仍舊按照原有鍵值數(shù)值大小排列，使得有效檢索集合范圍總是在整數(shù)范圍 [0, N-1] 之中。因此，特定值的下標(biāo)可能會(huì)隨著其他元素插入至數(shù)組或被刪除時(shí)而改變。
數(shù)組有兩種類型：不可變(immutable) 類型在創(chuàng)建數(shù)組之后，不能向其添加或刪除元素，而 可變(mutable) 類型可以添加或從中刪除元素?？勺償?shù)組的元素?cái)?shù)量***制(或者稱只受 CFArray 外部的約束限制，例如可用內(nèi)存空間大小)。與所有的 CoreFoundation 集合類型同理，數(shù)組將保持與元素對(duì)象的強(qiáng)引用關(guān)系。
為了進(jìn)一步弄清 CFArray 的細(xì)節(jié)，我們來(lái)分析一下 CFArray 的幾個(gè)操作方法：
- // 通過(guò)下標(biāo)查詢?cè)刂?nbsp;
- const void *CFArrayGetValueAtIndex(CFArrayRef array, CFIndex idx) {
- // 這個(gè)函數(shù)尚未開源
- // 通過(guò)給定的 CFTypeID 來(lái)驗(yàn)證指定元素是否匹配 Core Foundation 橋接類
- CF_OBJC_FUNCDISPATCHV(__kCFArrayTypeID, const void *, (NSArray *)array, objectAtIndex:idx);
- // 尚未開源
- // 通過(guò)給定的 CFTypeID 來(lái)驗(yàn)證 Core Foundation 類型合法性
- __CFGenericValidateType(array, __kCFArrayTypeID);
- CFAssert2(0 idx && idx __CFArrayGetCount(array), __kCFLogAssertion, "%s(): index (%d) out of bounds", __PRETTY_FUNCTION__, idx);
- CHECK_FOR_MUTATION(array);
- // 從內(nèi)存位置取出元素
- return __CFArrayGetBucketAtIndex(array, idx)->_item;
- }
- // 返回查詢?cè)氐牡刂?nbsp;
- CF_INLINE struct __CFArrayBucket *__CFArrayGetBucketAtIndex(CFArrayRef array, CFIndex idx) {
- switch (__CFArrayGetType(array)) {
- // 只允許兩種數(shù)組類型
- // 不可變對(duì)應(yīng)普通線性結(jié)構(gòu)，可變對(duì)應(yīng)雙端隊(duì)列
- case __kCFArrayImmutable:
- case __kCFArrayDeque:
- // 取地址再加上索引偏移量，返回元素地址
- return __CFArrayGetBucketsPtr(array) + idx;
- }
- return NULL;
- }
通過(guò)索引下標(biāo)查詢操作中，CFArray 仍然繼承了傳統(tǒng)數(shù)組的連續(xù)地址空間的性質(zhì)，所以其時(shí)間仍然可保持在 O(1) 復(fù)雜度，十分高效。
- void CFArrayInsertValueAtIndex(CFMutableArrayRef array, CFIndex idx, const void *value) {
- // 通過(guò)給定的 CFTypeID 來(lái)驗(yàn)證指定元素是否匹配 Core Foundation 橋接
- CF_OBJC_FUNCDISPATCHV(__kCFArrayTypeID, void, (NSMutableArray *)array, insertObject:(id)value atIndex:(NSUInteger)idx);
- // 通過(guò)給定的 CFTypeID 來(lái)驗(yàn)證 Core Foundation 類型合法性
- __CFGenericValidateType(array, __kCFArrayTypeID);
- CFAssert1(__CFArrayGetType(array) != __kCFArrayImmutable, __kCFLogAssertion, "%s(): array is immutable", __PRETTY_FUNCTION__);
- CFAssert2(0 idx && idx __CFArrayGetCount(array), __kCFLogAssertion, "%s(): index (%d) out of bounds", __PRETTY_FUNCTION__, idx);
- // 類型檢查
- CHECK_FOR_MUTATION(array);
- // 調(diào)用該函數(shù)進(jìn)行具體的數(shù)組變動(dòng)過(guò)程
- _CFArrayReplaceValues(array, CFRangeMake(idx, 0), &value, 1);
- }
- // 這個(gè)函數(shù)沒有經(jīng)過(guò) ObjC 的調(diào)度檢查，即 CF_OBJC_FUNCDISPATCHV 方法
- // 所以為安全考慮，只能用在已經(jīng)進(jìn)行調(diào)度檢查的函數(shù)入口之后
- void _CFArrayReplaceValues(CFMutableArrayRef array, CFRange range, const void **newValues, CFIndex newCount) {
- // 進(jìn)一步類型檢查
- CHECK_FOR_MUTATION(array);
- // 加鎖操作，增加自旋鎖防止競(jìng)爭(zhēng)
- BEGIN_MUTATION(array);
- // 聲明回調(diào)
- const CFArrayCallBacks *cb;
- // 偏移下標(biāo)，元素總數(shù)，數(shù)組改變后元素總數(shù)
- CFIndex idx, cnt, futureCnt;
- const void **newv, *buffer[256];
- // 獲取數(shù)組中元素個(gè)數(shù)
- cnt = __CFArrayGetCount(array);
- // 新數(shù)組元素總數(shù) = 原數(shù)組元素總數(shù) - 刪除的元素個(gè)數(shù) + 增加的元素個(gè)數(shù)
- futureCnt = cnt - range.length + newCount;
- CFAssert1(newCount futureCnt, __kCFLogAssertion, "%s(): internal error 1", __PRETTY_FUNCTION__);
- // 獲取數(shù)組中定義的回調(diào)方法
- cb = __CFArrayGetCallBacks(array);
- // 構(gòu)造分配釋放內(nèi)存抽象
- CFAllocatorRef allocator = __CFGetAllocator(array);
- // 需要的情況下持有新元素，并為其分配一個(gè)臨時(shí)緩沖區(qū)
- // 標(biāo)準(zhǔn)是新元素的個(gè)數(shù)是否超過(guò)256
- if (NULL != cb->retain && !hasBeenFinalized(array)) {
- newv = (newCount 256) ? (const void **)buffer : (const void **)CFAllocatorAllocate(kCFAllocatorSystemDefault, newCount * sizeof(void *), 0);
- if (newv != buffer && __CFOASafe) __CFSetLastAllocationEventName(newv, "CFArray (temp)");
- // 為新元素增加數(shù)據(jù)緩沖區(qū)
- for (idx = 0; idx newCount; idx++) {
- newv[idx] = (void *)INVOKE_CALLBACK2(cb->retain, allocator, (void *)newValues[idx]);
- }
- } else {
- newv = newValues;
- }
- // 數(shù)據(jù)抖動(dòng)量自加
- array->_mutations++;
- // 現(xiàn)在將一個(gè)數(shù)組的存儲(chǔ)區(qū)域分成了三個(gè)部分，每個(gè)部分都有可能為空
- // A: 從索引下標(biāo)零的位置到小于 range.location 的區(qū)域
- // B: 傳入的 range.location 區(qū)域
- // C: 從 range.location + range.length 到數(shù)組末尾
- // 需要注意的是，索引0的位置不一定位于可用存儲(chǔ)的***位，當(dāng)變化位置新值數(shù)量與舊值數(shù)量不同時(shí)，B區(qū)域需要先釋放再替換，然后A和C中的值根據(jù)情況進(jìn)行位移
- if (0 range.length) {
- // 正常釋放變化區(qū)域操作
- __CFArrayReleaseValues(array, range, false);
- }
- // B 區(qū)現(xiàn)在為清空狀態(tài)，需要重新填充數(shù)據(jù)
- if (0) {
- // 此處隱藏了判斷條件和代碼。
- // 大概操作是排除其他的干擾項(xiàng)，例如 B 區(qū)數(shù)據(jù)未完全釋放等。
- } else if (NULL == array->_store) {
- // 通過(guò)數(shù)據(jù)的首地址引用指針來(lái)判斷 B 區(qū)釋放
- if (0) {
- // 此處隱藏了判斷條件和代碼
- // 排除干擾條件，例如 futureCnt 不合法等
- } else if (0 futureCnt) {
- // 聲明一個(gè)雙端隊(duì)列對(duì)象
- struct __CFArrayDeque *deque;
- // 根據(jù)元素總數(shù)確定環(huán)狀緩沖區(qū)域可載元素總個(gè)數(shù)
- CFIndex capacity = __CFArrayDequeRoundUpCapacity(futureCnt);
- // 根據(jù)元素個(gè)數(shù)確定空間分配大小
- CFIndex size = sizeof(struct __CFArrayDeque) + capacity * sizeof(struct __CFArrayBucket);
- // 通過(guò)緩沖區(qū)構(gòu)造器來(lái)構(gòu)造存儲(chǔ)緩存
- deque = (struct __CFArrayDeque *)CFAllocatorAllocate((allocator), size, isStrongMemory(array) ? __kCFAllocatorGCScannedMemory : 0);
- if (__CFOASafe) __CFSetLastAllocationEventName(deque, "CFArray (store-deque)");
- // 確定雙端隊(duì)列左值
- deque->_leftIdx = (capacity - newCount) / 2;
- deque->_capacity = capacity;
- __CFAssignWithWriteBarrier((void **)&array->_store, (void *)deque);
- // 完成 B 區(qū)構(gòu)造，安全釋放數(shù)組
- if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) auto_zone_release(objc_collectableZone(), deque);
- }
- } else { // Deque
- // 根據(jù) B 區(qū)元素變化，重新定位 A 和 C 區(qū)元素存儲(chǔ)狀態(tài)
- if (0) {
- } else if (range.length != newCount) {
- // 傳入 array 引用，最終根據(jù)變化使得數(shù)組更新A、B、C分區(qū)規(guī)則
- __CFArrayRepositionDequeRegions(array, range, newCount);
- }
- }
- // 將區(qū)域B的新變化拷貝到B區(qū)域
- if (0 newCount) {
- if (0) {
- } else { // Deque
- // 訪問(wèn)線性存儲(chǔ)區(qū)
- struct __CFArrayDeque *deque = (struct __CFArrayDeque *)array->_store;
- // 在原基礎(chǔ)上，增加一段緩存區(qū)域
- struct __CFArrayBucket *raw_buckets = (struct __CFArrayBucket *)((uint8_t *)deque + sizeof(struct __CFArrayDeque));
- // 更改B區(qū)域數(shù)據(jù)，類似與 memcpy，但是有寫屏障(write barrier)，線程安全
- objc_memmove_collectable(raw_buckets + deque->_leftIdx + range.location, newv, newCount * sizeof(struct __CFArrayBucket));
- }
- }
- // 設(shè)置新的元素個(gè)數(shù)屬性
- __CFArraySetCount(array, futureCnt);
- // 釋放緩存區(qū)域
- if (newv != buffer && newv != newValues) CFAllocatorDeallocate(kCFAllocatorSystemDefault, newv);
- // 解除線程安全保護(hù)
- END_MUTATION(array);
- }
在 CFArray 的插入元素操作中，可以很清楚的看出這是一個(gè)雙端隊(duì)列(dequeue)的插入元素操作，而且是一種仿照 C++ STL 標(biāo)準(zhǔn)庫(kù)的存儲(chǔ)方式，緩沖區(qū)嵌套 map 表的靜態(tài)實(shí)現(xiàn)。用示意圖來(lái)說(shuō)明一下數(shù)據(jù)結(jié)構(gòu)：
在 STL 中的 deque，是使用的 map 表來(lái)記錄的映射關(guān)系，而在 Core Foundation 中，CFArray 在保證這樣的二次映射關(guān)系的時(shí)候很直接地運(yùn)用了二階指針 _store。在修改元素的操作中，CFArray 也略顯得暴力一些，先對(duì)數(shù)組進(jìn)行大塊的分區(qū)操作，再按照順序填充數(shù)據(jù)，組合成為一塊新的雙端隊(duì)列，例如在上圖中的雙端隊(duì)列中，在下標(biāo)為 7 的元素之前增加一個(gè)值為 100 的元素：
根據(jù)索引下標(biāo)會(huì)找到指定部分的緩存區(qū)，將其拿出并進(jìn)行重新構(gòu)造。構(gòu)造過(guò)程中或?qū)⑵鋭澐殖?A、B、C 三個(gè)區(qū)域，B 區(qū)域是修改部分。當(dāng)然如果不夠的話，系統(tǒng)會(huì)自己進(jìn)行緩存區(qū)的擴(kuò)容，即 CFAllocatorRef 官方提供的內(nèi)存分配/釋放策略。
CFAllocatorRef 是 Core Foundation 中的分配和釋放內(nèi)存的策略。多數(shù)情況下，只需要用默認(rèn)分配器 kCFAllocatorDefault ，等價(jià)于傳入 NULL 參數(shù)，這用會(huì)用 Core Foundation 所謂的“常規(guī)方法”來(lái)分配和釋放內(nèi)存。這種方法可能會(huì)有變化，我們不應(yīng)該以來(lái)與任何特殊行為。用到特殊分配器的情況很少，下來(lái)是官方文檔中給出的標(biāo)準(zhǔn)分配器及其功能。
| KCFALLOCATORDEFAULT | 默認(rèn)分配器，與傳入NULL等價(jià)。 |
|---|---|
| kCFAllocatorSystemDefault | 原始的默認(rèn)系統(tǒng)分配器。這個(gè)分配器用來(lái)應(yīng)對(duì)萬(wàn)一用CFAllocatorSetDefault改變了默認(rèn)分配器的情況，很少用到。 |
| kCFAllocatorMalloc | 調(diào)用malloc、realloc和free。如果用malloc創(chuàng)建了內(nèi)存，那這個(gè)分配器對(duì)于釋放CFData和CFString就很有用。 |
| kCFAllocatorMallocZone | 在默認(rèn)的malloc區(qū)域中創(chuàng)建和釋放內(nèi)存。在 Mac 上開啟了垃圾收集的話，這個(gè)分配器會(huì)很有用，但在 iOS 中基本上沒什么用。 |
| kCFAllocatorNull | 什么都不做。跟kCFAllocatorMalloc一樣，如果不想釋放內(nèi)存，這個(gè)分配器對(duì)于釋放CFData和CFString就很有用。 |
| KCFAllocatorUseContext | 只有CFAllocatorCreate函數(shù)用到。創(chuàng)建CFAllocator時(shí)，系統(tǒng)需要分配內(nèi)存。就像其他所有的Create方法，也需要一個(gè)分配器。這個(gè)特殊的分配器告訴CFAllocatorCreate用傳入的函數(shù)來(lái)分配CFAllocator。 |
在 _CFArrayReplaceValues 方法中的***一個(gè)判斷：
- if (newv != buffer && newv != newValues)
- CFAllocatorDeallocate(kCFAllocatorSystemDefault, newv);
會(huì)檢查一下緩存區(qū)的數(shù)量問(wèn)題，如果數(shù)量過(guò)多會(huì)釋放掉多余的緩存區(qū)。這是因?yàn)檫@個(gè)方法具有通用性，不僅僅可以使用在插入元素操作，在增加(CFArrayAppendValue)、替換(CFArrayReplaceValues)、刪除(CFArrayRemoveValueAtIndex)操作均可使用。由于將數(shù)據(jù)結(jié)構(gòu)采取分塊管理，所以時(shí)間分?jǐn)?，?fù)雜度大幅度降低。所以，我們看到 CFArray 的時(shí)間復(fù)雜度在查詢、增添元素操作中均有較高的水平。
而在 NSMutableArray 的實(shí)現(xiàn)中，蘋果為了解決移動(dòng)端的小內(nèi)存特點(diǎn)，使用 CFArray 中在兩端增加可擴(kuò)充的緩存區(qū)則會(huì)造成大量的浪費(fèi)。在 NSMutableArray原理揭露 一文中使用逆向的思路，挖掘 NSMutableArray 的實(shí)現(xiàn)原理，其做法是使用環(huán)形緩沖區(qū)對(duì)緩存部分做到***化的壓縮，這是蘋果針對(duì)于移動(dòng)設(shè)備的局限而提出的方案。
參考資料：
- Let’s Build NSMutableArray
http://t.cn/Rxs9e2g
- GNUStep · NSArray
http://t.cn/RxsCzbj
- What is the data structure behind NSMutableArray?
http://t.cn/RxsCvcG
- Apple Source Code – CF-855.17
http://t.cn/RxsCho3
