ios - NSMutableArray 是如何在快速枚举中达到这么高的速度的

Question

y 轴表示列表/数组中每个节点的平均访问时间(以 ns 为单位)(访问所有元素的总时间除以元素数)。

x 轴表示数组中被迭代的元素数。

其中红色是 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);

Answer 1

通过在链接列表上强制关闭 ARC，相关文件的效率显着提高。它将访问时间从 ~70ns 减少到 ~14ns。虽然这仍然较慢，但平均而言，NSArray 仅平均慢两倍，而不是慢十倍。

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

通过 Greg Parker's 评论发现。