应用大小问题
Uber的骑手，司机和食物的iOS移动应用程序的大小很大。选择迅速作为我们的主要编程语言，我们快节奏的开发环境和功能添加，分层软件及其依赖项，以及静态链接的平台库会导致大型应用程序二进制文件。降低应用程序规模对我们的客户体验至关重要。此外，Apple的App-Download-Size Limitations禁止大型应用程序下载．
应用程序下载大小的限制意味着首次用户在最需要应用程序时不能下载应用程序，而优步不能在现有用户没有使用Wi-Fi时向他们提供功能、促销或安全更新。我们建立了Uber Rider应用大小和用户参与度之间的关联——当应用大小超过下载大小限制时，它会导致应用安装减少10%，注册减少12%，首次预订减少20%，从而导致收入损失。在过去三年里，Uber Rider应用的规模经常接近应用商店的无线下载限制，而保持在这个限制以下显然是优先考虑的。
在接下来的文章中，我们将描述我们如何使用先进的编译技术将优步的iOS Rider应用程序的代码大小减少23%。这里讨论的想法也转化为在Uber Driver和Uber Eats iOS应用中分别节省17%和19%的代码量。
目标
我们首先通过以下目标降低优步的iOS应用大小：
- 将尺寸放在应用商店下载限制 - 较小
- 选择尺寸减少优化，随着应用程序的发展，不断为可预见的未来提供影响
- 要透明，这样应用程序开发人员就不会被要求把精力转移到缩小规模上
- 不倒退关键用例的性能
- 不要增加本地构建时间，即一个开发人员生产力的关键因素
Uber Rider应用洞察
优步骑手应用程序是用Swift和Objective-C编程语言的混合编写的。该应用程序有几个数百万的代码，迅速迅速。源代码包含约500个SWIFT模块，包括第三方库。司机和骑手应用程序具有相似但略有不同的特性。我们将专注于Uber Rider应用程序作为我们的规范示例。
图1描绘了IOS应用程序使用的默认构建流水线，包括在此处描述的工作之前的UBER骑手应用程序。工作流程涉及编制模块中的所有源文件以生成ARM64对象文件。几个这样的模块被独立编译。由于Uber骑手应用程序是多语言，因此它还将Objective-C文件分开编译为对象文件。所有对象文件（包括任何预构建的二进制文件）都与系统链接器链接（ld64）进入最后的二进制。应用程序本身可能会包装其他资源。使用全模模块优化编译单个模块迅速编译器，它在模块内执行过程间优化。我们使用-osize.标记生成大小优化的二进制文件。
我们使用了一些linting规则来防止二进制大小爆炸，包括避免大值类型(例如，struct和enum)，将访问控制级别限制到最低(例如，在可能的情况下避免公共和开放访问)，避免过度使用泛型，以及使用final属性。我们使用了一些内部静态分析工具来删除死代码和资源，并禁用反射元数据来减少二进制文件的大小。
虽然这些技术在一定程度上缩小了应用程序的规模，但它们的发展速度仍然赶不上我们快速增长的代码库。跨模块优化的机会仍然没有被探索，因此这是本文的重点。
在二进制级
超过75%的Uber Rider应用程序二进制是机器指令。我们系统地研究了这些机器指令的模式，发现大量的机器指令序列频繁重复。
指令序列副本及其特征
单个指令副本在任何二进制文件中都是丰富的，但在固定指令宽度架构上无法替换它们（risc.）如ARM64;更换指令克隆的成本高于保留原始指令。
另一方面，可以有利时为“概述”长度的指令模式。也就是说，我们可以用较短的序列，通常是单个呼叫或无条件分支指令代替序列，以便单一的模式发生。这需要将控制转移到概述的指令序列，以有效执行原始指令序列的序列，然后在原始序列之后立即恢复指令。
图2示出了优步骑手应用程序中找到的高度重复指令序列的示例。序列首先复制通用CPU寄存器的内容x20的美元进入注册x0美元通过一个带零寄存器的位或xzr美元．下一条指令调用swift_release”功能。以$为单位的价值X20是需要释放其引用的对象。
这两个指令可以被一个调用指令替换为新创建的指令outlined_function;的outlined_function执行前缀指令并最终执行尾部原来的功能,swift_release．
如果这样的2条指令模式出现了100万次(对于32位大小的指令来说，这是800万字节)，转换将这些2条指令序列削减为1条指令(这使总数为400万字节)，在outlined_function-节省近50%。这种以一个电话或返回指令结束的模式是最常见的，占我们在Uber Rider应用中可以编辑的所有重复的候选人的67%。
机器代码序列频繁重复，并且重复频率遵循幂律曲线。
图3绘制了机器编码序列(蓝线)与序列长度(红线)重叠的重复频率。x轴表示每个模式的唯一id，其中最高出现的模式被赋予id 1，其次最高的模式被赋予id 2，以此类推。这是一个对数-对数图。有一些模式重复的非常频繁，但也有一个非常长的尾巴的模式，每个逐步重复的次数更少，这符合幂律(y = axb)，有99.4%的信心。
图4显示了图3的相同红线，但是，X轴不在日志刻度上。红线显示重现分形模式-经常出现的模式有一个非常短的序列长度(左边);随着重复频率的降低，序列长度的多样性增加(右图)。x轴上从一个峰值到下一个峰值的数据点代表了一组重复相同次数的模式;在每个簇中，只有很少的长序列，但是随着序列长度的减少，出现了越来越多的模式。最后，比较左边的一个集群(较高的重复频率)和右边的另一个集群(较低的重复频率)，很明显，随着重复频率的降低，模式的多样性(水平台阶的长度)和序列长度(峰值的高度)都会增加。
虽然权力法和分形模式在几种物理，生物学和人为现象中揭示了自己，但我们的知识我们是第一个在计算机可执行代码中确定他们在机器代码序列中的存在的现象。据推测，机器代码是对计算机的人类表达指令，并且很好地确定了所有人类语言都在单词的频率中显示出权力。
图5通过概述下一个最有利可图的模式（X轴）绘制累积大小节省。很多模式（> 105)，以提取大多数(> 90%)的可能大小增益。一个人不能“硬编码”几个模式就希望获得显著的好处。
导致指令序列重复的原因
- 与参考计数和内存分配相关的高级语言和运行时功能是最常见的重复模式的常见原因。
清单1-6中出现频率最高的几个模式都与语言和运行时细节有关——Swift和Objective-C的引用计数和内存分配。
因为Swift和Objective-C都是引用计数的，所以增加(swift_retain和objc_retain.)及减量(swift_release和objc_release)的引用非常频繁。以清单1为例:第一个指令移动寄存器中出现的值x20的美元注册x0美元通过执行位或运算(ORR.指令用零寄存器xzr美元．第二条指令(提单)调用swift_release，哪一个减少了在参数中持有的堆对象的引用计数x0美元．在此示例中，对堆对象的指针最初存在于x20的美元(源寄存器)，但它必须被移到x0美元（目的地注册）以满足预计第一个参数的呼叫约定x0美元．
寄存器赋值选择可能导致许多重复的模式——例如，清单1和清单2仅在源寄存器方面有所不同。在整个程序二进制中，这些模式可能发生多次。一个函数调用指令有许多可能的目标，因此每一个都构成了一个独特的2指令模式。最后，被调用者可以期望有多个参数(例如，swift_allocObject清单3中有3个参数);因此，目标寄存器也可以是不同的，并且可以由指令调度程序重新排序，这也有助于几种2-指令模式。
2.大量使用新颖的高级语言特性及其相应的代码生成会导致某些非常长且不受欢迎的重复模式。我们将通过两个例子进一步说明这一点。
a.通用函数和闭包专门化:Swift支持通用函数和关闭．通用函数实例化和闭包在它们的调用位置上特殊化会产生高度相似的长机器指令序列。
b。O (N2）代码放大尝试表达式．
清单7:SWIFT中的典型成语通过从JSON反序列化构建对象。尝试表达可以抛出错误。
上面的清单7显示了Swift推荐的使用试一试向表达式反序列化JSON数据并分配给类的属性。在这个例子中，这个类我的课包含118属性，该属性从JSON对象初始化。初始化会发生通过试一试表达式，如果在传入的JSON对象中没有找到该属性，则抛出Error。如果任何一个try表达式失败，则必须释放之前创建的所有属性。当这个代码降低到LLVM IR，然后进入机器代码，它会导致N块代码，其中NTH.块和n - 1TH.Bock有n-1相同的说明，n-1TH.和n - 2TH.块具有N-2相同的指令等 - 这是一个O（n2)复制代码。
通过高级编译器技术解决
很明显，不管原因如何，指令序列都是重复的。我们利用机器代码序列的幂律性质来帮助减少代码大小。原则上，可以通过将每个重复位置的执行重定向到单个实例来替换任何重复序列。
因此，可以通过通过编译时间转换替换相同序列的许多情况来应用上述“概述”技术以节省大小。实际上，机器代码概述是LLVM中可用的转换，如果代码是根据大小编译的，最新的Swift编译器版本会启用该转换。
但是，我们发现机器概述的天真地应用不是很有利于。在默认的iOS构建管道中，每个模块都被转换为机器代码。在此设置中，如果我们在每个模块级别执行机器代码，仍然会有副本存在跨模块的副本，而且我们将错过查找跨越我们500个模块的副本的机会。
在Uber，我们开发了一个编译管道，可以让机器概述在整个项目层面上提供利益。我们进一步确定了机器的局限性，概述了它如何错失机会，并进行了开发重复机器概述允许更换其他代码大小。结果是优步骑车者（23％），优步司机（17％）和优步（19％）应用程序的显着代码减少，没有统计上显着的性能回归和来自我们的特征团队开发人员的零参与。
新的iOS构建管道
新的管道产生LLVM IR.对于每个模块都不需要直接生成机器码。然后，它将所有LLVM-IR文件合并为一个大的IR文件llvm-link.．随后，它使用此单个IR文件执行所有LLVM-IR级优化选择．然后将优化后的IR注入LLC.，将IR降低到目标机器代码;在此阶段，我们可以在整个程序上概述机器。这确保了：
- 识别候选机器代码序列时利用最大相似性
- 没有一个概述函数是另一个概述函数的克隆，如果我们只执行每个模块的机器概述，这将是常见的
机器代码最终与任何预编译的机器代码一起被送入系统链接器，以产生最终的二进制图像。
通过重复的机器轮廓来挤压更大的尺寸
本机概述，如最初构思在LLVM，采用了贪婪的启发式，以检测重复模式，并通过立即盈利而不是通过所有重复序列的全球盈利能力来命令它们。这是根本的背包优化问题这是np难度。我们注意到贪婪启发式浪费了一个重要的节省大小的机会。在图7a中，2个序列(BCD和ABCD)是潜在的轮廓模式。在不丧失一般性的前提下，假设在调用点没有概述的开销或概述的功能的框架开销。LLVM的MachineOutliner选择BCD是因为它在接下来的步骤中显示了最大的节省:选择BCD将把8 × 3 = 24条指令缩减为8条，同时引入一个3的新函数，总共节省13条指令;相反，选择ABCD将把5×4 = 20条指令压缩为5条，并引入4个新功能，总共只节省11条指令。列出BCD，如图7b所示，将代码减少到总共16条指令。然而，概述ABCD实际上更有利可图，因为它不仅允许首先概述ABCD，而且允许随后概述BCD，从而将剩余的候选项的总大小减少到15条指令，如图7c所示。然而，这种级联效应并不明显;显然，LLVM中实现的贪心算法是次优的。
我们通过介绍来解决了这个问题重复机概述在LLVM中。重复机器概述的想法是使用贪婪算法选择下一个最有利可图的模式，而不是丢弃已经概述的子字符串的冗长候选，我们继续在新候选人上迭代地应用相同的算法，现在包含一个或多个对已经概述的模式的调用。由于MachineoutLiner依赖于最新的活力信息，因此我们不得不更新介绍呼叫/分支指令后的候选人的活力信息。返回我们的示例，图7D显示了序列AX可以在第二次重复概述期间概述;最终尺寸为13条指示 - 比替代品更好。应调用重复次数。
重复概述提供默认贪婪算法的实用效果，在Uber rider应用程序上概述的默认机器上提供27％的大小节省。我们的评估表明，我们的应用程序会聚到5轮机器概述后的最佳代码大小。
将其付诸实践
- 采用．通过我们的自定义工作流程对默认构建工作流程进行大修需要维护本地LLVM Toolchain，这反过来需要从多个利益相关者的购买，包括开发人员体验，测试和发布团队。我们通过将配置标志引入要启用或禁用新建管道来解决此问题，使得在停电时更容易回滚。
- 语言互操作性。两个LLVM-IR文件，一个来自Swift编译器，另一个来自Clang编译器(针对Objective-C)，不能通过LLVM- link合并成一个单独的IR文件，因为两个编译器都使用了一个冲突的“Objective-C垃圾收集”LLVM元数据标志。因为我们的应用是Swift和Objective-C的混合物，这支持是必要的。以前，LLVM GCMetAdata是编码编码的单个值，编码编译器主要和次要版本和其他位。因此，比较来自不同编译器引起的所有比特导致冲突。通过将LLVM元数据分解为一组“属性”来修复它;稍后的链接阶段仅检查相关属性，忽略生成的编译器。因此，我们消除了冲突。
- 性能回归。就其本身而言，llvm-link并不保留数据在每个组成模块中出现的原始顺序。当合并多个模块时，来自不同模块的数据混合会导致数据局部性问题。特性开发人员通常将特性所需的所有数据放在其相关模块中，并将相关数据放在一起，但llvm-link破坏了这种程序员驱动的数据相关性。我们引入了一个新的数据布局订购在llvm-link中，它尊重其组成IR文件中数据的原始特定于模块的排序，即使在合并之后也是如此。这种优化消除了性能回归。
- Debuggability。一个概述函数不能将其指令映射回任何特定的源位置，因为多个源位置可以映射到它。在推出新的管道后，当我们的开发人员在调查bug报告时，他们有时会看到一个OUTLINED_FUNCTION_ID在他们的调用堆栈的顶部;他们误解了概要优化导致的失败。幸运的是，失败报告可以访问完整的调用堆栈，而不仅仅是叶函数。通过对回溯进行更深层次的检查，开发人员能够调试他们特性代码中的错误。
评估
终身代码储蓄
我们的新管道在持续的开发环境中发现了更多的二进制大小减少机会。图8显示了我们所有优化对应用程序代码字节的影响。在此图中，基线（蓝色）代码已经针对大小进行了优化，但它使用每个模块优化，并且没有重复的机器概述（表示默认的iOS管道）。总的来说，我们看到减少23％尺寸。
与线性回归线拟合的基线的代码大小增长斜率为2.7(96%置信)。优化后的代码大小增长(红线)斜率为1.37(98%的可信度)。因此，我们将代码大小的增长减少了大约2倍。我们相信这种“终身的”代码大小影响是我们开发的优化的一个显著好处。
在图9中，通过禁用机器概述产生标记为无标记的X轴，但是启用了LLVM中的所有其他尺寸减少优化。沿X轴的后续点逐渐增加回轮机器概述。
首先，将整个二进制代码大小(顶部两行)与代码大小(底部两行)进行比较，可以发现应用程序二进制代码大小随着代码段大小的增加而成比例地减少，这是由于重复概述的缘故。在我们的新构建管道中，五轮机器轮廓生成了120.1MB的二进制文件，与默认管道的145.7MB相比，它减少了17.6%的二进制文件大小。相同的方法生成的代码段为88.4MB，比默认管道中的114.5MB小22.8%。在22.8%的代码大小节省中，27%(7%)来自重复的机器概述。
其次，减少了连续的（但逐渐减少）的尺寸随着概述的机器数量增加。此外，模块内部概述高原的收益比模块间概述更快。三轮概述提取大部分大小的福利。超出五轮，根本没有好处，但最初的几轮也不能打折。我们选择了五轮作为优步骑手应用程序的默认值。
第三，比较底部两条线，很清楚，模块间（整个程序）重复机器概述显着优于模块内概述。在五回合的重复时，整个程序机概述提供88.42MB的代码大小，而仅在单个模块上执行相同的方式提供100.53MB（13.7％）代码尺寸。
生产性能数据
由于额外的分支/调用开销，大纲可能会降低性能。但是，由于减少了指令占用，性能提高也是可能的。Uber Rider应用非常注重用户界面(UI)，而我们的代码占用也非常大。在典型的使用场景中，大部分代码只运行一次——不像hpc风格的代码，没有单一的“热点”代码。
图10显示了由Uber Rider应用开发团队确定的几个关键用例(命名为核心跨度)的热图。每个跨度中的行表示不同的硬件版本，列表示不同的OS版本。由于生产数据可能有噪声，我们只在优化前和优化后用> 25K样本填充这些单元格。每个单元格中的值是50的比值TH.百分比(P50)执行跨度与我们的整个程序5轮重复的机器代码概述，除以时间执行相同的跨度没有优化;因此，值大于1.0表示性能回归，值小于1.0表示性能改进。
少数跨度显示出一些性能改进。平均而言，性能增益3.4％，并且在iPhone X GBL设备上的13.5.1 OS上的SPAN 8中的最佳情况下为25％。游戏中有多种因素：概述导致较小的指令足迹，因此可能较少的ICACH和ITLB压力，但它引入了更多指令来实现相同数量的工作。与没有概述相比，我们观察到每周期（IPC）指令增加4％，而且没有概述，这与3.4％的性能增益相比。SPAN 6显示了一些回归。它是最短的跨度，只有0.64秒的执行。
在图10中，我们注意到更多的蓝色单元格，表示整体性能收益。总的来说，由于我们的新管道和优化，我们看到几何平均性能增益为3.4％。鉴于评估中使用的真实数据量，我们对得出的结论是有信心的，并确信使用全程管道执行时，不仅将应用程序二进制大小保存23％，而且很温和地提高对于iOS移动应用程序的性能为3.4％，具有大代码占用占用品和少数代码热点。
构建时间
我们对10核iMac Pro(2017)的编译时间进行了评估，它配备了运行MacOS 10.15.6的64GB DDR4。默认管道在21分钟内构建应用;新管道无需机械勾画，耗时53分钟，其中包括约7分钟的llvm-link, 14分钟的opt, 11分钟的LLC和3分钟的系统链接。在llc中，一回合需要7分钟，两回合需要9分钟。每一轮额外增加的时间越来越少，通常不到30秒。总的来说，5轮构建在66分钟内完成——在基线基础上增加了45分钟。由于构建时间显著增加，我们不在调试构建中执行这些优化，而只在测试和发布构建中执行。此策略不会影响开发人员的生产力，但可以获得优化的好处。
总结
在大型应用程序中，如优步骑手应用程序，由于高级语言特征和调用约定，众多机器代码重复模式，要命名一些常见原因。在全程级别应用时，机器概述，显着降低了应用二进制大小。反复应用机器概述进一步降低代码大小。优步已成功地在生产中使用这些优化，并且有助于保持控制的应用规模，享受数百万日常用户。我们优化的好处随着时间的推移而增长，使得它们在快速增长的代码基础上进行代码大小和所需的高效。我们的规模减少优化对应用程序性能没有负面影响。
代码大小优化一直是编译器技术的核心，几十年来，但工作较少的工作要检测错过了机会在代码大小。在整个程序级别上观察复制的机器代码序列，为精确和量化重复的代码模式并将其归因于不同的代码转换层开辟了新的途径。
状态
本文讨论的优化要么已经上游到LLVM或在上游的过程中。https://reviews.llvm.org/D71219https://reviews.llvm.org/D7102https://reviews.llvm.org/D71217https://reviews.llvm.org/D94202
我们已经提出了我们的工作在2019年的LLVM开发商的会议中。
一个纸描述我们优化的技术细节及其普遍适用性发表在《代码生成和优化国际研讨会论文集》(CGO ' 21)(978-1-7281-8613-9/21/$31.00/©2021 IEEE)。请使用下面的引用工作。
Milind Chabbi，Jin Lin和Raj Barik，“生产IOS移动应用程序的代码大小优化的经验”，在国际代码生成和优化研讨会（CGO'21），Birtual Conference，Feb-Mar 2021年。
