jay403894-bit/JLib-Scheduler

JLib-Scheduler is a hybrid work stealing fiber-based jobs system using c++17. Marl alternative, fiber job system, lock-free Chase-Lev work-stealing - jay403894-bit/JLib-Scheduler

16 stars · 2 forks

README

JLib::Scheduler

A hybrid runtime for C++17+ that gives you:

Cilk-style work-stealing for fast parallel loops (ParallelFor, PushArray) No cost model in the range APIs -- ParallelFor has no probe and no calibrated constant; steals decide how work is divided TaskFlow-style dependency graphs (TaskDAG) with AND/OR gates Middleware-safe threads by default -- no TLS surprises Fiber-based blocking only when you actually suspend, so you never pay fiber overhead unless you need it

Built for real-time engines that mix compute-heavy loops, dependency-aware pipelines, and I/O-bound middleware in the same frame. Under the hood: hand-written context switching, lock-free Chase-Lev deques, a slab-allocated task system, frame DAGs with logic gates, and hybrid-core aware placement. Maturity. Test it in your own project before you depend on it. Run your workload, run your tests, and if it holds up, use it. What it should not be is dropped into a commercial project untested on the strength of a benchmark table -- including this one's. Bugs do get fixed: four defects were found and released inside a day in 1.3.x, two of which could hang a pool. But that was a day off. This is one person with a full-time job, so read it as evidence that reports get acted on -- not as a response time. During a work week the same four fixes would have taken weeks, and a report may sit for a while before anyone looks at it. Nothing here is staffed. Windows x64 & ARM64 (MSVC) · Linux x86-64 · Linux/Android AArch64 · macOS Apple Silicon · C++17 · BSD I built this scheduler to solve the problem of scheduling for my custom 2d/3d engine -- it was built to be the backbone of multithreaded simulation engines. I needed tasks that could wait on a gpu fence without parking a worker thread, enkiTS and taskflow cannot do this, marl can but was archived in April.

How it compares

enkiTS Taskflow marl this

Work-stealing yes yes yes yes

Suspend/resume inside a task no no yes yes

Dependency DAG with AND/OR gates partial yes no yes

Cache/SMT topology-aware stealing no no no yes

Maintained yes yes archived Apr 2026 yes

marl and FiberTaskingLib run every task on a fiber. Here fibers are opt-in, so middleware written for an ordinary thread pool works unchanged -- Jolt Physics runs through a JPH::JobSystem adapter and never learns fibers exist. Why that matters. Measured This was tested on my machine, third party tests have come back and some are faster than mine depending on hardware and platform. Needs and welcomes more testing for research! i9-13900K at Intel spec power limits, Release, 1.4.0. Medians of five runs on the default affinity policy, with the observed range in brackets. The two columns are one library under its two idle policies, not two products -- Sleep parks idle workers and is the default, NoSleep keeps them searching.

Sleep (default) NoSleep

Task enqueue → dequeue latency 4.6 µs [4.28-4.72] 1.0 µs [0.94-2.8] 4.6x

6-node frame DAG (build, validate, execute) 21.1 µs [20.2-22.1] 7.4 µs [7.2-8.4] 2.9x

1M-element recursive fork-join (10k leaves) 0.25 ms [0.17-0.29] 0.06 ms [0.06-0.13] 4.2x

Single-producer submission 1.2 M/s [0.90-1.48] 7.0 M/s [5.9-7.2] 5.8x

Bulk submission via PushBatch 14.7 M/s [14.2-18.2] 14.3 M/s [13.1-16.4] 1.0x

Bulk submission, 4 producers 2.9 M/s [2.3-3.9] 12.5 M/s [12.1-13.0] 4.3x

Per-item cost via PushArray (chunk 128) 0.55 ns 0.59 ns --

16 heavy tasks from an idle pool 10.8x of 16 12.6x of 16 flat

Reproduce either column with SchedulerBench, or both side by side with SchedulerBench both. The brackets matter: the last digit is not meaningful on several of these rows -- bulk submission and fork-join move ~20% run to run on an otherwise idle machine, and the NoSleep latency row is bimodal -- so read the order of magnitude and the ratio, not the number. A quiet machine means quiet. Two rounds of these numbers were thrown away because a WSL2 VM that had been shut down seconds earlier was still tearing down in the background, which pulled the whole NoSleep column down by up to 40%. If you reproduce this, give the machine real idle time first and take the run twice. Rows that moved against the 1.3.0 version of this table. PushBatch went 12.2 → 14.7 M/s and PushArray 1.0 → 0.55 ns/item; both follow from 1.4 cutting the task allocator's round trip from 9.3 ns to 2.1 ns. Everything else reproduces 1.3.0 within noise except one row: 4-producer submission under Sleep reads 2.9 M/s where the 1.3.0 table said 9.8. That was assumed to be a regression. It is not -- the row is BISTABLE, and neither number is wrong. v1.3.0 was checked out, rebuilt and measured beside 1.4.0: it reads 2.5-4.4 M/s against 1.4.0's 3.0-3.7, the same distribution, so nothing regressed between them. Sweeping pool size then showed what the row actually does:

pool 4 8 16 18 20 22 24 31

4-producer M/s 11.08 11.39 10.13 10.93 10.50 2.37 5.36 3.60

A cliff at ~21 workers. Below it the four producers keep the pool saturated, so workers never park and a Push costs the ~1 ns of an awake-worker notify. Above it the consumers drain faster than the producers submit, workers run dry and park, and every Push buys a kernel wake instead. Those are two regimes, ~10-11 M/s and ~3 M/s, and this 31-worker machine sits just past the edge -- so the row lands in either depending on how the run settles. This is the same failure mode the single-producer row is already documented for, one crossover to the right: four producers feed more consumers than one, so the cliff moves from ~14 workers to ~21. bench.cpp claimed the multi-producer case was flat across that sweep and served as the control for it. That claim was wrong and is now corrected -- fork-join and the frame DAG are the flat ones. So the 9.8 was a real reading from the saturated regime, and best-of-5 on a bistable metric publishes whichever regime got lucky -- which is also why the row was recorded as 8.4 M/s and then 9.8 M/s sixteen minutes later on identical code. Read this row as a submission-rate measurement with a crossover, not a capacity number, and expect either regime. Published as measured rather than quietly dropped. Measure on your own hardware before relying on any of this. These numbers come from one desktop with a large L3 and no competing load; a different cache hierarchy or a machine the application does not own will move them, in some cases below 1.0x. The wake path turned out to be the largest single cost in the scheduler, and nothing here had measured it until 1.3.0. That is what the first four rows are: whether a worker had to be woken by the kernel. NoSleep is not uniformly better, which is why both columns are shown -- it ties on PushBatch (where submission, not wake-up, is the cost) and loses on the blocking workload further down. That last row is the control, and it is the reason to believe the others. Its shortfall was predicted before measuring to be frequency scaling rather than wake latency -- 16 heavy tasks at once settle toward base clock on a chip at Intel spec power limits, where one task alone boosts. It stayed flat while everything else moved 2.9-5.8x. The default stays Sleep. Spinning workers are a battery and thermal problem on Android, they starve whatever else the host process runs, and they make the oversubscription policy incoherent. A fullscreen game is NOT the case for NoSleep, despite the table above -- an earlier version of this README said it was, and measurement says otherwise. The benchmarks flatter NoSleep because in a scheduler benchmark the pool is the workload: there is no render or audio thread for the spinning to tax, so only the wake saving shows up. Measured with an idle pool against a memory-bound main thread, NoSleep costs ~3.5% to every other thread in the process; measured inside a real 2D game it cost 23%. NoSleep is for batch and offline work where the task graph is the entire program, or for pipelines whose idle gaps are under ~100 µs. There is deliberately no middle setting -- a spin-then-park mode was built, measured worse than both extremes, and removed; the reasoning is in CHANGELOG.md. Structural properties, which do not vary by policy:

Task struct size 64 bytes, one cache line, static_assert-enforced

Fiber stacks 64 KB standard / 512 KB heavy, contiguous arena, guard-paged

Steal protocol single-item Chase-Lev CAS

This machine runs Intel's specified power limits with unlimited turbo disabled, so it boosts briefly and then settles near base clock under sustained load. That is the part behaving as Intel specifies it, not a handicap, but it is worth stating because most enthusiast boards ship with PL1 and PL2 effectively unlimited and most published numbers are measured that way. A machine running board defaults will beat every figure above. Numbers that are conservative for the reader are the right kind to be wrong, and this is also why the third-party results matter more than mine: some have come back faster, and the spread across machines says more than any single row. SchedulerBench prints the version it was built from. That exists because results get pasted into issues while the suite changes underneath them, and a number nobody can attribute to a build is not data. If a pasted run has no version line at all, it predates 1.0.1 and should be re-run. Run them yourself with SchedulerBench. It takes an affinity policy argument and defaults to the same one the library does. Measured against enkiTS, TaskFlow and marl Same machine, same harness, same worker count, both libraries expressed the way their authors intended. i9-13900K at Intel spec power limits (see the caveat under Measured), 31 workers, Release. Our two columns are 1.4.0; the other three were last measured at 1.3.0 and are carried over unchanged -- see the note under the table for why that is still a fair comparison. -- is not measured yet. Every column below was measured with only that scheduler running. The harness takes --only=jlib / --only=enki and starts nothing else, so no library's threads are alive while another is timed.

this (Sleep) this (NoSleep) enkiTS Taskflow marl

Round-trip submit→run→wait 4.3 µs 1.70 µs 21.7 µs 1.30 µs 0.88 µs

Independent tasks, per task 67 ns 65 ns 21.8 µs 310 ns 290 ns

Range work, per item 38 ns 25 ns 15 ns -- --

Bulk parallel-for, 20k items 0.36 ms 0.18 ms 0.373 ms 0.49 ms --

25% of tasks blocked 600 µs 7.2 ms 10.2 ms 15.4 ms -- 8.8 ms

Our two columns were re-measured at 1.4.0; the other three were not. enkiTS, Taskflow and marl have not changed and their cells are carried over -- but they were taken on the same machine in the same harness, so the comparison still holds. The NoSleep round-trip cell is the one to distrust: it read 0.97 µs at 1.3.0 and 1.70 µs here with an 83% spread across repeats, which is the harness being noisy on that row rather than a real move. The bulk row was re-measured after ParallelFor moved to recursive splitting, because the earlier figure was taken against the shared-cursor path that was mechanism-matched to enkiTS. It did not move: 0.355 ms against enkiTS 0.373 ms, which is a tie either way — inside both harnesses' spreads (8% ours, 9% theirs). Read it as neither library having an edge on a uniform bulk range, not as a win. See Parallel loops. The 4.3 µs Sleep round-trip is specifically the cost of waking a FULLY PARKED worker, not a fixed floor on submission. BenchLatency round-robins across every worker, so any given one only gets touched roughly once every pool-size iterations -- long enough to fully park every time, paying a real OS kernel wake on every hit. A breakdown built to answer where that time goes (build with -DJLIBSCHED_LATENCY_STATS=ON) found the OS wake itself is ~85% of it (4.00 µs of 4.89 µs in an instrumented build), with Worker()'s own loop order -- it checks the local deque and runs a full steal scan before ever looking at the inbox a cold wake was actually for -- contributing a real but small ~0.30 µs. Pin the same round trip to one worker instead (Push(1, task) every time) and it drops to 0.83 µs, a 5.9x difference, because that worker is usually still mid-backoff, not yet parked, when the next task lands. Neither number is "wrong" -- they measure different things: 4.3 µs is what a genuinely idle pool costs to wake (e.g. a game at a frame boundary), 0.83 µs is what a worker that's still warm from the last task costs. JLIBSCHED_LATENCY_STATS is a permanent, off-by-default diagnostic (same convention as JLIBSCHED_STEAL_STATS) for measuring this split on your own hardware. Blank cells are not measured yet, not zero. Versions: enkiTS at main, Taskflow 4.1.0, marl at main (archived, last commit 2026-04-27 — its column calibrates the fiber path, it is not a recommendation). The latency row is an idle-policy axis, not an architecture one. Taskflow and marl both keep their workers searching before parking — Taskflow tries ~64 steals then yields 150 more times before sleeping — so their defaults sit where NoSleep sits, and all three land within a few hundred nanoseconds of each other. enkiTS parks promptly, like the default here, and is far slower again because it suspends on a shared completion semaphore. Comparing anyone's default to Sleep here would be measuring configuration and calling it design. The blocking row is a crossover, not a verdict, and marl is the only honest peer for it. enkiTS and Taskflow have no fibers, so a blocked task there holds a thread and the comparison is architectural rather than close. marl suspends a fiber exactly as this does, so it measures two implementations of the same idea. Swept by how long each task blocks (10 batches of 256, 25% blocking, ms for all 2560 tasks, each library measured alone):

block for this (Sleep) marl

50 µs 8.0 5.0

150 µs 7.4 4.9

300 µs 6.6 5.6

600 µs 7.4 8.8

2000 µs 22.2 22.6

marl leads below roughly 400 µs and this leads above it. Two things worth knowing rather than smoothing over. Its Event carries sticky signalled state and waits on a predicate, so an already-satisfied wait costs it nothing, while JLib::Event is a stateless rendezvous and always pays a suspend/resume round trip -- that is a capability difference, not a slower fiber. And the fiber machinery itself is not where this row's cost lives: measured separately, attaching a fiber is free within noise and a full suspend/resume round trip is ~166 ns, against a ~1.3 µs baseline cost to submit a task at all. Three earlier explanations for this row -- the event registry lock, the serial resume path, and fiber acquisition -- were each measured and each wrong. Independent-task throughput is the row where the architecture actually shows: 69-74 ns against 290-310 ns for the two fiber/graph libraries, and enkiTS is not really in this race at all because submitting N single-item task sets is the usage it tells you to avoid. Sleep is the default and the mobile/embedded configuration; NoSleep holds every worker core and is for an application that owns the machine. They are close to two different products, which is why both are listed rather than only the flattering one. Note that NoSleep is not uniformly better: it loses on the blocking row (10.1 ms against 8.2 ms). Parked fibers have nothing for the spinning workers to do there, so the spin is pure waste. It wins where dispatch latency dominates and costs you where it does not. Isolation is not optional here, and it took a wrong result to learn that. An earlier version ran both libraries in one process. Under Sleep that is harmless, because the pool not being benchmarked is parked -- enkiTS measured alone (15.4 ns/item, 21.7 µs, 0.334 ms) matches what it measured beside a sleeping JLib (15.3, 21.4, 0.331). Under NoSleep it is not harmless at all: JLib's 31 workers spin through enkiTS's benchmarks too, 63 threads on 32 CPUs, and enkiTS's own numbers moved ~40% -- ranged per-item 15.3 → 8.7 ns, latency 21.4 → 18.2 µs -- purely because a JLib setting changed. A library's numbers moving when you reconfigure a different library is the signal that a harness is measuring the machine rather than the code. The first two rows are the same quantity measured on each library's own terms, and they disagree by 200x in opposite directions -- which is the point. enkiTS's scheduled entity is a 16-byte SubTaskSet in a contiguous fixed ring: no allocation, no pointer chase, and the caller owns the ITaskSet and keeps it alive. That is why its per-ITEM cost is so low, and why its per-TASK cost is so high when you actually need n independent task objects -- every AddTaskSetToPipe wakes the waiting pool so one thread can claim one task. A Task here is 64 bytes carrying its own callable, so it costs more per entity and can be fire-and-forget with captures. The size difference IS the API difference; neither is a missed optimisation. Read the rows accordingly: use PushArray/ParallelFor for range work and compare against row 3, use individual tasks for a heterogeneous frame graph and compare against row 2. Blocking is the row the fiber hybrid exists for, and it is a crossover rather than a win: even at 25% blocked it needs blocks longer than ~50 µs before parking beats simply holding the thread, peaks at 1.75x around 600 µs, and tapers again by 2 ms. Below that the fiber costs more than it saves. Reproduce with the opt-in harness -- it is not built by default and enkiTS is not vendored: git clone https://github.com/dougbinks/enkiTS cmake -B build-compare -DCMAKE_BUILD_TYPE=Release -DJLIBSCHED_ENKITS_DIR=/path/to/enkiTS cmake --build build-compare --config Release --target CompareEnkiTS ./build-compare/bin/Release/CompareEnkiTS --only=jlib ./build-compare/bin/Release/CompareEnkiTS --only=jlib nosleep ./build-compare/bin/Release/CompareEnkiTS --only=enki

Three runs, one scheduler each. With no --only it measures both in one process, which is valid only while every library present parks when idle -- so nosleep forces --only=jlib and says so, rather than quietly emitting a confounded column. bench/compare/compare_enkits.cpp records the predictions made before measuring and, next to each number, the harness faults that corrupted it first. The initial draft reported enkiTS as 15x slower and every one of those faults was the harness, not enkiTS -- worth reading before trusting any row here, and before writing a comparison of your own. Model checked The two lock-free structures are model checked with GenMC, not only tested. A test runs whichever interleaving the CPU happens to produce; a model checker enumerates every execution the C11 memory model permits, so for a bounded harness the result is exhaustive rather than lucky. Models live in tests/verify/.

Chase-Lev deque (deque_model.c) - one owner, two thieves, 174 executions, no errors. It also settled a real question: the published verified Chase-Lev uses seq_cst for the steal CAS and this uses acq_rel. Both check clean, so the weaker ordering is sufficient here and the seq_cst fences are what carry the ordering. Event waiter stack (event_model.c) - two pushers, one drainer, 24 executions, no errors. No waiter lost, none woken twice, no race on the plain nextWaiter field.

Each model ships a negative control, which is the part that makes a clean run mean anything. Build the deque model with -DNO_POP_FENCE and it produces a double-claim in under a second: two threads taking the same task, the use-after-free class. That fence had been called redundant more than once. This is not a proof of the whole scheduler. It covers two data structures at small bounds, which is where memory-ordering bugs live. Build cmake -B build -DCMAKE_BUILD_TYPE=Development cmake --build build -j

On Windows this silently builds Debug, not Development, unless you say otherwise. CMake's default generator there is Visual Studio, which is a MULTI-CONFIG generator: all three build types coexist in the same build/ tree, chosen at BUILD time via --config, not at configure time -- so -

source