大量的用户每天在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

创作场景

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