modify depends reads a database fully per each non-pending task

[9484e0dd]

Not sure how much this is related to #4121, and if this will be of any interest to @ashprice.

modify depends reads a database fully per each non-pending task.

dependencyIsCircular() calls tdb2.get(dep, current) for each depends edge.

Since #4127, TDB2::get() resolves pending UUIDs through _pending_index, but a non-pending UUID requires all_task_data().

My database has 1217 such edges from completed tasks out of 2087. Total size is 5578 tasks, 54 MB. Adding one dependency to a task with 69 completed tasks referenced through depends peaks at ~1 GB RSS over ~9.5 s. I suppose nothing is freed between dependency modifications in a command: one dependency 1005 MB, two 1935 MB, three 2945 MB. Fifty-four dependencies in a single modify therefore requires ~50 GB, which bricks my machine.

The script below creates a database with completed chains and a pending control, then measures a modify depends: against each.

import json
import os
import subprocess
import tempfile
import time
import uuid

TASK_BIN = os.environ.get("TASK", "task")
FILLER_COUNT = int(os.environ.get("FILLER", 2000))
ENTRY_DATE = "20200101T000000Z"


def new_uuid():
    return str(uuid.uuid4())


all_tasks = []
chain_heads = []


# Linear chain
def add_chain(length, status, name):
    link_uuids = []
    for i in range(length):
        link_uuids.append(new_uuid())

    for i in range(length):
        task = {
            "uuid": link_uuids[i],
            "description": name + str(i),
            "status": status,
            "entry": ENTRY_DATE,
        }
        if status == "completed":
            task["end"] = ENTRY_DATE
        if i + 1 < length:
            task["depends"] = [link_uuids[i + 1]]
        all_tasks.append(task)

    head_uuid = new_uuid()
    all_tasks.append({
        "uuid": head_uuid,
        "description": name,
        "status": "pending",
        "entry": ENTRY_DATE,
        "depends": [link_uuids[0]],
    })
    chain_heads.append((name, length, status, head_uuid))


for length in (10, 20, 40, 80):
    add_chain(length, "completed", "done" + str(length))
add_chain(80, "pending", "live80")

spare_uuid = new_uuid()
all_tasks.append({
    "uuid": spare_uuid,
    "description": "SPARE",
    "status": "pending",
    "entry": ENTRY_DATE,
})

# Filler tasks
for i in range(FILLER_COUNT):
    all_tasks.append({
        "uuid": new_uuid(),
        "description": "f" + str(i),
        "status": "pending",
        "entry": ENTRY_DATE,
    })


def run_task(args):
    started = time.monotonic()
    pid = os.fork()
    if pid == 0:
        devnull = os.open(os.devnull, os.O_WRONLY)
        os.dup2(devnull, 1)
        os.dup2(devnull, 2)
        try:
            os.execvp(TASK_BIN, [TASK_BIN, "rc.hooks=0", "rc.confirmation=off"] + args)
        except Exception:
            os._exit(127)
    _, _, usage = os.wait4(pid, 0)
    elapsed = time.monotonic() - started
    peak_rss_mb = usage.ru_maxrss / 1024.0
    return elapsed, peak_rss_mb


with tempfile.TemporaryDirectory() as data_dir, tempfile.TemporaryDirectory() as rc_dir:
    taskrc_path = os.path.join(rc_dir, "taskrc")
    os.environ["TASKDATA"] = data_dir
    os.environ["TASKRC"] = taskrc_path
    with open(taskrc_path, "w") as f:
        f.write("verbose=nothing\n")

    import_path = os.path.join(rc_dir, "db.json")
    with open(import_path, "w") as f:
        json.dump(all_tasks, f)
    run_task(["import", import_path])

    version = subprocess.run(
        [TASK_BIN, "--version"], capture_output=True, text=True
    ).stdout.strip()
    print(version + ": " + str(len(all_tasks)) + " tasks in DB")

    print("chain,len,status,time s,peak RSS MB")
    for name, length, status, head_uuid in chain_heads:
        elapsed, peak_rss_mb = run_task([head_uuid, "modify", "depends:" + spare_uuid])
        print("%s,%d,%s,%.2f,%.1f" % (name, length, status, elapsed, peak_rss_mb))

[djmitche]

This seems like a great use-case for exposing the DependencyMap directly to C++ -- this calculation could be performed entirely within that map. In fact, it might make sense to add some DependencyMap::reachable(from, to) method in the Rust implementation and just use that: adding dep would cause a cycle if reachable(dep, task.uuid()).

[9484e0dd]

This seems like a great use-case for exposing the DependencyMap directly to C++ -- this calculation could be performed entirely within that map.

From what I've checked, I assume DependencyMap stores edges only for pending tasks.

I believe my issue is caused by checks made against non-pending tasks, which are not cached (each miss loads the entire database).

Extending DependencyMap to cover all tasks would fix this, requiring one full database load per command, instead of full load per edge that happens now.

However, get_task_data from replica.rs can be used to check edges individually. It is already in TDB2.cpp.

[djmitche]

Oh, interesting! What if we only considered dependencies between pending tasks for the cyclic check? My understanding is that other aspects of dependencies are limited to pending tasks (which is why the depmap only includes those tasks).

The cyclic-dependency check is already best-effort: two replicas could add dependency edges independently that only became a cycle after a sync. So, I think the obvious edge case -- a dependency cycle exists but includes a non-pending task, and that task is then made pending -- is OK.

[9484e0dd]

What if we only considered dependencies between pending tasks for the cyclic check?

Indeed, this seems to solve the problem cleanly.

I tested the idea locally - replaced tdb2.get with tdb2.find_pending in dependencyIsCircular, thus skipping non-pending tasks.

2236-task database from the repro script: dependency chains of 10/20/40/80 reduce RSS from 24/35/55/86 MB to a flat 19 MB.
These 19 MB is what the pending tasks' chain costs itself.

Cycles between pending tasks still get rejected.
Completed tasks cycles are ignored, as expected.

So, I think the obvious edge case -- a dependency cycle exists but includes a non-pending task, and that task is then made pending -- is OK.

I think cycles (like ones hypothetically caused by syncs) can be reported via task diagnostics.
There is already a section for Broken ref that scans the full database anyway.

[djmitche]

Awesome -- do you want to send a PR with your fix?

[ashprice]

Oh! Sorry about this. I apologize for any troubles this has caused you - I have a planned fix for this, made in this commit: a9a92a9 .

There's some other loose ends that need tying up before I can marge that branch, but I'd welcome a fix for people who are using VCS builds.

[9484e0dd]

Awesome -- do you want to send a PR with your fix?

Sorry, I am not comfortable enough with C++ to own a PR.

Though, here is a patch of my ad-hoc fix, if you are interested.

--- a/src/dependency.cpp
+++ b/src/dependency.cpp
@@ -58,7 +58,9 @@
       // This is a basic depth first search that always terminates given the
       // fact that we do not visit any task twice
       for (const auto& dep : deps_current) {
-        if (Context::getContext().tdb2.get(dep, current)) {
+        Task* pending_dep = Context::getContext().tdb2.find_pending(dep);
+        if (pending_dep) {
+          current = *pending_dep;
           auto current_uuid = current.get("uuid");
 
           if (task_uuid == current_uuid) {

[djmitche]

@ashprice if that looks good to you, want to make up a PR? I'm in the middle of non-code things this weekend so don't have time to make a PR myself but I'm happy to ✔️

[9484e0dd]

Oh! Sorry about this. I apologize for any troubles this has caused you - I have a planned fix for this, made in this commit: a9a92a9 .

There's some other loose ends that need tying up before I can marge that branch, but I'd welcome a fix for people who are using VCS builds.

No trouble at all - the bug is not from #4127, it reproduces on 3.4.2 as well.

[ashprice]

Your patch is perfectly good on the C++ front, but you'll find it will cause a crash when modifying using an empty filter, which is a gotcha the tests didn't cover and I almost missed myself.

Throughout my work on taskwarrior I've found many times that changing something isn't as simple as you would think; there are many moving parts. And I've introduced more of them by introducing caching. 😆