C++ Lazy Task Scheduler

A header-only C++ library for composing and evaluating dependency-based computation graphs.

Overview

TTaskScheduler is a synchronous task scheduler for building and evaluating computation graphs.

Each task represents a node in the graph. A task may receive:

ordinary values;
results produced by other tasks;
a combination of both.

Dependencies are represented through typed FutureResult<T> objects. Requesting the result of a task recursively evaluates only the dependencies required for that result.

task result requested
        ↓
resolve deferred arguments
        ↓
evaluate unfinished dependencies
        ↓
execute current task
        ↓
cache and return result

Every successfully completed task is evaluated at most once. Later requests reuse its stored result.

This project implements synchronous, single-threaded dependency evaluation. It is not a thread pool and does not execute tasks in parallel.

Features

dependency-based computation graphs;
lazy, demand-driven task execution;
memoization of completed task results;
tasks with zero, one or two arguments;
dependencies in either argument position;
tasks depending on two other tasks;
heterogeneous result types inside one scheduler;
lambdas and callable objects;
captured lambdas;
custom argument and result types;
support for const member-function pointers with one argument;
sequential execution of all scheduled tasks;
task lookup, removal and scheduler reset;
exception propagation from task callables;
header-only implementation;
Google Test coverage;
CMake build.

Execution Model

flowchart LR
    A[Task A]
    B[Task B]
    C[Task C]
    D[Task D]

    A -->|FutureResult| B
    A -->|FutureResult| C
    B -->|FutureResult| D
    C -->|FutureResult| D

For this graph:

auto a = scheduler.add([] {
    return 3;
});

auto b = scheduler.add(
    [](int value) {
        return value + 1;
    },
    scheduler.getFutureResult<int>(a)
);

auto c = scheduler.add(
    [](int value) {
        return value - 1;
    },
    scheduler.getFutureResult<int>(a)
);

auto d = scheduler.add(
    [](int left, int right) {
        return left + right;
    },
    scheduler.getFutureResult<int>(b),
    scheduler.getFutureResult<int>(c)
);

Calling:

scheduler.getResult<int>(d);

evaluates the reachable graph in dependency order:

A → B
  ↘ C
B + C → D

Task A is shared by two branches but is executed only once.

Quick Example

#include "scheduler.h"

#include <iostream>

int main() {
    TTaskScheduler scheduler;

    auto source = scheduler.add([] {
        return 10;
    });

    auto doubled = scheduler.add(
        [](int value) {
            return value * 2;
        },
        scheduler.getFutureResult<int>(source)
    );

    auto result = scheduler.add(
        [](int left, int right) {
            return left + right;
        },
        scheduler.getFutureResult<int>(source),
        scheduler.getFutureResult<int>(doubled)
    );

    std::cout << scheduler.getResult<int>(result) << '\n';
}

Output:

Example: Quadratic Equation

The scheduler can avoid recalculating shared intermediate values.

For the equation:

ax² + bx + c = 0

the discriminant is required for both roots. It can be represented as one shared task:

flowchart LR
    AC[-4 × a × c]
    D[b² + previous result]
    Plus[-b + sqrt D]
    Minus[-b - sqrt D]
    X1[divide by 2a]
    X2[divide by 2a]

    AC --> D
    D --> Plus
    D --> Minus
    Plus --> X1
    Minus --> X2

#include "scheduler.h"

#include <cmath>
#include <iostream>

int main() {
    const float a = 1.0F;
    const float b = -2.0F;
    const float c = 0.0F;

    TTaskScheduler scheduler;

    const auto minus_four_ac = scheduler.add(
        [](float a, float c) {
            return -4.0F * a * c;
        },
        a,
        c
    );

    const auto discriminant = scheduler.add(
        [](float b, float value) {
            return b * b + value;
        },
        b,
        scheduler.getFutureResult<float>(minus_four_ac)
    );

    const auto numerator_x1 = scheduler.add(
        [](float b, float d) {
            return -b + std::sqrt(d);
        },
        b,
        scheduler.getFutureResult<float>(discriminant)
    );

    const auto numerator_x2 = scheduler.add(
        [](float b, float d) {
            return -b - std::sqrt(d);
        },
        b,
        scheduler.getFutureResult<float>(discriminant)
    );

    const auto x1 = scheduler.add(
        [](float a, float numerator) {
            return numerator / (2.0F * a);
        },
        a,
        scheduler.getFutureResult<float>(numerator_x1)
    );

    const auto x2 = scheduler.add(
        [](float a, float numerator) {
            return numerator / (2.0F * a);
        },
        a,
        scheduler.getFutureResult<float>(numerator_x2)
    );

    std::cout << "x1 = " << scheduler.getResult<float>(x1) << '\n';
    std::cout << "x2 = " << scheduler.getResult<float>(x2) << '\n';
}

The discriminant task is used by both branches and remains memoized after its first successful execution.

Lazy Evaluation

Adding a task does not execute it:

int executions = 0;

auto task = scheduler.add([&] {
    ++executions;
    return 42;
});

// executions == 0

The task runs when its value is requested:

const int result = scheduler.getResult<int>(task);

// executions == 1

Repeated requests reuse the stored result:

scheduler.getResult<int>(task);
scheduler.getResult<int>(task);

// executions is still 1

Only dependencies reachable from the requested task are evaluated.

auto used = scheduler.add([] {
    return 10;
});

auto unused = scheduler.add([] {
    return 999;
});

auto result = scheduler.add(
    [](int value) {
        return value * 2;
    },
    scheduler.getFutureResult<int>(used)
);

scheduler.getResult<int>(result);

The unused task remains unevaluated.

Deferred Arguments

A task argument is stored in DeferredArgument<T>.

It can contain either:

an immediate T value

or:

a FutureResult<T> referencing another task

At execution time:

T resolve() const;

returns the immediate value or recursively asks the scheduler to evaluate the referenced task.

This allows all combinations for two-argument tasks:

scheduler.add(function, value1, value2);

scheduler.add(
    function,
    scheduler.getFutureResult<T1>(task1),
    value2
);

scheduler.add(
    function,
    value1,
    scheduler.getFutureResult<T2>(task2)
);

scheduler.add(
    function,
    scheduler.getFutureResult<T1>(task1),
    scheduler.getFutureResult<T2>(task2)
);

Supported Callables

No Arguments

auto task = scheduler.add([] {
    return 42;
});

One Argument

auto task = scheduler.add(
    [](int value) {
        return value * 2;
    },
    21
);

Two Arguments

auto task = scheduler.add(
    [](int left, int right) {
        return left + right;
    },
    20,
    22
);

Lambda with Capture

int multiplier = 5;

auto task = scheduler.add([multiplier] {
    return multiplier * 10;
});

Custom Types

struct Point {
    double x;
    double y;
};

auto squared_length = scheduler.add(
    [](Point point) {
        return point.x * point.x + point.y * point.y;
    },
    Point{3.0, 4.0}
);

Const Member Functions

struct Adder {
    int bias;

    int add(int value) const {
        return value + bias;
    }
};

Adder adder{3};

auto task = scheduler.add(
    &Adder::add,
    adder,
    7
);

The object or the method argument may also be supplied through a FutureResult.

The current member-function overload supports const methods with exactly one explicit argument.

Public API

Task Identifier

using TaskIdentifier = std::size_t;

Task identifiers correspond to positions in the scheduler's internal task storage.

`add`

Adds a callable to the scheduler and returns its identifier.

template <typename Func>
TaskIdentifier add(Func function);

template <typename Func, typename Arg>
TaskIdentifier add(Func function, Arg argument);

template <typename Func, typename Arg1, typename Arg2>
TaskIdentifier add(
    Func function,
    Arg1 argument1,
    Arg2 argument2
);

Overloads accept FutureResult<T> in either or both argument positions.

There are also overloads for const member-function pointers with one method argument.

`getFutureResult<T>`

Creates a typed reference to a task result without evaluating the task immediately.

template <typename T>
FutureResult<T> getFutureResult(TaskIdentifier id);

Example:

auto future = scheduler.getFutureResult<double>(task_id);

FutureResult<T> provides:

T get() const;
operator T() const;
TaskIdentifier getId() const;

`getResult<T>`

Returns the result of a task.

template <typename T>
T getResult(TaskIdentifier id);

If the task has not yet completed, the scheduler:

resolves its arguments;
evaluates unfinished dependencies;
executes the task;
stores the result;
returns a copy.

If the task has already completed, the stored result is returned without executing the callable again.

`executeAll`

Executes every scheduled task that has not already completed.

void executeAll();

Execution is sequential. Dependencies may be evaluated recursively before the scheduler reaches their position in the task list.

`hasTask`

Checks whether an identifier currently refers to a stored task.

bool hasTask(TaskIdentifier id) const;

`removeTask`

Removes a task by resetting its internal storage slot.

void removeTask(TaskIdentifier id);

An invalid or already removed identifier causes std::out_of_range.

Removing a task does not renumber the remaining identifiers.

`clear`

Removes all tasks and resets identifier allocation.

void clear();

After clear(), new identifiers start again from zero.

Internal Design

classDiagram
    class TTaskScheduler {
        +add(...)
        +getFutureResult~T~(id)
        +getResult~T~(id)
        +executeAll()
        +removeTask(id)
        +hasTask(id)
        +clear()
    }

    class BaseTask {
        <<abstract>>
        +bool isExecuted
        +execute(scheduler)
        +getRawResult()
    }

    class TaskWithoutArgs~Func~ {
        +Func taskFunction
        +ResultType result
    }

    class TaskWithOneArg~Func, Arg~ {
        +DeferredArgument~Arg~ argument
        +ResultType result
    }

    class TaskWithTwoArgs~Func, Arg1, Arg2~ {
        +DeferredArgument~Arg1~ firstArgument
        +DeferredArgument~Arg2~ secondArgument
        +ResultType result
    }

    class FutureResult~T~ {
        +get()
        +getId()
    }

    class DeferredArgument~T~ {
        +resolve()
    }

    TTaskScheduler o-- BaseTask
    BaseTask <|-- TaskWithoutArgs
    BaseTask <|-- TaskWithOneArg
    BaseTask <|-- TaskWithTwoArgs
    DeferredArgument o-- FutureResult

Type Erasure

Tasks with different callable and result types are stored together as:

std::vector<std::unique_ptr<BaseTask>>

BaseTask provides a virtual execution interface, while templated derived classes retain the concrete callable, argument and result types.

The implementation has three task models:

TaskWithoutArgs<Func>
TaskWithOneArg<Func, Arg>
TaskWithTwoArgs<Func, Arg1, Arg2>

Result Memoization

Every task contains:

bool isExecuted;

and a result object of its concrete return type.

A successful execution stores the result and sets the flag. Subsequent calls return the cached result.

If a callable throws, the exception propagates and isExecuted remains false. A later request may attempt the task again.

Ownership

the scheduler owns tasks through std::unique_ptr;
task callables and immediate arguments are stored by value;
FutureResult<T> stores a non-owning pointer to its scheduler;
results live inside their task objects.

Complexity

Let:

N be the total number of scheduled tasks;
R be the number of unfinished tasks reachable from a requested result.

Operation	Complexity
`add`	amortized `O(1)`
`hasTask`	`O(1)`
`removeTask`	`O(1)`
repeated `getResult` for a completed task	`O(1)` plus result copy
first `getResult`	`O(R)` task executions
`executeAll`	`O(N)` task visits plus dependency execution
`clear`	`O(N)` destruction

Each successfully executed task is evaluated at most once until it is removed or the scheduler is cleared.

Memory usage is O(N) plus storage owned by callables, arguments and results.

Exception Behaviour

Exceptions thrown by task callables are not swallowed:

auto task = scheduler.add([]() -> int {
    throw std::runtime_error("calculation failed");
});

scheduler.getResult<int>(task);

The exception propagates to the caller.

Invalid identifiers passed to removeTask produce:

std::out_of_range("Bad task ID")

An identifier greater than or equal to the current task list size produces the same exception in getResult.

Build

Requirements

a C++23-compatible compiler;
CMake 3.12 or newer;
Git access during the first CMake configuration so GoogleTest can be downloaded.

Clone

git clone https://github.com/Alexandr-prog34/TaskScheduler.git
cd TaskScheduler

Configure and Compile

cmake -S . -B build
cmake --build build

For a release build with a single-configuration generator:

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build

Run the Example

The example executable builds a quadratic-equation computation graph.

./build/bin/labwork9

On a multi-configuration generator, the executable may be located inside a configuration directory:

./build/bin/Debug/labwork9

Tests

Run the complete test suite through CTest:

ctest --test-dir build --output-on-failure

The test executable can also be run directly:

./build/tests/task_scheduler_tests

On a multi-configuration generator:

./build/tests/Debug/task_scheduler_tests

GoogleTest 1.12.1 is downloaded through CMake FetchContent.

The current tests cover:

tasks without arguments;
one- and two-argument tasks;
linear dependency chains;
branching graphs;
lazy execution;
result caching;
dependencies in either argument position;
two future arguments;
integers, doubles, strings and booleans;
mixed-type chains;
custom structures;
const member-function pointers;
lambdas with captures;
independent tasks;
exception propagation;
task lookup and removal.

Project Structure

.
├── bin/
│   ├── CMakeLists.txt
│   └── main.cpp
├── lib/
│   └── scheduler.h
├── tests/
│   ├── CMakeLists.txt
│   └── tests_scheduler.cpp
├── CMakeLists.txt
└── README.md

The implementation is header-only:

#include "scheduler.h"

The repository builds two targets:

Target	Purpose
`labwork9`	Quadratic-equation example executable
`task_scheduler_tests`	Google Test executable

Current Limitations

The scheduler demonstrates lazy dependency evaluation, but it is not yet a production-ready task-execution framework.

Synchronous Execution

All tasks run on the calling thread.

The scheduler does not currently provide:

worker threads;
parallel execution;
asynchronous completion;
cancellation;
priorities;
timeouts.

No Cycle Detection

A dependency cycle causes recursive evaluation without a cycle check.

Task A depends on Task B
Task B depends on Task A

A production implementation should track task states such as:

pending
executing
completed
failed

and report cyclic dependencies explicitly.

Runtime Result-Type Safety

Task results are exposed internally through void*.

The caller must provide the exact result type:

scheduler.getResult<CorrectType>(task);

Supplying an incorrect T is not validated and may cause undefined behaviour.

The same applies to:

scheduler.getFutureResult<T>(task);

A safer implementation should store runtime type information or encode the result type in the task handle.

Removed Dependencies

removeTask can invalidate a dependency referenced by another task.

Additionally, getResult validates the identifier range but does not currently check whether the corresponding task slot has been removed.

Type Requirements

The current task models store result objects as direct data members and return them by value.

As a consequence, the implementation is primarily suited to types that are:

default-constructible;
copyable;
assignable.

Void-returning tasks and move-only result types are not supported.

DeferredArgument<T> also stores an immediate T value directly, which imposes similar constraints on argument types.

Callable Storage

Callables and arguments are copied into task objects. Move-only callables and move-only arguments are not currently supported.

Member Functions

The specialised member-function overloads currently support:

const member functions;
one explicit method argument.

Other member-function signatures can still be wrapped manually in a lambda.

Future Lifetime

FutureResult<T> stores a raw pointer to the scheduler.

A future becomes invalid when:

the scheduler is destroyed;
the referenced task is removed;
clear() is called and task identifiers are reused.

Build Naming

The CMake project and example target are still named labwork9, which exposes the repository's academic origin.

Recommended Roadmap

rename the repository to cpp-lazy-task-graph;
rename the CMake project and example target;
introduce a typed TaskHandle<T>;
remove result access through unchecked void*;
add cycle detection;
validate removed task slots in getResult;
represent task state explicitly;
support move-only callables, arguments and results;
support void-returning tasks;
use std::invoke for generic callable and member-function handling;
replace the arity-specific task classes with tuple-based argument storage;
support an arbitrary number of arguments;
add parallel execution for independent graph branches;
add failure-state caching and dependency error propagation;
add graph visualisation;
add GitHub Actions for GCC and Clang;
add AddressSanitizer and UndefinedBehaviorSanitizer;
add code coverage;
add a license.

What This Project Demonstrates

computation-graph modelling;
lazy evaluation;
memoization;
dependency resolution;
C++ templates;
callable type deduction;
custom future-like handles;
type erasure through polymorphism;
heterogeneous task storage;
RAII and smart-pointer ownership;
graph branching and shared dependencies;
unit testing with Google Test.

Name		Name	Last commit message	Last commit date
Latest commit History 3 Commits
bin		bin
lib		lib
tests		tests
.gitignore		.gitignore
CMakeLists.txt		CMakeLists.txt
README.md		README.md

Folders and files

Latest commit

History

Repository files navigation