一、Application 的启动流程
二、DAG有向无环图
在上图中，任务的执行有方向(有序)，且没有回环。在图论中，这种一个有向图无法从某个顶点出发经过若干条边回到该点，那么这个图就是一个有向无环图，简称DAG图。DAG常常被用来表示事件之间的驱动依赖关系，管理任务之间的调度。
在一个DAG中:
- 顶点c图中的一个点，比如任务1，任务2;
- 边连接两个顶点的线段叫做边;
- 入度:代表当前有多少边指向顶点（依赖多少任务);
- 出度:代表有多少边从顶点发出（被多少任务依赖)。
1、拓扑排序（根据任务的优先级和依赖关系排序）
在将我们的启动任务绘制完成DAG之后，我们接下来，就需要求出DAG的拓扑序列，即对我们的启动任务执行顺序进行排序。
对于上文中的任务依赖关系来说，我们只需要保证2与3在1之后执行，4在2之后，5在3、4任务之后执行即可。因此我们可以得到排序后的结果为:
- 1 ->2->3->4 ->5
- 1 ->2->4->3->5
- 1 ->3->2->4->5
因此图的拓扑排序不是唯一的！只要符合以下两点要求即可：
- 每个顶点出现且只出现一次。
- 若存在一条从顶点A到顶点B的路径，那么在序列中顶点A出现在顶点B的前面。
对DAG进行拓扑排序，我们可以选择BFS (广度优先）或者DFS(深度优先)。利用BFS的算法排序的过程如下:
- 找出图中0入度的顶点;
- 依次在图中删除这些顶点，删除后再找出0入度的顶点;
- 删除后再找出O入度的顶点，重复执行第二步
入度为0的顶点为任务1，得到结果:1
删除任务1后，此时任务2与任务3入度数由1变为0，得到结果:1->2->3
删除任务2后，任务4入度数由1变为0;删除任务3后，任务5入度数由2变为1，得到结果:1->2->3。
删除任务4后，任务5入度数由1变为0，得到结果:1->2->3->4-> 5。
三、Android Startup概述
Android Startup提供一种在应用启动时能够更加简单、高效的方式来初始化组件。开发人员可以使用Android Startup来简化启动序列，并显式地设置初始化顺序与组件之间的依赖关系。 与此同时，Android Startup支持同步与异步等待、手动控制依赖执行时机，并通过有向无环图拓扑排序的方式来保证内部依赖组件的初始化顺序。
在2021年8月4日，Android Jetpack组件中发布了AppStartup 1.1.0正式版本。但是AppStartup只提供了同步初始化与任务依赖的处理。因此Github上基于AppStartup有一个优化的: Android Startup:
https://github.com/idisfkj/android-startup/blob/master/README-ch.md
那么面对面试被问到启动优化，除了我们补充资料中的冷热暖启动、耗时统计、CPU Profile等内容之外，针对无法改动的初始化工作，我们就可以根据上述资料中介绍到的启动任务管理与面试官交流其中包含的各项技术。
四、BFS 和 DFS
广度优先搜索算法（Breadth-First-Search，缩写为 BFS），是一种利用队列实现的搜索算法。简单来说，其搜索过程和 湖面丢进一块石头激起层层涟漪 类似。
深度优先搜索算法（Depth-First-Search，缩写为 DFS），是一种利用递归实现的搜索算法。简单来说，其搜索过程和 不撞南墙不回头 类似。
BFS 常用于找单一的最短路线，它的特点是 搜到就是最优解，而 DFS 用于找所有解的问题，它的空间效率高，而且找到的不一定是最优解，必须记录并完成整个搜索，故一般情况下，深搜需要非常高效的剪枝（剪枝的概念请百度）。
五、资料和总结
5.1、总结
你是如何处理Android的启动优化的?
不改变现有启动任务执行逻辑的前提下，启动优化本质上就是解决任务的依赖性问题，依赖问题本质就是数据结构问题！什么是有向无环图，拓扑排序?
一个有向图无法从某个顶点出发经过若干条边回到该点，那么这个图就是一个有向无环图，简称DAG图。DAG常被用来表示事件之间的驱动依赖关系，管理任务之间的调度。拓扑排序是对一个有向图构造拓扑序列的过程。-
阻塞问题解决
如：A、B、C三个线程。AB线程先执行，C线程需要在AB线程执行完第二步再来执行。
用CountDownLatch解决。
5.2、资料
支付宝客户端架构解析:Android客户端启动速度优化之「垃圾回收」
支付宝 App 构建优化解析：通过安装包重排布优化 Android 端启动性能
六、具体分析
通常我们为了更快的达到目标，把与目标无关的事情，提到完成目标之后，通过减少执行代码从而减少执行时间的方式，叫着软优化。相对的，对于提升系统的吞吐效率，对于相同的代码用更少的执行时间完成，叫着硬优化。硬优化是面向硬件资源，包括CPU，内存，网络，磁盘 IO等的调度，减少等待时间，最大化利用硬件资源，保持系统负载在合理范围内。
总结下来无非就是两点：一是 如何保证时序 ；二是 怎么控制拥塞，提高吞吐，充实不瞎忙。我们先看一组实验数据，在并发下面的 IO 性能。
1、阶段划分
什么阶段做什么事情，前面打基础，只有夯实了基础，后期才能顺理成章。我们把 APP 的启动阶段做了以下细分：
- 启动流程如下：
可以看到：整个流程很清晰，分阶段、多任务并发执行，不存在老框架下几条初始化链路交错在一起的情况，首页那一块位置不受干扰。
2、任务编排
无锁化：得益于有向无环图，通过构建任务间的依赖，启动框架严格按照图的顺序执行各项 SDK 的初始化，真正做到时序可预期，原本需要靠锁来保证状态同步的，现在转变成了无锁化。
无锁化的好处：
代码执行效率高：SDK 的初始化基本上都需要考虑多线程安全问题，如果从时序上能保证顺序，也即不存在竞争，等同于无锁；减少 ANR，降低卡顿故障：比如我们之前查的网络库在 vivo y85a 上启动长时卡顿达 1s 以上的问题，如果我们能正确梳理各项 SDK 之间的依赖，类似的问题就可以避免了；
3、 任务调度
要支持多任务并发，那肯定绕不开线程池，既然要用到线程池，那线程池大小需要一个比较合理的设置。
核心思想
阶段（Stage）+ 线程池（ThreadPool Executor）线程池大小
因为我们的 SDK 大多涉及到 so 的加载、文件的读写，线程等待时间占比比较高，所以我采用了一个通用的估算方法：2N + 1，N 是 CPU 个数。线程优先级
把先于首页（落地页）的阶段的线程优先级都调高一些，以求得到优先调度，尽快执行；进入 idle 阶段后，性质原因，慢任务居多，调整线程池大小，同时把优先级调低，做到尽量不干扰 UI 主线程，在后台慢慢跑。
启动环境是应用中最为复杂环节，任务多，负载重，资源争抢下，不管是 CPU ，内存，网络，IO都有可能成为瓶颈，启动框架的引入，让我们在面对这些挑战时，有了一个明确的方向，给出一个稍微系统化的解。当然，系统资源调度优化是个非常深刻的课题，加上手机各种硬件配置多样性，我们在这个领域仍然面临更大的挑战，当前只是一个开始。
4、问题定义
网络的链路优化
可以看到，手淘首次安装冷启动30s内，网络请求数达到 400上下。非首次冷启动30s内，请求数相比首装冷启减少，但依然在 100+。启动场景下，存在着以下几个问题：
- 请求过多：重复请求、请求滥发情况严重。
- 数据量过大：资源文件的下载占流量的80%以上。
- 业务方请求时机不合理：非首页&启动必要请求需延后。
过量的请求集中在启动阶段导致原本就有限的网络带宽和端上处理能力更加严峻。
5、深入剖析
一直以来，性能埋点方案均为独立的模块，更多针对各个SDK关注自身的请求性能。但是从一个数据或图片请求链路上来看，一个完整的请求往往跨越多个核心SDK。特定场景内（启动），每个环节的耗时都会牵一发而动全身影响请求的性能，剥离完整请求和特定场景单纯从某个中间模块看整体性能往往不能发现最根本的问题。就现状而言，独立SDK的埋点方案显然不能够把一个请求串联起来，以一个场景切入做更精准的分析。因此，亟需从特定场景下请求的完整链路角度来分析，以揪出各个阶段的耗时请求。
对于请求整个链路，我们把请求的关键耗时阶段抽象为以下几点。
发送处理：本地处理耗时，包含数据或图片库处理，网络库处理耗时网络库耗时：纯网络传输时间返回处理：包括网络库响应处理回调和上层图片库的处理（json解析/图片解码）操作回调消息-回调执行：任务dispatch到主线程并开始消费的耗时，反映主线程的流畅程度回调执行-回调返回：业务在回调内部执行处理的耗时
从首次安装冷启动的场景切入，我们线下针对启动30s内的请求在图片库、网络库内部进行了日志打点统计，以获取请求全链路各个关键阶段的耗时情况。如下图：
分析启动请求耗时阶段，针对每个阶段得出以下结论和优化点：
发送处理阶段：网络库bindService影响前x个请求，图片并发限制图片库线程排队。网络耗时：部分请求响应size大，包括 SO文件，Cache资源，图片原图大尺寸等。返回处理：个别数据网关请求json串复杂解析严重耗时（3s），且历史线程排队设计不合适。上屏阻塞：回调UI线程被阻，反映主线程卡顿严重。高端机达1s，低端机恶化达3s以上。回调阻塞：部分业务回调执行耗时，阻塞主线程或回调线程。
6、请求治理
对于应用启动，尽快地完成启动展现可交互页面给用户是第一要务。有限的网络带宽和端上处理能力，意味着过多的请求势必会导致资源争抢更加严重。首页无关&不合理请求很大程度上回阻塞启动主链路请求的响应耗时。
针对启动阶段请求，我们开展了请求治理行动，每个请求责任到人，横向推动业务方评估请求的必要性。主要从以下几个方面展开：
多次重复的请求：业务方务必收敛请求次数，减少非必须请求。数据大的请求：如资源文件、so文件，非启动必须统一延后或取消。业务方回调执行阻塞主线程耗时过长整改：我们知道，肉眼可见流畅运行，需要运行60帧/秒， 意味着每帧的处理时间不超过16ms。针对主线程执行回调超过16ms的业务方，推动主线程执行优化。协议json串过于复杂导致解析耗时严重：网络并发线程数有限，解析耗时过长意味着请求长时间占用MTOP线程影响其他关键请求执行。推动业务方handler注入使用自己的线程解析或简化json串。
7、 数据指标定义
第一个维度-指标：定义合适的数据指标，结合业务场景，多方位评估启动和页面的用户体感性能。
1、数据指标：经过手淘用户体验提升项目组的讨论，定义了如下指标来衡量用户的体感数据， 之前大部分的响应时长只规定了渲染完成时长， 可以反映应用的部分性能情况，但是渲染完成后用户多久可以对应用进行操作， 是否有卡顿，无法通过该指标观察到。因此新增了两个指标，可交互时长和可流畅交互时长，可以比较直观的反映用户最早可以对应用进行交互的时间。
-
渲染时长：点击进入页面，页面80%以上内容渲染完毕。
-
可交互时长：页面渲染完毕后立即开始滑屏操作，页面能响应滑屏事件那一刻即为可交互时长。
-
可流畅交互时长：页面进入可交互状态后，匀速连续上下滑动屏幕，直至屏幕上下滚动跟手势同步次数超过3次以上即可判断为可流畅交互。
2、业务场景：不论是应用启动还是在应用中打开页面都会有不同的业务场景。只有从多个不同的场景下对应用进行多角度评估， 获得的数据才能够全面反映用户在不同情况下的真实感受。
- 启动：可按照不同的安装方式、启动方式、启动发起方分为不同的启动业务场景。
- 页面打开：可按照不同的页面进入方式氛围不同的页面响应时间业务场景。
第二个维度-自动化：自动化手段可以支撑实现体感数据的高效采集和3个用户体感数据的准确计算。
第三个维度-流程：通过指标定义， 以及对应指标数据的自动化采集，我们可以在发布前、发布中、发布后的全研发流程中对应用的用户体感性能进行评估。
7、关键点识别
主要思路是从视频中找出来渲染完成、可交互完成、可流畅交互完成几个节点的关键特征，通过程序算法去进行识别。
考虑过的几种识别算法：
- 算法1: 相邻两帧变化趋于平稳，无变化时，认为渲染完成， 经过实验后发现对于存在动画的页面，该算法的结果会比实际情况要长。
- 算法2: 使用参考帧概念，将业务页面渲染完成的图片作为参考， 比较每一帧与该参照图的相似度， 当相似度>=门限时，认为启动完成。该算法的缺点是对于一些变化频繁的页面， 比如首页更换了banner图或氛围，变了投放元素，原来的参考图就无效了，需要进行更换且更换成本较高。
- 算法3: 检测关键特征，如8个icon， 5个tab都出现认为启动完成。这个算法的难点在于不同页面的特征提取，需要比较多的调整工作，而且在不同分辨率的手机上特征出现情况可能不一样， 还需要根据屏幕适配。
- 算法4：通过OCR提取图片中的文字信息作为关键特征。该算法的优势：1. 在于应用页面上基本都是有文字的， OCR也可以识别到图片上的文字， 文字出现则图片加载完成， 和用户体感是一致的；2. 文字作为特征，过滤掉了很多图片特征可能带来的噪声， 减少了算法调试的工作量；另外阿里集团内有非常成熟和优秀的OCR服务——读光，文档识别率超过99.7%， 使用水滴平台封装的OCR服务，可以快速接入和使用。最终的识别方案就是基于OCR识别来进行的，以下介绍下基于OCR的识别方案的改进过程。
通过观察视频，我们可以发现这样一个规律， 中转页， 开始进入页面， 页面渲染完成，页面可滑动这几种状态下， OCR字符串长度是不一样的，并且由于操作的固定性（进入页面，来回滑动）这个曲线存在一定的模式，基本可以分为两种， 一种是可滑动后滑动到的页面字数比渲染完成要多， 另一种是可滑动后滑动到的页面字数比渲染完成要少。
8、小结
性能优化是老生常谈的问题，说简单也不简单，需要一个系统化的视角来分析和解决。找问题，不仅仅是要看到某段区间慢了，更要去深入分析，为什么慢了。trace 上一段方法执行时间过长，有可能是本身逻辑复杂，或是有 IO 等耗时操作，也有可能是因为 CPU 调度，IO 竞争等原因，因此，在分析上一定要能系统化进行全局思考。
工具是性能优化利器，除了使用像 trace 及 systrace，过渡绘制等常见的工具，还用到一些 linux 命令，直观的观察系统内各进程及线程的运行情况，当前系统负载情况等，当然，原生工具还是有一些局限性，特别是像IO 的读写分析这样特别领域，还是显得有些力不从心，为此在优化过程中我们也沉淀了不少的工具，比如细粒度方法级耗时监控，及IO 读写的监控，有了合适的工具，能极大的提高效率。
整个优化过程中，发现问题不难，难的是对解决方案技术决策。这次优化过程中，我们发现比较大的一个问题是代码规模迅速膨胀，功能堆砌式累积，启动整个系统运行时的效率偏低，当前手淘的架构不能满足对极致体验的要求。因此我们的主要手段是对启动框架重新定义，包括前面提到的对任务进行按序编排，对网络资源的合理使用，减少排队情况，以此提升系统的吞吐率。优化过程除了拼智力，还得拼体力。手淘的业务规模十分复杂，上百个启动任务需要重新 reivew，梳理特性编排顺序，还有数百个网络请求的清理，用阿里的土话说，脑力，心力，体力，缺一不可。
一般说在缓存的使用场景上，通常是借助于 LRU 算法或是其变种，提升 cache 的命中率。智能化预加载，是我们在优化过程进一步尝试，希望在命中率与下载缓存数上寻找到一个最适合的奇点。这次针对 H5 的缓存优化，我们尝试使用了机器学习的方式，通过统计用户的使用习惯及 H5 的访问频次来设计H5的缓存下载，在大辐降低下载缓存数量的同时，又保证了命中率的基本稳定。
无人化验证优化数据，在整个性能优化过程是非常重要的一环，能够快速验证优化是否有效。除了性能本身的收益之外，我们更需要关注优化对业务的影响。对于手淘来说，要在前进中，重构架构无疑是相当于飞行中更换引擎，任何不经意一句代码，都可能对业务造成严重的影响。而 AB 实验，在优化过程中扮演着非常关键的决策的角色，我们的优化项是否能真正上线，一切以 AB 实验的结果为依据。借助于AB 实验，隔离掉无关因素，认真核对实验中的数据是否存在不可预期的变化，及时控制其中风险
