image.png

問題種類

時間復(fù)雜度

在集合里數(shù)據(jù)量小的情況下時間復(fù)雜度對于性能的影響看起來微乎其微。但如果某個開發(fā)的功能是一個公共功能，無法預(yù)料調(diào)用者傳入數(shù)據(jù)的量時，這個復(fù)雜度的優(yōu)化顯得非常重要了。

image

上圖列出了各種情況的時間復(fù)雜度，比如高效的排序算法一般都是 O(n log n)。接下來看看下圖：

image

圖中可以看出 O(n) 是個分水嶺，大于它對于性能就具有很大的潛在影響，如果是個公共的接口一定要加上說明，自己調(diào)用也要做到心中有數(shù)。當(dāng)然最好是通過算法優(yōu)化或者使用合適的系統(tǒng)接口方法，權(quán)衡內(nèi)存消耗爭取通過空間來換取時間。

下面通過集合里是否有某個值來舉個例子：

那么 OC 里幾種常用集合對象提供的接口方法時間復(fù)雜度是怎么樣的。

NSArray / NSMutableArray

首先我們發(fā)現(xiàn)他們是有排序，并允許重復(fù)元素存在的，那么這么設(shè)計就表明了集合存儲沒法使用里面的元素做 hash table 的 key 進(jìn)行相關(guān)的快速操作，。所以不同功能接口方法性能是會有很大的差異。

• containsObject:，containsObject:，indexOfObject*，removeObject: 會遍歷里面元素查看是否與之匹對，所以復(fù)雜度等于或大于 O(n)
• objectAtIndex:，firstObject:，lastObject:，addObject:，removeLastObject: 這些只針對棧頂棧底操作的時間復(fù)雜度都是 O(1)
• indexOfObject:inSortedRange:options:usingComparator: 使用的是二分查找，時間復(fù)雜度是 O(log n)

NSSet / NSMutableSet / NSCountedSet

這些集合類型是無序沒有重復(fù)元素。這樣就可以通過 hash table 進(jìn)行快速的操作。比如 addObject:, removeObject:, containsObject: 都是按照 O(1) 來的。需要注意的是將數(shù)組轉(zhuǎn)成 Set 時會將重復(fù)元素合成一個，同時失去排序。

NSDictionary / NSMutableDictionary

和 Set 差不多，多了鍵值對應(yīng)。添加刪除和查找都是 O(1) 的。需要注意的是 Keys 必須是符合 NSCopying。

containsObject 方法在數(shù)組和 Set 里不同的實現(xiàn)

在數(shù)組中的實現(xiàn)

可以看到會遍歷所有元素在查找到后才進(jìn)行返回.

接下來可以看看 containsObject 在 Set 里的實現(xiàn)：

找元素時是通過鍵值方式從 map 映射表里取出，因為 Set 里元素是唯一的，所以可以 hash 元素對象作為 key 達(dá)到快速獲取值的目的。

用 GCD 來做優(yōu)化

我們可以通過 GCD 提供的方法來將一些需要耗時操作放到非主線程上做，使得 App 能夠運行的更加流暢響應(yīng)更快。但是使用 GCD 時需要注意避免可能引起線程爆炸和死鎖的情況，還有非主線程處理任務(wù)也不是萬能的，如果一個處理需要消耗大量內(nèi)存或者大量CPU操作 GCD 也沒法幫你，只能通過將處理進(jìn)行拆解分步驟分時間進(jìn)行處理才比較妥當(dāng)。

異步處理事件

image

上圖是最典型的異步處理事件的方法

需要耗時長的任務(wù)

image

將 GCD 的 block 通過 dispatch_block_create_with_qos_class 方法指定隊列的 QoS 為 QOS_CLASS_UTILITY。這種 QoS 系統(tǒng)會針對大的計算，I/O，網(wǎng)絡(luò)以及復(fù)雜數(shù)據(jù)處理做電量優(yōu)化。

避免線程爆炸

• 使用串行隊列
• 使用 NSOperationQueues 的并發(fā)限制方法 NSOperationQueue.maxConcurrentOperationCount

舉個例子，下面的寫法就比較危險，可能會造成線程爆炸和死鎖

image

那么怎么能夠避免呢？首先可以使用 dispatch_apply

或者使用 dispatch_semaphore

GCD 相關(guān) Crash 日志

管理線程問題

線程閑置時

線程活躍時

主線程閑置時

主隊列

I/O 性能優(yōu)化

I/O 是性能消耗大戶，任何的 I/O 操作都會使低功耗狀態(tài)被打破，所以減少 I/O 次數(shù)是這個性能優(yōu)化的關(guān)鍵點，為了達(dá)成這個目下面列出一些方法。

• 將零碎的內(nèi)容作為一個整體進(jìn)行寫入
• 使用合適的 I/O 操作 API
• 使用合適的線程
• 使用 NSCache 做緩存能夠減少 I/O

NSCache

image

達(dá)到如圖的目的為何不直接用字典來做呢？
NSCache 具有字典的所有功能，同時還有如下的特性：

• 自動清理系統(tǒng)占用內(nèi)存
• NSCache 是線程安全
• -(void)cache:(NSCache *)cache willEvictObject:(id)obj; 緩存對象將被清理時的回調(diào)
• evictsObjectsWithDiscardedContent 可以控制是否清理

那么 NSCache是如何做到這些特性的呢？

接下來學(xué)習(xí)下 NSCache 是如何做的。首先 NSCache 是會持有一個 NSMutableDictionary。

需要設(shè)計一個 Cached 對象結(jié)構(gòu)來保存一些額外的信息

在 Cache 讀取的時候會對 _accesses 數(shù)組的添加刪除通過 isEvictable 布爾值來保證線程安全操作。使用 Cached 對象里的 accessCount 屬性進(jìn)行 +1 操作為后面自動清理的條件判斷做準(zhǔn)備。具體實現(xiàn)如下：

在每次 Cache 添加時會先去檢查是否自動清理，會創(chuàng)建一個 Cached 對象將 key，object，cost 等信息記錄下添加到 _accesses 數(shù)組和 _objects 字典里。

那么上面提到的自動清理內(nèi)存的方法是如何實現(xiàn)的呢？
既然是自動清理必定需要有觸發(fā)時機(jī)和進(jìn)入清理的條件判斷，觸發(fā)時機(jī)一個是發(fā)生在添加 Cache 內(nèi)容時，一個是發(fā)生在內(nèi)存警告時。條件判斷代碼如下：

所以 NSCache 的 totalCostLimit 的值會和每次 Cache 添加的 cost 之和對比，超出限制必然觸發(fā)內(nèi)存清理。

清理時會對經(jīng)常訪問的 objects 不清理，主要是通過 _totalAccesses 和總數(shù)獲得平均訪問頻率，如果那個對象的訪問次數(shù)是小于平均值的才需要清理。

在清理之前還需要一些準(zhǔn)備工作，包括標(biāo)記 Cached 對象的 isEvictable 防止后面有不安全的線程操作。將滿足條件的清理 objects 放到清理數(shù)組里，如果空間釋放足夠就不用再把更多的 objects 加到清理數(shù)組里了，最后遍歷清理數(shù)組進(jìn)行逐個清理即可。

在清理時會執(zhí)行回調(diào)內(nèi)容，這樣如果有些緩存數(shù)據(jù)需要持續(xù)化存儲可以在回調(diào)里進(jìn)行處理。

完整的實現(xiàn)可以查看 GNUstep Base 的 NSCache.m 文件。

下面可以看看 NSCache 在 SDWebImage 的運用是怎么樣的：

可以看出利用 NSCache 自動釋放內(nèi)存的特點將圖片都放到 NSCache 里這樣在內(nèi)存不夠用時可以自動清理掉不常用的那些圖片，在讀取 Cache 里內(nèi)容時如果沒有被清理會直接返回圖片數(shù)據(jù)，清理了的話才會執(zhí)行 I/O 從磁盤讀取圖片，通過這種方式能夠利用空間減少磁盤操作，空間也能夠更加有效的控制釋放。

控制 App 的 Wake 次數(shù)

通知，VoIP，定位，藍(lán)牙等都會使設(shè)備從 Standby 狀態(tài)喚起。喚起這個過程會有比較大的消耗，應(yīng)該避免頻繁發(fā)生。通知方面主要要在產(chǎn)品層面多做考慮。定位方面，下面可以看看定位的一些 API 看看它們對性能的不同影響，便于考慮采用合適的接口。

連續(xù)的位置更新

這個方法會時設(shè)備一直處于活躍狀態(tài)。

延時有效定位

高效節(jié)能的定位方式，數(shù)據(jù)會緩存在位置硬件上。適合于跑步應(yīng)用應(yīng)該都采用這種方式。

重大位置變化

會更節(jié)能，對于那些只有在位置有很大變化的才需要回調(diào)的應(yīng)用可以采用這種，比如天氣應(yīng)用。

區(qū)域監(jiān)測

也是一種節(jié)能的定位方式，比如在博物館里按照不同區(qū)域監(jiān)測展示不同信息之類的應(yīng)用比較適合這種定位。

經(jīng)常訪問的地方

總的來說，不要輕易使用 startUpdatingLocation() 除非萬不得已，盡快的使用 stopUpdatingLocation() 來結(jié)束定位還用戶一個節(jié)能設(shè)備。

內(nèi)存對于性能的影響

首先 Reclaiming 內(nèi)存是需要時間的，突然的大量內(nèi)存需求是會影響響應(yīng)的。

如何預(yù)防這些性能問題，需要刻意預(yù)防么

堅持下面幾個原則爭取在編碼階段避免一些性能問題。

• 優(yōu)化計算的復(fù)雜度從而減少 CPU 的使用
• 在應(yīng)用響應(yīng)交互的時候停止沒必要的任務(wù)處理
• 設(shè)置合適的 QoS
• 將定時器任務(wù)合并，讓 CPU 更多時候處于 idle 狀態(tài)

那么如果寫需求時來不及注意這些問題做不到預(yù)防的話，可以通過自動化代碼檢查的方式來避免這些問題嗎？

如何檢查

根據(jù)這些問題在代碼里查，寫工具或用工具自動化查？雖然可以，但是需要考慮的情況太多，現(xiàn)有工具支持不好，自己寫需要考慮的點太多需要花費太長的時間，那么什么方式會比較好呢？

通過監(jiān)聽主線程方式來監(jiān)察

首先用 CFRunLoopObserverCreate 創(chuàng)建一個觀察者里面接受 CFRunLoopActivity 的回調(diào)，然后用 CFRunLoopAddObserver 將觀察者添加到 CFRunLoopGetMain() 主線程 Runloop 的 kCFRunLoopCommonModes 模式下進(jìn)行觀察。

接下來創(chuàng)建一個子線程來進(jìn)行監(jiān)控，使用 dispatch_semaphore_wait 定義區(qū)間時間，標(biāo)準(zhǔn)是 16 或 20 微秒一次監(jiān)控的話基本可以把影響響應(yīng)的都找出來。監(jiān)控結(jié)果的標(biāo)準(zhǔn)是根據(jù)兩個 Runloop 的狀態(tài) BeforeSources 和 AfterWaiting 在區(qū)間時間是否能檢測到來判斷是否卡頓。

如何打印堆棧信息，保存現(xiàn)場

打印堆棧整體思路是獲取線程的信息得到線程的 state 從而得到線程里所有棧的指針，根據(jù)這些指針在 符號表里找到對應(yīng)的描述即符號化解析，這樣就能夠展示出可讀的堆棧信息。具體實現(xiàn)是怎樣的呢？下面詳細(xì)說說：

獲取線程的信息

這里首先是要通過 task_threads 取到所有的線程，

遍歷時通過 thread_info 獲取各個線程的詳細(xì)信息

獲取線程里所有棧的信息

可以通過 thread_get_state 得到 machine context 里面包含了線程棧里所有的棧指針。

創(chuàng)建一個棧結(jié)構(gòu)體用來保存棧的數(shù)據(jù)

符號化

符號化主要思想就是通過棧指針地址減去 Slide 地址得到 ASLR 偏移量，通過這個偏移量可以在 __LINKEDIT segment 查找到字符串和符號表的位置。具體代碼實現(xiàn)如下：

需要注意的地方

需要注意的是這個程序有消耗性能的地方 thread get state。這個也會被監(jiān)控檢查出，所以可以過濾掉這樣的堆棧信息。

能夠獲取更多信息的方法

獲取更多信息比如全層級方法調(diào)用和每個方法消耗的時間，那么這樣做的好處在哪呢？

可以更細(xì)化的測量時間消耗，找到耗時方法，更快的交互操作能使用戶體驗更好，下面是一些可以去衡量的場景：

• 響應(yīng)能力
• 按鈕點擊
• 手勢操作
• Tab 切換
• vc 的切換和轉(zhuǎn)場

可以給優(yōu)化定個目標(biāo)，比如滾動和動畫達(dá)到 60fps，響應(yīng)用戶操作在 100ms 內(nèi)完成。然后逐個檢測出來 fix 掉。

如何獲取到更多信息呢？

通過 hook objc_msgSend 方法能夠獲取所有被調(diào)用的方法，記錄深度就能夠得到方法調(diào)用的樹狀結(jié)構(gòu)，通過執(zhí)行前后時間的記錄能夠得到每個方法的耗時，這樣就能獲取一份完整的性能消耗信息了。

hook c 函數(shù)可以使用 facebook 的 fishhook， 獲取方法調(diào)用樹狀結(jié)構(gòu)可以使用 InspectiveC，下面對于他們的實現(xiàn)詳細(xì)介紹一下：

獲取方法調(diào)用樹結(jié)構(gòu)

首先設(shè)計兩個結(jié)構(gòu)體，CallRecord 記錄調(diào)用方法詳細(xì)信息，包括 obj 和 SEL 等，ThreadCallStack 里面需要用 index 記錄當(dāng)前調(diào)用方法樹的深度。有了 SEL 再通過 NSStringFromSelector 就能夠取得方法名，有了 obj 通過 object_getClass 能夠得到 Class 再用 NSStringFromClass 就能夠獲得類名。

存儲讀取 ThreadCallStack

pthread_setspecific() 可以將私有數(shù)據(jù)設(shè)置在指定線程上，pthread_getspecific() 用來讀取這個私有數(shù)據(jù)，利用這個特性可以就可以將 ThreadCallStack 的數(shù)據(jù)和該線程綁定在一起，隨時進(jìn)行數(shù)據(jù)的存取。代碼如下：

記錄方法調(diào)用深度

因為要記錄深度，而一個方法的調(diào)用里會有更多的方法調(diào)用，所以方法的調(diào)用寫兩個方法分別記錄開始 pushCallRecord 和記錄結(jié)束的時刻 popCallRecord，這樣才能夠通過在開始時對深度加一在結(jié)束時減一。

在 objc_msgSend 前后插入執(zhí)行方法

最后是 hook objc_msgSend 需要在調(diào)用前和調(diào)用后分別加入 pushCallRecord 和 popCallRecord。因為需要在調(diào)用后這個時機(jī)插入一個方法，而且不可能編寫一個保留未知參數(shù)并跳轉(zhuǎn)到 c 中任意函數(shù)指針的函數(shù)，那么這就需要用到匯編來做到。

下面針對 arm64 進(jìn)行分析，arm64 有31個64 bit 的整數(shù)型寄存器，用 x0 到 x30 表示，主要思路就是先入棧參數(shù)，參數(shù)寄存器是 x0 - x7，對于objc_msgSend方法來說 x0 第一個參數(shù)是傳入對象，x1 第二個參數(shù)是選擇器 _cmd。 syscall 的 number 會放到 x8 里。然后交換寄存器中，將用于返回的寄存器 lr 移到 x1 里。先讓 pushCallRecord 能夠執(zhí)行，再執(zhí)行原始的 objc_msgSend，保存返回值，最后讓 popCallRecord 能執(zhí)行。具體代碼如下：

記錄時間的方法

為了記錄耗時，這樣就需要在 pushCallRecord 和 popCallRecord 里記錄下時間。下面列出一些計算一段代碼開始到結(jié)束的時間的方法

第一種： NSDate 微秒

第二種：clock_t 微秒clock_t計時所表示的是占用CPU的時鐘單元

第三種：CFAbsoluteTime 微秒

第四種：CFTimeInterval 納秒

第五種：mach_absolute_time 納秒

最后兩種可用，本質(zhì)區(qū)別
NSDate 或 CFAbsoluteTimeGetCurrent() 返回的時鐘時間將會會網(wǎng)絡(luò)時間同步，從時鐘 偏移量的角度。mach_absolute_time() 和 CACurrentMediaTime() 是基于內(nèi)建時鐘的。選擇一種，加到 pushCallRecord 和 popCallRecord 里，相減就能夠獲得耗時。

如何 hook msgsend 方法

那么 objc_msgSend 這個 c 方法是如何 hook 到的呢。首先了解下 dyld 是通過更新 Mach-O 二進(jìn)制的 __DATA segment 特定的部分中的指針來邦定 lazy 和 non-lazy 符號，通過確認(rèn)傳遞給 rebind_symbol 里每個符號名稱更新的位置就可以找出對應(yīng)替換來重新綁定這些符號。下面針對關(guān)鍵代碼進(jìn)行分析：

遍歷 dyld

首先是遍歷 dyld 里的所有的 image，取出 image header 和 slide。注意第一次調(diào)用時主要注冊 callback。

找出符號表相關(guān) Command

接下來需要找到符號表相關(guān)的 command，包括 linkedit segment command，symtab command 和 dysymtab command。方法如下：

獲得 base 和 indirect 符號表

進(jìn)行方法替換

有了符號表和傳入的方法替換數(shù)組就可以進(jìn)行符號表訪問指針地址的替換，具體實現(xiàn)如下：

統(tǒng)計方法調(diào)用頻次

在一些應(yīng)用場景會有一些頻繁的方法調(diào)用，有些方法的調(diào)用實際上是沒有必要的，但是首先是需要將那些頻繁調(diào)用的方法找出來這樣才能夠更好的定位到潛在的會造成性能浪費的方法使用。這些頻繁調(diào)用的方法要怎么找呢？

大致的思路是這樣，基于上面章節(jié)提到的記錄方法調(diào)用深度的方案，將每個調(diào)用方法的路徑保存住，調(diào)用相同路徑的相同方法調(diào)用一次加一記錄在數(shù)據(jù)庫中，最后做一個視圖按照調(diào)用次數(shù)的排序即可找到調(diào)用頻繁的那些方法。下圖是完成后展示的效果：

image

接下來看看具體實現(xiàn)方式

設(shè)計方法調(diào)用頻次記錄的結(jié)構(gòu)

在先前時間消耗的 model 基礎(chǔ)上增加路徑，頻次等信息

拼裝方法路徑

在遍歷 SMCallTrace 記錄的方法 model 和 遍歷方法子方法時將路徑拼裝好，記錄到數(shù)據(jù)庫中

記錄方法調(diào)用頻次數(shù)據(jù)庫

創(chuàng)建數(shù)據(jù)庫

這里的 lastcall 是記錄是否是最后一個方法的調(diào)用，展示時只取最后一個方法即可，因為也會有完整路徑可以知道父方法和來源方法。

添加記錄

添加記錄時需要先檢查數(shù)據(jù)庫里是否有相同路徑的同一個方法調(diào)用，這樣可以給 frequency 字段加一已達(dá)到記錄頻次的目的。

檢索記錄

檢索時注意按照調(diào)用頻次字段進(jìn)行排序即可。

找出 CPU 使用大的線程堆棧

在前面檢測卡頓打印的堆棧里提到使用 thread_info 能夠獲取到各個線程的 cpu 消耗，但是 cpu 不在主線程即使消耗很大也不一定會造成卡頓導(dǎo)致卡頓檢測無法檢測出更多 cpu 消耗的情況，所以只能通過輪詢監(jiān)控各線程里的 cpu 使用情況，對于超過標(biāo)準(zhǔn)值比如70%的進(jìn)行記錄來跟蹤定位出耗電的那些方法。下圖是列出 cpu 過載時的堆棧記錄的展示效果：

image

有了前面的基礎(chǔ)，實現(xiàn)起來輕松多了

Demo

工具已整合到先前做的 GCDFetchFeed 里。

• 子線程檢測主線程卡頓使用的話在需要開始檢測的地方添加 [[SMLagMonitor shareInstance] beginMonitor]; 即可。
• 需要檢測所有方法調(diào)用的用法就是在需要檢測的地方調(diào)用 [SMCallTrace start]; 就可以了，不檢測打印出結(jié)果的話調(diào)用 stop 和 save 就好了。這里還可以設(shè)置最大深度和最小耗時檢測來過濾不需要看到的信息。
• 方法調(diào)用頻次使用可以在需要開始統(tǒng)計的地方加上 [SMCallTrace startWithMaxDepth:3]; 記錄時使用 [SMCallTrace stopSaveAndClean]; 記錄到到數(shù)據(jù)庫中同時清理內(nèi)存的占用?？梢?hook VC 的 viewWillAppear 和 viewWillDisappear，在 appear 時開始記錄，在 disappear 時記錄到數(shù)據(jù)庫同時清理一次。結(jié)果展示的 view controller 是 SMClsCallViewController，push 出來就能夠看到列表結(jié)果。

資料

WWDC

• WWDC 2013 224 Designing Code for Performance
• WWDC 2013 408 Optimizing Your Code Using LLVM
• WWDC 2013 712 Energy Best Practices
• WWDC 2014 710 writing energy efficient code part 1
• WWDC 2014 710 writing energy efficient code part 2
• WWDC 2015 230 performance on ios and watchos
• WWDC 2015 707 achieving allday battery life
• WWDC 2015 708 debugging energy issues
• WWDC 2015 718 building responsive and efficient apps with gcd
• WWDC 2016 406 optimizing app startup time
• WWDC 2016 719 optimizing io for performance and battery life
• WWDC 2017 238 writing energy efficient apps
• WWDC 2017 706 modernizing grand central dispatch usage

參考深入剖析 iOS 性能優(yōu)化