Add new sorting mechanism.
Create a pending job sorting mechanism that is more like
topological-sort. The new system sorts pending jobs for each
individual app and then picks from each app's list based on the adjusted
"enqueue" time to retain some fairness. This new sorting may result in
an app's jobs being run more closely together (which helps reduce the
number of separate process startups).
Runtime changes (A=# of apps, J=average # jobs per app):
Previous implementation New implementation
Sorting: A*J*log(A*J) A*J*log(J)
Insertion: log(A*J) log(A*J)+J
Remove(Object): A*J log(A*J)
Iteration: A*J A*J*log(A)
Contains: A*J log(A*J)
Bug: 141645789
Bug: 204924801
Bug: 223437753
Test: atest frameworks/base/services/tests/servicestests/src/com/android/server/job
Test: atest frameworks/base/services/tests/mockingservicestests/src/com/android/server/job
Change-Id: Ie077c5ad1cd6c0bd4ff4a9f1e2f000ed99c048b0
2 files changed