老青菜

iOS NSMutableArray 底层实现

2020-12-10

在这之前,一直以为NSMutableArray底层实现和普通可变数组(c++ vector)一样,插入和删除都会涉及到元素移动,时间复杂度可能会达到O(n),效率并不高,直到看到这篇文章 NSMutableArray原理揭露 ,才发现自己理解是错误的。这里记录一下自己的分析过程。

普通可变数组

一般数组都是一段连续的线性内存空间,这样根据索引顺序操作非常方便,c++ vector。但是也有缺点,比如以下两种情况:

1.第n个位置插入
首先需要根据情况扩容,然后把n后面的元素往右移动(交换),最后再更新n上的元素。

2.删除第n个元素
首先清除第n个元素,然后把n后面的元素往左移动(交换)。

操作图如下,很显然,当数组内容非常多的时候,移动操作会很耗时,最坏情况下,时间复杂度是O(n)

NSMutableArray 源码

NSMutableArrayCoreFoundation框架提供的可变数组。苹果开源的 gnustep/libs-base 里包含了Foundation模块代码。找到NSArray.m文件,抽取部分关键代码。

@implementation NSMutableArray
+ (id) arrayWithObject: (id)anObject {
  NSMutableArray    *obj = [self allocWithZone: NSDefaultMallocZone()];
  obj = [obj initWithObjects: &anObject count: 1];
  return AUTORELEASE(obj);
}
- (void) addObject: (id)anObject {
  [self subclassResponsibility: _cmd];
}
- (void) replaceObjectAtIndex: (NSUInteger)index withObject: (id)anObject {
  [self subclassResponsibility: _cmd];
}
- (void) insertObject: anObject atIndex: (NSUInteger)index {
  [self subclassResponsibility: _cmd];
}
- (void) removeObjectAtIndex: (NSUInteger)index {
  [self subclassResponsibility: _cmd];
}

我们发现,insertObjectremoveObjectAtIndex最后都调用了subclassResponsibility。这个函数表示子类的责任,需要子类重写实现的,如果没有实现,NSObject+GNUstepBase.m有个默认实现,会抛出NSException异常。

- (id) subclassResponsibility: (SEL)aSel {
  char    c = (class_isMetaClass(object_getClass(self)) ? '+' : '-');
  [NSException raise: NSInvalidArgumentException
    format: @"[%@%c%@] should be overridden by subclass",
    NSStringFromClass([self class]), c,
    aSel ? (id)NSStringFromSelector(aSel) : (id)@"(null)"];
  while (1) ;   // Does not return
}

那么NSMutableArray子类到底是谁呢?子类是如何实现insertObjectremoveObjectAtIndex的呢?

__NSArrayM 底层结构

通过object_getClass(obj),我们可以得到NSArray的 isa 指针指向__NSArrayINSMutableArray的 isa 指针指向__NSArrayM。翻遍了苹果开放的源代码,没有找到__NSArrayM相关的代码,应该是私有的类吧。于是开始以下尝试:

ivars

首先想到的是通过class_copyIvarList打印出__NSArrayM的成员。

NSMutableArray *obj = [[NSMutableArray alloc] initWithObjects:@"1", nil];
Class cls = obj.class;
unsigned int count = 0;
Ivar *members = class_copyIvarList(cls, &count);
for(int i = 0; i < count; i++) {
    Ivar ivar = members[i];
    const char *memberName = ivar_getName(ivar);
    //id value = object_getIvar(obj, ivar);
    NSLog(@"%@",[NSString stringWithCString:memberName encoding:NSUTF8StringEncoding]);
}
free(members);

最后输出cowstorage两个 ivar。但是我们尝试用object_getIvar打印storage值的时候,出现EXC_BAD_ACCESS野指针了,看来storage不是普通的结构,我们得换种方法。

class-dump

class-dump ,针对未加密的可执行文件,class-dump 可以导出头文件,很早的时候做dingding/wechat红包插件就是利用这个软件导出分析业务逻辑的。这里需要注意的是:

AppStore下载ipa的是加密的,要先用越狱手机安装,使用 dumpdecrypted 砸壳。
或者直接在PP助手里下载破解版本的。

回过来,我们进入正题,开始 dump 。

1.我们先下载好 class-dump

2.拷贝 CoreFoundation.framework~/Downloads 文件夹下。

# OS macOS Catalina 10.15.7 + XCode Version 12.2 (12B45b)
cp -rf /System/Library/Frameworks/CoreFoundation.framework ~/Downloads

3.开始 dump 。

# 输出头文件到 ~/Downloads/CoreFoundationHeaders
./class-dump -H ~/Downloads/CoreFoundation.framework -o ~/Downloads/CoreFoundationHeaders

dump 完成后,我们找到__NSArrayM.h,提取并合并部分代码:

typedef struct {
    id *list;
    unsigned int offset;
    unsigned int size;
    union {
        unsigned long long mutations;
        struct {
            unsigned int muts;
            unsigned int used;
        } ;
    } state;
} CDStruct_a6934631;

@interface __NSArrayM : NSMutableArray {
     void *cow;
    CDStruct_a6934631 storage;
}
- (void)removeObjectAtIndex:(unsigned long long)arg1;
- (void)insertObject:(id)arg1 atIndex:(unsigned long long)arg2;

下面我们详细的分析下__NSArrayM内存布局。

内存布局

__NSArrayM.h主要包含了以下几个成员:

cow:不清楚实际作用。
storage:实际储存内容的结构体。
storage->_list:缓冲区元素数组首地址指针。
storage->_offset:缓冲区首元素的位置索引。
storage->_size:缓冲区总大小。
storage->_used:缓冲区实际使用量大小。

__NSArrayM也是一段连续的线性内存,用_offset标记了首元素的偏移位置,_used标记了实际使用量大小,_size表示总大小。这样的结构和 环形缓冲区 很像,只不过环形缓冲区用了startend标记首尾位置。
如下图,第一张是__NSArrayM的结构,第二张是通用环形缓冲区的结构。数组ABCDEF,A作为首元素,位置是3,F作为尾元素,位置是0,整个缓冲区元素遍历顺序就是 3->4->5->6->7->0->1->2 。


验证一下

接下来我们来验证一下__NSArrayM的环形缓冲区结构,看下addinsertremove各种操作下的内存结构表现是怎么样的。

1.新建数组
首先,我们新建一个和__NSArrayM内存布局一样的ZHMutableArray class,方便后面打印结构体变量值。

typedef struct {
     //id = void *
    void **list;
    //首元素位置
    unsigned int offset;
    //总大小
    unsigned int size;
    union {
        unsigned long long mutations;
        struct {
            unsigned int muts;
            //使用的大小
            unsigned int used;
        } ;
    } state;
} CDStruct_a6934631;
@interface ZHMutableArray : NSObject  {
    @public void *cow;
    @public CDStruct_a6934631 storage;
}
@end
@implementation ZHMutableArray
@end

2.打印结构体
接着,我们准备打印__NSArrayM成员的函数,使用我们刚才新建的ZHMutableArray,因为内存布局一样,所以可以直接强转过来,输出成员的值。

@implementation ZHMutableArrayTest
/// 获取 arrayM 描述信息
+(NSString *) getDesc:(NSMutableArray *)list {
    assert([NSStringFromClass([list class]) isEqualToString:@"__NSArrayM"]);
    ZHMutableArray *array = (ZHMutableArray *)list;
    NSMutableString *description = [[NSMutableString alloc] init];
    int offset = array->storage.offset;
    int size = array->storage.size;
//    [description appendFormat:@"cow:%@", array->cow];
    [description appendFormat:@"offset:%d", offset];
    [description appendFormat:@",size:%d", size];
    [description appendFormat:@",used:%u", array->storage.state.used];
    [description appendFormat:@",mutations:%llu", array->storage.state.mutations];
    [description appendFormat:@",muts:%u", array->storage.state.muts];
    for (int i = 0; i < size; i++) {
        if (i==0) {
            [description appendString:@"\r\n"];
        }
        [description appendFormat:@"[%d]%@,%p  |  ", i
        , array->storage.list[i], array->storage.list[i]];
    }
    return description;
}
@end

3.开始测试
接下来我们开始验证,来看下 首尾插入删除、中间插入删除等操作下,__NSArrayM内存结构的表现。

/// 环形测试
+ (void)testCircle {
    id objA = @"A";
    id objB = @"B";
    id objC = @"C";
    id objD = @"D";
    id objE = @"E";
    // 1.初始化,容量设置为1
    NSMutableArray *list2 = [[NSMutableArray alloc] initWithCapacity:1];
    printf("1.init\r\n%s", [[ZHMutableArrayTest getDesc:list2] UTF8String]);
    // 2.尾部追加 objA、objB
    [list2 addObject:objA];
    [list2 addObject:objB];
    printf("\r\n\r\n2.add object:\r\n%s", [[ZHMutableArrayTest getDesc:list2] UTF8String]);
    // 3.首位置插入 objC
    [list2 insertObject:objC atIndex:0];
    printf("\r\n\r\n3.insert object at 0:\r\n%s", [[ZHMutableArrayTest getDesc:list2] UTF8String]);
    // 4.删除首位置元素
    [list2 removeObjectAtIndex:0];
    printf("\r\n\r\n4.remove object at 0:\r\n%s", [[ZHMutableArrayTest getDesc:list2] UTF8String]);
    // 5.在第2个位置上插入 objD
    [list2 insertObject:objD atIndex:1];
    printf("\r\n\r\n5.insert object at 1:\r\n%s", [[ZHMutableArrayTest getDesc:list2] UTF8String]);
    // 6.在第2个位置上插入 objE
    [list2 insertObject:objE atIndex:1];
    printf("\r\n\r\n6.insert object at 1:\r\n%s", [[ZHMutableArrayTest getDesc:list2] UTF8String]);
    // 7.移除第3个元素
    [list2 removeObjectAtIndex:2];
    printf("\r\n\r\n7.remove object at 2:\r\n%s", [[ZHMutableArrayTest getDesc:list2] UTF8String]);
    // 8.移除尾部元素
    [list2 removeLastObject];
    printf("\r\n\r\n8.remove last object:\r\n%s", [[ZHMutableArrayTest getDesc:list2] UTF8String]);
    // 9.移除所有元素
    [list2 removeAllObjects];
    printf("\r\n\r\n9.remove all object:\r\n%s", [[ZHMutableArrayTest getDesc:list2] UTF8String]);
}

运行后输出以下日志:

1.init
offset:0,size:2,used:0,mutations:1,muts:1
[0](null),0x0  |  [1](null),0x0  |  

2.add object:
offset:0,size:2,used:2,mutations:8589934595,muts:3
[0]A,0x1082ecde8  |  [1]B,0x1082ece08  |  

3.insert object at 0:
offset:3,size:4,used:3,mutations:12884901892,muts:4
[0]A,0x1082ecde8  |  [1]B,0x1082ece08  |  [2](null),0x0  |  [3]C,0x1082ece28  |

4.remove object at 0:
offset:0,size:4,used:2,mutations:8589934597,muts:5
[0]A,0x1082ecde8  |  [1]B,0x1082ece08  |  [2](null),0x0  |  [3]C,0x1082ece28  |

5.insert object at 1:
offset:0,size:4,used:3,mutations:12884901894,muts:6
[0]A,0x1082ecde8  |  [1]D,0x1082ece48  |  [2]B,0x1082ece08  |  [3]C,0x1082ece28  |

6.insert object at 1:
offset:3,size:4,used:4,mutations:17179869191,muts:7
[0]E,0x1082ece68  |  [1]D,0x1082ece48  |  [2]B,0x1082ece08  |  [3]A,0x1082ecde8  |

7.remove object at 2:
offset:3,size:4,used:3,mutations:12884901896,muts:8
[0]E,0x1082ece68  |  [1]B,0x1082ece08  |  [2]B,0x1082ece08  |  [3]A,0x1082ecde8  |

8.remove last object:
offset:3,size:4,used:2,mutations:8589934601,muts:9
[0]E,0x1082ece68  |  [1]B,0x1082ece08  |  [2]B,0x1082ece08  |  [3]A,0x1082ecde8  |

9.remove all object:
offset:0,size:0,used:0,mutations:10,muts:10

我们发现几个现象,其实大部分都是环形缓冲区的特点:

  1. 观察操作1、3,自动初始化或添加元素的时候,_size 会变成偶数,也就是自动扩容到偶数2倍大小。

  2. 观察操作3、4,首位置插入或删除元素,旧的元素位置并没有移动,只是更新了_offset

  3. 观察操作4,删除元素,没有清除缓冲区里的元素指针。经过测试,这和 NSString 无关,换成 NSObject 也是一样,指针并不会清空,但是打印storage.list[i]的值,就会野指针 crash 了,因为内存已经被释放了。

  4. 观察操作4、8,删除元素,不会减少缓冲区大小,_size还是4。

  5. 观察操作5、6,中间插入元素,会选择距离插入位置较近的方向移动,也就是需要移动的元素最少,然后更新_offset。比如说操作6,因为要插入到位置1,此时缓冲区有3个元素,向前只需要移动1个元素,而向后需要移动2个元素。那么肯定移动前面的元素了。

  6. 观察操作7,删除中间元素,和中间插入一样,会选择需要移动元素较少的一边,进行移动,然后更新_offset。并且不会清除元素指针,只会被移动覆盖。

  7. 观察操作9,删除所有元素,_offset_size都会清0,缓冲区也会清0。

接下来看下首尾插入删除和中间插入删除的内存结构变化。

1.首尾插入删除

首位置插入或删除元素

比普通数组更高效,旧的元素位置并没有移动,只是更新了_offset_used,如下图:

尾位置插入或删除元素

和普通数组一样,只更新了_used,不需要移动元素,如下图:

2.中间插入删除

中间插入元素,会选择距离插入位置较近的方向移动,也就是需要移动的元素较少的一方,进行移动,然后更新_offset

删除中间元素,和中间插入一样,会选择需要移动元素较少的一边,进行移动,然后更新_offset。并且不会清除元素指针,只会被移动覆盖。

总结

1. 内存结构

NSMutableArray内部使用了__NSArrayM子类,__NSArrayM使用storage存储环形缓冲区结构。主要结构如下:

unsigned int _list:缓冲区元素数组首地址指针。
unsigned int _offset:缓冲区首元素的位置索引。
unsigned int _size:缓冲区总大小。
unsigned int _used:缓冲区实际使用量大小。

2. 环形特性

__NSArrayM内部使用的环形缓冲区结构,主要有以下特性:

  1. 2的倍数扩容。初始化或添加元素的时候,按照2的倍数扩容。

  2. 首尾插入删除很快,O(1),只需要更新_offset

  3. 单纯移除某个元素,缓冲区大小_size不会减小,移除所有元素操作,缓冲区才会清0。

  4. 中间插入删除,效率比较低,会选择移动较少的一方的元素进行移动。不过仍然比普通可变数组中间插入删除效率要高。

  5. 删除元素,元素指针不会清除,只会被其他元素指针移动覆盖。但是最后一个移动的元素指针就不会清除了,因为没有被覆盖的指针。

参考链接

wiki-环形缓冲区

NSMutableArray原理揭露

gnustep/libs-base

class-dump

Tags: objc
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章