Uber是如何处理大体积App的

性能优化

App 体积问题

Uber的乘客，司机，外卖app体积十分庞大，swift是我们首选的编程语言。我们的快速开发环境和附加功能，软件的分层以及相关依赖库，还有静态链接系统静态库导致app二进制库十分庞大。减少程序体积决定了我们的用户体验。而且，苹果下载体积限制进制大型app通过流量进行下载。

苹果下载体积限制意味着不能够在非Wifi环境下第一次下载app，以及更新最新的功能，促销活动以及安全能力。我们在Uber乘客端app和用户的参与度之间建立了联系--当app体积超过下载限制，将导致10%的app下载量减少，12%的签到用户减少，20%的第一次预定量减少，直接影响了收入的减少。在过去的三年里，Uber乘客端app经常接近苹果的下载体积限制。保持在这个体积限制之下是一个很清晰的优先级。

在下面的文章中我们将会介绍我们如何使用现金的编译技术减少了23%的Uber乘客端app体积。在本文中介绍的方法司机端和外卖端17%和19%的体积大小。

目标

我们着手减少 Uber 的 iOS 应用程序大小，目标如下：

1. 使大小远低于 App Store 下载限制——越小越好
2. 随着应用程序的发展，选择在可预见的未来持续产生影响的缩减优化
3. 保持透明，这样应用程序开发人员就不会被要求将精力转移到减小尺寸上
4. 不要让关键用例的性能退化
5. 不要增加本地构建时间，这是开发人员生产力的关键因素

深入了解 Uber Rider 应用程序

Uber乘客端应用程序混合使用 Swift 和 Objective-C 编程语言编写。该应用程序有几百万行代码，其中绝大多数是 Swift。源代码由大约 500 个 swift 模块组成，包括第三方库。司机端和乘客端应用程序具有相似但略有不同的特征。我们将专注于Uber乘客端应用程序作为我们的规范示例。

图1描述了iOS应用程序（包括 Uber乘客端应用程序）使用的默认构建管道。工作流包含编译模块中的所有源文件以生成ARM64目标文件。几个这样的模块是独立编译的。由于Uber乘客端应用程序是多语言的，它还会将 Objective-C 文件单独编译为目标文件。所有目标文件，包括任何预先构建的二进制文件，都通过系统链接器 ( ld64 )链接到最终的二进制文件中。应用程序本身可能会打包额外的资源。单个模块使用Swift编译器中的整体模块优化进行编译，该编译器在模块内执行过程间优化。我们使用-Osize 标志以生成大小优化的二进制文件。

我们采用了几个限制规则来防止二进制大小爆炸，其中包括避免大值类型（例如，结构和枚举），将访问控制级别限制为最低（例如，尽可能避免公共和开放访问），避免过度使用泛型，以及使用final属性。我们使用了几个内部静态分析工具来删除死代码和资源，并禁用反射元数据以减少二进制大小。

虽然这些技术共同减少了应用程序的大小，但我们快速增长的代码库总体上超过了它们。跨模块优化的机会仍有待探索，因此是本文的重点。

在二进制级别

超过 75% 的 Uber Rider 应用程序二进制文件是机器指令。我们系统地研究了这些机器指令的模式，发现大量机器指令序列频繁重复。

指令序列副本及其特征

单指令副本在任何二进制文件中都很丰富，但它们无法在固定指令宽度架构（RISC）（如 ARM64）上被有利地替代；替换指令克隆的成本高于保留原始指令的成本。

另一方面，长度为 2 或更多的指令模式可以有利地"outlined"。也就是说，我们可以用较短的序列替换一个序列，通常是对模式的一次出现的单个调用或无条件分支指令。这需要将控制转移到有效执行原始指令序列的概述指令序列，然后在紧接原始序列之后的指令处恢复。

图 2 显示了在Uber乘客端应用程序中发现的高度重复指令序列的示例。该序列首先通过与零寄存器$xzr的按位或将通用 CPU 寄存器$x20的内容复制到寄存器$x0 中。下一条指令调用`swift_release`函数。$ x20 中的值是一个需要释放引用的对象。

这两条指令可以替换为对新创建的outline_function的调用指令；outlined_function执行前缀指令和最后尾调用原始功能swift_release。

如果这样的 2 条指令模式出现 100 万次（对于 32 位大小的指令来说是 800 万字节），转换会将这些 2 条指令序列减少为 1 条指令（总共 400 万字节） )，在outline_function 中有 2 个额外的指令——节省了近 50%。这种以调用或返回指令结尾的模式是最常见的，占我们可以在Uber乘客端应用程序中有利地编辑的所有重复候选者的 67%。

机器代码序列频繁重复，重复频率遵循幂律曲线。

图 3 绘制了与序列长度（红线）重叠的机器代码序列中的重复频率（蓝线）。x 轴表示每个模式的唯一 id，其中出现次数最多的模式的 id 为 1，次高的模式的 id 为 2，依此类推。它是一个日志图。一些模式非常频繁地重复，但也有很长的模式尾部，每个模式重复的次数逐渐减少，符合幂律(y = ax b )，置信度为 99.4%。

注：幂律来自上世纪20年代对于英语单词频率的分析，真正常用的单词量很少，很多单词不常被使用，语言学家发现单词使用的频率和它的使用优先度是一个常数次幂的反比关系。

图 4 显示了与图 3 相同的红线，但是 x 轴不在对数刻度上。红线显示了一个反复出现的分形模式 — 频繁出现的模式具有非常短的序列长度（左侧）；随着重复频率的降低，序列长度的多样性增加（右侧）。x 轴上从一个峰值到下一个峰值的数据点代表一组重复相同次数的模式；在每个簇内，长序列很少，但随着序列长度的减少，出现了越来越多的模式。最后，比较左边的一个簇（较高的重复频率）和右边的另一个簇（较低的重复频率），很明显，随着重复频率的降低，模式的多样性（水平步长）和序列长度（尖峰的高度）增加。

虽然幂律和分形模式已经在一些物理、生物和人造现象中显现出来，但据我们所知，我们是第一个在计算机可执行代码的机器代码序列中识别它们的存在。据推测，机器代码是人类对计算机指令的表达，并且众所周知，所有人类语言都显示出单词频率的幂律。

图 5 通过概述下一个最有利可图的模式（x 轴）绘制了可能的累积规模节省。需要勾勒出许多模式 (> 10 5 ) 以提取大部分 (> 90%) 可能的大小增益。人们不能“硬编码”一些模式并希望获得显着的好处。

什么导致指令序列重复

与引用计数和内存分配相关的高级语言和运行时特性是最频繁重复模式

下图清单1-6中出现频率最高的几个模式都与语言和运行时细节有关——Swift 和 Objective-C 的引用计数和内存分配。

由于 Swift 和 Objective-C 都是引用计数的，因此递增（swift_retain和objc_retain ）和递减（swift_release和objc_release ）引用的指令非常频繁。以清单 1 为例：第一条指令通过对零寄存器$xzr执行按位或运算（ORR指令），将寄存器$x20 中存在的值移动到寄存器$x0 。第二条指令 ( BL ) 调用swift_release ，它减少参数$x0中的堆对象的引用计数. 在此示例中，指向堆对象的指针最初存在于$x20 （源寄存器）中，但必须将其移至$x0 （目标寄存器）以满足调用约定，即期望$x0 中的第一个参数。

寄存器分配选择可能导致许多重复模式——例如，清单 1 和清单 2 仅在源寄存器上有所不同。在整个程序二进制文件中，这些模式可以出现多次。函数调用指令有许多可能的目标，因此每个目标都有助于形成独特的 2 指令模式。最后，被调用者可以期望多个参数（例如，清单 3 中的swift_allocObject期望 3 个参数）；因此，目标寄存器也可以不同，并由指令调度程序重新排序，这也有助于形成几种 2 指令模式。

大量使用新颖的高级语言特性及其相应的代码生成导致某些非常长且不受欢迎的重复模式

泛型函数和闭包特化：Swift 支持泛型函数和闭包。通用函数实例化和闭包专门在它们的调用点产生高度相似的长机器指令序列。

try表达式的O(N^2)代码爆炸。

显示了 Swift 推荐的常用习惯用法，用于使用try表达式反序列化 JSON 数据并分配给类的属性。在此示例中，类MyClass包含 118 个属性，这些属性是从 JSON 对象初始化的。初始化是通过try表达式进行的，如果在传入的 JSON 对象中找不到该属性，则会抛出 Error 。如果任何一个 try 表达式失败，则必须释放所有先前创建的属性。当这段代码被降到 LLVM IR 然后进入机器码时，它会引入 N 个代码块，其中第 N个块和第 N-1个块有 N-1 个相同的指令，第 N-1个和第N-2个块有 N-2 条相同的指令等等——这是一个 O(N^2) 复制代码。

通过高级编译器技术的解决方案

很明显，无论原因如何，指令序列都会重复。我们利用机器代码序列的幂律特性来帮助减少代码大小。原则上，可以通过将每个重复位置的执行重定向到单个实例来替换任何重复序列。

因此，可以应用前面提到的outlining技术，通过编译时转换用函数调用替换同一序列的许多实例来节省大小。事实上，machine-code outlining是 LLVM 中可用的一种转换，如果代码针对大小进行编译，则最新的 Swift 编译器版本会启用它。

然而我们发现原生的machine outlining并不是十分有益的。在默认的 iOS 构建管道中，每个模块都被转换为机器代码。在这种情况下，如果我们在每个模块级别执行machine-code outlining，仍然会存在跨模块的副本，而且我们将错过找到跨越500个模块的副本的机会。

在 Uber，我们开发了一个编译管道，可以让machine outlining在整个程序级别提供好处。我们进一步确定了machine outlining在如何错失机会方面的局限性，并开发了重复的machine outlining以进一步减少代码大小。结果是 Uber Rider (23%)、Uber Driver (17%) 和 Uber Eats (19%) 应用程序的代码大小显着减少，没有统计上显着的性能回归，我们的功能团队开发人员的参与为零。

新的 iOS 构建管道

新管道为每个模块生成LLVM IR，而不是直接生成机器代码。然后，它使用llvm-link将所有 LLVM-IR 文件组合成一个大的 IR 文件。随后，它使用opt对这个单个 IR 文件执行所有 LLVM-IR 级别的优化。然后我们将优化后的 IR 提供给llc，这将 IR 降低到目标机器代码；在这个阶段，我们在整个程序级别上启用了machine outlining。这确保：

1. 在识别候选机器代码序列时利用最大相似性
2. 没有outlining的函数是另一个outlining的函数的克隆，我们只执行每个模块的machine outlining将是十分常见的。

机器代码最终与任何预编译的机器代码一起提供给系统链接器，以生成最终的二进制镜像。

使用重复的Machine Outlining挤压更多尺寸

在最初的LLVM 中构想中Machine Outlining采用贪婪算法来检测重复模式，并根据它们的直接盈利能力而不是所有重复序列的全局盈利能力对它们进行排序。这是基本的背包优化问题，是NP复杂度。我们注意到贪婪模式浪费了一个重要的节省大小的机会。如下图a中所示，两个序列（BCD和ABCD）是潜在的outlining模式。在不失一般性的情况下，假设在调用点没有outlining的开销或outlined function的帧开销。LLVM的MachineOutliner选择BCD因为它在紧接的下一步中显示了最大的节省：选择 BCD 会将 8 × 3 = 24 条指令缩小为 8 条，同时引入指令数为3的新函数，总共节省 13 条指令；相比之下选择 ABCD 会将 5×4 = 20 条指令缩减为 5 条，并引入指令数为4的新函数，总共仅节省 11 条指令。OutliningBCD，如图b所示，将指令总共减少到16条指令。然而OutliningABCD在现实中更有利可图，因为它不仅允许首先OutliningABCD，还允许随后在其余候选上OutliningBCD，如图c所示将总大小减少到 15 条指令。然而这种级联效应并不是立即明显的。显然在 LLVM 中实现的贪心算法是次优的。

我们通过在 LLVM 中引入重复machine outlining，重复machine outlining的想法是像以前一样使用贪婪算法选择下一个最有利可图的模式，但是我们并没有丢弃已经outlined的较长候选者。而是继续对新候选者迭代应用相同的算法，现在包含一个或多个已outlined的模式的调用。由于MachineOutliner依赖于最新的活性信息，我们必须更新候选者的活跃度信息在引入调用/分支指令后。回到之前的例子，图d 显示序列 AX 可以在轮廓的第二次重复过程中被勾勒出来；最终大小是 13 条指令——比之前两种选择都要好。重复次数应该是可调的。

与默认贪婪算法相比，重复machine outlining提供了实际好处，与 Uber Rider 应用程序上的默认machine outlining相比，可节省 27% 的大小。我们的评估表明，经过5轮machine outlining后，我们的应用程序收敛到最佳代码大小。

付诸实践

1. 采用: 使用我们的自定义工作流彻底检查默认构建工作流需要维护本地 LLVM 工具链，而这又需要来自多个利益相关者的支持，包括开发人员体验、测试和发布团队。我们通过引入一个配置标志来启用或禁用新的构建管道来解决这个问题，从而在发生中断时更容易回滚。

2. 语言的互通性: 由于“Objective-C 垃圾回收”冲突，两个 LLVM-IR 文件，一个由 Swift 编译器生成，另一个由 Clang 编译器（用于 Objective-C）生成，无法通过 llvm-link 合并为单个 IR 文件两个编译器都使用 LLVM 元数据标志。由于我们的应用程序是 Swift 和 Objective-C 的混合体，因此这种支持是必要的。以前 LLVM GCMetadata 是编码编译器主要和次要版本以及其他位的单个值。因此，比较来自不同编译器的所有位会导致冲突。我们通过将 LLVM 元数据分解为一组“属性”来修复它；稍后链接阶段只检查相关属性，而忽略生成它的编译器。因此我们消除了冲突。

3. 性能退化: 就其本身而言，llvm-link 不会保留数据在每个组成模块中的原始顺序。当合并多个模块时，来自不同模块的数据的混合会导致数据局部性问题。功能开发人员通常将功能所需的所有数据放在其相关模块中，并将相关数据放在一起，但 llvm-link 破坏了这种程序员驱动的数据亲和性。我们在 llvm-link 中引入了一个新的数据布局排序，即使在合并后，它也遵循其组成 IR 文件中存在的原始模块特定的数据排序。这种优化消除了性能回归。

4. 可调试性: outlined函数不能将其指令映射回任何特定的源位置，因为多个源位置可以映射到它。推出新管道后，当我们的开发人员调查错误报告时，他们有时会在调用堆栈顶部看到 OUTLINED_FUNCTION_ID；他们误解为失败是outlining优化导致的。幸运的是失败报告可以访问完整的调用堆栈，而不仅仅是叶函数。通过更深入地检查回溯，开发人员能够调试其功能代码中的故障。

评估

终生代码大小节省

我们的新管道在持续开发环境中找到了更多减少二进制大小的机会。图8显示了我们所有优化对应用程序代码字节的影响。在这个图中，基线（蓝色）代码已经针对大小进行了优化，但它使用了每个模块的优化并且没有重复的machine outlining（代表默认的 iOS 管道）。总体而言，我们看到尺寸减少了 23%。

拟合线性回归线的基线的代码大小增长的斜率为 2.7（96% 置信度）。我们优化后的代码大小增长（红线）的斜率为 1.37（98% 置信度）。因此，我们将代码大小增长率减少了大约2倍。我们相信这种“终身”代码大小影响是我们开发的优化的一个重要好处。

图8注：蓝线显示了我们未应用本文中讨论的任何优化时代码大小的增长。红线显示了我们的大小缩减优化的效果：首先，我们将代码大小减少了 23%，但其次，更重要的是，我们将代码大小增长速度降低了 2 倍。

图9大小缩减比较：

1.代码部分(红黑)和完整的应用程序二进制文件(蓝黄)的比较。
2.不同轮次的重复machine outlining比较(横坐标代表轮次)。
3.跨模块的machine outlining(inter)和模块内的machine outlining(intra)

在图 9 中，标记为 None 的 x 轴是通过禁用machine outlining生成的，但是启用了 LLVM 中的所有其他尺寸减小优化。沿 x 轴的后续点逐渐增加machine outlining的轮次。

首先，将整个二进制大小（顶部两行）与代码大小（底部两行）进行比较表明，由于重复outlining，应用程序二进制大小与代码段大小成比例地减小。我们新构建管道中的五轮machine outlining生成了一个120.1MB 的二进制文件，与默认管道的 145.7MB 相比，二进制文件的大小减少了 17.6%。同样产生了 88.4MB 的代码段，与默认管道中的 114.5MB 相比小了 22.8%。在 22.8% 的代码大小节省中，27%（7% 分）来自重复的machine outlining。

其次，随着machine outlining轮数的增加，尺寸持续（但逐渐减少）减小。此外模块内outlining的增益比模块间outlining更早。三轮outlining提取大部分尺寸优势。超过五轮，根本没有任何好处，但最初的几轮不能打折。我们选择了五轮作为 Uber Rider 应用程序的默认值。

第三，比较底部两行，很明显，模块间（整个程序）重复machine outlining明显优于模块内outlining。在五轮重复中，整个程序machine outlining提供了 88.42MB 的代码大小，而仅对单个模块执行相同的操作会增加到 100.53MB (13.7%) 的代码大小。

生产性能数据

由于额外的分支/调用开销，Outlining可能会降低性能。由于指令占用空间的减少，性能提升也是可能的。Uber Rider 应用程序在用户界面 (UI) 上很密集，我们的代码占用空间很大。在典型的使用场景中，大部分代码只运行一次---与 HPC 风格的代码不同，没有单一的“热点”代码。

图 10 显示了 Uber Rider 应用程序开发团队确定的几个关键用例（名为核心跨度）的热图。每个跨度中的行代表不同的硬件版本，列代表不同的操作系统版本。由于来自生产的数据可能有噪声，因此我们仅在优化前后填充具有 > 25K 样本的单元格。每个单元格中的值是在我们整个程序5轮重复machine outlining的情况下执行跨度的第50个百分位数（P50）时间除以在没有优化的情况下执行相同跨度的时间的比率；因此，大于1.0的值表示性能退化，小于1.0的值表示性能改进。

少数跨度显示了一些性能改进。平均有 3.4% 的性能提升，在 iPhone X Gbl 设备上的 13.5.1 操作系统上，跨度 8 的最佳情况是 25%。有多种因素在起作用：outlining导致更小的指令占用空间，因此可能减少 icache(高速缓冲存储器) 和 iTLB（指令TLB） 压力，但它引入了更多的指令来完成相同数量的工作。我们观察到，与没有outlining相比，有machine outlining的每周期指令 (instructions per cycle：IPC) 增加了 4%，这与 3.4% 的性能提升相当。跨度6显示了一些回归。它是最短的跨度，执行时间仅为 0.64 秒。

在图 10 中，我们注意到更多蓝色单元格表示整体性能提升。总体而言，由于我们的新管道和优化，我们看到了 3.4% 的几何平均性能增益。鉴于评估中使用的真实世界数据量，我们对得出的结论充满信心，并相信machine outlining在使用整个程序管道执行时，不仅可以将应用程序二进制文件大小节省 23%，而且还略有改善对于代码占用量大且代码热点很少的 iOS 移动应用程序，性能提高了 3.4%。

构建时间

我们在配备 64GB DDR4、运行 MacOS 10.15.6 的 10 核 iMac Pro（2017）上评估编译时间。默认管道在 21 分钟内构建应用程序；有machine outlining的新管道需要 53 分钟，其中包括大约 7 分钟的 llvm-link、14 分钟的 opt、11 分钟的 llc 和 3 分钟的系统链接器。llc 一轮outlining大约需要 7 分钟，2 轮需要 9 分钟。每多轮增加的额外时间逐渐减少，通常在 30 秒以下。总体而言，5 轮outlining在 66 分钟内构建 - 基线增加了 45 分钟。由于构建时间显着增加，我们不在调试构建中执行这些优化，而仅在测试和发布构建中执行这些优化。此策略不会影响开发人员的生产力，同时获得优化的好处。

概括

在大型应用程序（例如 Uber Rider 应用程序）中，由于高级语言功能和调用约定，许多机器代码模式会重复，仅举几个常见原因。机器大纲在整个程序级别应用时，可显着减少应用程序二进制文件的大小。重复应用machine outlining可进一步减小代码大小。优步在生产中成功地采用了这些优化，并在控制应用程序大小方面发挥了重要作用，使数百万日常用户受益。我们优化的好处会随着时间的推移而增长，这使得它们非常有效地减少代码大小，并且在快速增长的代码库中是理想的。我们的尺寸缩减优化对应用性能没有负面影响。

几十年来，代码大小优化一直是编译器技术的核心，但在检测代码大小错失机会方面所做的工作却很少。在整个程序级别观察复制的机器代码序列开辟了一条新的途径来精确定位和量化重复的代码模式并将它们归因于不同的代码转换层。