前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP最新优惠活动
返回腾讯云官网
社区首页 >专栏 >从 Objective-C 和 Swift 看字典的性能优化（1）

从 Objective-C 和 Swift 看字典的性能优化（1）

作者头像
酷酷的哀殿
发布于 2021-04-09 14:38:44
1.1K0
发布于 2021-04-09 14:38:44
举报
文章被收录于专栏：酷酷的哀殿

最近有些群友反馈自己经常遇到一些与 NSDictionary 底层相关的面试题。

本系列文章会通过分析系统库汇编的方式对此类问题进行答疑解惑。?

一、·NSDictionary· 结构简介

1、类簇

在 iOS 的系统库中，很多集合类都是类簇。

尽管我们通常只会用到 NSDictionary 和 NSMutableDictionary 两个类，但是系统库会存在很多不同的子类。

2、语法糖

从 Xcode 4.4 开始，编译器新增了一些被称为 字面量 的语法糖。

以下面的代码为例：

代码语言：javascript
复制
NSDictionary *masses = @{ @"H" : @1.0078,  @"He" : @4.0026, @"O" : @15.9990, @"C" : @12.0096 };

clang 编译器的 SemaExprObjC.cpp[1] 会将上述代码转为下面等价实现：

代码语言：javascript
复制
id keys[] = { @"H", @"He", @"O", @"C" };
id values[] = { [NSNumber numberWithDouble:1.0078], [NSNumber numberWithDouble:4.0026],
                [NSNumber numberWithDouble:15.9990], [NSNumber numberWithDouble:12.0096] };
NSDictionary *masses = [NSDictionary dictionaryWithObjects:objects forKeys:keys count:4];

通过查看编译产出的汇编代码，我们可以证明上面的结论：

image

二、__NSPlaceholderDictionary

__NSPlaceholderDictionary 是占位的类型，通常只出现在崩溃日志中。

本节会以下面的代码为例对 __NSPlaceholderDictionary 出现的场景进行分析

代码语言：javascript
复制
id obj = nil;
NSDictionary *dic = @{ @"k" : @"v", obj : obj };

在字典的初始化过程中，+[NSDictionary dictionaryWithObjects:forKeys:count:]会先调用objc_alloc 进行初始化

image

objc_alloc 会转发到 +[NSDictionary alloc] 处理

image

随后会经过层层转发，最后调用 +[NSDictionary allocWithZone:] 进行下一步处理

代码语言：javascript
复制
## 第一次转发
libobjc.A.dylib`objc_alloc:
    0x7fff20190b4d <+0>:  test   rdi, rdi
    0x7fff20190b50 <+3>:  je     0x7fff20190b6c            ; <+31>
    0x7fff20190b52 <+5>:  mov    rax, qword ptr [rdi]
    0x7fff20190b55 <+8>:  test   byte ptr [rax + 0x1d], 0x40
    0x7fff20190b59 <+12>: jne    0x7fff20188a75            ; _objc_rootAllocWithZone
    0x7fff20190b5f <+18>: mov    rsi, qword ptr [rip + 0x66bc3952] ; "alloc"
->  0x7fff20190b66 <+25>: jmp    qword ptr [rip + 0x5fe8d124] ; (void *)0x00007fff20173780: objc_msgSend
    0x7fff20190b6c <+31>: xor    eax, eax
    0x7fff20190b6e <+33>: ret

## 第二次转发
libobjc.A.dylib`+[NSObject alloc]:
->  0x7fff2018ec56 <+0>: jmp    0x7fff2018ec7a            ; _objc_rootAlloc

## 第三次转发
libobjc.A.dylib`_objc_rootAlloc:
    0x7fff2018ec7a <+0>:  mov    rax, qword ptr [rdi]
    0x7fff2018ec7d <+3>:  test   byte ptr [rax + 0x1d], 0x40
    0x7fff2018ec81 <+7>:  je     0x7fff2018ec88            ; <+14>
    0x7fff2018ec83 <+9>:  jmp    0x7fff20188a75            ; _objc_rootAllocWithZone
    0x7fff2018ec88 <+14>: mov    rsi, qword ptr [rip + 0x66bc5831] ; "allocWithZone:"
    0x7fff2018ec8f <+21>: xor    edx, edx
->  0x7fff2018ec91 <+23>: jmp    qword ptr [rip + 0x5fe8eff9] ; (void *)0x00007fff20173780: objc_msgSend

[NSDictionary allocWithZone:] 会转发到 __NSDictionaryImmutablePlaceholder 进入不可变数组的通用处理逻辑

image

__NSDictionaryImmutablePlaceholder 内部会将常量 ___immutablePlaceholderDictionary 加载到 $rax 寄存器并返回 (x86-64 架构)

代码语言：javascript
复制
CoreFoundation`__NSDictionaryImmutablePlaceholder:
->  0x7fff2048cbba <+0>: lea    rax, [rip + 0x5fd19e7f]   ; ___immutablePlaceholderDictionary
    0x7fff2048cbc1 <+7>: ret

返回 +[NSDictionary dictionaryWithObjects:forKeys:count:] 后，会拼装一个新的方法调用 -[__NSPlaceholderDictionary initWithObjects:forKeys:count:]

相关参数信息：

代码语言：javascript
复制
类型是 __NSPlaceholderDictionary
(lldb) x/a $rdi
0x7fff801a6a40: 0x00007fff86d73ec0 (void *)0x00007fff86d73ee8: __NSPlaceholderDictionary
(lldb) x/a $rax
0x7fff801a6a40: 0x00007fff86d73ec0 (void *)0x00007fff86d73ee8: __NSPlaceholderDictionary

方法名是  "initWithObjects:forKeys:count:"
(lldb) x/s $rsi
0x7fff6143917e: "initWithObjects:forKeys:count:"

第一个参数:objects
(lldb)  x/2a $rbx
0x7ffedfe95488: 0x000000010fd6e5f8 @"'v'"
0x7ffedfe95490: 0x0000000000000000

第二个参数:keys
(lldb)  x/2a $rcx
0x7ffedfe95478: 0x000000010fd6e5b8 @"'k'"
0x7ffedfe95480: 0x0000000000000000

第三个参数：count
(lldb) p/x $r8
(unsigned long) $13 = 0x0000000000000002
(lldb)

-[__NSPlaceholderDictionary initWithObjects:forKeys:count:] 内部会先做一些基础校验

本例中，会通过下面的循环依次判断每个值是否合法

代码语言：javascript
复制
# 依次判断每个 keys[i] 是否等于 nil
0x7fff2048cbf8 <+44>:  cmp    qword ptr [rsi + 8*rcx], 0x0

# 等于 nil 时，转到 0x7fff2048cca7 进行异常处理
0x7fff2048cbfd <+49>:  je     0x7fff2048cca7            ; <+219>

# 不等于 nil 时，rcx = rcx + 1
0x7fff2048cc03 <+55>:  inc    rcx

# 判断 rcx 是否等于 rax；rax 是传入的 count
0x7fff2048cc06 <+58>:  cmp    rax, rcx

# 判断是否将所有的 key 循环结束，如果没有，则转到 0x7fff2048cbf8 进行下一步处理
0x7fff2048cc09 <+61>:  jne    0x7fff2048cbf8            ; <+44>
代码语言：javascript
复制
# rdi 是函数的第一个参数，这里会将校验失败的 rcx 传给下个函数
0x7fff2048cca7 <+219>: mov    rdi, rcx
0x7fff2048ccaa <+222>: call   0x7fff204a9ec4            ; -[__NSPlaceholderDictionary initWithObjects:forKeys:count:].cold.5

-[__NSPlaceholderDictionary initWithObjects:forKeys:count:].cold.5 内部逻辑比较简单，会直接通过 _CFThrowFormattedException 抛出异常

代码语言：javascript
复制
CoreFoundation`-[__NSPlaceholderDictionary initWithObjects:forKeys:count:].cold.5:
->  0x7fff204a9ec4 <+0>:  push   rbp
    0x7fff204a9ec5 <+1>:  mov    rbp, rsp
    0x7fff204a9ec8 <+4>:  mov    rcx, rdi
    0x7fff204a9ecb <+7>:  lea    rax, [rip + 0x5fcf9176]   ; NSInvalidArgumentException
    0x7fff204a9ed2 <+14>: mov    rdi, qword ptr [rax]
    0x7fff204a9ed5 <+17>: lea    rsi, [rip + 0x5fcfd33c]   ; @"*** %s: attempt to insert nil object from objects[%lu]"
    0x7fff204a9edc <+24>: lea    rdx, [rip + 0x1dc1bc]     ; "-[__NSPlaceholderDictionary initWithObjects:forKeys:count:]"
    0x7fff204a9ee3 <+31>: xor    eax, eax
    0x7fff204a9ee5 <+33>: call   0x7fff2049e6bd            ; _CFThrowFormattedException

崩溃日志关键信息：

注意，我们可以通过崩溃日志的 objects[1] 判断是第二个键值对出现了 nil

代码语言：javascript
复制
 *** Terminating app due to uncaught exception 'NSInvalidArgumentException', reason: '*** -[__NSPlaceholderDictionary initWithObjects:forKeys:count:]: attempt to insert nil object from objects[1]'
*** First throw call stack:
(
 0   CoreFoundation                      0x00007fff20421af6 __exceptionPreprocess + 242
 1   libobjc.A.dylib                     0x00007fff20177e78 objc_exception_throw + 48
 2   CoreFoundation                      0x00007fff2049e77f _CFThrowFormattedException + 194
 3   CoreFoundation                      0x00007fff204a9eea -[__NSPlaceholderDictionary initWithCapacity:].cold.1 + 0
 4   CoreFoundation                      0x00007fff2048ccaf -[__NSPlaceholderDictionary initWithObjects:forKeys:count:] + 227
 5   CoreFoundation                      0x00007fff20420773 +[NSDictionary dictionaryWithObjects:forKeys:count:] + 49

三、__NSDictionaryI

__NSDictionaryI 是存有多个键值对的不可变字典，其内部结构如下：

代码语言：javascript
复制
classDiagram
class __NSDictionaryI {
  ## 当前使用的数量
	unsigned _used : 57;
	## 是否复制 key
	unsigned _copyKeys : 1;
	## size 索引
	unsigned _szidx : 6;
	## key 和 value
	id _list[0];
}

本节会通过下面的代码对 __NSDictionaryI 接着上一节内容进行分析

代码语言：javascript
复制
NSDictionary *dic = @{ @"k" : @"v", @"k" : @"v2" };

-[__NSPlaceholderDictionary initWithObjects:forKeys:count:] 各种校验结束后，会转发到 __NSDictionaryI_new 进行下一步处理（rcx 代表字典的 count ；r8d 等于常量 1，代表会复制 key）

image

__NSDictionaryI_new 内部会依次进行以下处理

敲重点： 1、__NSDictionaryCapacities 会搭配后面的 __NSDictionarySizes 常量来控制字典的空间大小和动态扩容 2、数组的长度是 40

image

  • 通过指令 mov qword ptr [rbp - 0x78], r8 将 常量 1 暂存
  • 读取一个常量数组：__NSDictionaryCapacities

字典读取后，会开始进入下面的循环

代码语言：javascript
复制
    0x7fff203432fd <+51>:  lea    rax, [rip + 0x1dd87c]     ; __NSDictionaryCapacities
    0x7fff20343304 <+58>:  xor    ebx, ebx

    # 循环
    0x7fff20343306 <+60>:  cmp    qword ptr [rbx + rax], r13
    0x7fff2034330a <+64>:  jae    0x7fff20343322            ; <+88>
    0x7fff2034330c <+66>:  add    rbx, 0x8
    0x7fff20343310 <+70>:  add    r14, 0x4
    0x7fff20343314 <+74>:  cmp    r14, 0x100
    ## 循环 64次后强制终止（64=0x100/0x4）
    0x7fff2034331b <+81>:  jne    0x7fff20343306            ; <+60>

汇编代码会依次将 __NSDictionaryCapacities 常量数组的值取出来并和 r13 存储的内容进行比较

JAE 的含义是：无符号大于等于则跳转

代码语言：javascript
复制
JA   ;无符号大于则跳转
JNA  ;无符号不大于则跳转
JAE  ;无符号大于等于则跳转  同JNB
JNAE ;无符号不大于等于则跳转 同JB

本例中，count 是 2，所以，截止时，rbx = 0x8，r14 = 0x4

对应的 arm64 架构的版本：

代码语言：javascript
复制
0x00000001803b0e54 A80D00B0               adrp       x8, #0x180565000           ; 0x1805651e0@PAGE
0x00000001803b0e58 08810791               add        x8, x8, #0x1e0             ; 0x1805651e0@PAGEOFF, ___NSDictionaryCapacities

                                      loc_1803b0e5c:
0x00000001803b0e5c 09797AF8               ldr        x9, [x8, x26, lsl #3]      ; CODE XREF=___NSDictionaryI_new+100
0x00000001803b0e60 3F0116EB               cmp        x9, x22
## 大于等于时触发终止
0x00000001803b0e64 A2000054               b.hs       loc_1803b0e78

0x00000001803b0e68 5A070091               add        x26, x26, #0x1
0x00000001803b0e6c 5F0301F1               cmp        x26, #0x40
## 循环 64 次后强制终止（64=0x40/0x1）
0x00000001803b0e70 61FFFF54               b.ne       loc_1803b0e5c

随后会读取常量数组 __NSDictionarySizes，并将对应位置的值取出来

image

3 代表该字典可以存储的键值对数量

随后，会通过位移计算 __NSDictionaryI 额外的体积占用，并调用 __CFAllocateObject 创建对象

本例中，字典最多持有 3 个键值对，体积占用是 6 个指针，对应的体积是 0x30 = 48 = 3 x 2 x 8 = 3<<4

代码语言：javascript
复制
## 获取 __NSDictionaryI 类型
0x7fff20343322 <+88>:  lea    rdi, [rip + 0x66a2d857]   ; (void *)0x00007fff86d70ba8: __NSDictionaryI
## 获取 [__NSDictionaryI self]，返回值放在 rax 寄存器
0x7fff20343329 <+95>:  call   0x7fff204ab4fa            ; symbol stub for: objc_opt_self
## rcx 指向 __NSDictionarySizes 常量数组
0x7fff2034332e <+100>: lea    rcx, [rip + 0x1dd6fb]     ; __NSDictionarySizes
## 根据偏移量 0x8 取出 3
0x7fff20343335 <+107>: mov    rbx, qword ptr [rbx + rcx]
## 放到 rsi 寄存器
0x7fff20343339 <+111>: mov    rsi, rbx
## 左移 4 位，相当于 3*16=6*8
0x7fff2034333c <+114>: shl    rsi, 0x4
## rdi 持有 __NSDictionaryI
0x7fff20343340 <+118>: mov    rdi, rax
## 通过 __CFAllocateObject 创建对象的实例
0x7fff20343343 <+121>: call   0x7fff2043153b            ; __CFAllocateObject

objc_opt_self 等价于 [obj self]

只有较新的 objc 版本才有该方法

代码语言：javascript
复制

// Calls [obj self]
id
objc_opt_self(id obj)
{
#if __OBJC2__
    if (fastpath(!obj || obj->isTaggedPointer() || !obj->ISA()->hasCustomCore())) {
        return obj;
    }
#endif
    return ((id(*)(id, SEL))objc_msgSend)(obj, @selector(self));
}

__CFAllocateObject 内部会调用 class_createInstance 创建该类的实例，并额外申请 0x30 的内存

__CFAllocateObject 结束后会开始更新实例的值

代码语言：javascript
复制

0x7fff20343343 <+121>: call   0x7fff2043153b            ; __CFAllocateObject
刚创建的实例：
0x7f8371e06960: 0x00007fff86d70b80 (void *)0x00007fff86d70ba8: __NSDictionaryI
0x7f8371e06968: 0x0000000000000000
0x7f8371e06970: 0x0000000000000000
0x7f8371e06978: 0x0000000000000000
0x7f8371e06980: 0x0000000000000000
0x7f8371e06988: 0x0000000000000000
0x7f8371e06990: 0x0000000000000000
0x7f8371e06998: 0x0000000000000000

## 下面的汇编代码相当于 dic->_szidx=(r14>>2)；可读性比较差是因为编译器无法优化

  ### 读取 __NSDictionaryI._szidx 的值
  0x7fff20343348 <+126>: mov    rdx, qword ptr [rip + 0x66a2c7d9] ; __NSDictionaryI._szidx

  ### 因为 _szidx 只占用6bit，所以需要先读取原来的值
  0x7fff2034334f <+133>: mov    cl, byte ptr [rax + rdx]

  ### 随后，只保留最低的2bit，_szidx 对应的旧值被清零
  0x7fff20343352 <+136>: and    cl, 0x3

  ### 旧的低位2bit加上新的6bit
  0x7fff20343355 <+139>: or     r14b, cl

  ### 存储到 _szidx和旁边2位的 bit
  0x7fff20343358 <+142>: mov    byte ptr [rax + rdx], r14b

经过上面的流程，0x7f8371e06968 的高6位内容会被更新
0x7f8371e06960: 0x00007fff86d70b80 (void *)0x00007fff86d70ba8: __NSDictionaryI
0x7f8371e06968: 0x0400000000000000
0x7f8371e06970: 0x0000000000000000
0x7f8371e06978: 0x0000000000000000
0x7f8371e06980: 0x0000000000000000
0x7f8371e06988: 0x0000000000000000
0x7f8371e06990: 0x0000000000000000
0x7f8371e06998: 0x0000000000000000

## 与 _szidx 类似，下面的汇编等价于 dic->_used = (0x1ffffffffffffff & $r13)

0x7fff2034335c <+146>: mov    rsi, qword ptr [rip + 0x66a2c7bd] ; __NSDictionaryI._used
0x7fff20343363 <+153>: movabs rcx, 0x1ffffffffffffff
0x7fff2034336d <+163>: and    rcx, r13
0x7fff20343370 <+166>: movabs rdx, -0x200000000000000
0x7fff2034337a <+176>: and    rdx, qword ptr [rax + rsi]
0x7fff2034337e <+180>: or     rdx, rcx
0x7fff20343381 <+183>: mov    qword ptr [rax + rsi], rdx

经过上面的流程，0x7f8371e06968 的低57位内容会被更新
(lldb) x/8a $rax
0x7f8371e06960: 0x00007fff86d70b80 (void *)0x00007fff86d70ba8: __NSDictionaryI
0x7f8371e06968: 0x0400000000000002
0x7f8371e06970: 0x0000000000000000
0x7f8371e06978: 0x0000000000000000
0x7f8371e06980: 0x0000000000000000
0x7f8371e06988: 0x0000000000000000
0x7f8371e06990: 0x0000000000000000
0x7f8371e06998: 0x0000000000000000

## [rbp - 0x78] 暂存的是 1 ，所以下面的汇编等价于 dic->_copyKeys = (x&2)
cl=旧8bit
8 位	AL、BL、CL、DL、DIL、SIL、BPL、SPL、R8L、R9L、R10L、R11L、R12L、R13L、R14L、R15L
16 位	AX、BX、CX、DX、DI、SI、BP、SP、R8W、R9W、R10W、R11W、R12W、R13W、R14W、R15W
32 位	EAX、EBX、ECX、EDX、EDI、ESI、EBP、ESP、R8D、R9D、R10D、R11D、R12D、R13D、R14D、R15D
64 位	RAX、RBX、RCX、RDX、RDI、RSI、RBP、RSP、R8、R9、R10、R11、R12、R13、R14、R15

0x7fff20343385 <+187>: mov    rsi, qword ptr [rip + 0x66a2c7ac] ; __NSDictionaryI._copyKeys
0x7fff2034338c <+194>: mov    cl, byte ptr [rax + rsi]
0x7fff2034338f <+197>: mov    rdi, qword ptr [rbp - 0x78]
0x7fff20343393 <+201>: mov    edx, edi
## dl=edx=edi=rdi=*[rbp - 0x78]=1
## 经过 and 后，dl=0
0x7fff20343395 <+203>: and    dl, 0x2

## cl=旧8bit，并清掉旧值
0x7fff20343398 <+206>: and    cl, -0x3
## 设置新的值
0x7fff2034339b <+209>: or     cl, dl
## 存储
0x7fff2034339d <+211>: mov    byte ptr [rax + rsi], cl

下一步的逻辑比较简单，就是依次通过 ____NSDictionaryI_new_block_invoke 将输入存储到 _list区域

image

____NSDictionaryI_new_block_invoke 内部的汇编比较多，我们只对内部的逻辑进行简单的介绍

image

  • 通过调用 hash 和 isEqual: 判断是否有重复的值
  • 通过 objc_retain 对 value 进行复制操作

如下图所示，经过上面的一些列流程后，dic 会变成一个只持有 k 和 v 键值对的结构体

image

总结

本文主要分享了 NSDictionary 的两个子类：__NSPlaceholderDictionary 和 __NSDictionaryI 的构造过程进行了简单的分析。

下一篇暂定会介绍 cow 机制。

参考资料

[1]

SemaExprObjC.cpp: https://github.com/apple/llvm-project/blob/bf7404b17f35826f76aede830a7de279afaeb321/clang/lib/Sema/SemaExprObjC.cpp#L965

本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-03-31，如有侵权请联系 cloudcommunity@tencent.com 删除
objective-c
c++
c#
汇编语言
编程算法

本文分享自 酷酷的哀殿 微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

objective-c
c++
c#
汇编语言
编程算法
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
LV.
文章
0
获赞
0
目录
  • 一、·NSDictionary· 结构简介
    • 1、类簇
      • 2、语法糖
      • 二、__NSPlaceholderDictionary
      • 三、__NSDictionaryI
      • 总结
        • 参考资料
        领券

        腾讯云开发者

        扫码关注腾讯云开发者

        扫码关注腾讯云开发者

        领取腾讯云代金券

        热门产品

        热门推荐

        更多推荐

        Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

        深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

        腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

        Copyright © 2013 - 2024 Tencent Cloud.

        All Rights Reserved. 腾讯云 版权所有

        登录 后参与评论