难得的Android 启动优化好文！
（给安卓开发精选加星标）
转自：程序员徐公
https://juejin.cn/post/6926794003794903048
这是一篇非常难得的文章，现在做启动优化动不动就聊拓扑结构，这篇文章从数据结构到算法到设计都给大家说清楚了，开源项目也有非常强的借鉴意义。
当然开源项目是不断迭代的，文章可能无法保证始终是最新的代码，不过并不影响对原理的掌握。
说到 Android 启动优化，大家第一时间可能会想到异步加载。将耗时任务放到子线程加载，等到所有加载任务加载完成之后，再进入首页。
多线程异步加载方案确实是 ok 的。但如果遇到前后依赖的关系呢。比如任务2 依赖于任务 1，这时候要怎么解决呢。
最简单的方案是将任务1 丢到主线程加载，然后再启动多线程异步加载。
如果遇到更复杂的依赖呢？
任务3 依赖于任务 2， 任务 2 依赖于任务 1 呢，这时候你要怎么解决。更复杂的依赖关系呢？
总不能将任务 2，任务 3 都放到主线程加载吧，这样多线程加载的意义就不大了。
有没有更好的方案呢？
答案肯定是有的，使用有向无环图。它可以完美解决先后依赖关系。
1、有向无环图
重要概念
有向无环图（Directed Acyclic Graph, DAG）是有向图的一种，字面意思的理解就是图中没有环。常常被用来表示事件之间的驱动依赖关系，管理任务之间的调度。
顶点：图中的一个点，比如顶点 1，顶点 2。
边：连接两个顶点的线段叫做边，edge。
入度：代表当前有多少边指向它。
在上图中，顶掉 1 的入度是 0，因为没有任何边指向它。顶掉 2 的入度是 1， 因为 顶掉 1 指向 顶掉 2. 同理可得出 5 的入度是 2，因为顶掉 4 和顶点 3 指向它。
拓扑排序：拓扑排序是对一个有向图构造拓扑序列的过程。它具有如下特点。
每个顶点出现且只出现一次。
若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面
由于有这个特点，因此常常用有向无环图的数据结构用来解决依赖关系。
上图中，拓扑排序之后，任务2肯定排在任务1之后，因为任务2依赖 任务1， 任务3肯定在任务2之后，因为任务3依赖任务2。
拓扑排序一般有两种算法，第一种是入度表法，第二种是 DFS 方法。下面，让我们一起来看一下怎么实现它。
入度表法
入度表法是根据顶点的入度来判断是否有依赖关系的。若顶点的入度不为 0，则表示它有前置依赖。它也常常被称作 BFS 算法。
算法思想
建立入度表，入度为 0 的节点先入队。
当队列不为空，进行循环判断。
节点出队，添加到结果 list 当中。
将该节点的邻居入度减 1。
若邻居节点入度为 0，加入队列。
若结果 list 与所有节点数量相等，则证明不存在环。否则，存在环。
实例讲解
下图所示的有向无环图，采用入度表的方法获取拓扑排序过程。
首先，我们选择入度为 0 的顶点，这里顶点 1 的入度为 0，删除顶点 1 之后，图变成如下。
这时候，顶点 2 和顶点 4 的入度都为 0，我们可以随便删除一个顶点。（这也就是为什么图的拓扑排序不是唯一的原因）。这里我们删除顶点 2，图变成如下：
这时候，我们再删除顶点 4，图变成如下：
选择入度为 0 的顶点 3，删除顶点 3 之后，图标称如下，
最后剩余顶点5，输出顶点5，拓扑排序过程结束。最终的输出结果为：
到此，优先无环图的入度法的流程已经讲解完毕。你清楚了嘛。
时间复杂度
设 AOE 网有 n 个事件，e 个活动，则算法的主要执行是：
求每个事件的ve值和vl值：时间复杂度是O(n+e) ；
根据ve值和vl值找关键活动：时间复杂度是O(n+e) ；
因此，整个算法的时间复杂度是O(n+e)。
从上面的入度表法，我们可以知道，要得到有向无环图的拓扑排序，我们的关键点要找到入度为 0 的顶点。然后接着删除该结点的相邻所有边。再遍历所有结点。直到入度为 0 的队列为空。这种方法其实是 BFS。
在了解了 BFS 算法之后，我们看看如何利用已知的知识来做一个启动框架。
2、手把手教你实现 AnchorTask
AnchorTask，锚点任务，它的实现原理是构建一个有向无环图，拓扑排序之后，如果任务 B 依赖任务 A，那么 A 一定排在任务 B 之前。
了解原理之前，请必须先了解有向无环图和多线程的一些基本知识，不然，下文，你基本是看不懂的。
一个共识
如何构建一个有向无环图
多线程中，任务执行是随机的，那如何保证任务被依赖的任务先于任务执行呢？
具体实现
IAnchorTask
首先，我们定义一个 IAnchorTask 接口，主要有几个方法。
isRunOnMainThread(): Boolean表示是否在主线程运行，默认值是 false。
priority(): Int方法 表示线程的优先级别，默认值是 Process.THREAD_PRIORITY_FOREGROUND。
needWait()表示当我们调用 AnchorTaskDispatcher await时，是否需要等待，return true，表示需要等待改任务执行结束，AnchorTaskDispatcher await方法才能继续往下执行。
fun getDependsTaskList(): List<Class<out AnchorTask>>?方法返回前置任务依赖，默认值是返回 null。
fun run()方法，表示任务执行的时候
interface IAnchorTask : IAnchorCallBack {
/**
* 是否在主线程执行
*/
fun isRunOnMainThread(): Boolean
/**
* 任务优先级别
*/
@IntRange(
from = Process.THREAD_PRIORITY_FOREGROUND.toLong(),
to = Process.THREAD_PRIORITY_LOWEST.toLong()
)
fun priority(): Int
/**
* 调用 await 方法，是否需要等待改任务执行完成
* true 不需要
* false 需要
*/
fun needWait(): Boolean
/**
* 当前任务的前置任务，可以用来确定顶点的入度
*/
fun getDependsTaskList(): List<Class<out AnchorTask>>?
/**
* 任务被执行的时候回调
*/
fun run()
}
await 方法，调用它，当前任务会等待。
countdown() 方法，如果当前计数器值 > 0,会减一，否则，什么也不操作。
abstract class AnchorTask : IAnchorTask {
private val countDownLatch: CountDownLatch = CountDownLatch(getListSize())
private fun getListSize() = getDependsTaskList()?.size ?: 0
companion object {
const val TAG = "AnchorTask"
}
/**
* self call,await
*/
fun await() {
countDownLatch.await()
}
/**
* parent call, countDown
*/
fun countdown() {
countDownLatch.countDown()
}
}
排序实现
无环图的拓扑排序，这里采用的是 BFS 算法。具体的可以见 AnchorTaskUtils#getSortResult方法，它有三个参数。
1、list 存储所有的任务。
2、taskMap: MutableMap<Class<out AnchorTask>, AnchorTask> = HashMap()存储所有的任务,key 是 Class，value 是 AnchorTask。
算法思想
1、首先找出所有入度为 0 的队列，用 queue 变量存储。
2、当队列不为空，进行循环判断。
从队列 pop 出，添加到结果队列。
遍历当前任务的子任务，通知他们的入度减一（其实是遍历 taskChildMap），如果入度为 0，添加到队列 queue 里面。
3、当结果队列和 list size 不相等试，证明有环
@JvmStatic
fun getSortResult(
list: MutableList<AnchorTask>, taskMap: MutableMap<Class<out AnchorTask>, AnchorTask>,
taskChildMap: MutableMap<Class<out AnchorTask>, ArrayList<Class<out AnchorTask>>?>
): MutableList<AnchorTask> {
val result = ArrayList<AnchorTask>()
// 入度为 0 的队列
val queue = ArrayDeque<AnchorTask>()
val taskIntegerHashMap = HashMap<Class<out AnchorTask>, Int>()
// 建立每个 task 的入度关系
list.forEach { anchorTask: AnchorTask ->
val clz = anchorTask.javaClass
if (taskIntegerHashMap.containsKey(clz)) {
throw AnchorTaskException("anchorTask is repeat, anchorTask is $anchorTask, list is $list")
}
val size = anchorTask.getDependsTaskList()?.size ?: 0
taskIntegerHashMap[clz] = size
taskMap[clz] = anchorTask
if (size == 0) {
queue.offer(anchorTask)
}
}
// 建立每个 task 的 children 关系
list.forEach { anchorTask: AnchorTask ->
anchorTask.getDependsTaskList()?.forEach { clz: Class<out AnchorTask> ->
var list = taskChildMap[clz]
if (list == null) {
list = ArrayList<Class<out AnchorTask>>()
}
list.add(anchorTask.javaClass)
taskChildMap[clz] = list
}
}
// 使用 BFS 方法获得有向无环图的拓扑排序
while (!queue.isEmpty()) {
val anchorTask = queue.pop()
result.add(anchorTask)
val clz = anchorTask.javaClass
taskChildMap[clz]?.forEach { // 遍历所有依赖这个顶点的顶点，移除该顶点之后，如果入度为 0，加入到改队列当中
var result = taskIntegerHashMap[it] ?: 0
result--
if (result == 0) {
queue.offer(taskMap[it])
}
taskIntegerHashMap[it] = result
}
}
// size 不相等，证明有环
if (list.size != result.size) {
throw AnchorTaskException("Ring appeared，Please check.list is $list, result is $result")
}
return result
}
AnchorTaskDispatcher
AnchorTaskDispatcher 这个类很重要，有向无环图的拓扑排序和多线程的依赖唤醒，都是借助这个核心类完成的。
它主要有几个成员变量。
// 存储所有的任务
private val list: MutableList<AnchorTask> = ArrayList()
// 存储所有的任务,key 是 Class<out AnchorTask>，value 是 AnchorTask
private val taskMap: MutableMap<Class<out AnchorTask>, AnchorTask> = HashMap()
// 储存当前任务的子任务， key 是当前任务的 class，value 是 AnchorTask 的 list
private val taskChildMap: MutableMap<Class<out AnchorTask>, ArrayList<Class<out AnchorTask>>?> =
HashMap()
// 拓扑排序之后的主线程任务
private val mainList: MutableList<AnchorTask> = ArrayList()
// 拓扑排序之后的子线程任务
private val threadList: MutableList<AnchorTask> = ArrayList()
//需要等待的任务总数，用于阻塞
private lateinit var countDownLatch: CountDownLatch
//需要等待的任务总数，用于CountDownLatch
private val needWaitCount: AtomicInteger = AtomicInteger()
它有一个比较重要的方法 setNotifyChildren(anchorTask: AnchorTask)，有一个方法参数 AnchorTask，它的作用是通知该任务的子任务，当前任务执行完毕，入度数减一。
/**
* 通知 child countdown,当前的阻塞任务书也需要 countdown
*/
fun setNotifyChildren(anchorTask: AnchorTask) {
taskChildMap[anchorTask::class.java]?.forEach {
taskMap[it]?.countdown()
}
if (anchorTask.needWait()) {
countDownLatch.countDown()
}
}
接下来看一下 start 方法。
fun start(): AnchorTaskDispatcher {
if (Looper.myLooper() != Looper.getMainLooper()) {
throw AnchorTaskException("start method should be call on main thread")
}
startTime = System.currentTimeMillis()
val sortResult = AnchorTaskUtils.getSortResult(list, taskMap, taskChildMap)
LogUtils.i(TAG, "start: sortResult is $sortResult")
sortResult.forEach {
if (it.isRunOnMainThread()) {
mainList.add(it)
} else {
threadList.add(it)
}
}
countDownLatch = CountDownLatch(needWaitCount.get())
val threadPoolExecutor =
this.threadPoolExecutor ?: TaskExecutorManager.instance.cpuThreadPoolExecutor
threadList.forEach {
threadPoolExecutor.execute(AnchorTaskRunnable(this, anchorTask = it))
}
mainList.forEach {
AnchorTaskRunnable(this, anchorTask = it).run()
}
return this
}
它主要干几件事。
class AnchorTaskRunnable(
private val anchorTaskDispatcher: AnchorTaskDispatcher,
private val anchorTask: AnchorTask
) : Runnable {
override fun run() {
Process.setThreadPriority(anchorTask.priority())
// 前置任务没有执行完毕的话，等待，执行完毕的话，往下走
anchorTask.await()
anchorTask.onStart()
// 执行任务
anchorTask.run()
anchorTask.onFinish()
// 通知子任务，当前任务执行完毕了，相应的计数器要减一。
anchorTaskDispatcher.setNotifyChildren(anchorTask)
}
}
3、通知子任务，当前任务执行完毕了，相应的计数器（入度数）要减一。
AnchorTask 的原理不复杂，本质是有向无环图与多线程知识的结合。
前置任务没有执行完毕的话，等待，执行完毕的话，往下走。 执行任务。 通知子任务，当前任务执行完毕了，相应的计数器（入度数）要减一。
介绍完原理，再看下用法。
第一步：在 moulde build.gradle 配置远程依赖。
implementation 'com.xj.android:anchortask:0.1.0'
最新的版本号可以看这里 lastedt version。
https://dl.bintray.com/xujun94/maven/com/xj/android/anchortask/
第二步：自定义 AnchorTaskB，继承 AnchorTask，重写相应的方法。
class AnchorTaskB : AnchorTask() {
override fun isRunOnMainThread(): Boolean {
return false
}
override fun run() {
val start = System.currentTimeMillis()
try {
// 在这里进行操作，这里通过睡眠模拟耗时操作
Thread.sleep(300)
} catch (e: Exception) {
}
com.xj.anchortask.library.log.LogUtils.i(
TAG, "AnchorTaskOne: " + (System.currentTimeMillis() - start)
)
}
// 返回依赖的任务，这里是通过 class name 去找到对应的 task
override fun getDependsTaskList(): List<Class<out AnchorTask>>? {
return ArrayList<Class<out AnchorTask>>().apply {
add(AnchorTaskA::class.java)
}
}
}
如果任务 C 依赖任务 B，任务 A，可以这样写：
class AnchorTaskC : AnchorTask() {
override fun getDependsTaskList(): List<Class<out AnchorTask>>? {
return ArrayList<Class<out AnchorTask>>().apply {
add(AnchorTaskA::class.java)
add(AnchorTaskB::class.java)
}
}
}
最后，通过 AnchorTaskDispatcher.instance .addTask(AnchorTaskFive())添加任务，并调用 start() 方法启动， await() 方法表示阻塞等待所有任务执行完毕。
AnchorTaskDispatcher.instance.setContext(this).setLogLevel(LogUtils.LogLevel.DEBUG).setTimeOutMillion(1000L).
.addTask(AnchorTaskZero())
.addTask(AnchorTaskOne())
.addTask(AnchorTaskTwo())
.addTask(AnchorTaskThree())
.addTask(AnchorTaskFour())
.addTask(AnchorTaskFive())
.start()
.await()
https://github.com/gdutxiaoxu/AnchorTask
- EOF -
看完本文有收获？请分享给更多人
推荐关注「安卓开发精选」，提升安卓开发技术
点赞和在看就是最大的支持❤️