FaceBook 安卓 Feed 流的内存优化实践

大量的用户每天在 Android 设备上使用 Facebook，滚动新闻 Feed 流页面，包括个人资料，活动，页面和组，与他们关心的人员和信息进行互动等一系列行为。 所有这些不同的 Feed 类型都由 Android Feed Platform 小组创建的平台提供支持，因此我们对 Feed 平台进行的任何优化都可能提高我们的应用程序的性能。 我们专注于页面的滚动性能，因为我们希望用户在滚动他们的 Feed 流页面时有一个平滑的体验。

为了帮助我们实现这一点，我们有几种自动化工具，可以跨不同的场景和不同的设备在 Feed 平台上运行性能测试，测量代码在运行时内存使用，帧速率等方面的运行情况。 其中一个工具 Traceview 显示了我们的程序对 Long.valueOf ()函数的调用次数相对较多，这导致对象在内存中累积并导致应用程序卡顿停止等。 这篇文章描述这个问题，我们权衡了各种潜在解决方案之后，对改进 Feed 流平台而进行的一系列优化。

便利性带来的缺点

我们从 Traceview 的一个方法分析报告中注意到：facebook 的 app 对 Long.valueOf ()函数的大量调用。之后，我们进行了又进一步的测试，证实了当我们滚动新闻列表时，Long.valueOf ()方法的调用会意外升高。

当我们查看堆栈时，我们发现这个函数没有被直接的从 Facebook 的代码调用，而是隐式地由编译器插入的代码。 在分配长整型对象的原始长值时调用此函数。 Java 支持对象和原始的简单类型（例如，整数，字符），并提供了一种在它们之间无缝转换的方式。 这种方式称为自动装箱，因为它将基本类型装箱为相应的类型的对象类型。 虽然这是一个方便的开发功能，但是它同时也创建了开发人员不知道的新对象。

在对一个示例应用程序的堆栈中发现 Long 对象有大量的存在; 虽然每个对象本身都不大，但是存在的大量的 Long 对象占据了应用程序在堆中的大部分内存。 对于运行 Dalvik 的设备来说，会有很大的影响。 与 Android 的 ART 运行时环境不同，Dalvik 没有分代式垃圾回收机制 ，造成很多小对象的垃圾回收效率很低。 当我们滚动新闻 Feed 流，会造成 Long 对象数量增加，垃圾收集将导致应用程序卡顿来从内存中清除未使用的对象。 积累的对象越多，垃圾收集器将越来越频繁地暂停应用程序，导致卡顿使得户体验不佳。

幸运的是，Traceview 和 Allocation Tracker 等工具可以帮助我们找到这些函数调用的位置。 在查看了这些自动装箱事件的根源之后，我们发现大多数成因都是：将 Long 类型的基本类型数据插入 HashSet 数据结构中造成。 （我们使用这个数据结构存储新闻 Feed 的哈希值，稍后检查某个哈希是否已经在 Set 中。）HashSet 提供对具体 feed 的快速访问。 由于哈希计算并存储在一个原始的长变量中，然而我们的 HashSet 仅适用于对象，所以当调用 set.put(Hash )时，我们会得到不可避免的自动装箱。

作为一个解决方案，可以使用基本数据类型而不是对象类型的 Set 实现，但是结果并不像我们预期的那么简单。

目前的解决方案

有几个现有的 Java 库为原始数据类型提供了 Set 实现。 几乎所有这些类库都是 10 多年前创建的，当时在移动设备上运行的唯一的 Java 是 J2ME。为了确定可行性，我们需要在 Dalvik / ART 下进行测试，并确保它们在资源更受限的移动设备上表现良好。 我们创建了一个小型测试框架来帮助将这些库与现有的 HashSet 进行比较。 结果表明，这些库中的一些库具有比 HashSet 更快的运行时间，并且具有较少的 Long 对象，但是它们仍然在内部分配了很多 Long 对象。 例如，Troow 库中的一部分 TLongHashSet 在测试时分配了大约 2 MB 的对象，共有 1,000 个 item

对其他的类库进行测试，包括 PCJ 和 Colt, 显示了类似的结果。

现有的解决方案不符合我们的需求。 我们考虑是否可以创建一个新的 Set 实现，并针对 Android 进行优化。 在 Java 的 HashSet 中，使用单个 HashMap 来实现一个相对简单的实现。

向 HashSet 添加新 item 意味着将其添加到内部 HashMap，其中对象是关键字，而 HashSet 的实例是该值。 要检查对象成员身份，HashSet 将检查其内部 HashMap 是否包含对象作为键。 可以使用 Android 优化的 map 和相同的原则来实现 HashSet 的替代方案。

引进 LongArraySet

你可能已经熟悉了 LongSparseArray，它是 Android 支持类库中的一个类，用作使用 long 类型作为 key 的 map。 使用示例

LongSparseArray 的工作方式与 HashMap 不同。 当调用 mapHashmap.get(KEY5 )时，下图说明了如何在 HashMap 中找到该值：

当使用 HashMap 上的键检索值时，它使用密钥的哈希值作为索引访问数组中的值，即 O（1）时间复杂度的的直接访问。 对 LongSparseArray 进行相同的调用如下所示：

LongSparseArray 使用二分搜索，运行时间为 O(log N )的时间复杂度操作搜索排序密钥数组的密钥值。 数组中的键的索引值用于查找 values 数组中的值。

HashMap 分配一个大数组，以避免 hash 冲突，但是这样导致搜索速度较慢。 LongSparseArray 分配两个小数组，使其内存占用更小。 但是为了支持其搜索算法，LongSparseArray 需要在连续的内存块中分配其内部数组。 添加更多的 item 将需要在当前空间不足的情况下分配新的数组。 LongSparseArray 的工作原理使得它在保存超过 1,000 个项目时效率下降，这些差异对性能有更重要的影响。（您可以在官方文档中了解有关 LongSparseArray 的更多信息，并通过观看 Google 的简短视频。）

由于 LongSparseArray 的键是原始 long 类型，所以我们可以使用与 HashSet 相同的方法创建一个数据结构，使用 LongSparseArray 作为内部映射而不是 HashMap。

建立 LongArraySet

新的数据结构更加合理。通过使用与之前相同的测试框架，我们将新的数据结构与 HashSet 进行了比较。 每个数据结构都通过添加 X 个 item 进行测试，检查每个 item 的存在，然后删除所有 item。 我们使用不同数量的 item（X = 10，X = 100，X = 1,000 …）运行测试，并平均每个 item 完成每个操作所花费的时间。

运行时结果（时间显示为纳秒）：

我们看到使用新数据结构的 contains 和 delete 方法的运行时效率改进。 另外，随着数组中 item 数的增加，添加新 item 花费更多时间。 这与我们已经知道的 LongSparseArray 是一致的 ，当 item 数量超过 1,000 时，它与 HashMap 的表现不一样。 在我们的用例中，我们只处理了数百个 item，所以这是一个我们愿意做的权衡。

我们也看到了内存使用有很大的改善。 在查看堆转储和分配跟踪报告时，我们注意到对象分配的减少。 下面是当添加 1,000 个 item 进行 20 次迭代时，HashSet 和 LongArraySet 实现的并行分配报告：

除了避免所有 Long 对象分配之外，LongSparseArray 更具有内存效率，在这种情况下的分配减少了约 30％。

结语

通过了解其他数据结构如何工作，我们能够为我们的需求创建一个更优化的数据结构。 垃圾收集器必须工作的越少，这样丢帧的可能性就越低。 使用新的 LongArraySet 类和类似的 IntArraySet 作为原始 int 数据类型，我们能够在整个应用程序中减少大量的对象内存分配。

这个案例研究表明了我们选择数据结构的重要性。虽然这种解决方案对于所有用例来说并不完美，因为这种实现对于非常大的数据集来说较慢，但是还可以继续对我们的代码进行优化。

你可以在下面网址找到两个数据结构的源代码。 我们很高兴继续努力应对挑战，优化我们的 Feed 平台，并与社区分享我们的解决方案。

本文转载自公众号贝壳产品技术（ID：gh_9afeb423f390）。

原文链接：

https://mp.weixin.qq.com/s/naZe4cXcXfe9cXQPLoZf9g