koin
koin copied to clipboard
InsertKoinIO
Optimizing traversal over linked scopes
We've been developing a large multi-module application. Not to store a large number of "single" definitions in memory, we came up with a scope mechanism for a gradle module. The scope of the module is active while fragments using the entities of this module are displayed. With the growth of the application, many scopes with a large number of links between them were created (using link()).
When traversing a scope tree while looking for a definition, the problem occurs. I will give an example: Scope A contains linked scopes B, C, and D Scope B contains linked scopes E and F Scope C contains linked scope B
Consider the worst-case scenario of linked scopes traversal: We are looking for the definition from scope D starting with scope A. When scope A does not contain the required definition, function findInOtherScopes() is called, then go to scope B, then go to scopes E, and F. So, we made sure that Scope B also does not contain the required definition. Then, go to scope C, that leads to scope B, which contains E and F. Finally, we go to D and resolve desired definition.
The search took place two times in the scopes B, E, F. If you scale this example to 30 scopes with a large number of links, it will turn out that in some scopes resolveValue() will be called hundreds of times, which has a very negative impact on performance. For example, a large ViewModel requires 3 seconds to resolve dependencies. The same takes only 150 ms with the proposed improvements. I understand that our case is very specific, but if Koin allows developers to work flexibly with scopes and create large relationship graphs, then it will be useful to optimize this traversal using memoization. The idea is to store the qualifiers of already visited scopes when traversing in order to call the resolveValue() function only once in each scope for the requested class.
Hi! I came up with a better solution for linked scopes traversal.
The goal is the same: resolve dependencies faster in linked scopes.
The current algorithm uses depth-first search using recursive calls findInOtherScope.
But breadth-first search is more suitable for this task, because the required definitions are more likely to be in the nearest scopes than in the more outlying (or deep) scopes. For example if I link scope A with some scopes B and C, I would expect to get the required definition from B or C, not from its linked scopes.
But that's not the most important thing. The main difference is the addition of a new method specifically for searching linked scoped (resolveLinkedScopeInstanceOrNull).
Firstly, it does not search in injected parameters, because it is enough to perform this search 1 time in the topmost scope.
Second, it doesn't throw an exception. Multiple throws are quite expensive in terms of performance due to stacktrace filling.
The new method returns null in case of exception and the search moves on to the next scope.
But this only applies to searching in linkeds scopes, resolveValue will still throw exceptions if the definiton is not found.
Also all tests pass without errors.
This algorithm is on average 2 times faster compared to the previous solution with only memoization.
I will be glad to discuss and receive feedback!
I will update this pull request after https://github.com/InsertKoinIO/koin/pull/1561