coding with objc & swift

实现快速枚举

| Comments

上周我们讨论了”Objective-C遍历技术的对比“。本周,我们来完成剩下部分——如何在你的程序中实现快速枚举。

基础知识

快速枚举有两个优点。一是,实现快速枚举后,你可以直接使用for/in语法遍历你的对象。二是,如果将快速枚举实现得很好,会大大提高遍历的速度。

实现快速枚举,很简单。只需要实现NSFastEnumeration协议就可以了,而且这个协议只有一个方法:

1
2
3
- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state
                                  objects:(id *)stackbuf
		                          count:(NSUInteger)len;

怎么样?看上去很简单,对吧?等一下,NSFastEnumerationState是什么啊?

1
2
3
4
5
6
typedef struct {
        unsigned long state;
        id *itemsPtr;
        unsigned long *mutationsPtr;
        unsigned long extra[5];
    } NSFastEnumerationState;

呃,这似乎变得有点复杂了……

字段和参数的解释

实现这个方法前,让我们先来搞清楚这些参数、字段以及返回值的用途。

这个方法的目的是返回对象数组中的一部分对象。每次调用返回一组对象,这样使对象可以成批的被返回给调用者。为了获得最好的运行效率,这里使用了一个C数组,这样就需要两个参数——数组首地址指针和数组长度。

数组长度被作为返回值返回。这也是方法名字中”count”所代表的意思。数组的首地址指针由NSFastEnumerationState结构体中的itemsPtr字段指定。这两个值共同确定了这个方法返回给调用者的数组。

NSFastEnumeration被设计成允许返回一个指向内存的指针。然而,这并不适于所有数据结构,因此它也被设计成允许将内部对象拷贝到调用者提供的一个数组容器中。在这里,stackbuf即是指调用者提供的数组容器,len是数组容器的大小。

NSFastEnumeration还被设计成在遍历集合的时候,可以检测到集合的变动。如果检测到集合被修改了,就会抛出一个异常。mutationsPtr被用于指向会随着集合变动而变化的一个值。

好了,大部分字段和参数的意思都讲解完了。唯一没讲的就是state和extra这两个字段。这两个字段是预留给被调用者的,你可以自由的使用它们来存储任何你觉得有用的数据。

循环代码的结构

现在,我们知道了所有这些东西是用来干什么的,但是为了真正理解这些东西是如何工作的,最好是要了解一下编译器生成了哪些代码。比如,你写了这样的代码:

1
2
3
4
for(id obj in collection)
{
	// body
}

那么,在这背后到底发生了些什么呢?

编译器在堆栈上创建了一个NSFastEnumerationState变量,以及一个堆栈缓冲区。然后创建两个嵌套的循环,一个用于不停的调用countByEnumeratingWithState:…方法,另一个则用于遍历这个方法返回的数组。所以最后会生成类似下面这种代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//定义所有需要的局部状态变量
NSFastEnumerationState state = { 0 };
id stackbuf[16];
BOOL firstLoop = YES;
long mutationsPtrValue;

//外部循环
NSUInteger count;
while((count = [collection countByEnumeratingWithState: &state objects: stackbuf count: 16]))
{
    // 检查变量对象是否被修改过,但是只会在第一次循环后才检查
    // (请注意,我不太确定真实情况下编译器会把这个检查放在内部循环中还是放在外部循环中,
    // 并且不同版本的编译器实现的方式也可能不一样)
    if(!firstLoop && mutationsPtrValue != *state.mutationsPtr)
        @throw ..mutation exception...
    firstLoop = NO;
    mutationsPtrValue = *state.mutationsPtr;

    //内部循环,遍历NSFastEnumeration调用返回的数组
    id obj;
    for(NSUInteger index = 0; index < count; index++)
    {
        obj = state.itemsPtr[index];
        // body
    }
}

注意到了吗,这些代码并没有用到state和extra字段。正如我前面提到的,这些纯粹都是提供给被调用者用于组织返回数据的。

一次返回一个对象

NSFastEnumeration最主要的一个目的是想通过成批的遍历来提高遍历速度。一次只返回一个对象实际上有点背于这个理念。然而,这样也更容易实现,也可以让你能够使用for/in语法来变量你的对象。要避免”预优化(premature optimization)”的思想,如果一次返回一个对象更容易,那么就用这个方法。

例如,假如你有如下一个链表类:

1
2
3
4
@implementation LinkedList : NSObject
{
	struct Node *listHead;
}

现在我们来为这个类实现NSFastEnumeration协议,用简单的方式,以一次返回一个对象的方式来实现它。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id *)stackbuf count:(NSUInteger)len
{
    // 行动计划: 用extra[0]指向要遍历的下一个对象。
    // 由于extra[0]是一个long类型,所以这里会涉及到一些类型转换
    if(state->state == 0)
    {
        // state为0代表这是第一次调用,我们在第一调用时设置好各种初始状态
        // 由于这里我们不会试着检测集合的变化,所以直接将mutationsPtr指向一个确定不会变的地方
        state->mutationsPtr = (unsigned long *)self;

        // 设置extra[0]初始指向链表的头部
        state->extra[0] = (long)listHead;

        // 最后更新state,表明遍历已经开始了
        state->state = 1;
    }

    // 从extra[0]取出节点
    struct Node *currentNode = (struct Node *)state->extra[0];

    // 如果是NULL,则遍历完成,返回0以表示遍历结束
    if(!currentNode)
        return NULL

    // 否则, 将itemsPtr指向节点的值
    state->itemsPtr = &currentNode->value

    // 更新extra[0],指向下一个节点
    if(currentNode)
        state->extra[0] = (long)currentNode->next;

    // 一次只返回一个项目
    return 1;
}

还不错,除了一些指针和整型之间的类型转换。

成批的返回

让我们假设,最后事实证明上面那个方法真的太慢了,你想要让它更快一些。你可以试试成批的返回对象。由于链表中的对象不是连续存储的,要这样做,你就必须将要返回的对象拷贝到stackbuf中去。虽然stackbuf的大小不确定,但是我们可以认为它足够大到出来这样的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 - (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id *)stackbuf count:(NSUInteger)len
{
   // 行动机会: 几乎和前面一样,我们还是用extra[0]指向下一个要访问的节点,只是会一次遍历多个节点。
   if(state->state == 0)
   {
       state->mutationsPtr = (unsigned long *)self;
       state->extra[0] = (long)listHead;
       state->state = 1;
   }

   // 从extra[0]中取出节点
   struct Node *currentNode = (struct Node *)state->extra[0];

   // objCount用于记录我们遍历了多少个对象,以便稍后返回这个数目。
   NSUInteger objCount = 0;

   // 我将会把返回的对象放进stackbuf中,因此itemsPtr指向它
   state->itemsPtr = stackbuf;

   // 循环遍历节点,直到stackbuf被我们装满了或者没有任何节点可再遍历时结束遍历
   while(currentNode && objCount < len)
   {
       // 填充当前stackbuf位置,并将它指向下一个位置
       *stackbuf++ = currentNode->value

       // 移动到下一个节点
       currentNode = currentNode->next;

       // 记录节点数目
       objCount++;
   }

   // 更新extra[0],使其指向下一个节点
   if(currentNode)
       state->extra[0] = (long)currentNode->next;

   return objCount;
}

这并没有多难,并且它会显著地降低for/in循环中间的函数调用次数。

返回整块内存的指针

为了获得最好的性能,你可以返回一段对象连续存储的内存指针。翻译的有点拗口哈。举个例子,假如你有一个如下的简单的数组类:

1
2
3
4
5
@interface Array : NSObject
{
    id *pointer;
    NSUInteger count;
}

为这个类实现NSFastEnumeration协议相当地简单。只需要返回指向所有对象的内部指针就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id *)stackbuf count:(NSUInteger)len
{
    if(state->state == 0)
    {
        state->mutationsPtr = (unsigned long *)self;
        state->itemsPtr = pointer;
        state->state = 1;
        return count;
    }
    else
        return 0;
}

这个很简单吧!而且,它的速度也很快,因为最后遍历循环基本上就被转换成C中的for循环形式了。

NSFastEnumeration也可以被用在一些更复杂的数据结构上。如果你有一系列连续的指向对象块的指针(a series of contiguous object pointers),你可以依次的返回这些对象块的指针,这样可以加快对所有对象的遍历速度。 这种情况下,你可以充分的利用extra这个值来跟踪当前你在内部数据结构中的位置。

关于临时对象的一个注意事项

也许你已经发现了,用extra存储Objective-C对象很方便:

1
state->extra[1] = (long)[NSArray arrayWith...];

但是,要注意了!当使用下面这种完全合法的遍历代码时,就有问题了:

1
2
3
4
5
6
7
8
NSAutoreleasePool *pool = [NSAutoreleasePool new];
    for(id obj in collection)
    {
        // do stuff with obj
        [pool release];
        pool = [NSAutoreleasePool new];
    }
    [pool release];

当自动释放池被释放的时候,你返回的数组也会跟着被释放掉。然后当你下次再想访问它的时候,就会挂掉。并且你还不能retain你那个数组,因为不能保证调用者一定会遍历完然后让你有机会释放掉它。调用者可能在遍历过程中很早就跳出了,这种情况下你的对象就泄漏了。

真的没有常规的方法来解决这个问题。(我试过实现了一个完全疯狂的解决方案:追踪堆栈指针的位置以便知道什么时候可以安全的销毁这些临时对象。但是,怎么说呢?太疯狂了。)所以如果可能的话,尝试避免像这样使用extra来存储临时对象。如果不得不这样做,那么要当心在for/in循环中别对这些对象使用自动释放。通常情况下,可能你是你实现的NSFastEnumeration方法的唯一使用者,所以这看起来是个不值一提的自我约定,但是这确实是你必须要注意的一个问题。

结论

实现NSFastEnumeration协议让你可以使用简单优美的语法来遍历你自定义的集合类对象。而且,通常也能够获得更快的遍历速度。虽然初见之时NSFastEnumeration很令人畏惧,但实际上是相当容易实现它的,当然也取决于你的内部数据结构的复杂程度。

译自: Friday Q&A 2010-04-16: Implementing Fast Enumeration

Comments