實現 CFArray

平時都在用 NSArray，但最近搞一個純C的庫，不想有太多依賴，所以想把 NSArray 的功能提取出來。NSArray 和 CFArray 是 Toll-Free bridged的，而且 CFArray 是開源的。所以這裡研究了一下 CFArray 的實現，並且給出一個純C的、無其他依賴的替代實現。

蘋果的實現

在翻CF的源碼前，我在網上找到一篇很有意思的老文章：http://ridiculousfish.com/blog/posts/array.html (2005年)。這篇文章裡面，對 CFArray 和 STL Vector 做了一次性能對比，結果如下：

這篇文章寫於2005年，那時的 CFArray 實現的非常有意思：在 CFArray 容量超過300000左右時，消耗的時間完全變了。我很好奇的測試了一下現在系統的實現，已經跟那時的結果完全不一樣了。於是我翻了一下CF的歷史源碼，看到了 CFArray 這些年的變化。

1.最開始，CFArray 底層是用 deque(雙端隊列)實現的，在頭部尾部進行插入刪除性能很高，但是在 deque 中間插入刪除時，就需要 memmove 來挪動內存了，性能就會降下來。蘋果的方法是，當 CFArray 長度超過某個數值(具體來說是262040)時，將底層的 deque 換成 balanced tree。

具體來說，蘋果寫了一個名為 CFStorage 的類，用 balanced tree 實現了大數量的數值的存儲和編輯，並且在插入和刪除時有很好的性能。CFArray 在長度達到阈值(262040)時，就會在底層替換為CFStorage來完成操作。

2. 但是在2011年，CF-635.15中，蘋果把這個特性去掉了。具體的對比可以看下面兩個文件。
http://opensource.apple.com/source/CF/CF-550/CFArray.c
http://opensource.apple.com/source/CF/CF-635.15/CFArray.c 在這之後， CFArray 就只是用簡單的deque實現了，長度越大，位於中間的插入刪除耗時就越長。至於為什麼這麼改？我也不知道。。也許是怕切換數據結構造成的時間抖動？也許是這個 feature 根本沒有多少人用到？

3.最新的 CFArray 中，代碼應該又調整了。性能比單純的雙端隊列高，我猜測應該換成了一個環形緩沖區。但是蘋果還沒有開源最新的代碼。

 我的測試和實現

在我的系統(10.9.1)裡面，我參考最新的 CFArray 源碼實現了一個純 C 的 deque。隨後與系統CFArray做性能對比，發現在隨機插入的時候，系統的CFArray仍然有更高的性能。當我把deque換成circular後再進行對比，性能就完全一致了。所以，我猜測現在系統的 CFArray 底層又換成了circular，只是最新的代碼還沒有開源出來。

我的實現代碼放到了 https://github.com/ibireme/yy_array，裡面有個純C的、簡單的引用計數對象的實現，有個 CFMutableArray 和 CFMutableDictionary 的模仿實現。所有 API 都和 CoreFoundation 類似。 還沒有沒仔細 test，但應該沒什麼大問題。

下面是我自己的實現和CFArray的一個性能對比：除去隨機數的影響，插入性能應該是一致的。

 

 結論

好了，現在可以回頭看看蘋果給出的時間復雜度的描述了：

1 2 3 4 5 6 7 8 9 10 11 12 Computational Complexity The access time for a value in the array is guaranteed to be at worst O(lg N) for any implementation, current and future, but will often be O(1) (constant time). Linear search operations similarly have a worst case complexity of O(N*lg N), though typically the bounds will be tighter, and so on. Insertion or deletion operations will typically be linear in the number of values in the array, but may be O(N*lg N) clearly in the worst case in some implementations. There are no favored positions within the array for performance; that is, it is not necessarily faster to access values with low indices, or to insert or delete values with high indices, or whatever.

用開頭那篇博客的話來說：Don't second guess Apple, because Apple has already second guessed YOU.

 

PS: [NSMutableArray arrayWithCapacity:xxx]中的capacity沒有任何作用。。僅僅是一個hint而已。。

原文地址http://blog.ibireme.com/2014/02/17/cfarray/