原文Memory optimization for feeds on Android——Udi Cohen炫贤。

數(shù)以百萬的人在Android設(shè)備上運(yùn)行FaceBook跳座，瀏覽著新聞，資訊堕担，大事韵吨，頁面入挣，朋友圈和他們關(guān)心的信息。一個(gè)叫Android Feed Platform的團(tuán)隊(duì)創(chuàng)建了一個(gè)新平臺(tái)來提供這些信息鲫售。因此任何對(duì)這個(gè)平臺(tái)的優(yōu)化共螺，都惠及我們的應(yīng)用。我們下面著重于滾動(dòng)的效率情竹，希望能在滿足人們求知欲的同時(shí)享受如絲順滑的體驗(yàn)藐不。

為了實(shí)現(xiàn)這個(gè)目標(biāo)，我們做了幾個(gè)自動(dòng)化工具來測(cè)試平臺(tái)在不同場(chǎng)景和設(shè)備上運(yùn)行的性能秦效，以此衡量出代碼在運(yùn)行時(shí)的內(nèi)存使用率雏蛮，幀率等。當(dāng)使用其中一個(gè)工具棉安，TraceView底扳，測(cè)試發(fā)現(xiàn)對(duì)Long.valueOf()有頻發(fā)的調(diào)用，使內(nèi)存中堆積的對(duì)象過多贡耽，導(dǎo)致崩潰衷模。這篇文章描述了如何解決這個(gè)問題，我們權(quán)衡的潛在的解決方案的過程蒲赂，和我們對(duì)平臺(tái)所做的最終優(yōu)化阱冶。

方便的缺點(diǎn)

通過TraceView發(fā)現(xiàn)Long.valueOf()的頻發(fā)調(diào)用后，我們進(jìn)一步地測(cè)試發(fā)現(xiàn)滥嘴，在滾動(dòng)新聞時(shí)木蹬，意料之外的是這個(gè)方法被更頻發(fā)地調(diào)用了。

Test Result

當(dāng)我們查看調(diào)用堆棧時(shí)若皱，發(fā)現(xiàn)方法調(diào)用者不是Facebook的代碼而是編譯器的隱式代碼插入镊叁。調(diào)用這個(gè)方法用于把long裝箱成Long尘颓。Java既支持復(fù)雜類型，也支持基本類型（像integer晦譬，long等關(guān)鍵字）疤苹，并提供無縫轉(zhuǎn)換。這個(gè)特性稱為自動(dòng)裝箱敛腌，把一個(gè)基本類型轉(zhuǎn)化為對(duì)應(yīng)的復(fù)雜數(shù)據(jù)類型卧土。雖然是很便利的特性，同時(shí)也創(chuàng)建了對(duì)開發(fā)者透明的對(duì)象像樊。

這些未知對(duì)象占用內(nèi)存總和尤莺。

objects add up

app的heap dump檢測(cè)出來Long對(duì)象占用了很大一部分內(nèi)存；但是每個(gè)對(duì)象本身并不大生棍，數(shù)量之多令人咂舌颤霎。特別使用Dalvik時(shí)容易發(fā)生問題，不比新一代的Android運(yùn)行時(shí)ART足绅，擁有分代垃圾回收機(jī)制捷绑，能選擇更合適的時(shí)機(jī)回收數(shù)量眾多的小對(duì)象。當(dāng)我們將新聞列表上下滾動(dòng)時(shí)氢妈，大量對(duì)象被創(chuàng)建粹污，垃圾收回策略會(huì)讓應(yīng)用暫停，去清理內(nèi)存首量。越多的對(duì)象堆積壮吩，內(nèi)存回收就更為頻繁，導(dǎo)致應(yīng)用卡頓甚至崩潰加缘，給用戶留下劣質(zhì)的體驗(yàn)鸭叙。

幸運(yùn)的是，擁有TraceView和Allocation Tracker這樣的好工具拣宏，幫我們分析出卡頓的原因沈贝，問題處在自動(dòng)裝箱上。我們發(fā)現(xiàn)大部分的操作勋乾，是把long插入到HashSet<Long>時(shí)發(fā)生的宋下。（我們使用Hashset<Long>來存儲(chǔ)新聞的哈希值，校驗(yàn)新聞是否唯一）辑莫。HashSet提供快速的對(duì)象獲取学歧，因?yàn)楣Ｖ涤?jì)算出來由long表示，然而HashSet<Long>是與復(fù)雜對(duì)象交互的各吨，當(dāng)我們調(diào)用setStories.put(lStoryHash)時(shí)枝笨，自動(dòng)裝箱無可避免。

解決方案是，繼承Set横浑，使其能與簡(jiǎn)單類型交互剔桨，結(jié)果并未如我們想象那么簡(jiǎn)單。

可行的方案

存在一些與簡(jiǎn)單類型交互的Set子類徙融，這些庫幾乎都是十年前的當(dāng)Java還是J2ME的年代领炫。為了彰顯新時(shí)代的活力，我們決定在Dalvik/ART上進(jìn)行測(cè)試张咳，確保他們能在更苛刻的條件下表現(xiàn)良好。我們寫了個(gè)輕量級(jí)的測(cè)試框架似舵，這些老庫將與HashSet一較高下脚猾。結(jié)果顯示這些老庫都比HashSet速度快，占用內(nèi)存少砚哗，但是它們內(nèi)部還是會(huì)創(chuàng)建對(duì)象龙助，例如TLongHashSet， Trove庫的一個(gè)類蛛芥，用1000個(gè)例子測(cè)試大概分配了2MB內(nèi)存提鸟。

result

其他測(cè)試庫，比如PCJ和Colt仅淑，結(jié)果幾乎一致称勋。

已存在的輪子并不符合我們的需求，所以就為Android創(chuàng)建一個(gè)合適的Set輪子涯竟∩南剩看看HashSet的源碼實(shí)現(xiàn)，簡(jiǎn)單地使用HashMap來實(shí)現(xiàn)復(fù)雜的功能庐船。

    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里添加對(duì)象意味這往HashMap里面添加鍵和HashSet自己的實(shí)例作為值银酬。HashSet通過內(nèi)部HashMap是否包含相同的鍵值來校驗(yàn)插入的對(duì)象】鹬樱可以選擇使用Android優(yōu)化過的Map來優(yōu)化HashSet揩瞪。

介紹LongArraySet

也許你很熟悉LongSparseArray，它是Android提供的一個(gè)以long為鍵的Map篓冲±钇疲可以這樣用：

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

LongSparseArray的不同于HashMap，當(dāng)調(diào)用mapHashmap.get(KEY5)纹因，HashMap是這樣查詢的

HashMap Get A Value

整個(gè)取值的過程是喷屋，用鍵值的哈希值作為下標(biāo)，在列表中獲取值瞭恰。時(shí)間復(fù)雜度是O(1)屯曹。

而LongSparseArray取值是這樣的。

LongSparseArray Get A Value

LongSparseArray通過二分查找法在有序的鍵列表中找到鍵，時(shí)間復(fù)雜度是O(log N)恶耽，通過鍵的下標(biāo)在值隊(duì)列中取到對(duì)應(yīng)值密任。

HashMap需要額外分配空間來避免沖突，導(dǎo)致尋址變慢偷俭。LongSparseArray創(chuàng)建兩個(gè)列表使占用內(nèi)存小浪讳，但為了支持二分查找法，需要一塊連續(xù)的內(nèi)存空間涌萤。當(dāng)添加的數(shù)量大于當(dāng)前連續(xù)內(nèi)存數(shù)時(shí)淹遵，需要一整塊新的連續(xù)內(nèi)存。當(dāng)總長(zhǎng)度超過1000時(shí)负溪，LongSparseArray的表現(xiàn)就不太理想啦透揣，存在巨大的性能問題（參考官方文檔或者看Google的短視頻）

因?yàn)?code>LongSparseArray的鍵是簡(jiǎn)單類型的，我們可以創(chuàng)造一個(gè)新的數(shù)據(jù)結(jié)構(gòu)川抡，把LongSparseArray作為HashSet的內(nèi)部類來使用辐真。

就叫LongArraySet吧！

新的數(shù)據(jù)結(jié)構(gòu)看起來是有希望的崖堤，但優(yōu)化的第一條規(guī)則是“測(cè)試”侍咱。通過先前的測(cè)試框架，我們把新的數(shù)據(jù)結(jié)構(gòu)與HashSet進(jìn)行比對(duì)密幔，通過添加X個(gè)item來測(cè)試楔脯，檢查它們內(nèi)部的結(jié)構(gòu)，隨即移除他們胯甩。在添加不同數(shù)量(X=10,X=100,X=1000....)淤年，同時(shí)平均下來每次的操作時(shí)間，結(jié)果是：

result

我們發(fā)現(xiàn)Contains和Remove操作在運(yùn)行環(huán)境下都有性能提升蜡豹。隨著數(shù)量的增加麸粮，Add操作耗費(fèi)更多的時(shí)間。這個(gè)上面LongSparseArray內(nèi)部結(jié)構(gòu)造成的——當(dāng)數(shù)量超過1000時(shí)镜廉，表現(xiàn)就比不上HashMap弄诲。在我們自己的應(yīng)用中，只需要處理幾百個(gè)item娇唯，值得替換一下齐遵。

我們也看到內(nèi)存使用的提升，在看Heap和Allocate Tracker時(shí)塔插，我們發(fā)現(xiàn)對(duì)象創(chuàng)建的數(shù)量減少了梗摇，下面是
HashSet和LongArraySet在20次循環(huán)中添加1000個(gè)item的對(duì)比結(jié)果。

compare

LongArraySet能很好地避免創(chuàng)建Long對(duì)象想许，在這個(gè)場(chǎng)景下減少了30%的內(nèi)存分配伶授。

結(jié)論

通過深入了解其他數(shù)據(jù)結(jié)構(gòu)断序，我們能夠創(chuàng)建出更適合自身的數(shù)據(jù)結(jié)構(gòu)。垃圾回收運(yùn)行的次數(shù)越少糜烹，掉幀的情況發(fā)生就越少违诗。使用新的數(shù)據(jù)結(jié)構(gòu)LongArraySet，和以int為鍵的IntArraySet疮蹦，就能優(yōu)化整個(gè)應(yīng)用的內(nèi)存使用诸迟。

這個(gè)例子表明任何可行的方法都需要衡量得出最優(yōu)解。我們也接受這個(gè)方案并不是放之四海而皆準(zhǔn)的愕乎，對(duì)于重量級(jí)數(shù)據(jù)而言阵苇，這個(gè)提升是有限的，但對(duì)于我們來說感论，是更優(yōu)解慎玖。

你可以在這里找到源碼，我們也為接下來面臨的挑戰(zhàn)而感到興奮笛粘，希望日后還有機(jī)會(huì)分享更多的干貨。