HeartbeatScheduler 0.1.0

HeartbeatScheduler — nanosecond task scheduling without the heart pangs

Parallelizing micro-tasks is particularly troublesome. Conventional task schedulers are dominated by scheduling and context-switching overhead, which harms, rather than helps, performance at that scale.

When the work itself takes nanoseconds, the microseconds spent dispatching tasks and waking threads outweigh anything the extra cores win back: in the Performance tables below, Parallel.For runs short loops at 0.1x to 0.7x of a single thread's speed.

Heartbeat scheduling for parallel loops in .NET: a loop runs sequentially, and at most once per heartbeat (5 µs by default) each thread splits off half its remaining work for an idle worker. Parallelism thus costs a bounded fraction of run time however short the iterations, and a loop shorter than a heartbeat stays a plain loop on the calling thread. Allocation-free per loop.

Usage

Install HeartbeatScheduler from NuGet:

dotnet add package HeartbeatScheduler

using HeartbeatScheduling;

using var scheduler = new HeartbeatScheduler(new HeartbeatOptions { Workers = 3 });
scheduler.For(0, items.Length, new Calculator(items));   // items: Action[]

sealed class Calculator(Action[] items) : IHeartbeatLoop
{
    public void Execute(int index, int worker) => items[index].Invoke();
}

For iterations of a few nanoseconds, a batched loop (IHeartbeatBatchLoop) hands each thread contiguous batches, so the inner loop stays tight and the heartbeat is checked between batches. Given an estimate of the mean cost per iteration (in microseconds with ForMicroseconds, of any precision, or as a TimeSpan for costs of 100 ns or more), a loop predicted to take less than a heartbeat runs as a plain loop on the calling thread, involving no worker, and one predicted to take more is split up front, as soon as a worker is idle, without waiting for a beat. Splits are then guarded by work rather than a count: each half keeps a quarter of a heartbeat of predicted work, so a few long iterations still spread across threads.

A struct body (scheduler.For(0, n, new PricerStruct(...))) is inlined into the scheduling loop, with no interface call per iteration; each range runs on its own copy, so keep results in the arrays it references. Once its own share is done, the calling thread takes work from busy workers until the loop completes. Idle workers spin, then park between loops; with IdlePolicy = HeartbeatIdlePolicy.BusySpin they never park, so a loop starts without signalling anyone, at the cost of a busy core per worker. If an iteration throws, the other threads abandon their ranges at their next beat, and the first exception is rethrown after the join.

The host can own the worker threads: StartWorker hands it each worker's loop to run on a thread of its choosing, set up as it wishes (priority, CPU affinity, quality of service), for example by posting it to one of its event loops:

using var scheduler = new HeartbeatScheduler(new HeartbeatOptions
{
    Workers = loops.Length,
    StartWorker = (lane, run) => loops[lane - 1].Post(run),   // holds that loop's thread until the scheduler is disposed
});

HeartbeatThreads holds the thread side: HeartbeatThreads.Background(namePrefix, quality), the default (a background thread per worker), and HeartbeatThreads.SetCurrentQuality(HeartbeatThreadQuality.High), which raises the calling thread, whether a worker's or the host's own (on macOS, the user-interactive band; on Windows, the highest thread priority).

Performance

Against Parallel.For, fixed-size chunks (Parallel.ForEach over a Partitioner), CommunityToolkit's ParallelHelper (a struct body, the range split up front into a piece per core) and ZeroAllocJobScheduler's IJobParallelFor. Each loop is a map, Out[i] = Body(i), with no shared writes; the costs shown are the plain loop's, measured. Every contender is held to six cores (DOTNET_PROCESSOR_COUNT=6, and Parallel.For capped by MaxDegreeOfParallelism), and the heartbeat scheduler's workers busy-wait (IdlePolicy = HeartbeatIdlePolicy.BusySpin). Measured on .NET 10 with the repository's own harness (bench/HeartbeatScheduler.Bench): the best of five timed rounds, after a warm-up. Figures vary by about ±5% between runs. The heartbeat columns use a struct body, batched, without and with the mean iteration cost as an estimate. Each cell is the speed-up over a plain loop on one thread, so below 1.0x is slower than not parallelizing at all.

Flat loops:

Level-by-level evaluation of a leveled graph (each level one loop, the join the barrier before the next), about 110,000 nodes in all, against evaluating it on one thread. The heartbeat columns use a struct body, without and with the mean node cost as an estimate. ZeroAllocJobScheduler's idle workers block rather than spin, so each level waits for them to wake.

Allocation, counted on every thread (the workers' and the thread pool's included):

Build

dotnet test HeartbeatScheduler.slnx

dotnet run -c Release --project bench/HeartbeatScheduler.Bench

Credits

Based on the heartbeat scheduling technique of Acar et al. (PLDI 2018), for flat loops: one loop at a time per scheduler, and a loop body must not start another.

License

MIT. See LICENSE.