Start optimized directed acyclic graph task management
Launch performance is the user’s first impression when using the APP, so it is very important. I believe many students can name some conventional methods, such as
Such as loading only necessary modules, lazy loading, etc. From a large-scale strategic perspective, there is no problem and some results can be achieved, but there are still some problems.
Why do you need to start the framework?
For many APPs, because startup includes many basic SDKs, the initialization of SDKs has a certain sequence; business SDKs revolve around multiple
Built with the basic SDK. So how to ensure that these SDKs are initialized efficiently at the correct stage, in the correct dependency order? How to reasonably schedule tasks
services so as not to overload the system?
For example, we have 5 initialization tasks, and there are dependencies between these 5 tasks as shown below:
Initialization Task 1 is executed first, Task 2 and Task 3 need to wait for Task 1 to be executed, Task 4 needs to wait for Task 2 to be executed, Task 3 and Task 4 are completed.
After the execution is completed, task 5 can be executed.
Faced with the complex dependency scenarios between the above initialization tasks, how should we solve them?
At this time, we actively call according to the task execution order according to the task dependencies:
new Thread{<!-- -->
public void run(){<!-- -->
SDK1.init();
SDK2.init();
SDK3.init();
SDK4.init();
SDK5.init();
}
}
Doing this will cause task 3 to wait for task 2 to complete before it can be executed!
Therefore we can put Task 2 into a separate asynchronous thread to complete the initialization:
new Thread{<!-- -->
public void run(){<!-- -->
SDK1.init();
//Execute asynchronously alone
new Thread(){<!-- -->
public void run(){<!-- -->
SDK2.init();
}
}.start();
SDK3.init();
SDK4.init(); //May be executed before SDK2 is completed
SDK5.init();
}
}
According to the dependency relationship, we know that task 4 needs to wait for task 2 to be completed. However, the above code may cause task 2 to be incomplete and task 4 to start executing.
OK situation.
Then we change again:
new Thread{<!-- -->
public void run(){<!-- -->
SDK1.init();
Thread t2 = new Thread(){<!-- -->
public void run(){<!-- -->
SDK2.init();
}
}.start();
t2.start();
SDK3.init();
t2.join(); // join waits for SDK2 initialization to complete
SDK4.init();
SDK5.init();
}
}
At this time, if task 2 is executed first, task 4 should be executed immediately, but in the above code, task 4 needs to wait for task 3 to be executed.
In the end we found that no matter what we did, we would encounter different problems. And when our initial tasks are more and the relationships are more complex, the hand
Automatically managing the execution of our tasks becomes extremely cumbersome and error-prone. And in the face of ever-changing needs, once the startup task changes (added, deleted
(Exception, dependency changes) If there is no design, it will “change the whole body.” So at this time, we need a startup framework to help us complete the startup
Management and scheduling of mobile tasks.
Startup framework design
In fact, the startup framework is a task scheduling system. What needs to be done is to sort out the relationship between the initial tasks clearly, orderly, and reasonably arrange them.
Scheduling positions and scheduling time, while improving the utilization of hardware resources.
Task management
On the premise that our application side does not change the existing startup task execution logic, startup optimization is essentially to solve the task dependency problem, that is, execute first
What, execute what again. The essence of the dependency problem is the problem of data structure.
DAG directed acyclic graph
Based on the relationship between startup tasks, we draw the corresponding diagrams as follows:
In the above figure, the execution of tasks is directed (ordered) and there are no loops. In graph theory, such a directed graph cannot start from a certain vertex and pass through several lines.
If the edge returns to this point, then this graph is a directed acyclic graph, or DAG graph for short. DAG is often used to represent driver dependencies between events and manage
Scheduling between tasks.
In a DAG:
Vertex: a point in the graph, such as task 1, task 2;
Edge: A line segment connecting two vertices is called an edge;
In-degree: represents how many edges currently point to the vertex (depending on how many tasks);
Out-degree: represents how many edges originate from the vertex (how many tasks it depends on).
Topological sorting
After drawing our startup tasks into the DAG, we next need to find the topological sequence of the DAG, that is, the execution sequence of our startup tasks
Sort.
For the task dependencies above, we only need to ensure that 2 and 3 are executed after 1, 4 is executed after 2, and 5 is executed after tasks 3 and 4. because
From this we can get the sorted result as:
1 -> 2 -> 3 -> 4 -> 5
1 -> 2 -> 4 -> 3 -> 5
1 -> 3 -> 2 -> 4 -> 5
Therefore the topological ordering of the graph is not unique! As long as the following two requirements are met:
Each vertex appears exactly once.
If there is a path from vertex A to vertex B, then vertex A appears before vertex B in the sequence
For topological sorting of DAG, we can choose BFS (Breadth First) or DFS (Depth First). The process of sorting using the BFS algorithm is as follows:
- Find the vertex with 0 in-degree in the graph;
- Delete these vertices in the graph in turn, and then find the vertices with 0 in-degree after deletion;
- After deleting, find the vertex with 0 in-degree and repeat the second step.
The vertex with indegree 0 is task 1, and the result is: 1
After deleting task 1, the degree of integration between task 2 and task 3 changes from 1 to 0, and the result is: 1 -> 2 -> 3
After deleting task 2, the degree of task 4 changes from 1 to 0; after deleting task 3, the degree of task 5 changes from 2 to 1, and the result is: 1 -> 2 -> 3
After deleting task 4, the entry degree of task 5 changes from 1 to 0, and the result is: 1 -> 2 -> 3 -> 4 -> 5
Code implementation
Based on the previous scenario, we design the Startup interface:
public interface Startup<T> extends Dispatcher {<!-- -->
T create(Context context); //Perform initialization tasks
/**
* Which tasks does this task depend on?
*
* @return
*/
List<Class<? extends Startup<?>>>> dependencies();
//Number of dependent tasks (number of in-degrees)
int getDependenciesCount();
}
At the same time, an AndroidStartup abstract class is provided. The current function of this abstract class is very simple and is implemented according to dependencies.
getDependenciesCount method:
public abstract class AndroidStartup<T> implements Startup<T> {<!-- -->
@Override
public List<Class<? extends Startup<?>>> dependencies() {<!-- -->
return null;
}
@Override
public int getDependenciesCount() {<!-- -->
List<Class<? extends Startup<?>>> dependencies = dependencies();
return dependencies == null ? 0 : dependencies.size();
}
}
Based on the above interfaces and abstract classes, we can define our own startup task classes:
public class Task1 extends AndroidStartup<String> {<!-- -->
@Nullable
@Override
public String create(Context context) {<!-- -->
//Perform initialization
return "Task1 returns data";
}
}
public class Task2 extends AndroidStartup<Void> {<!-- -->
static List<Class<? extends Startup<?>>> depends;
static {<!-- -->
//This task depends on task 1
depends = new ArrayList<>();
depends.add(Task1.class);
}
@Nullable
@Override
public Void create(Context context) {<!-- -->
//Perform initialization
return null;
}
@Override
public List<Class<? extends Startup<?>>> dependencies() {<!-- -->
return depends;
}
}
Finally we complete the code implementation of topological sorting:
1. Find the task with in-degree 0
At this step, we also recorded the following table:
List<? extends Startup<?>> startupList; //Input list of tasks to be sorted
Map<Class<? extends Startup>, Integer> inDegreeMap = new HashMap<>();
Deque<Class<? extends Startup>> zeroDeque = new ArrayDeque<>();
Map<Class<? extends Startup>, Startup<?>> startupMap = new HashMap<>();
Map<Class<? extends Startup>, List<Class<? extends Startup>>> startupChildrenMap
= new HashMap<>();
for (Startup<?> startup : startupList) {<!-- -->
//startupMap task table
startupMap.put(startup.getClass(), startup);
//inDegreeMap in-degree table: records the in-degree of each task (number of dependent tasks)
int dependenciesCount = startup.getDependenciesCount();
inDegreeMap.put(startup.getClass(), dependenciesCount);
//zeroDeque (0 in-degree queue): records tasks with an in-degree number (number of dependent tasks) of 0
if (dependenciesCount == 0) {<!-- -->
zeroDeque.offer(startup.getClass());
} else {<!-- -->
//Traverse the dependent (parent) task list of this task
for (Class<? extends Startup<?>> parent : startup.dependencies()) {<!-- -->
List<Class<? extends Startup>> children = startupChildrenMap.get(parent);
if (children == null) {<!-- -->
children = new ArrayList<>();
//startupChildrenMap task dependency table: record the child task startup of this parent task parent
startupChildrenMap.put(parent, children);
}
children.add(startup.getClass());
}
}
2. Delete tasks with an in-degree of 0
List<Startup<?>> result = new ArrayList<>(); //Sort the results
//Process tasks with in-degree 0
while (!zeroDeque.isEmpty()) {<!-- -->
Class<? extends Startup> cls = zeroDeque.poll();
Startup<?> startup = startupMap.get(cls);
result.add(startup);
//Delete this task with indegree 0
if (startupChildrenMap.containsKey(cls)){<!-- -->
List<Class<? extends Startup>> childStartup = startupChildrenMap.get(cls);
for (Class<? extends Startup> childCls : childStartup) {<!-- -->
Integer num = inDegreeMap.get(childCls);
inDegreeMap.put(childCls,num-1); //In-degree-1
if (num - 1 == 0){<!-- -->
zeroDeque.offer(childCls);
}
}
}
}
In this step, we first delete Task1 with an in-degree of 0 and record it in the result set result; after deleting Task1, through the task dependency
Table: startupChildrenMap, find Task2 and Task3:
Then reduce the in-degrees of Task2 and Task3 by one from the in-degree table: inDegreeMap:
If it is found that the entry degree of Task2/Task3 becomes 0 after minus one, then add it to the zero entry queue: zeroDeque:.
Continue looping until processing is complete. This is the process of implementing topological sorting using breadth search!
Thread management
The startup tasks can be executed in an orderly manner after topological sorting based on DAG, but do all initialization tasks must be required when we start the program?
Should I block the main thread to initialize it? So at this time we have to consider adding a thread management module, so now we encounter such a situation
A requirement: Now we have to put the five tasks into sub-threads for initialization and execution, and at the same time ensure the order of execution between the tasks. At this time we should
what to do?
Let’s take a look at the interview process:
Q: Assume there are two threads A and B. Thread B needs to be executed after thread A completes execution.
A:
Thread t1 = new Thread() {<!-- -->
@Override
public void run() {<!-- -->
System.out.println("Execute the first thread task!");
}
};
t1.start();
t1.join(); //Block waiting for thread 1 to complete execution
Thread t2 = new Thread() {<!-- -->
@Override
public void run() {<!-- -->
System.out.println("Execute the second thread task!");
}
};
t2.start();
Q: Suppose there are two threads A and B. The execution in thread A is divided into three steps. How can I continue to execute the code of thread B after thread A completes the second step?
What to do?
A:
Object lock = new Object();
Thread t1 = new Thread() {<!-- -->
@Override
public void run() {<!-- -->
System.out.println("The first step is completed!");
System.out.println("The second step is completed!");
synchronized (lock) {<!-- -->
lock.notify();
}
System.out.println("The third step is completed!");
}
};
Thread t2 = new Thread() {<!-- -->
@Override
public void run() {<!-- -->
synchronized (lock) {<!-- -->
try {<!-- -->
lock.wait();
} catch (InterruptedException e) {<!-- -->
e.printStackTrace();
}
}
System.out.println("Execute the second thread task!");
}
};
t2.start();
t1.start();
Q: Suppose there are three threads A, B, and C. The execution of threads A and B is divided into three steps. Thread C needs to be executed when both thread A and thread B have reached the second step.
Execution, what to do?
A:
Object lock1 = new Object();
Object lock2 = new Object();
Thread t1 = new Thread() {<!-- -->
@Override
public void run() {<!-- -->
System.out.println("t1: The first step is completed!");
System.out.println("t1: The second step is completed!");
synchronized (lock1) {<!-- -->
lock1.notify();
}
System.out.println("t1: The third step is completed!");
}
};
Thread t2 = new Thread() {<!-- -->
@Override
public void run() {<!-- -->
System.out.println("t2: The first step is completed!");
System.out.println("t2: The second step is executed!");
synchronized (lock2) {<!-- -->
lock2.notify();
}
System.out.println("t2: The third step is completed!");
}
};
Thread t3 = new Thread() {<!-- -->
@Override
public void run() {<!-- -->
synchronized (lock1) {<!-- -->
try {<!-- -->
lock1.wait();
} catch (InterruptedException e) {<!-- -->
e.printStackTrace();
}
}
synchronized (lock2) {<!-- -->
try {<!-- -->
lock2.wait();
} catch (InterruptedException e) {<!-- -->
e.printStackTrace();
}
}
System.out.println("Execute the third thread task!");
};
t3.start();
t2.start();
t1.start();
In the Q&A above, the last question:
Suppose there are three threads A, B, and C. The execution of threads A and B is divided into three steps. Thread C cannot be executed until both thread A and thread B have reached the second step. What should I do?
According to the interviewer’s answer, thread 3 first waits for the notification from thread 1, and then waits for the notification from thread 2 before it can be executed. However, if thread 2 passes
The notification arrives before thread 1’s notification. Then at this time, thread 3 will always be blocked because thread 1 has already issued a notification.
So facing the above problems, we need to use latching – CountDownLatch can solve this problem very well:
When initializing CountDownLatch, you need to specify a status value, which can be regarded as a counter.
When we call the await method, if the status value is 0, blocking will not occur, otherwise it will block. After calling the countDown method, the CAS machine will be used
Control the status value by -1 until the status value is 0, await will no longer block!
CountDownLatch countDownLatch = new CountDownLatch(2);
Thread t1 = new Thread() {<!-- -->
@Override
public void run() {<!-- -->
System.out.println("t1: The first step is completed!");
System.out.println("t1: The second step is completed!");
countDownLatch.countDown();
System.out.println("t1: The third step is completed!");
}
};
Thread t2 = new Thread() {<!-- -->
@Override
public void run() {<!-- -->
System.out.println("t2: The first step is completed!");
System.out.println("t2: The second step is executed!");
countDownLatch.countDown();
System.out.println("t2: The third step is completed!");
}
};
Thread t3 = new Thread() {<!-- -->
@Override
public void run() {<!-- -->
try {<!-- -->
countDownLatch.await();
} catch (InterruptedException e) {<!-- -->
e.printStackTrace();
}
System.out.println("Execute the third thread task!");
};
t3.start();
t2.start();
t1.start();
Therefore, we modified the interface and abstract class created in the first step and added:
public abstract class AndroidStartup<T> implements Startup<T>{<!-- -->
//.....
//Create a lock based on the number of in-degrees (number of dependent tasks)
private CountDownLatch mWaitCountDown = new CountDownLatch(getDependenciesCount());
//When executing this task, call toWait
@Override
public void toWait() {<!-- -->
try {<!-- -->
mWaitCountDown.await();
} catch (InterruptedException e) {<!-- -->
e.printStackTrace();
}
}
//When the task that I have no dependencies on is completed, I need to call toNotify of this task.
@Override
public void toNotify() {<!-- -->
mWaitCountDown.countDown();
}
// Whether to execute in the main thread
boolean callCreateOnMainThread();
// If executed in a child thread, specify the thread pool
Executor executor();
//.....
}
So far we have solved the thread synchronization problem very well with the help of lock-CountDownLatch!
Solution to blocking problem
So far we have solved the problem of task execution order and thread management, but what if we face such a scenario?
Task 2 must be executed in the main thread, and other tasks are executed in child threads.
If we sort, the topological sequence obtained is: 12345.
If asynchronous task 1 is executed, since synchronous task 2 needs to be executed on the main thread, asynchronous task 3 can only wait for synchronous task 2 to be executed.
Get distributed execution!
Faced with the above scenario, because Task 3 needs to wait for Task 2 to be completed, we cannot reasonably use multi-threaded resources and have no impact on the application startup speed.
Complete optimization has been achieved. At this point we need to transform our topological sort.
In the second step of topological sorting code implementation, we change the code to:
List<Startup<?>> result = new ArrayList<>();
List<Startup<?>> main = new ArrayList<>(); //Tasks performed by the main thread
List<Startup<?>> threads = new ArrayList<>(); //Tasks performed by child threads
while (!zeroDeque.isEmpty()) {<!-- -->
Class<? extends Startup> cls = zeroDeque.poll();
Startup<?> startup = startupMap.get(cls);
//Revise
if (startup.callCreateOnMainThread()) {<!-- -->
main.add(startup);
} else {<!-- -->
threads.add(startup);
}
...
}
//Add child thread to result first
result.addAll(threads);
result.addAll(main);
After modification, if the previous sorting result was: 12345, it will become: 13452.
The execution process at this time is:
Task1 -> sub-thread execution
Task3 -> Child thread waits for Task1
Task4 -> Child thread waits for Task2
Task5 -> Child thread waits for Task3 + Task4
Task2 -> main thread waits for Task1
If Task1 is completed, Task2 and Task3 will be executed in the main thread and child thread respectively;
If Task3 is completed, Task5 will continue to wait for Task4;
Task4 is waiting for Task2 to complete execution. After Task2 is completed, it notifies Task4 to execute (toNotify);
Task4 is executed and Task5 is executed.
Therefore, we actually implement topological sorting of sub-thread tasks and main thread tasks, first distribute all sub-thread tasks, and then execute the main thread tasks.
This satisfies the task execution sequence.
Summary
On August 4, 2021, the official version of AppStartup 1.1.0 was released in the Android Jetpack component. But AppStartup only provides initial synchronization
ization and task dependency handling. Therefore, there is an optimized one based on AppStartup on Github: Android Startup: https://github.com/idisf
kj/android-startup/blob/master/README-ch.md
In fact, the above content introduces the principle of this framework to you:
Then when asked about startup optimization in the interview, in addition to the hot and cold startup, time-consuming statistics, CPU Pro?le and other contents in our supplementary information, for those who cannot
For the initialization work of the changes, we can communicate with the interviewer about the various technologies included in it based on the startup task management introduced in the above information.
Derivative reading
Alipay client architecture analysis: Android client startup speed optimization “garbage collection”
Alipay App build optimization analysis: Optimizing Android startup performance through installation package rearrangement