NSMutableArray在快速枚举中如何实现高速？

Question

纵轴表示访问列表/数组中每个节点的平均时间（以ns为单位）（访问所有元素所需的总时间除以元素数量）。

横轴表示正在迭代的数组中的元素数量。

其中红色是NSMutableArray的实现，蓝色是我的链表(CHTape)。

在每个外部循环中，每个列表/数组都会添加一个空字符串@""。在内部循环中，检索每个列表/数组中的字符串，计时并记录。最后，输出时间以产生Wolfram语言输出以生成绘图。

NSMutableArray如何实现如此出色和一致的结果？如何才能达到类似的效果？

我的NSFastEnumeration实现：

- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id __unsafe_unretained [])stackBuffer count:(NSUInteger)len
{
    if (state->state == 0)
    {
        state->state = 1;
        state->mutationsPtr = &state->extra[1];
        state->extra[0] = (unsigned long)head;
    }

    CHTapeNode *cursor = (__bridge CHTapeNode *)((void *)state->extra[0]);

    NSUInteger i = 0;

    while ( cursor != nil && i < len )
    {
        stackBuffer[i] = cursor->payload;
        cursor = cursor->next;
        i++;
    }
    state->extra[0] = (unsigned long)cursor;

    state->itemsPtr = stackBuffer;

    return i;
}

完整的测试代码：

NSMutableArray *array = [NSMutableArray array];
CHTape *tape = [CHTape tape];

unsigned long long start;

unsigned long long tapeDur;
unsigned long long arrayDur;

NSMutableString * tapeResult = [NSMutableString stringWithString:@"{"];
NSMutableString * arrayResult = [NSMutableString stringWithString:@"{"];

NSString *string;

int iterations = 10000;

for (int i = 0; i <= iterations; i++)
{
    [tape appendObject:@""];
    [array addObject:@""];

    // CHTape
    start = mach_absolute_time();
    for (string in tape){}
    tapeDur = mach_absolute_time() - start;


    // NSArray
    start = mach_absolute_time();
    for (string in array){}
    arrayDur = mach_absolute_time() - start;


    // Results

    [tapeResult appendFormat:@"{%d, %lld}", i, (tapeDur/[tape count])];
    [arrayResult appendFormat:@"{%d, %lld}", i, (arrayDur/[array count])];

    if ( i != iterations)
    {
        [tapeResult appendString:@","];
        [arrayResult appendString:@","];
    }
}

[tapeResult appendString:@"}"];
[arrayResult appendString:@"}"];

NSString *plot = [NSString stringWithFormat:@"ListPlot[{%@, %@}]", tapeResult, arrayResult];
NSLog(@"%@", plot);

- Atlas

---

NSMutableArray 随着大小的增长改变其内部实现 - 很可能它只是针对你所使用的大小被实现为原始的C数组。 - Richard J. Ross III

它还针对迭代进行了高度优化，因为这是数组上最常用的操作之一。 - Richard J. Ross III

如果您愿意深入挖掘源代码，您可能也可以在开源CFArray实现中找到所有答案。 - Richard J. Ross III

请参见https://dev59.com/fHrZa4cB1Zd3GeqP3ogy：`countByEnumeratingWithState:...`实现不需要复制元素。 - Martin R

你的-countByEnumeratingWithState...方法是否启用了ARC？NSArray的实现已经关闭了ARC，因此它避免了不必要的retain/release调用。 - Greg Parker

Answer 1

强制关闭与链接列表相关的文件的ARC，效率大幅提高。它将访问时间从约70纳秒降低到约14纳秒。虽然这仍然比NSArray平均慢，但仅仅是平均慢两倍，而不是十倍。

虽然ARC可以使某些代码更快，但在迭代情况下会增加不必要的释放/保留调用。

感谢Greg Parker的评论发现了这一点。

- Atlas