Mac OS X NSArray 枚舉性能研究
一天，我在思考 NSArray 枚舉方法 (也稱迭代方法): Mac OS X 10.6 和 iOS 4 帶來了以塊(block)組成的美麗新世界，enumerateObjectsUsingBlock: 方法隨之而來。我感覺這個方法要慢于快速枚舉 (for (object in array) { ... })，因為有總體開銷，但我并不能確定。因此我決定做一次性能測評。
都有哪些枚舉方法?
總體來說，我們有4種可以使用的枚舉方法 (參考 Mike Ash 的 周五常見問題 2010-04-09: Objective-C 的枚舉方法對比)。
1、objectAtIndex: enumeration 使用一個 for 循環(huán)，遞增循環(huán)變量，然后用 [myArray objectAtIndex:index] 來訪問元素。這是最基本的枚舉形式。
- NSUInteger count = [myArray count];
- for (NSUInteger index = 0; index < count ; index++) {
- [self doSomethingWith:[myArray objectAtIndex:index]];
- }
2、NSEnumerator 外部迭代(external iteration)的形式: [myArray objectEnumerator] 返回一個對象，這個對象有 nextObject 方法。我們可以循環(huán)調用這個方法，直到返回 nil 為止。
- NSEnumerator *enumerator = [myArray objectEnumerator];
- id object;
- while (object = [enumerator nextObject]) {
- [self doSomethingWith:object];
- }
3、NSFastEnumerator The idea behind 快速枚舉 的思想是利用 C 數(shù)組快速訪問 來優(yōu)化迭代。不僅它理論上比傳統(tǒng)的 NSEnumerator 更快，而且 Objective-C 2.0 提供了這種簡明的語法：
- id object;
- for (object in myArray) {
- [self doSomethingWith:object];
- }
4、Block enumeration（塊枚舉）引入 blocks 后出現(xiàn)的方法，它可以基于塊來迭代訪問一個數(shù)組。它的語法沒有快速枚舉那么簡潔，但它有一個有趣的特性: 并發(fā)枚舉。如果枚舉的順序并不重要，而且實施的處理可以并發(fā)進行，不用鎖，這種方法可以在多核系統(tǒng)上帶來相當明顯的效率提升。詳情參考 并發(fā)枚舉一節(jié)。
- [myArray enumerateObjectsUsingBlock:^(id object, NSUInteger index, BOOL *stop) {
- [self doSomethingWith:object];
- }];
- [myArray enumerateObjectsWithOptions:NSEnumerationConcurrent usingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
- [self doSomethingWith:object];
- }];
線性枚舉
首先，我們討論一下線性枚舉：一個項目接著前一個。
圖表
結論
有一點令人驚訝的是，NSEnumerator甚至比使用objectAtIndex:還慢。這對于Mac OS X 和IOS是一個事實。我猜想這是由于枚舉器在每次迭代時都去檢查數(shù)組是否被修改。自然地，快速枚舉保存了每個原始的名字，因此是最快的解決方案。
對于小的數(shù)組，block enumeration 比objectAtIndex:稍慢一點，但在有大量元素的數(shù)組里，它的性能變得與fast enumeration差不多快。
fast enumeration和NSEnumeration之間的區(qū)別在很多地方已經(jīng)非常明顯：對于iPhone 4S，前者花費約0.037秒而后者需要0.140秒。這已經(jīng)相差了3.7陪。
奇怪的一點
***在程序中分配 NSArray 和***用objectEnumerator 獲取 enumerator 都需要異常長的時間才能完成。例如，在我 2007 年的 17 寸 MacBook Pro 上分配含一個元素的數(shù)組，所需時間的中位數(shù)是 415 納秒。但***分配的時候會需要 500,000 納秒，有時甚至要到 1,000,000 納秒！獲取 enumerator 也是如此：盡管中位數(shù)只有 673 納秒，***獲取卻要花 500,000 納秒以上。
我只能猜測其中的原因，但我懷疑延遲加載是罪魁禍首。在實際應用中，你可能不會注意到這一點，因為等到執(zhí)行你的代碼時，Cocoa 或 Cocoa Touch 很可能已經(jīng)創(chuàng)建過數(shù)組了。
并發(fā)枚舉
如果情況允許，你可以選擇用塊枚舉來并發(fā)枚舉對象。這意味著計算的工作量可以分散到幾個 CPU 內核上。并不是每種枚舉過程中的處理都是可并發(fā)的，因此只有沒用到鎖的時候，才能使用并發(fā)枚舉：要么每一步操作確實是絕對相互獨立的，要么有原子性的操作可用 (如 OSAtomicAdd32 之類)。
那么，它相比其他枚舉類型有多大優(yōu)勢呢？
圖表
結論
元素不多時，并發(fā)枚舉是目前最慢的方法。主要原因可能是為了讓數(shù)組能并發(fā)訪問而做的準備工作和開啟線程（我不知道用的是 GCD 還是“傳統(tǒng)的”線程，這不重要；這是我們不需關心的實現(xiàn)細節(jié)）。
盡管如此，如果數(shù)組足夠大，并發(fā)枚舉突然就成了最快的方法了，正如我們所料。在 iPhone 4S 上枚舉 100 萬個元素，用并發(fā)枚舉需要 0.024 秒，但快速枚舉需要 0.036 秒。相形之下，還是同一個數(shù)組，NSEnumeration 要用 0.139 秒! 這已經(jīng)是非常大的差距了，足有 5.7 倍之多。
在我的辦公室，2011 iMac 24"采用了酷睿i7四核CPU，同時在0.0016秒之內列舉了百萬項。同一數(shù)組快速枚舉了0.0044秒和NSEnumeration o.oo93秒。那個因數(shù)是5.8，它非常接近于ipone 4S的結果。在這里，我期待一個更大的差異，雖然，在我的2007 MacBook采用了Core2 Duo雙核CPU，在這里因數(shù)剛好是3.7.當同時枚舉的閾值成為有用，在某處以我的測試是10，000和50,000分子之間。用更少的分子元素，去掉正常的塊迭代。
#p#
分配方式
我也想知道枚舉的性能會不會受數(shù)組創(chuàng)建方式的影響。我測試了兩個不同的方法：
-
首先創(chuàng)建一個 C 數(shù)組，里面引用了數(shù)組元素的對象實例，然后再用 initWithObjects:count: 創(chuàng)建NSArray。
-
直接創(chuàng)建 NSMutableArray 并依次用 addObject: 添加對象。
結果是迭代過程的沒有區(qū)別，但分配過程有所不同：initWithObjects:count: 快一些。數(shù)組元素很多時，差距更加顯著。這個例子創(chuàng)建了一個元素為 NSNumber 的數(shù)組：
- NSArray *generateArrayMalloc(NSUInteger numEntries) {
- id *entries;
- NSArray *result;
- entries = malloc(sizeof(id) * numEntries);
- for (NSUInteger i = 0; i < numEntries; i++) {
- entries[i] = [NSNumber numberWithUnsignedInt:i];
- }
- result = [NSArray arrayWithObjects:entries count:numEntries];
- free(entries);
- return result;
- }
我是如何來測量的？
你可以從 http://darkdust.net/files/arraytest.m 來下載這個測試應用 看看我是如何來測量的。基本上我就是測量重復迭代一個數(shù)組（什么處理也不做）1000次需要多長時間。在圖表中，取每個數(shù)組尺寸的平均值。這個應用的編譯選項是關閉優(yōu)化（-O0）。對于 iOS，我是在一個 iPhone 4S 上進行的測試。對 MAC OS X，我用我家里2007年產(chǎn)的 MacBook Pro 17”和我辦公室2011年產(chǎn)的 iMac 24”來測試。MAC OS X的圖表顯示的是iMac上的結果，在MacBook Pro上的圖表看起來與此相似，只是更慢一些。
英文原文：NSArray enumeration performance examined
原文鏈接：http://www.oschina.net/translate/nsarray-enumeration-performance
