通过 Instruments 优化 CPU 性能

通过 Instruments 优化 CPU 性能

了解如何借助 Instruments 中的两个新硬件辅助工具，针对 Apple 芯片来优化你的 App。我们将首先介绍如何分析你的 App，然后深入介绍通过 Processor Trace 调用的每个函数。此外，我们将讨论如何使用 CPU Counters 的各个模式来分析代码中的 CPU 瓶颈问题。

章节
- 0:00 - 简介与内容安排
- 2:28 - 性能思维
- 8:50 - 分析器
- 13:20 - Span 类型
- 14:05 - Processor Trace
- 19:51 - 瓶颈分析
- 31:33 - 总结
- 32:13 - 后续步骤
资源
相关视频

WWDC25
WWDC24
- 探索 Swift 性能
WWDC23
- 使用 Instruments 分析挂起
WWDC22
- Swift 并发的可视化与优化
大家好我叫 Matt 是一名操作系统内核工程师今天我将教你如何使用 Instruments 来优化 Apple 芯片 CPU 的代码高效利用 CPU 资源可以避免当你的 App 需要处理大量数据或快速响应交互时出现明显的等待延迟但预测软件性能表现很困难这主要有两个原因首先是 Swift 源代码与实际运行代码之间存在多层抽象你编写的 App 源代码会被编译成机器指令最终在 CPU 上执行但你的代码并非孤立运行它会被编译器生成的支撑代码、Swift 运行时以及其他系统框架所增强这些都可能通过内核系统调用来代表你的 App 处理特权操作
这使得你难以评估代码所依赖的软件抽象层的实际开销第二个难以预测代码性能的原因在于 CPU 执行指令的方式在单个 CPU 内部功能单元会并行工作以实现高效指令执行为此指令会采用乱序执行方式仅保持表面上的顺序执行此外 CPU 还受益于多层内存缓存机制来确保数据快速访问这些特性能够大幅加速常见的编码模式比如线性内存扫描或针对罕见条件的防御性检查如提前退出但某些数据结构、算法或实现方式若不经仔细优化甚至彻底重构 CPU 将难以高效执行我们将介绍为 CPU 优化代码的正确路径首先会探讨如何开展性能调查以数据为导向优先聚焦最具提速潜力的部分接着回顾传统的性能分析方法这是识别代码中 CPU 过度消耗的很好的切入点为了更深入分析并填补性能分析的盲区我们将使用 Processor Trace 记录每条指令并衡量软件抽象层的开销最后借助升级版的 CPU Counters 工具来分析 CPU 瓶颈掌握算法微观优化的技巧让我们首先建立正确的性能调查思维模式第一步是保持开放的心态：性能瓶颈的源头往往出人意料收集数据来验证假设并确保你对代码执行过程的心智模型是准确的
举例来说除了单线程 CPU 性能外还需考虑其他可能导致减速的因素线程和任务除了在 CPU 上执行外还可能因阻塞而等待资源如文件或共享可变状态的访问 “Swift 并发的可视化与优化” 讲座介绍了分析任务“脱 CPU”原因的工具
当线程解除阻塞、在 CPU 上运行时也可能存在 API 误用问题比如为代码设置了错误的服务质量等级或隐式创建了过多线程更多详情请阅读有关调节代码性能的文档但如果问题出在效率上你要么需要更改算法及关联的数据结构要么改进实现方式即算法在编程语言中的具体表达借助工具来确定应该优先关注哪个方向试试用 Xcode 内置的 CPU 监视器检测用户与 App 交互时是否存在 CPU 高负载情况若需分析线程间的阻塞行为及最终解除阻塞的线程请使用 System Trace 工具
而针对影响 UI 或 App 主线程的问题则使用专门的 Hangs 工具关于如何确认 App CPU 使用率需要优化的具体方法请参考“使用 Instruments 分析挂起”讲座但即使有工具的指导实施优化时也需谨慎激进的微观优化可能使代码难以扩展和维护且往往依赖于脆弱的编译器优化如自动向量化或引用计数消除在着手侵入式的微观优化前不妨探索能否彻底规避慢速操作先思考这段代码为何需要执行或许能直接删除这段代码根本不做这项工作感谢观看本次讲座…… 开个玩笑但说真的虽然这通常不现实却能有效检验你对这项工作结果重要性的预判
你也可以尝试将工作推迟到关键路径之外执行或仅在结果对用户可见时才执行同样预先计算数值也可以掩盖实际完成工作所需的时间甚至可能涉及在构建时直接固化某些值不过这些方法可能会导致不必要的功耗增加或增大 App 的下载体积对于输入相同的重复操作缓存是另一种解决方案但往往会带来新的难题比如缓存失效或内存占用增加当你已经穷尽一切方法仍无法避免在性能敏感场景下执行这些工作时就需要让 CPU 更快地完成任务这也正是我们今天要重点讨论的优化工作应优先针对那些对用户体验影响最大的代码通常是用户与 App 交互关键路径中会感知到性能问题的部分但也可能是那些耗电的长时间运行操作在本讲座中我们将以预先生成的整数列表的搜索为例展开分析因为它正处在我 App 的关键路径上
我的 App 已经采用了二分查找这一经典算法它通过有序数组不断对半缩小搜索范围来定位元素以这个包含 16 个元素的数组为例我们要搜索数字 5 所在的元素首先 5 小于数组中间元素 20 说明目标必在前半部分 5 又小于前半部分中间元素 9 因此目标应在数组的前 1/4 区域在与数字 3 比较后仅用 4 步就锁定了匹配元素这是我 App 中某个框架提供的二分查找实现它是一个独立的函数它的参数命名采用了 “finding a needle in a haystack” (大海捞针) 的比喻支持在 haystack 这个集合中搜索可比较的 needle 这一算法跟踪两个变量： start 标记当前搜索范围的起始位置 length 表示待搜索区域的剩余元素数量当存在待搜索元素时它检查搜索空间的中间值若 needle 小于这个值保持 start 不变将搜索空间减半若 needle 等于中间值元素被找到返回中间索引否则将 start 调整至中间元素后一位同时减半搜索空间
我们将准备逐步优化这一算法通过比较每秒完成的搜索次数或搜索吞吐量来验证每个优化步骤是否有效优化不必追求每次都有巨大飞跃有些优化可能很难量化但微小的优化积累起来也会产生显著效果
为支持持续优化我编写了自动化测试来测量搜索吞吐量测试环境无需特别复杂只需获得性能的评估即可这个 repeat-while 循环会持续调用搜索闭包直到达到指定时长我在搜索闭包调用处使用了 OS 标记区间方便工具精准定位待优化的测试代码段我选择了“兴趣点”类别因为 Instruments 默认集成了这个功能计时部分采用 ContinuousClock 与 Date 不同它不会回退且开销极低这个方案虽简单却能有效收集算法性能的粗略数据测试命名为 searchCollection 模拟了 App 二分查找用例我们将运行搜索 1 秒钟并为标记添加描述性名称以便在同一记录中运行多组测试闭包内的循环会反复调用二分查找函数从而分摊时间检测的开销现在让我们在 Instruments 分析器下运行这个测试分析二分查找的 CPU 表现现有两个专注于 CPU 分析的性能分析器可供选择： Time Profiler 和 CPU Profiler 经典的 Time Profiler 工具基于计时器定期对正在系统 CPU 上运行的内容进行采样在本例中我们看到两个 CPU 上正在执行某些任务每次采样时 Time Profiler 会捕获每个 CPU 上运行线程的用户空间调用栈
随后 Instruments 可以将这些采样数据可视化为调用树或火焰图通过详情视图近似展示需要针对 CPU 性能进行优化的关键代码这种方法有助于分析工作负载随时间分布的情况或识别哪些线程同时处于活跃状态但使用计时器采样调用栈存在一个“混叠”的问题混叠是指系统中某些周期性任务的执行节奏与采样计时器的频率同步在这里蓝色区域实际占据了大部分 CPU 时间但采样器捕获调用栈时恰巧总是遇到橙色函数正在执行这导致橙色函数在 Instruments 调用树中的占比被错误放大
为解决这个问题可改用 CPU Profiler 它基于各 CPU 的时钟频率自主采样建议在 CPU 性能优化时优先选择 CPU Profiler 而非 Time Profiler 因为它的采样更精确并能更公平地衡量消耗 CPU 资源的软件
这些钟形标记代表 CPU 周期计数器对当前运行调用栈的采样时刻 Apple 芯片采用非对称 CPU 设计部分核心会以较低时钟频率运行以提升能效自动升频的单个 CPU 核心会被更频繁采样彻底避免 Time Profiler 对高速运行 CPU 采样不足的问题我们将使用 CPU Profiler 来找出二分查找函数中哪些部分消耗了最多的 CPU 周期在 Xcode 的测试导航器中你可以通过辅助点按测试名称然后选择“Profile”选项从单元测试启动 Instruments 本例中我们将选择 Profile searchCollection
这会打开 Instruments 并显示模板选择界面我将选择 CPU Profiler 在录制器设置中我们将切换到延迟模式以降低开销然后开始录制分析器默认的即时模式有助于确认 App 的交互是否被捕获但对于在与 Instruments 同一台机器上运行的自动化测试我们希望等到录制结束后再进行分析从而尽量减少工具可能带来的额外开销 Instruments 中的新文稿界面往往令人望而生畏窗口分为上下两部分上半部分显示时间轴上的活动轨迹每个轨迹可以包含多个通道其中通过图表来展示不同级别或区域
在时间轴下方是详情试图其中显示当前检测时间范围内的摘要信息所有扩展详情都会在右侧呈现为了快速定位我们可以在“兴趣点”轨迹中找到执行搜索操作的区间辅助点按这个区间可选择设置检测范围这样下方详情试图将仅显示标记区间内捕获的数据点按测试运行进程对应的轨迹后时间轴下方的详情试图会展示 CPU 性能分析数据这个视图以调用树的形式呈现测试过程中各函数被 CPU 周期计数器采样的情况按住 Option 键并点按首列函数旁的 V 形图标调用树会持续展开直至样本计数出现显著差异的第一个节点这个位置最接近我们的二分查找函数我们将通过点按二分查找函数名称旁边的箭头并选择“聚焦子树” 来集中分析这个函数每个函数的权重由样本计数乘以每次采样间隔的周期数决定调用树显示二分查找函数调用了大量处理 Collection 类型的函数占据了相当比例的样本协议见证的调用约占样本的四分之一还有分配甚至数组对 Objective-C 类型的检查如果我们改用更匹配搜索数据特征的容器类型就能避免数组和泛型带来的开销让我们尝试新的 Span 类型当元素在内存中连续存储时许多数据结构都符合这一特性可以用 Span 替代 Collection 它本质上是一个基址和计数的组合但同时能防止内存引用逃逸或泄漏到使用它的函数之外如需深入了解 Span 请观看 “优化 Swift 代码的内存使用和性能”讲座改用 Span 只需要将 haystack 和 return 类型改为 Span 算法本身无需修改
这一微小调整能使搜索速度提升四倍但当前版本的二分查找仍对 App 有影响我想进一步分析 Span 的边界检查是否导致了额外开销为此我们将切换到一款名为 “Processor Trace”的新工具从 Instruments 16.3 开始 Processor Trace 可以完整追踪应用进程在用户空间执行的所有指令这标志着性能测量方式的根本性变革：无采样偏差对 App 性能的影响极低仅有 1% 的影响 Processor Trace 需要依赖特定 CPU 功能目前仅支持 Mac、搭载 M4 的 iPad Pro 或搭载 A18 的 iPhone 开始前需先在设备上启用处理器追踪功能在 Mac 上打开“隐私与安全性” 和“开发者工具”下的设置在 iPhone 或 iPad 上这个设置位于“开发者”部分为了获得最佳的 Processor Trace 使用体验建议将追踪时间控制在几秒钟内与 CPU Profiler 的采样方式不同你无需批量处理任务：即使是单个需要优化的代码实例也足以进行分析让我们对 Span 版本的二分查找运行 Processor Trace 这次测试只需少量迭代即可要分析这个测试我会在行号边栏中辅助点按测试图标这会显示与之前相同的菜单但比切换导航栏更便捷选择 Processor Trace 模板后
即可开始录制
Processor Trace 需要处理大量数据因此捕获和分析过程可能需要一些时间 Processor Trace 让 CPU 记录每个分支决策同时还会记录周期计数和当前时间以跟踪 CPU 在每个函数中花费的时间随后 Instruments 会结合 App 和系统框架的可执行二进制文件重构程序的执行路径并为每个函数调用标注消耗的周期数和耗时我们之所以限制追踪时间是因为即使 CPU 已尽可能精简记录的信息对于一个多线程应用程序而言仍可能产生每秒数 GB 的数据量现在文稿已准备就绪让我们放大时间轴以检查二分查找的函数调用情况由于搜索操作在整个录制中仅占极小部分我们需要在时间轴下方的详情试图中通过“关注区域列表”找到它然后辅助点按对应行并选择“设置检测范围并缩放” 为了定位执行二分查找的线程我们将辅助点按“启动线程”单元格然后选择“在时间轴中固定线程”
Processor Trace 会为每个线程轨迹新增一个函数调用火焰图因此我将向上拖动固定线程的分隔线为它腾出空间
Processor Trace 以火焰图的形式直观展示代码执行情况火焰图是一种用于呈现函数开销与调用关系的图形化工具：条状宽度表示函数执行耗时纵向层级代表嵌套调用栈但大多数火焰图显示采样数据它的成本仅是基于样本数的估算值但 Processor Trace 的时间轴火焰图截然不同：它能精确还原 CPU 实际执行的调用时序各颜色条块代表不同的二进制来源：棕色表示系统框架洋红色表示 Swift 运行时与标准库蓝色表示编译到 App 二进制或自定义框架中的代码当前追踪结果的第一部分显示了发出标记的开销因此我们进一步放大检测范围末尾附近的二分查找代码部分按住 Option 键并在时间轴上点按拖动来放大
在 10 次迭代中我可以任选一个二分查找函数调用通过辅助点按设置检测范围并进行缩放这正是 Processor Trace 的强大之处即便某个函数仅运行几百纳秒我们也能完整捕获所有调用过程虽然可以进一步放大分析但让我们直接查看时间轴下方的函数调用摘要这个摘要以表格形式呈现与时间轴相同的信息其中包含短时间调用的完整函数名称我将按周期数对这个表格进行排序
最初关于边界检查导致了性能下降的假设是错误的当前二分查找的实现仍然存在协议元数据开销且无法内联数值比较操作这些操作最终占据了搜索总周期数相当大的比例这是因为泛型 Comparable 参数未针对具体元素类型进行特化
由于我的代码位于 App 链接的框架中 Swift 编译器无法为调用方传递的类型生成专用的二分查找版本
当框架代码出现这类开销时你应该为框架函数添加可内联标注以在框架客户端的二进制文件中生成特化实现
但内联会使代码分析变得复杂因为代码会与调用方混合为了避免测试工具中的内联干扰我会将这个函数手动特化为 App 和测试使用的 Int 类型并使用新函数名虽然代码丧失了很多通用性但速度提升了约 1.7 倍我们仍需持续优化因为二分查找仍然是导致 App 卡顿的因素之一花如此多时间优化单个函数看似有些奇怪随着持续评估和收集更多数据你可能会发现其他代码才是性能瓶颈所在我们特化的 Span 二分查找在 Processor Trace 中并未显示任何意料之外的函数调用因此需要从 CPU 执行层面理解代码的运行机制才能进一步优化我们可以使用 CPU Counters 工具来检测代码在 CPU 运行时遇到的瓶颈在再次使用 Instruments 之前我们需要先建立对 CPU 工作原理的心智模型从根本上说 CPU 只是按照指令列表执行操作修改寄存器和内存数据并与外围设备交互
当 CPU 执行指令时它需要遵循一系列步骤这些步骤大致可分为两个阶段首先是指令交付阶段确保 CPU 有指令可执行然后是指令处理阶段负责实际执行这些指令在指令交付阶段 CPU 会获取指令将指令解码为更易于执行的微操作大多数指令会被解码为单个微操作但有些指令会执行多个操作如发起内存请求递增索引值要处理一个微操作它会被发送到映射与调度单元进行路由和派发随后操作会被分配到执行单元或需要访问内存时的加载-存储单元
如果 CPU 必须串行执行这些阶段才能开始下一次获取效率将会非常低下因此 Apple 芯片采用了流水线技术当一个单元完成当前操作后立即处理下一个操作保持所有单元持续处于工作状态
这种流水线设计和执行单元的冗余复制支持了指令级并行
这与通过 Swift Concurrency 或 Grand Central Dispatch 实现的进程或线程级并行有本质区别后者依赖多个 CPU 核心执行不同的操作系统线程指令级并行性让单个 CPU 能利用原本可能闲置的单元时间并高效利用硬件资源保持流水线各环节满载你的 Swift 源代码并不直接控制这种并行机制而是必须帮助编译器生成一个合适的指令序列
遗憾的是由于 CPU 各单元间的复杂交互关系可并行化的指令序列并不总是直观可见单元间的每个箭头都代表着流水线中可能发生停滞的位置这些“瓶颈”会限制可实现的并行度
要确定哪些性能瓶颈与我们的工作负载相关 Apple 芯片 CPU 能够统计每个执行单元中发生的特定事件及指令的其他特征 CPU Counters 工具通过读取这些计数器将它们转化为更高层次的性能指标今年我们为这些计数器新增了预设模式让它们更易使用 Instruments 采用一种称为 “瓶颈分析”的引导式迭代方法来分析代码性能现在我们就用它来查明为何二分查找仍然运行缓慢尽管它没有任何明显的函数调用开销 CPU Counters 工具采用工作负载采样机制因此我们需要重新使用之前与 CPU Profiler 配合的测试框架来再次测量吞吐量
现在让我们用 Instruments 对特化 Span 实现的测试用例进行分析
我们将选择 CPU Counters 模板
如今它提供了包含精选测量模式的引导式配置
若想了解每个模式的具体功能只需点按模式选择框旁的信息图标即可查看相关文档这就开始计数检测吧
初始的 CPU 瓶颈模式将 CPU 的工作负载分解为四大类这些类别涵盖了 CPU 所有潜在的性能表现维度 Instruments 会以彩色堆叠条形图和详情视图中的汇总表来呈现这些分类数据在记录过程中 Instruments 将采集测试线程的 CPU 计数器数据并将它们转化为具体的瓶颈占比百分比我们将像之前一样使用“兴趣点” 来定位和缩放选择搜索操作区域
接着将执行二分查找算法的线程固定到时间轴上
当悬停在对应的 CPU 瓶颈轨道时可以看到 “废弃瓶颈”指标占比较高下方详情视图展示了检测范围内的指标聚合数据选择“废弃瓶颈”行后右侧扩展详情视图会显示相应说明 Instruments 还会在时间轴图表上方显示备注信息点按这个备注可在下方查看更多细节这些信息虽然有用但我仍无法确定搜索操作的哪个部分导致了瓶颈在“建议下一模式”列下辅助点按 “已丢弃采样”单元格将出现选项让你以不同模式重新分析工作负载我们来试一下这个模式与 CPU Bottlenecks 略有不同它仍会收集计数器数据但同时会配置计数器来触发采样采样数据仅聚焦于产生无效工作的指令为了定位问题我们再次通过 “兴趣点”确定分析范围
然后选择测试进程路径
并导航到时间线下方的“指令采样”
这里展示的并非调用栈而是直接导致问题的具体指令点按函数名旁的箭头打开 “源代码视图” 即可看到因 CPU 分支预测错误而被采样的源代码在这里 needle 与中间值的比较指令被错误预测要理解这些源代码行为何导致如此多的错误预测我们需要深入了解 CPU
CPU 很“狡猾” 会乱序执行指令之所以指令看起来是按顺序执行的只是因为指令完成后进行了额外的重排序步骤这意味着 CPU 会预先推测接下来要执行的指令负责这项工作的分支预测器通常很准确但当缺乏历史执行规律来判断是否进行分支跳转时就可能选择错误路径
在我们的二分查找算法中循环包含两种分支第一种循环条件在循环结束前通常都会执行因此预测准确率高未在采样中显现问题而针对目标值的检查本质上属于随机分支预测器难以处理也就不足为奇
我已重写循环体消除了那些影响控制流且难以预测的分支这个 If 语句的主体仅根据条件分配值这样 Swift 编译器就可以生成条件移动指令从而避免跳转到不同指令的分支操作而基于条件从函数返回或跳出循环的操作必须通过分支指令实现因此我还移除了提前返回的逻辑我使用了未经检查的算术来避免会终止程序的分支这类微优化往往会使代码变得脆弱易损更不用说还会降低安全性和可读性当我们做出这类改动时应该返回初始的 CPU Bottlenecks 模式来检查它对其他瓶颈指标的影响我已经采集了新版无分支二分查找的跟踪数据现在的速度比带分支的版本快约两倍现在性能瓶颈几乎完全集中在指令处理环节 Instruments 建议我们改用指令处理模式重新分析工作负载
这个模式备注应运行 L1D 缓存未命中采样模式缓存未命中样本显示对数组的内存访问操作正是导致 CPU 无法高效执行指令的根本原因我们来进一步了解 CPU 与内存找出原因
CPU 通过多级缓存体系访问内存这种设计能显著加速对相同地址或可预测访问模式的重复访问它从集成在每个 CPU 核心内部的一级缓存开始这一层级存储容量有限但提供最快的内存访问速度较慢的二级缓存位于 CPU 核心外部提供更大的缓存空间若两级缓存均未命中则需访问主内存访问速度比缓存命中路径慢 50 倍这些缓存还将内存划分为 64 或 128 字节的分段称为缓存行：即使指令仅需读取 4 字节数据缓存也会预加载更多数据以期后续指令需要访问邻近的其他字节
让我们看看这对二分查找算法有何影响在这个示例中蓝色线条代表数组元素灰色胶囊状区域则是 CPU 缓存操作的缓存行
初始状态下整个数组都不在缓存中第一次比较会将一个缓存行及多个元素加载到一级数据缓存但紧接着的下一次比较就会遭遇缓存未命中随后的迭代过程持续出现缓存失效直到搜索范围缩小到单个缓存行大小区域为止二分查找对 CPU 内存层级结构而言是个病态案例
但如果我们能接受对元素重新排序以适配缓存特性就可以将查找点放置在同一个缓存行上这种布局被称为 Eytzinger 布局得名于 16 世纪奥地利一位用这个方式编排家族图谱的家谱学家这种优化并非毫无代价它通过牺牲顺序遍历性能来提升搜索速度因为顺序遍历操作现在反而会出现缓存未命中让我们回到最初的二分查找示例演示如何将有序数组重组为 Eytzinger 布局以中间元素为根节点将二分查找过程建模为树形结构其中每个中点都是子节点 Eytzinger 布局实际上就是这颗树的广度优先遍历序列
靠近树根的元素排列更为紧凑更可能共享缓存行现在再次搜索数字 5 时前三个步骤都在同一缓存行内完成而位于数组末端的叶节点则必然引发不可避免的缓存未命中
我记录的 CPU Bottlenecks 轨迹显示 Eytzinger 二分查找比无分支版本还要快两倍但这个案例揭示了一个有趣的现象从技术层面看性能瓶颈仍然存在于指令处理环节我们虽然优化了缓存友好性但工作负载本质上仍受限于内存带宽
这时应当监控性能表现以确定何时停止转而去优化 App 中的其他代码因为当前的搜索操作已不再影响关键路径性能在这个过程中我们显著提升了搜索吞吐量首先通过 CPU Profiler 检测到从 Collection 切换到 Span 带来的显著加速
接着 Processor Trace 揭示了未特化泛型的开销最后在瓶颈分析的指导下通过微优化实现了质的飞跃总体而言借助 Instruments 我们最终将搜索函数提速约 25 倍要达成这些优化效果我们一开始要秉持正确的思维模式借助工具验证假设逐步建立对抽象成本的直觉认知通过层层递进地使用更精细的工具发现那些容易被忽视但容易解决的开销待软件层面的开销解决后再转向针对 CPU 瓶颈的优化我们逐渐理解甚至开始体谅那些被视为理所当然的 CPU 特性这个顺序很重要：必须确保聚焦 CPU 的工具不会被额外的软件运行时开销干扰
要将这些方法应用到你的 App 请以性能优化的思维收集数据、追踪线索编写性能测试用例以便能反复使用这些 Instruments 进行测量在论坛上反馈工具使用问题请观看我之前提到的讲座以及 WWDC24 关于 Swift 性能的讲座这些都能帮助你构建更精确的心智模型评估 Swift 强大抽象机制的开销若想进一步理解 CPU 如何执行代码请参阅《Apple 芯片 CPU 优化指南》感谢观看愿你享受使用 Instruments 工具在代码的“haystack”中寻找优化“needle”的乐趣

public func binarySearch<E, C>(
    needle: E,
    haystack: C
) -> C.Index where E: Comparable, C: Collection<E> {
    var start = haystack.startIndex
    var length = haystack.count

    while length > 0 {
        let half = length / 2
        let middle = haystack.index(start, offsetBy: half)
        let middleValue = haystack[middle]
        if needle < middleValue {
            length = half
        } else if needle == middleValue {
            return middle
        } else {
            start = haystack.index(after: middle)
            length -= half + 1
        }
    }

    return start
}

7:49 - Throughput benchmark

import Testing
import OSLog

let signposter = OSSignposter(
    subsystem: "com.example.apple-samplecode.MyBinarySearch",
    category: .pointsOfInterest
)

func search(
    name: StaticString,
    duration: Duration,
    _ search: () -> Void
) {
    var now = ContinuousClock.now
    var outerIterations = 0
    
    let interval = signposter.beginInterval(name)
    let start = ContinuousClock.now
    repeat {
        search()
        outerIterations += 1
        now = .now
    } while (start.duration(to: now) < duration)
    let elapsed = start.duration(to: now)
    let seconds = Double(elapsed.components.seconds) +
            Double(elapsed.components.attoseconds) / 1e18
    let throughput = Double(outerIterations) / seconds
    signposter.endInterval(name, interval, "\(throughput) ops/s")
    print("\(name): \(throughput) ops/s")
}

let arraySize = 8 << 20
let arrayCount = arraySize / MemoryLayout<Int>.size
let searchCount = 10_000

struct MyBinarySearchTests {
    let sortedArray: [Int]
    let randomElements: [Int]
    
    init() {
        let sortedArray: [Int] = (0..<arrayCount).map { _ in
                .random(in: 0..<arrayCount)
        }.sorted()
        self.randomElements = (0..<searchCount).map { _ in
            sortedArray.randomElement()!
        }
        self.sortedArray = sortedArray
    }

    @Test func searchCollection() throws {
        search(name: "Collection", duration: .seconds(1)) {
            for element in randomElements {
                _ = binarySearch(needle: element, haystack: sortedArray)
            }
        }
    }
}

13:46 - Binary search in Span

public func binarySearch<E: Comparable>(
    needle: E,
    haystack: Span<E>
) -> Span<E>.Index {
    var start = haystack.indices.startIndex
    var length = haystack.count

    while length > 0 {
        let half = length / 2
        let middle = haystack.indices.index(start, offsetBy: half)
        let middleValue = haystack[middle]
        if needle < middleValue {
            length = half
        } else if needle == middleValue {
            return middle
        } else {
            start = haystack.indices.index(after: middle)
            length -= half + 1
        }
    }

    return start
}

15:09 - Throughput benchmark for binary search in Span

extension MyBinarySearchTests {
    @Test func searchSpan() throws {
        let span = sortedArray.span
        search(name: "Span", duration: .seconds(1)) {
            for element in randomElements {
                _ = binarySearch(needle: element, haystack: span)
            }
        }
    }

    @Test func searchSpanForProcessorTrace() throws {
        let span = sortedArray.span
        signposter.withIntervalSignpost("Span") {
            for element in randomElements[0..<10] {
                _ = binarySearch(needle: element, haystack: span)
            }
        }
    }
}

19:17 - Binary search in Span

public func binarySearchInt(
    needle: Int,
    haystack: Span<Int>
) -> Span<Int>.Index {
    var start = haystack.indices.startIndex
    var length = haystack.count

    while length > 0 {
        let half = length / 2
        let middle = haystack.indices.index(start, offsetBy: half)
        let middleValue = haystack[middle]
        if needle < middleValue {
            length = half
        } else if needle == middleValue {
            return middle
        } else {
            start = haystack.indices.index(after: middle)
            length -= half + 1
        }
    }
    return start
}

23:04 - Throughput benchmark for binary search in Span

extension MyBinarySearchTests {
    @Test func searchSpanInt() throws {
        let span = sortedArray.span
        search(name: "Span<Int>", duration: .seconds(1)) {
            for element in randomElements {
                _ = binarySearchInt(needle: element, haystack: span)
            }
        }
    }
}

26:34 - Branchless binary search

public func binarySearchBranchless(
    needle: Int,
    haystack: Span<Int>
) -> Span<Int>.Index {
    var start = haystack.indices.startIndex
    var length = haystack.count

    while length > 0 {
        let remainder = length % 2
        length /= 2
        let middle = start &+ length
        let middleValue = haystack[middle]
        if needle > middleValue {
            start = middle &+ remainder
        }
    }

    return start
}

27:20 - Throughput benchmark for branchless binary search

extension MyBinarySearchTests {
    @Test func searchBranchless() throws {
        let span = sortedArray.span
        search(name: "Branchless", duration: .seconds(1)) {
            for element in randomElements {
                _ = binarySearchBranchless(needle: element, haystack: span)
            }
        }
    }
}

29:27 - Eytzinger binary search

public func binarySearchEytzinger(
    needle: Int,
    haystack: Span<Int>
) -> Span<Int>.Index {
    var start = haystack.indices.startIndex.advanced(by: 1)
    let length = haystack.count

    while start < length {
        let value = haystack[start]
        start *= 2
        if value < needle {
            start += 1
        }
    }
    
    return start >> ((~start).trailingZeroBitCount + 1)
}

30:34 - Throughput benchmark for Eytzinger binary search

struct MyBinarySearchEytzingerTests {
    let eytzingerArray: [Int]
    let randomElements: [Int]

    static func reorderEytzinger(_ input: [Int], array: inout [Int], sourceIndex: Int, resultIndex: Int) -> Int {
        var sourceIndex = sourceIndex
        if resultIndex < array.count {
            sourceIndex = reorderEytzinger(input, array: &array, sourceIndex: sourceIndex, resultIndex: 2 * resultIndex)
            array[resultIndex] = input[sourceIndex]
            sourceIndex = reorderEytzinger(input, array: &array, sourceIndex: sourceIndex + 1, resultIndex: 2 * resultIndex + 1)
        }
        return sourceIndex
    }

    init() {
        let sortedArray: [Int] = (0..<arrayCount).map { _ in
            .random(in: 0..<arrayCount)
        }.sorted()
        var eytzingerArray: [Int] = Array(repeating: 0, count: arrayCount + 1)
        _ = Self.reorderEytzinger(sortedArray, array: &eytzingerArray, sourceIndex: 0, resultIndex: 1)
        self.randomElements = (0..<searchCount).map { _ in
            sortedArray.randomElement()!
        }
        self.eytzingerArray = eytzingerArray
    }

    @Test func searchEytzinger() throws {
        let span = eytzingerArray.span
        search(name: "Eytzinger", duration: .seconds(1)) {
            for element in randomElements {
                _ = binarySearchEytzinger(needle: element, haystack: span)
            }
        }
    }
}

- 0:00 - 简介与内容安排
- 由于 Swift 源代码与机器指令之间存在多层抽象，以及 CPU 乱序执行指令和使用内存缓存的复杂方式，因此针对 Apple 芯片 CPU 的代码优化非常复杂。 Instruments 可帮助开发者应对这些复杂情况，并支持性能调查，通过分析系统性能来识别 CPU 使用率过高的情况。使用 Processor Trace 和 CPU Counters 工具来记录指令、衡量成本和分析瓶颈，最终提高代码效率并改进 App 性能。
- 2:28 - 性能思维
- 在调查 App 中的性能问题时，保持开放的心态并收集数据来验证假设至关重要。速度变慢可能是由多种因素导致的，例如等待资源的线程受阻、API 滥用或算法效率低下。 Xcode 中的 CPU Gauge 以及 Instruments 中的 System Trace 和 Hangs 等工具对于识别 CPU 使用模式、阻塞行为和 UI 无响应非常有用。由于微优化会使代码更难维护，因此在深入进行微优化之前，最好先探索替代方法。这些替代方法包括避免不必要的工作、通过并发延迟相关任务、预先计算值，以及缓存由复杂操作计算的状态。如果这些策略已用尽，则有必要优化 CPU 密集型的代码。重点优化对用户体验有重大影响的代码，例如用户交互的关键路径。建议采用逐步优化，通过 Xcode 和 Instruments 中的自动化测试和性能指标来衡量进度。
- 8:50 - 分析器
- 为了分析这个讲座中二分查找示例的 CPU 性能，Instruments 中提供了两个分析工具：Time Profiler 和 CPU Profiler。 Time Profiler 会定期对 CPU 活动进行采样，但可能会受到混叠的影响，即周期性任务会扭曲 CPU 使用情况的表示。而 CPU Profiler 则基于 CPU 的时钟频率独立地对 CPU 进行采样，因此更加精确，更适合用于 CPU 优化。在这次分析中，我们选择了 CPU Profiler 并从 Xcode 的测试导航器启动，然后将 Instruments 中的录制模式设置为“延迟模式”，以最大程度地减少开销。讲座中还介绍了 Instruments 中的各个区域，包括时间线视图、轨道和通道，以及显示分析结果的详细信息视图。通过查看“xctest”进程的 Points of Interest 轨道和 Process 轨道，可以识别出示例 App 中执行二分查找的具体区域。详细信息视图中的调用树显示，与“Collection”协议相关的函数会消耗大量 CPU 时间。为了优化性能，建议改用更高效的容器类型，例如“Span”，以避免使用具有写时拷贝语义的“Array”和泛型所带来的开销。
- 13:20 - Span 类型
- Swift 6.2 引入“Span”，这是一种高效利用内存的数据结构，用于表示具有基地址和长度的连续内存范围。在二分查找的输入和输出类型中使用“Span”，可以在不改变算法的情况下将性能提高 400%。接下来，为了进一步优化性能，使用 Processor Trace 工具来分析边界检查带来的开销。
- 14:05 - Processor Trace
- Instruments 16.3 引入了一个名为 Processor Trace 的重要新工具。借助这个工具，你可以在搭载 M4 及更新芯片的 Mac 和 iPad Pro 上，或搭载 A18 及更新芯片的 iPhone 上，全面记录 App 进程在用户空间中执行的所有指令。 Processor Trace 需要特定的设备设置才能启用，并且由于会生成大量数据，最适合用于短时间的会话跟踪。通过记录每个分支决策、周期计数和当前时间，Instruments 可以重建 App 的确切执行路径。数据以火焰图的形式直观呈现，显示了每个函数调用在一段时间内所花费的时间。与使用采样的传统火焰图不同，Processor Trace 的火焰图提供了 CPU 如何执行代码的精确表示。这样，你就能以前所未有的精度识别性能瓶颈。通过对追踪数据的分析可以清楚地看到，协议元数据开销以及数值比较操作无法内联是导致特定二分查找函数显著变慢的主要原因。为了解决这个问题，该函数被手动特化为 Int 类型，从而将性能大幅提高了约 170%。然而，由于 App 的二分查找实现仍然会导致 App 的整体速度变慢，因此仍需要进一步优化。
- 19:51 - 瓶颈分析
- Apple 芯片 CPU 分两个阶段执行指令：指令传递和指令处理，这两个阶段采用流水线技术以实现指令级并行。这允许同时处理多个操作，从而最大限度地提高效率。但是，流水线中可能会出现瓶颈，导致操作停滞并限制并行度。 CPU Counters 工具通过对每个 CPU 单元中的事件进行计数来帮助识别这些瓶颈。它使用预设模式来衡量 CPU 性能，并将工作划分为几大类。当你分析采样数据时，它们可以查明导致问题的具体指令，例如错误预测的分支方向，这可能导致浪费周期和性能下降。 CPU 使用分支预测器乱序执行指令以提高性能。然而，随机分支可能会误导这些预测器。为了缓解这种情况，代码被重写以避免难以预测的分支，最终得到一个无分支的二分查找，速度大约提高了一倍。由于 CPU 利用层次化的缓存来加快数据检索速度，App 的优化重点转向内存访问。二分查找算法的访问模式对于这种层次结构来说是病态的，导致频繁出现缓存未命中。通过使用 Eytzinger 布局重新排列数组元素，缓存局部性得到了改善，二分查找的速度又提高了 200%。尽管进行了这些重大优化，但代码在指令处理方面仍然存在技术瓶颈，但通过各种分析和微优化技术，整体搜索函数的速度提高了约 2500%。
- 31:33 - 总结
- 通过首先测量和优化软件开销，然后专注于 CPU 的性能瓶颈，二分查找 App 的性能得到了提升。这一过程解决了那些容易被忽视的问题，并使代码更贴合 CPU 架构的特点。
- 32:13 - 后续步骤
- 要优化 App，请使用 Instruments 来收集数据、运行性能测试和分析结果。你还可以观看有关 Swift 性能的讲座，并阅读开发者文档中的《Apple 芯片 CPU 优化指南》。如有疑问或建议，也可以前往 Apple 开发者论坛。

章节

资源

相关视频

WWDC25

WWDC24

WWDC23

WWDC22