Facebook Feed 流的內存優(yōu)化實踐

點擊“開發(fā)者技術前線”，選擇“星標??”

讓一部分開發(fā)者看到未來

翻譯：可可 |英文：https://code.facebook.com/posts/973222319439596

引言

大量的用戶每天在Android設備上使用Facebook，滾動新聞Feed流頁面，包括個人資料，活動，頁面和組，與他們關心的人員和信息進行互動等一系列行為。所有這些不同的Feed類型都由Android Feed Platform小組創(chuàng)建的平臺提供支持，因此我們對Feed平臺進行的任何優(yōu)化都可能提高我們的應用程序的性能。我們專注于頁面的滾動性能，因為我們希望用戶在滾動他們的Feed流頁面時有一個平滑的體驗。

為了幫助我們實現這一點，我們有幾種自動化工具，可以跨不同的場景和不同的設備在Feed平臺上運行性能測試，測量代碼在運行時內存使用，幀速率等方面的運行情況。其中一個工具Traceview顯示了我們的程序對Long.valueOf（）函數的調用次數相對較多，這導致對象在內存中累積并導致應用程序卡頓停止等。這篇文章描述這個問題，我們權衡了各種潛在解決方案之后，對改進Feed流平臺而進行的一系列優(yōu)化。

便利性帶來的缺點

我們從Traceview的一個方法分析報告中注意到：facebook的app對Long.valueOf（）函數的大量調用。之后，我們進行了又進一步的測試，證實了當我們滾動新聞列表時，Long.valueOf（）方法的調用會意外升高。

當我們查看堆棧時，我們發(fā)現這個函數沒有被直接的從Facebook的代碼調用，而是隱式地由編譯器插入的代碼。在分配長整型對象的原始長值時調用此函數。Java支持對象和原始的簡單類型（例如，整數，字符），并提供了一種在它們之間無縫轉換的方式。這種方式稱為自動裝箱，因為它將基本類型裝箱為相應的類型的對象類型。雖然這是一個方便的開發(fā)功能，但是它同時也創(chuàng)建了開發(fā)人員不知道的新對象。

在對一個示例應用程序的堆棧中發(fā)現Long對象有大量的存在; 雖然每個對象本身都不大，但是存在的大量的Long對象占據了應用程序在堆中的大部分內存。對于運行Dalvik的設備來說，會有很大的影響。與Android的ART運行時環(huán)境不同，Dalvik沒有一代間垃圾回收機制，造成很多小對象的垃圾回收效率很低。當我們滾動新聞Feed流，會造成Long對象數量增加，垃圾收集將導致應用程序卡頓來從內存中清除未使用的對象。積累的對象越多，垃圾收集器將越來越頻繁地暫停應用程序，導致卡頓使得戶體驗不佳。

幸運的是，Traceview和Allocation Tracker等工具可以幫助我們找到這些函數調用的位置。在查看了這些自動裝箱事件的根源之后，我們發(fā)現大多數成因都是：將Long類型的基本類型數據插入HashSet <Long>數據結構中造成。（我們使用這個數據結構存儲新聞Feed的哈希值，稍后檢查某個哈希是否已經在Set中。）HashSet提供對具體feed的快速訪問。由于哈希計算并存儲在一個原始的長變量中，然而我們的HashSet僅適用于對象，所以當調用set.put（Hash）時，我們會得到不可避免的自動裝箱。

作為一個解決方案，可以使用基本數據類型而不是對象類型的Set實現，但是結果并不像我們預期的那么簡單。

目前的解決方案

有幾個現有的Java庫為原始數據類型提供了Set實現。幾乎所有這些類庫都是10多年前創(chuàng)建的，當時在移動設備上運行的唯一的Java是J2ME。為了確定可行性，我們需要在Dalvik / ART下進行測試，并確保它們在資源更受限的移動設備上表現良好。我們創(chuàng)建了一個小型測試框架來幫助將這些庫與現有的HashSet進行比較。結果表明，這些庫中的一些庫具有比HashSet更快的運行時間，并且具有較少的Long對象，但是它們仍然在內部分配了很多Long對象。例如，Troow庫中的一部分TLongHashSet在測試時分配了大約2 MB的對象，共有1,000個item

對其他的類庫進行測試，包括PCJ和Colt, 顯示了類似的結果。

現有的解決方案不符合我們的需求。我們考慮是否可以創(chuàng)建一個新的Set實現，并針對Android進行優(yōu)化。在Java的HashSet中，使用單個HashMap來實現一個相對簡單的實現。

public class HashSet<E> extends AbstractSet<E> implements Set<E>, ... {

    transient HashMap<E, HashSet<E>> backingMap;    

    ...

    @Override public boolean add(E object) {
        return backingMap.put(object, this) == null;    
    }

    @Override public boolean contains(Object object) {
        return backingMap.containsKey(object);    
    }

    ...        
}

向HashSet添加新item意味著將其添加到內部HashMap，其中對象是關鍵字，而HashSet的實例是該值。要檢查對象成員身份，HashSet將檢查其內部HashMap是否包含對象作為鍵。可以使用Android優(yōu)化的map和相同的原則來實現HashSet的替代方案。

引進LongArraySet

你可能已經熟悉了LongSparseArray，它是Android支持類庫中的一個類，用作使用long類型作為key的map。使用示例

LongSparseArray<String> longSparseArray = new LongSparseArray<>();
longSparseArray.put(3L, "Data");String data = longSparseArray.get(3L); // the value of data is "Data"

LongSparseArray的工作方式與HashMap不同。當調用mapHashmap.get（KEY5）時，下圖說明了如何在HashMap中找到該值：

當使用HashMap上的鍵檢索值時，它使用密鑰的哈希值作為索引訪問數組中的值，即O（1）時間復雜度的的直接訪問。對LongSparseArray進行相同的調用如下所示：

LongSparseArray使用二分搜索，運行時間為O（log N）的時間復雜度操作搜索排序密鑰數組的密鑰值。數組中的鍵的索引值用于查找values數組中的值。

HashMap分配一個大數組，以避免hash沖突，但是這樣導致搜索速度較慢。LongSparseArray分配兩個小數組，使其內存占用更小。但是為了支持其搜索算法，LongSparseArray需要在連續(xù)的內存塊中分配其內部數組。添加更多的item將需要在當前空間不足的情況下分配新的數組。LongSparseArray的工作原理使得它在保存超過1,000個項目時效率下降，這些差異對性能有更重要的影響。（您可以在官方文檔中了解有關LongSparseArray的更多信息，并通過觀看Google的簡短視頻。）

由于LongSparseArray的鍵是原始long類型，所以我們可以使用與HashSet相同的方法創(chuàng)建一個數據結構，使用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％。

結論

通過了解其他數據結構如何工作，我們能夠為我們的需求創(chuàng)建一個更優(yōu)化的數據結構。垃圾收集器必須工作的越少，這樣丟幀的可能性就越低。使用新的LongArraySet類和類似的IntArraySet作為原始int數據類型，我們能夠在整個應用程序中減少大量的對象內存分配。

這個案例研究表明了我們選擇數據結構的重要性。雖然這種解決方案對于所有用例來說并不完美，因為這種實現對于非常大的數據集來說較慢，但是還可以繼續(xù)對我們的代碼進行優(yōu)化。

你可以在下面網址找到兩個數據結構的源代碼。我們很高興繼續(xù)努力應對挑戰(zhàn)，優(yōu)化我們的Feed平臺，并與社區(qū)分享我們的解決方案。

---END---

選擇”開發(fā)者技術前線 “星標??，內容一觸即達。點擊原文更多驚喜！

開發(fā)者技術前線 匯集技術前線快訊和關注行業(yè)趨勢，大廠干貨，是開發(fā)者經歷和成長的優(yōu)秀指南。

歷史推薦

京東APP中Flutter探索及優(yōu)化

為什么我不推薦你用 Flutter 開發(fā)？

今日頭條 App 屏幕適配方案落地研究

點個在看，解鎖更多驚喜！