GothenburgBitFactory / GothenburgBitFactory/taskwarrior

Use or reimplement Taskchampion's DependencyMap instead of TW's getBlockedTasks() + urgency_inherit()

Open
#4,121 5 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
6.1k
Forks
423
Avg merge
1d 19h
Merged PRs (30d)
11

Description

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()`](https://github.com/GothenburgBitFactory/taskwarrior/blob/d1afef41c071e5cdb8f342780896f55246d79f13/src/TDB2.cpp#L256) which then runs [`dependency_scan(std::vector& tasks)`](https://github.com/GothenburgBitFactory/taskwarrior/blob/d1afef41c071e5cdb8f342780896f55246d79f13/src/TDB2.cpp#L444), 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()`](https://github.com/GothenburgBitFactory/taskwarrior/blob/d1afef41c071e5cdb8f342780896f55246d79f13/src/Task.cpp#L1820) will invoke [`getBlockedTasks()`](https://github.com/GothenburgBitFactory/taskwarrior/blob/d1afef41c071e5cdb8f342780896f55246d79f13/src/Task.cpp#L1087) and [`getDependencyTasks()`](https://github.com/GothenburgBitFactory/taskwarrior/blob/d1afef41c071e5cdb8f342780896f55246d79f13/src/Task.cpp#L1070) 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()`:
```C++
std::vector Task::getBlockedTasks() const {
auto uuid = get("uuid");

std::vector 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`](https://github.com/GothenburgBitFactory/taskchampion/blob/ed28b06fa75a88b8668582665fd0696830f8489e/src/depmap.rs#L13) 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.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.