Floo：计算记忆化技术让手机APP更快！

本篇文章于2022年发表在Mobisys国际会议上，普林斯顿大学和利福尼亚大学洛杉矶分校在系统和网络领域的Murali Ramanujam等学者，在这篇文章中分享了他们在移动应用程序性能优化方面的最新进展。本文从一个新颖的优化视角出发，观察到在移动应用程序和操作系统中执行源代码导致的计算延迟对应用程序的响应能力产生了越来越大的影响。为了解决这个日益恶化的瓶颈，本文提出了 Floo，这是一个自动将“记忆化”技术集成到应用程序二进制文件中的系统，从而减少了响应延迟敏感的用户交互所需的计算量。Floo 不仅可以确保所有重用计算的正确性，还通过屏蔽缓存查找开销和高缓存命中率获得了最大的潜在加速效益。

01 背景 动机

客户端计算延迟是交互响应时间的瓶颈

移动应用程序成功的关键因素之一是它们快速响应用户交互的能力，但目前大多数用户仍在反映应用程序的表现仍落后于预期，近一半应用程序的交互响应时间超过3秒。

从底层出发，应用程序以事件驱动的方式运行，用户通过设备传感器（例如屏幕、麦克风）与应用程序交互，这些交互触发计算和网络获取，递归解决，直到交互被完全处理，交互响应时间（IRT）包括如下图所示的部分。

最近的一波研究重点在解决应用程序处理用户交互过程中的网络瓶颈，从他们的研究中我们发现客户端计算是导致应用程序响应速度欠佳的主要原因，分别占 WiFi 和 LTE 网络中位响应时间的 63.4% 和 43.8%。

解决客户端计算延迟的关键洞察在于应用程序计算完全在应用程序二进制文件和操作系统的源代码（很少更新）中执行，而不是在每次交互过程中下载的文件和程序。因此随着时间的推移，与用户的交互延迟表现出相当大的稳定性。

更具体地来解释这一点，响应用户交互而执行的计算由调用图定义，该调用图完全由应用程序二进制文件（或 APK）和底层计算堆栈（即 Android 代码库）中的代码指定。调用图嵌入了事件处理函数，这些函数被定义为响应特定的用户交互而触发，例如 onTouch()。这些事件处理程序下方的子图列出了可能遍历以最终解决交互的完整系列的嵌套函数调用和回调。应用交互涉及解析以相应事件处理程序为根的整个子图，除非中间调用中的代码或后续用户操作显式抢占。需要注意的是一个函数可能会出现在调用图中的多个位置。

计算瓶颈将持续存在并恶化

随着移动网络的持续改进并超过能量受限的智能手机 CPU（尤其是随着 5G 的出现），应用程序继续变得更加功能丰富（计算密集型），这种计算瓶颈将持续存在并恶化。

为了证明计算延迟瓶颈会长期存在，首先需要获得网络延迟设置为0ms的实验环境以精确测量计算延迟占整个交互延迟的百分比。为了创建0ms网络延迟环境，使用了back-to-back执行策略，背靠背执行每个交互并记录两次运行的IRT，因为第二次运行利用热网络缓存来最小化获取延迟。

本文收集了近几年在应用商店仍可用的APK文件，并使用真实的用户交互跟踪。如图4所示，每个应用程序版本的每次交互计算延迟都在稳步增加。例如，在过去 5 年中，每次应用程序交互的中位数计算时间增加了一倍以上，从 0.6 秒增长到 1.3 秒。

移动网络迅速改善，而手机 CPU 的加速继续受到能源限制的阻碍，所以交互延迟的影响会持续增强。

02 设计方案

解决思路

基于上述关键洞察，解决计算开销的自然解决方案是减少支持每次交互所需的计算量，计算结果记忆化技术可以在用户与应用程序的交互会话期间本地重用客户端计算结果。记忆化，即函数调用的计算重用，记录函数的唯一ID、函数读取的所有变量合集和函数写入的所有变量合计，在交互处理期间为图中遍历的每个节点独立做出记忆决策。

为了保证易用性和可行性，首先需要一种完全自动化的方法，无需任何开发人员的辅助；其次应用程序存在数以百万计的短调用（0.1-7.3ms），记忆化处理不当反而会导致性能下降。因为关键挑战在于：高查询开销，设备资源有限和正确性-加速的权衡。

• 重复之前的计算结果涉及深度参数比较操作，并可能需要针对大量缓存项执行类似分析。光查找开销就能迅速拉长某些调用的低运行时间，消除了好处（实际上导致了减速）。

• 大量的缓存查询会严重消耗移动设备的系统资源，得不偿失的收益给系统带来显著的压力。

• 实用的记忆化要求一种方法来保证正确性，同时尽可能少地避免缓存命中。尽可能早的在不同函数调用之前做出记忆化的决定以产生收益。

当然，并非所有工作负载都适合记忆化。计算必须随着时间的推移固有地重复，以便重复使用结果。此外，用户感知的应用程序操作和生成的应用程序状态应该是一致的，我们必须在保证记忆化正确性的前提下，尽可能提高记忆化的优化效益。

Floo的设计

基于上述设计思路，Floo共包含三大类组件：离线分析组件，缓存管理器组件和前瞻查询引擎。

1. 用于记忆化的离线分析组件

为给定的调用使用记忆化（即填充或查询缓存）需要了解函数在调用完成后将在外部可见的状态上执行的读取和写入操作，例如 Java 堆上的类字段、通过嵌套调用或返回语句传递的值，以及对屏幕或文件系统的更新。为了提取这些信息，Floo 在安装之前需要静态分析应用二进制文件 (APK) 和 Android 平台中的 Java 字节码。

静态分析需要迭代每一行代码以提取读取和写入操作的列表，记录函数参数、返回值和嵌套调用，以尽可能精细的粒度进行跟踪。

• 需要遵循赋值语句来跟踪对不同变量（即变量指向同一个底层对象）读取和写入的别名，跨函数别名跟踪，进行变量的指向分析，确定它们是否指向同一个内存对象。

• Floo 必须记录对外部可见状态的访问，在函数的范围内，可以通过三种方式访问值（基元或对象），每种方式都需要不同的过程来确定外部可见性。

• 不同类的字段代表Java中唯一的全局变量，在给定调用范围之外持续存在。对类字段（静态和实例）的所有访问都是外部可见的，并且必须被跟踪。

• 原语参数作为值传递进函数，只有当底层值最终通过返回、嵌套调用或类字段退出函数时，对它们的访问才在外部可见。

• 分配给函数中创建的原语值或对象值的变量的更新只有在这些更新通过返回语句、调用或添加到类字段退出函数时才会在外部可见。

嵌套函数的合并涉及将嵌套函数的读取和写入添加到父函数的相应集合中，并从父函数的写入集中删除调用。最后，Floo 使用轻量级语句对每个函数进行检测，以收集读取和写入状态，并向计算缓存发出适当的查询或填充消息。

某些函数可能会嵌入对非确定性 API 的调用，这类函数需要从记忆化的过程中排除，因为函数运行时低并且只能容忍最小的记忆化开销，也只有 4.3% 的函数使用非确定性 API。

2.缓存管理器组件

Floo 的缓存管理器在专用线程上运行，并以多线程方式运行以处理传入消息。在每次调用开始时，函数向缓存管理器发出阻塞查询，其中包括 (1) 函数的 Floo 分配的唯一标识符，(2) 每个函数状态变量的 {name, current value, type} 三元组列表。对象类型的参数会先通过序列化函数的哈希码进行比较，以期望快速提取失败的匹配。

在缓存未命中时，函数正常执行，在调用终止前，Floo 为每个变量聚合上述三元组，并在函数的预定写入状态下嵌套调用，将此信息发送到缓存以形成反映此调用的新缓存项。在命中时，缓存管理器返回对应缓存项的写入集中所有变量的三元组，通过执行分配或列出的调用直接应用每次写入。在发送缓存消息时，Floo 将读写器锁应用于对象，直到缓存管理器在其上下文中生成副本，从而排除与其他线程的竞争。

2.1 快速缓存查询

为了有效地执行给定的查询，计算缓存是使用自定义数据结构组织。缓存条目根据其功能是驻留在 AOSP 还是应用程序定义的代码中进行分区。在每个映射中，存在一个由函数 id 键控的映射，每个 id 指向一组缓存条目，每个函数的条目都表示为类似 trie 的结构。

trie型结构的好处是在比较缓存项和查询变量时：如果不匹配，可以快速消除所有包含不匹配值的项，而无需进一步分析；如果匹配，不需要再次比较这一变量，可以立即删除所有其他具有不同值的项。缓存管理器会优先考虑快速失败的轻量级比较，先是原语，再是哈希码，最后是深度比较。

2.2 控制流感知缓存

目前在线记忆化方法有可能会错过正确的缓存命中，缓存条目列出了函数可以基于离线静态分析进行的所有可能的读取和写入，而不是在填充调用期间实际执行的那部分。因此，如果一个函数可以读取𝑎、𝑏和𝑐，但调用只能读取𝑎和𝑏，那么𝑐的值不应影响该调用的给定缓存条目的可用性。

为了解决这个问题，使用 Floo 的缓存项是控制流感知的，只记录每次调用期间实际进行的读取和写入状态。Floo在查询时仍然必须包含函数所有可能读取状态的保守集合，并定义了一个新的缓存命中标准：如果查询和给定条目之间的交集中的所有变量都具有相同的值，则可以安全地将该条目视为命中，并且可以停止查询执行而不考虑任何其他条目。

3. 前瞻查询引擎

阻塞缓存查询通常会超过大多数应用程序调用的亚毫秒运行时间，为了克服这个问题，Floo 结合了一个前瞻引擎，有机会为即将到来的函数调用提前执行查询。

Floo 提取应用程序的调用图并将其存储在前瞻引擎的内存中，还要了解调用图中当前执行的位置。根据事件触发函数onTouch()获取相应子图的根，并维护一个指针指向当前计算的位置，随后根据缓存查询中嵌入的函数 ID 进行更新。

由于某些函数在预测查询之前其变量的访问状态一直会变化，因此在决定对函数 𝑓𝑢𝑛𝑐 的下游调用执行查询时，前瞻引擎从当前指针遍历调用图，直到 𝑓𝑢𝑛𝑐 并聚合所有经历过函数的写入状态。调用图解析中的任何不确定性都通过考虑所有可能的遍历来解决。𝑓𝑢𝑛𝑐 的读取集中没有出现在聚合写入集中的任何变量都将使用已知且可以立即收集的值，其他值分配通配符 *，有通配符的查询可以返回多个匹配项，返回项存储在 Floo 缓存的一小部分，称为微缓存。

4.缓存管理

Floo 采用了自定义缓存准入和驱逐策略，通过利用一些经验观察来最大限度地提高有限资源的加速效益。

• 某些函数在其调用过程中几乎从未在缓存中命中，为了减少对缓存内存和线程资源的压力，Floo 的缓存管理器会在每个函数的初始条目添加到缓存后跟踪其命中率。如果该命中率低于预定义的阈值（5%），Floo 将从记忆化过程中停用该函数，并删除其缓存。Floo 会定期重新激活此类功能并重新启动跟踪以应对应用程序或用户的更改。

• 由于缓存空间有限，Floo统计缓存项可能产生的加速收益效用，这与命中数和单次命中加速相关。以最低的开销收集过去的加速信息，在剔除缓存项时有限剔除效用最低的项

03 实验评估

实验评估环境的实现

首先，使用 apktool 将每个应用程序的 APK 分解为 .𝑠𝑚𝑎𝑙𝑖 文件来提取 Java 字节码，从相应的𝑑𝑒𝑥 文件中提取AOSP代码的字节码文件。然后通过 Soot 将两个来源的字节码转换为称为 Jimple 的中间表示，并在其上执行静态分析和检测。随后，将更新的应用定义代码与 Floo 缓存管理器和前瞻引擎的字节码版本组合成一个新的 APK。离线分析组件包含约 1100 行 Java 代码，缓存管理器和前瞻引擎共同使用约 4600 行 Java 代码实现，缓存条目使用 Kyro v5 持久化到磁盘。

交互响应时间通过使用 ffmpeg 记录手机屏幕并跟踪非动态像素的视觉变化何时停止来测量。

在每个实验中随机应用交互跟踪记录，等待 𝛿 （0~24不等）小时重复此操作，每个应用总共测量 5 次跟踪。Floo 默认被授予访问 32 个设备线程和 512 MB 内存的权限。

加速效果性能测试

图 11 显示了 Floo 减少应用程序计算延迟的能力。在所有考虑的条件下，每个应用交互的中位数和第 95 个百分位的总计算时间加速中位数分别为 36.9-43.8%（0.46-0.54 秒）和 68.6-77.6%（0.86-0.98 秒）。

从上图还能分析出，Floo 在 Note 9 上的加速比 Pixel 5 略大，因为前者拥有较慢的 CPU，从而增加了 Floo 带来的每次缓存命中的有效时间节省。对于给定的手机，在 WiFi 上的加速比在 LTE 上更大，例如，Pixel 5 的中位数加速从 36.8% 增长到 42.9%。原因是 WiFi 上的往返时间较短，导致客户端计算阻塞的时间更长。

感兴趣的朋友可以通过原文查阅更多更详细的信息。

04 总结

随着移动应用程序的功能不断复杂和移动网络速度（5G，WiFi6）的飞速改进，移动应用程序响应时间的瓶颈更多的体现在客户端计算上，计算延迟随着时间的推移又表现出很大的稳定性，因为它们是在几乎不变的代码库中执行。为了解决这个日益恶化的瓶颈，本文提出了 Floo，一个自动将记忆化集成到应用程序二进制文件中的系统，以减少响应延迟敏感的用户交互所需的计算量。Floo 的关键是它的技术可以同时确保所有重用计算的正确性，同时通过屏蔽缓存查找开销和高缓存命中率获得最大的潜在加速。同时Floo 采用的机制有助于促进下一代性能优化研究。

The End

致谢

感谢本次论文解读者，来自华东师范大学的硕士生李行，主要研究方向为跨设备存储管理。