This is an idea that I raised on the Discord a long time ago, it relates to #3993, #3618, and #3334. I thought it best to (finally) make a tracked issue for it, as otherwise it will be lost to time. This is something that I am unsure if I can do myself, so help is very welcome. (I will try though, as this has recently become an issue for me again while doing some more complicated projects.)
Currently, if you have many complicated dependency relations, performance for all your reports will pretty much tank, and this performance hit will increase the more you have assuming rc.urgency.inherit=1. Performance for modifications also seems to be affected in TW v3 much more (compared to v2), but I am not sure if this is related to these functions or some other ones, so that should be saved for a different issue. I haven't yet checked if TW is using native TW functions or native Taskchampion functions for those.
These issues seem to relate to the implementation of a few functions in TW's code. Bear with me if I've misunderstood any of it - I don't really know C++ nor am I a software engineer.
If I'm reading the code right, pending tasks are loaded via TDB2::pending_tasks() which then runs dependency_scan(std::vector<Task>& tasks), each time TW is run. This does cache whether the task is blocking some other task, and whether the task is blocked, but it doesn't seem to cache any other information about the dependency relationships. Other functions then must reconstruct that information, and if rc.urgency.inherit=1 this means that urgency_inherit() will invoke getBlockedTasks() and getDependencyTasks() for each task, recursively - the information related to this is not cached, regardless of whether they have changed or not (as far as I understand) - though once an urgency score is calculated for some task, that at least is reused by other functions. Presumably though, given inheritance means urgency will change during resolution, that doesn't save us much.
To caculate the urgency of some task A, TW will call urgency() and then urgency_inherit() and getBlockedTasks() which will scan all blocked tasks. For each blocked task, this repeats. If task C blocks the same tasks, it must redo all of this work for every single task and every single dependency, and every single dependency of those dependencies.
urgency_inherit() itself doesn't seem particularly expensive, as opposed to the repeated calls to getBlockedTasks(). On its own this function also isn't too bad, it's the fact that it is called repeatedly.
Task::getBlockedTasks():
std::vector<Task> Task::getBlockedTasks() const {
auto uuid = get("uuid");
std::vector<Task> blocked;
for (auto& it : Context::getContext().tdb2.pending_tasks())
if (it.getStatus() != Task::completed && it.getStatus() != Task::deleted &&
it.hasDependency(uuid))
blocked.push_back(it);
return blocked;
}
#endif
Taskchampion's DependencyMap improves on this situation in many ways and offers a good model for how to improve TW's functions here. It retains the dependency graph for reuse. Given most people will always have more tasks than dependencies, this is a significant improvement, instead of having to scan tasks * dependencies you only scan dependencies.
I think maybe this could be improved, as well? From what I understand, the current approach stores a list of pairs of task:dependency, and that list of pairs must be traversed each time a task is checked. Using a HashMap seems like it would be computationally less expensive at the cost of using more memory. This would presumably be an improvement in those rare cases where you have more dependencies than tasks. What kind of real-world impact this would have I have no idea - either way the current DependencyMap function is preferable to how TW does it, and can act as a model for implementation.
This is an idea that I raised on the Discord a long time ago, it relates to #3993, #3618, and #3334. I thought it best to (finally) make a tracked issue for it, as otherwise it will be lost to time. This is something that I am unsure if I can do myself, so help is very welcome. (I will try though, as this has recently become an issue for me again while doing some more complicated projects.)
Currently, if you have many complicated dependency relations, performance for all your reports will pretty much tank, and this performance hit will increase the more you have assuming
rc.urgency.inherit=1. Performance for modifications also seems to be affected in TW v3 much more (compared to v2), but I am not sure if this is related to these functions or some other ones, so that should be saved for a different issue. I haven't yet checked if TW is using native TW functions or native Taskchampion functions for those.These issues seem to relate to the implementation of a few functions in TW's code. Bear with me if I've misunderstood any of it - I don't really know C++ nor am I a software engineer.
If I'm reading the code right, pending tasks are loaded via
TDB2::pending_tasks()which then runsdependency_scan(std::vector<Task>& tasks), each time TW is run. This does cache whether the task is blocking some other task, and whether the task is blocked, but it doesn't seem to cache any other information about the dependency relationships. Other functions then must reconstruct that information, and ifrc.urgency.inherit=1this means thaturgency_inherit()will invokegetBlockedTasks()andgetDependencyTasks()for each task, recursively - the information related to this is not cached, regardless of whether they have changed or not (as far as I understand) - though once an urgency score is calculated for some task, that at least is reused by other functions. Presumably though, given inheritance means urgency will change during resolution, that doesn't save us much.To caculate the urgency of some task A, TW will call
urgency()and thenurgency_inherit()andgetBlockedTasks()which will scan all blocked tasks. For each blocked task, this repeats. If task C blocks the same tasks, it must redo all of this work for every single task and every single dependency, and every single dependency of those dependencies.urgency_inherit()itself doesn't seem particularly expensive, as opposed to the repeated calls togetBlockedTasks(). On its own this function also isn't too bad, it's the fact that it is called repeatedly.Task::getBlockedTasks():Taskchampion's
DependencyMapimproves on this situation in many ways and offers a good model for how to improve TW's functions here. It retains the dependency graph for reuse. Given most people will always have more tasks than dependencies, this is a significant improvement, instead of having to scan tasks * dependencies you only scan dependencies.I think maybe this could be improved, as well? From what I understand, the current approach stores a list of pairs of task:dependency, and that list of pairs must be traversed each time a task is checked. Using a HashMap seems like it would be computationally less expensive at the cost of using more memory. This would presumably be an improvement in those rare cases where you have more dependencies than tasks. What kind of real-world impact this would have I have no idea - either way the current DependencyMap function is preferable to how TW does it, and can act as a model for implementation.