平时都在用 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_music_base/blob/master/yy_music_base/ym_array.c，里面有个纯C的、简单的引用计数对象的实现，有个 CFMutableArray 和 CFMutableDictionary 的模仿实现。所有 API 都和 CoreFoundation 类似。 还没有没仔细 test，但应该没什么大问题。

下面是我自己的实现和CFArray的一个性能对比：除去随机数的影响，插入性能应该是一致的。

 

 结论

好了，现在可以回头看看苹果给出的时间复杂度的描述了：

用开头那篇博客的话来说：Don’t second guess Apple, because Apple has already second guessed YOU.

 

PS: [NSMutableArray arrayWithCapacity:xxx]中的capacity没有任何作用。。仅仅是一个hint而已。。