Objective-C 數組遍歷的性能及原理
數組的遍歷，這個話題貌似沒什么好探究的，該怎么遍歷就怎么遍歷唄！但是如果要回答這些問題:
OC數組有哪幾種遍歷方式?
哪種方式效率最高?為什么?
各種遍歷方式的內部實現是怎么樣的?
NS(Mutable)Array的內部結構是怎么樣的?
我覺得還是需要探究一下.
一.OC數組的類體系
當我們創建一個NSArray對象時，實際上得到的是NSArray的子類 __NSArrayI 對象.同樣的,我們創建 NSMutableArray 對象，得到的同樣是其子類 __NSArrayM 對象.有趣的是,當我們創建只有一個對象的 NSArray 時，得到的是 __NSSingleObjectArrayI 類對象.
__NSArrayI 和 __NSArrayM , __NSSingleObjectArrayI 為框架隱藏的類.
OC數組的類體系如下:
通過NSArray和NSMutableArray接口，返回的卻是子類對象，怎么做到的?
先介紹另一個私有類: __NSPlaceholderArray ,和兩個此類的全局變量 ___immutablePlaceholderArray , ___mutablePlaceholderArray 。 __NSPlaceholderArray 從類命名上看，它只是用來占位的，具體怎么占位法稍后討論,有個重要特點是， __NSPlaceholderArray 實現了和 NSArray , NSMutableArray 一摸一樣的初始化方法,如 initWithObjects:count: , initWithCapacity: 等.
介紹完 __NSPlaceholderArray 后，這個機制可以總結為以下兩個大步驟:
(1).NSArray重寫了 + (id)allocWithZone:(struct _NSZone *)zone 方法,在方法內部,如果調用類為 NSArray 則直接返回全局變量 ___immutablePlaceholderArray ，如果調用類為 NSMUtableArray 則直接返回全局變量 ___mutablePlaceholderArray 。
也就是調用 [NSArray alloc] 或者 [NSMUtableArray alloc] 得到的僅僅是兩個占位指針，類型為 __NSPlaceholderArray .
（2).在調用了 alloc 的基礎上，不論是 NSArray 或 NSMutableArray 都必定要繼續調用某個 initXXX 方法,而實際上調用的是 __NSPlaceholderArray 的 initXXX .在這個 initXXX 方法內部,如果 self == ___immutablePlaceholderArray 就會重新構造并返回 __NSArrayI 對象,如果 self == ___mutablePlaceholderArray 就會重新構造并返回 _NSArrayM 對象.
總結來說，對于 NSArray 和 NSMutableArray ， alloc 時拿到的僅僅是個占位對象， init 后才得到真實的子類對象.
接下來清點一下幾種遍歷方式:
二.OC數組遍歷的幾種方式
1.for 循環
for (NSUInteger i = 0; i < array.count; ++i) {
object = array[i];
}
array[i] 會被編譯器轉化為對 - (ObjectType)objectAtIndexedSubscript:(NSUInteger)index 的調用，此方法內部調用的就是 - (ObjectType)objectAtIndex:(NSUInteger)index 方法.
2.for in
for (id obj in array) {
xxx
}
文章稍后會討論到for in的內部實現
3.enumerateObjectsUsingBlock
通過block回調順序遍歷:
[array enumerateObjectsUsingBlock:^(id _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
xxx
}];
4.enumerateObjectsWithOptions:usingBlock:
通過block回調，在子線程中遍歷，對象的回調次序是亂序的,而且調用線程會等待該遍歷過程完成:
[array enumerateObjectsWithOptions:NSEnumerationConcurrent usingBlock:^(id _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
xxx
}];
通過block回調，在主線程中逆序遍歷:
[array enumerateObjectsWithOptions:NSEnumerationReverse usingBlock:^(id _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
xxx
}];
5.objectEnumerator/reverseObjectEnumerator
通過Enumerator順序遍歷:
NSEnumerator *enumerator = array.objectEnumerator;
while((object = enumerator.nextObject)) {
xxx
}
通過ReverseEnumerator逆序遍歷:
NSEnumerator *enumerator = array.reverseObjectEnumerator;
while((object = enumerator.nextObject)) {
xxx
}
6.enumerateObjectsAtIndexes:options:usingBlock:
通過block回調，在子線程中對指定IndexSet遍歷，對象的回調次序是亂序的,而且調用線程會等待該遍歷過程完成:
[array enumerateObjectsAtIndexes:[NSIndexSet xxx] options:NSEnumerationConcurrent usingBlock:^(id _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
xxx
}];
通過block回調，在主線程中對指定IndexSet逆序遍歷：
[array enumerateObjectsAtIndexes:[NSIndexSet xxx] options:NSEnumerationReverse usingBlock:^(id _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
xxx
}];
三.性能比較
以100為步長,構造對象數目在0-100萬之間的 NSArray , 分別用上述的遍歷方式進行遍歷并計時(單位us)，而且在每一次遍歷中，僅僅只是得到對象，沒有其他任何輸入輸出，計算之類的干擾操作。每種遍歷方式采集得1萬組數據,得到如下的性能對比結果:
橫軸為遍歷的對象數目,縱軸為耗時,單位us.
從圖中看出，在對象數目很小的時候，各種方式的性能差別微乎其微。隨著對象數目的增大， 性能差異才體現出來.
其中 for in 的耗時一直都是最低的，當對象數高達100萬的時候， for in 耗時也沒有超過5ms.
其次是for循環耗時較低.
反而，直覺上應該非常快速的多線程遍歷方式:
[array enumerateObjectsWithOptions:NSEnumerationConcurrent usingBlock:^(id _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
xxx
}];
卻是性能最差的。
enumerateObjectsUsingBlock : 和 reverseObjectEnumerator 的遍歷性能非常相近.
為什么會有這樣的結果，文章稍后會從各種遍歷的內部實現來分析原因。
四.OC數組的內部結構
NSArray 和 NSMutableArray 都沒有定義實例變量，只是定義和實現了接口,且對內部數據操作的接口都是在各個子類中實現的.所以真正需要了解的是子類結構,了解了 __NSArrayI 就相當于了解 NSArray ,了解了 __NSArrayM 就相當于了解 NSMutableArray .
1. __NSArrayI
__NSArrayI的結構定義為:
@interface __NSArrayI : NSArray
{
NSUInteger _used;
id _list[0];
}
@end
_used 是數組的元素個數,調用 [array count] 時，返回的就是 _used 的值。
id _list[0] 是數組內部實際存儲對象的數組,但為何定義為0長度呢？這里有一篇關于0長度數組的文章: http://blog.csdn.net/zhaqiwen/article/details/7904515
這里我們可以把 id _list[0] 當作 id *_list 來用，即一個存儲 id 對象的 buff .
由于 __NSArrayI 的不可變,所以 _list 一旦分配，釋放之前都不會再有移動刪除操作了，只有獲取對象一種操作.因此 __NSArrayI 的實現并不復雜.
2. __NSSingleObjectArrayI
__NSSingleObjectArrayI的結構定義為:
@interface __NSSingleObjectArrayI : NSArray
{
id object;
}
@end
因為只有在"創建只包含一個對象的不可變數組"時,才會得到 __NSSingleObjectArrayI 對象，所以其內部結構更加簡單，一個 object 足矣.
3. __NSArrayM
__NSArrayM的結構定義為:
@interface __NSArrayM : NSMutableArray
{
NSUInteger _used;
NSUInteger _offset;
int _size:28;
int _unused:4;
uint32_t _mutations;
id *_list;
}
@end
__NSArrayM 稍微復雜一些，但是同樣的，它的內部對象數組也是一塊連續內存 id* _list ，正如 __NSArrayI 的 id _list[0] 一樣
_used :當前對象數目
_offset :實際對象數組的起始偏移,這個字段的用處稍后會討論
_size :已分配的 _list 大小(能存儲的對象個數，不是字節數)
_mutations ：修改標記，每次對 __NSArrayM 的修改操作都會使 _mutations 加1,“ *** Collection <__NSArrayM: 0x1002076b0> was mutated while being enumerated. ”這個異常就是通過對 _mutations 的識別來引發的
id *_list 是個循環數組.并且在增刪操作時會動態地重新分配以符合當前的存儲需求.以一個初始包含5個對象,總大小 _size 為6的 _list 為例:
_offset = 0 , _used = 5 , _size=6
在末端追加3個對象后:
_offset = 0 , _used = 8 , _size=8
_list 已重新分配
刪除對象A:
_offset = 1 , _used = 7 , _size=8
刪除對象E:
_offset = 2 , _used = 6 , _size=8
B,C往后移動了，E的空缺被填補
在末端追加兩個對象:
_offset = 2 , _used = 8 , _size=8
_list 足夠存儲新加入的兩個對象，因此沒有重新分配，而是將兩個新對象存儲到了 _list 起始端
因此可見, __NSArrayM 的 _list 是個循環數組,它的起始由 _offset 標識.
五.各種遍歷的內部實現
1.快速枚舉
前面并沒有說過快速枚舉這個詞，怎么這里突然蹦出來了，實際上for in就是基于快速枚舉實現的，但是先不討論for in,先認識一個協議: NSFastEnumeration ，它的定義在 Foundation 框架的 NSFastEnumeration .h 頭文件中:
@protocol NSFastEnumeration
- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id __unsafe_unretained _Nullable [_Nonnull])buffer count:(NSUInteger)len;
@end
NSFastEnumerationState 定義:
typedef struct {
unsigned long state;
id __unsafe_unretained _Nullable * _Nullable itemsPtr;
unsigned long * _Nullable mutationsPtr;
unsigned long extra[5];
} NSFastEnumerationState;
看了這些定義和蘋果文檔，我也不知道究竟怎么用這個方法，它怎么就叫快速枚舉了呢,除非知道它的實現細節，否則用的時候疑惑太多了.因此我們就先不管怎么用，而是來看看它的實現細節.
__NSArrayI , __NSArrayM , __NSSingleObjectArrayI 都實現了 NSFastEnumeration 協議.
(1) __NSArrayI的實現:
根據匯編反寫可以得到:
- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id __unsafe_unretained _Nullable [_Nonnull])buffer count:(NSUInteger)len {
if (!buffer && len > 0) {
CFStringRef errorString = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("*** %s: pointer to objects array is NULL but length is %lu"), "-[__NSArrayI countByEnumeratingWithState:objects:count:]",(unsigned long)len);
CFAutorelease(errorString);
[[NSException exceptionWithName:NSInvalidArgumentException reason:(__bridge NSString *)errorString userInfo:nil] raise];
}
if (len >= 0x40000000) {
CFStringRef errorString = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("*** %s: count (%lu) of objects array is ridiculous"), "-[__NSArrayI countByEnumeratingWithState:objects:count:]",(unsigned long)len);
CFAutorelease(errorString);
[[NSException exceptionWithName:NSInvalidArgumentException reason:(__bridge NSString *)errorString userInfo:nil] raise];
}
static const unsigned long mu = 0x01000000;
if (state->state == 0) {
state->mutationsPtr = μ
state->state = ~0;
state->itemsPtr = _list;
return _used;
}
return 0;
}
可見在 __NSArrayI 對這個方法的實現中,主要做的事就是把 __NSArrayI 的內部數組 _list 賦給 state->itemsPtr ,并返回 _used 即數組大小. state->mutationsPtr 指向一個局部靜態變量, state->state 看起來是一個標志，如果再次用同一個 state 調用這個方法就直接返回0了.
至于傳入的 buffer , len 僅僅只是用來判斷了一下參數合理性。
看來有點明白快速枚舉的意思了，這一下就把全部對象獲取到了，而且在一個c數組里，之后要獲得哪個位置的對象都可以快速尋址到,調用方通過 state->itemsPtr 來訪問這個數組,通過返回值來確定數組里對象數目.
例如遍歷一個 NSArray 可以這樣:
NSFastEnumerationState state = {0};
NSArray *array = @[@1,@2,@3];
id buffer[2];
//buffer 實際上內部沒有用上，但還是得傳， 2表示我期望得到2個對象，實際上返回的是全部對象數3
NSUInteger n = [array countByEnumeratingWithState:&state objects:buffer count:2];
for (NSUInteger i=0; i<n; ++i) {
NSLog(@"%@", (__bridge NSNumber *)state.itemsPtr[i]);
}
看來之所以叫快速遍歷，是因為這種方式直接從c數組里取對象，不用調用別的方法，所以快速.
__NSSingleObjectArrayI 的實現也猜得出了，在此就不貼代碼了.我們來看看 __NSArrayM 是怎么實現這個協議的.
(2) __NSArrayM的實現:
- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id __unsafe_unretained _Nullable [_Nonnull])buffer count:(NSUInteger)len {
if (!buffer && len > 0) {
CFStringRef errorString = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("*** %s: pointer to objects array is NULL but length is %lu"), "-[__NSArrayI countByEnumeratingWithState:objects:count:]",(unsigned long)len);
CFAutorelease(errorString);
[[NSException exceptionWithName:NSInvalidArgumentException reason:(__bridge NSString *)errorString userInfo:nil] raise];
}
if (len >= 0x40000000) {
CFStringRef errorString = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("*** %s: count (%lu) of objects array is ridiculous"), "-[__NSArrayI countByEnumeratingWithState:objects:count:]",(unsigned long)len);
CFAutorelease(errorString);
[[NSException exceptionWithName:NSInvalidArgumentException reason:(__bridge NSString *)errorString userInfo:nil] raise];
}
if (state->state != ~0) {
if (state->state == 0) {
state->mutationsPtr = &_mutations;
//找到_list中元素起始的位置
state->itemsPtr = _list + _offset;
if (_offset + _used <= _size) {
//必定沒有剩余元素
//標示遍歷完成
state->state = ~0;
return _used;
}
else {
//有剩余元素（_list是個循環數組，剩余元素在_list從起始位置開始存儲）
//state->state存放剩余元素數目
state->state = _offset + _used - _size;
//返回本次得到的元素數目 (總數 - 剩余)
return _used - state->state;
}
}
else {
//得到剩余元素指針
state->itemsPtr = _list;
unsigned long left = state->state;
//標示遍歷完成了
state->state = ~0;
return left;
}
}
return 0;
}
從實現看出，對于 __NSArrayM ，用快速枚舉的方式最多只要兩次就可以獲取全部元素. 如果 _list 還沒有構成循環，那么第一次就獲得了全部元素，跟 __NSArrayI 一樣。但是如果 _list 構成了循環，那么就需要兩次，第一次獲取 _offset 到 _list 末端的元素,第二次獲取存放在 _list 起始處的剩余元素.
2.for in的實現
如前面性能比較一節提到的，for in的性能是最好的，可以猜測for in基于應該就是剛剛討論的快速枚舉。
如下代碼:
NSArray *arr = @[@1,@2,@3];
for (id obj in arr) {
NSLog(@"obj = %@",obj);
}
通過 clang -rewrite-objc main.m 命令看看編譯器把for in變成了什么:
//NSArray *arr = @[@1,@2,@3];
NSArray *arr = ((NSArray *(*)(Class, SEL, const ObjectType *, NSUInteger))(void *)objc_msgSend)(objc_getClass("NSArray"), sel_registerName("arrayWithObjects:count:"), (const id *)__NSContainer_literal(3U, ((NSNumber *(*)(Class, SEL, int))(void *)objc_msgSend)(objc_getClass("NSNumber"), sel_registerName("numberWithInt:"), 1), ((NSNumber *(*)(Class, SEL, int))(void *)objc_msgSend)(objc_getClass("NSNumber"), sel_registerName("numberWithInt:"), 2), ((NSNumber *(*)(Class, SEL, int))(void *)objc_msgSend)(objc_getClass("NSNumber"), sel_registerName("numberWithInt:"), 3)).arr, 3U);
{
//for (id obj in arr) obj的定義
id obj;
//NSFastEnumerationState
struct __objcFastEnumerationState enumState = { 0 };
//buffer
id __rw_items[16];
id l_collection = (id) arr;
//第一次遍歷,調用countByEnumeratingWithState:objects:count:快速枚舉方法
_WIN_NSUInteger limit =
((_WIN_NSUInteger (*) (id, SEL, struct __objcFastEnumerationState *, id *, _WIN_NSUInteger))(void *)objc_msgSend)
((id)l_collection,
sel_registerName("countByEnumeratingWithState:objects:count:"),
&enumState, (id *)__rw_items, (_WIN_NSUInteger)16);
if (limit) {
//保存初次得到的enumState.mutationsPtr的值
unsigned long startMutations = *enumState.mutationsPtr;
do {
unsigned long counter = 0;
do {
//在獲取enumState.itemsPtr中每個元素前，都檢查一遍enumState.mutationsPtr所指標志是否改變，改變則拋出異常
//對__NSArrayI，enumState.mutationsPtr指向一個靜態局部變量，永遠也不會拋異常
//對__NSArrayM，enumState.mutationsPtr指向_mutations變量, 每次增刪操作后,_mutations會+1
if (startMutations != *enumState.mutationsPtr)
objc_enumerationMutation(l_collection);
//獲取每一個obj
obj = (id)enumState.itemsPtr[counter++]; {
//NSLog(@"obj = %@",obj);
NSLog((NSString *)&__NSConstantStringImpl__var_folders_rg_wm9xjmyn1kz01_pph_34xcqc0000gn_T_main_c95c5d_mi_8,obj);
};
__continue_label_2: ;
} while (counter < limit);
//再一次遍歷,獲取剩余元素
} while ((limit = ((_WIN_NSUInteger (*) (id, SEL, struct __objcFastEnumerationState *, id *, _WIN_NSUInteger))(void *)objc_msgSend)
((id)l_collection,
sel_registerName("countByEnumeratingWithState:objects:count:"),
&enumState, (id *)__rw_items, (_WIN_NSUInteger)16)));
//遍歷完成
obj = ((id)0);
__break_label_2: ;
}
//沒有元素，空數組
else
obj = ((id)0);
}
可見，for in就是基于快速枚舉實現的，編譯器將for in轉化為兩層循環，外層調用快速枚舉方法批量獲取元素，內層通過c數組取得一批元素中的每一個，并且在每次獲取元素前，檢查是否對數組對象進行了變更操作，如果是，則拋出異常.
3.enumerateObjectsUsingBlock:
該方法在 NSArray 中實現，所有子類對象調用的都是這個實現
- (void)enumerateObjectsUsingBlock:(void ( ^)(id obj, NSUInteger idx, BOOL *stop))block {
if (!block) {
CFStringRef errorString = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("*** %s: block cannot be nil"), "-[NSArray enumerateObjectsUsingBlock:]");
CFAutorelease(errorString);
[[NSException exceptionWithName:NSInvalidArgumentException reason:(__bridge NSString *)errorString userInfo:nil] raise];
}
[self enumerateObjectsWithOptions:0 usingBlock:block];
}
內部直接以 option = 0 調用了 enumerateObjectsWithOptions: usingBlock:
4. enumerateObjectsWithOptions: usingBlock:
(1) __NSArrayI 的實現
- (void)enumerateObjectsWithOptions:(NSEnumerationOptions)opts usingBlock:(void (^)(id _Nonnull, NSUInteger, BOOL * _Nonnull))block {
if (!block) {
CFStringRef errorString = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("*** %s: block cannot be nil"), "-[__NSArrayI enumerateObjectsWithOptions:usingBlock:]");
CFAutorelease(errorString);
[[NSException exceptionWithName:NSInvalidArgumentException reason:(__bridge NSString *)errorString userInfo:nil] raise];
}
__block BOOL stoped = NO;
void (^enumBlock)(NSUInteger idx) = ^(NSUInteger idx) {
if(!stoped) {
@autoreleasepool {
block(_list[idx],idx,&stoped);
}
}
};
if (opts == NSEnumerationConcurrent) {
dispatch_apply(_used, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), enumBlock);
}
else if(opts == NSEnumerationReverse) {
for (NSUInteger idx = _used - 1; idx != (NSUInteger)-1 && !stoped; idx--) {
enumBlock(idx);
}
}
//opts == 0
else {
if(_used > 0) {
for (NSUInteger idx = 0; idx != _used - 1 && !stoped; idx++) {
enumBlock(idx);
}
}
}
}
(1) __NSArrayM 的實現
__NSArrayM 的實現唯一不同的是 enumBlock
void (^enumBlock)(NSUInteger idx) = ^(NSUInteger idx) {
if(!stoped) {
@autoreleasepool {
NSUInteger idx_ok = _offset + idx;
//idx對應元素在_list起始處(循環部分)
if (idx_ok >= _size) {
idx_ok -= _size;
}
block(_list[idx_ok],idx,&stoped);
}
}
};
5.objectEnumerator/reverseObjectEnumerator
通過 array.objectEnumerator 得到的是一個 __NSFastEnumerationEnumerator 私有類對象,在這個 enumerator 對象上每次調用 - (id)nextObject 時，實際上內部每次都調用的是 array 的快速枚舉方法：
- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id __unsafe_unretained _Nullable [_Nonnull])buffer count:(NSUInteger)len
只不過每次只獲取并返回一個元素.
而通過 array.reverseObjectEnumerator 得到的是一個 __NSArrayReverseEnumerator 私有類對象,在這個 enumerator 對象上每次調用 - (id)nextObject 時，內部直接調用是: objectAtIndex: 來返回對象.
6.enumerateObjectsAtIndexes:options:usingBlock:
由于時間關系后面再貼了.
6.總結
到此，應該可以回答文章開頭提到的幾個問題了.
關于性能的差異：
for in 之所以快，是因為它基于快速枚舉，對 NSArray 只要一次快速枚舉調用就可以獲取到包含全部元素的c數組,對 NSMUtableArray 最多兩次就可以全部獲取。
for 之所以比 for in 稍慢，僅僅是因為它函數調用開銷的問題，相對于 for in 直接從c數組取每個元素的方式， for 靠的是每次調用 objectAtIndex: 。
而 NSEnumerationConcurrent+Block 的方式耗時最大，我認為是因為它采用了多線程，就這個方法來講，多線程的優勢并不在于遍歷有多快，而是在于它的回調在各個子線程，如果有 遍歷+分別耗時計算 的場景，這個方法應該是最適合的,只是此處只測遍歷速度，它光啟動分發管理線程就耗時不少，所以性能落后了.
希望通過此文能對你有幫助.
來自：http://www.jianshu.com/p/66f8410c6bbc