难得的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 之前。

了解原理之前，请必须先了解有向无环图和多线程的一些基本知识，不然，下文，你基本是看不懂的。

一个共识

前置任务：任务 3 依赖于任务 0，1，那么任务 3 的前置任务是任务 0， 1。

子任务：任务 0 执行完之后，任务 3 才能执行，那么称呼任务 3 为任务 0 的子任务。

如何构建一个有向无环图

这里我们采用 BFS 方法实现。

多线程中，任务执行是随机的，那如何保证任务被依赖的任务先于任务执行呢？

这里要解决的主要有三个问题

1、首先我们要解决一个问题，它有哪些前置任务，这个可以用 list 存储，代表它依赖的任务 list。当它所依赖的任务 list 没有执行完毕，当前任务需要等待。

2、当前任务执行完毕之后，所有依赖它的子任务需要感知到。我们可以用一个 map 来存储这种关系，key 是当前任务，value 是依赖于当前任务的集合（list）。

3、多线程当中，等待和唤醒功能，有多种方式可以实现。wait、notify 机制，ReentrantLock Condition 机制，CountDownLatch 机制。这里我们选择 CountDownLatch 机制，因为 CountDownLatch 有点类似于计数器，特别适合这种场景。

具体实现

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()

}

它有一个实现类 AnchorTask，增加了 await 和 countdown 方法。

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。

3、taskChildMap: MutableMap<Class<out AnchorTask>, ArrayList<Class<out AnchorTask>>?> = HashMap(),储存当前任务的子任务， key 是当前任务的 class，value 是 AnchorTask 的 list。

算法思想

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
}

它主要干几件事。

1、检测是否在主线程，不是抛出异常，这里为什么要检测在主线程呢？主要是构建有向无环图的过程，我们必须保证是线程安全的。

2、获取有向无环图的拓扑排序。

3、根据拓扑排序的排序结果，执行相应的任务。可以看到在执行任务的时候，我们使用 AnchorTaskRunnable包裹起来。


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)
    }
}

AnchorTaskRunnable 有点类似于装饰者模式，多线程依赖的执行关系在这里都得到体现，只有几行代码。

1、前置任务没有执行完毕的话，等待，执行完毕的话，往下走。

2、执行任务。

3、通知子任务，当前任务执行完毕了，相应的计数器（入度数）要减一。

AnchorTask 的原理不复杂，本质是有向无环图与多线程知识的结合。

1、根据 BFS 构建出有向无环图，并得到它的拓扑排序。

2、在多线程执行过程中，我们是通过任务的子任务关系和 CounDownLatch 确保先后执行关系的。

前置任务没有执行完毕的话，等待，执行完毕的话，往下走。
执行任务。
通知子任务，当前任务执行完毕了，相应的计数器（入度数）要减一。

介绍完原理，再看下用法。

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