ForkJoin

ForkJoin is a work-first execution context for Crystal. It is meant for jobs that create more jobs as they run: tree walks, divide-and-conquer algorithms, recursive pipelines, and similar workloads where the amount of parallel work is not known up front.

The scheduler keeps newly spawned fibers close to the worker that created them. Idle workers steal batches from busy workers, so a recursive job can spread out without sending every spawn through one shared queue. This is the same broad idea behind Cilk and Java's ForkJoinPool, adapted to Crystal's fibers and execution-context API.

Install

Add the shard to shard.yml:

dependencies:
  fork_join:
    github: naqvis/fork_join

Install dependencies:

shards install

Use it

require "fork_join"
require "wait_group"

context = ForkJoin::ExecutionContext.new(
  "recursive-work",
  capacity: System.cpu_count.to_i,
)

context.spawn do
  spawn { left_branch }
  spawn { right_branch }
end

# Change the active parallelism when the workload changes.
context.resize(2)

# Complete application work before shutting down the context.
context.shutdown

A plain spawn inside a ForkJoin fiber stays in the same context. Calls to context.spawn from another context or a bare system thread are accepted as external work.

The context can be resized while it is running:

context.resize(2)

Shrinking is cooperative. A retired worker puts its queued fibers back into the shared injection queue before releasing its event-loop registration and system thread.

shutdown is deliberately non-draining. Wait for application fibers to finish, then call it from outside the context. New external submissions are rejected once shutdown begins, and calling shutdown from one of the context's own fibers raises an exception instead of waiting on itself.

How scheduling works

Each worker has a bounded local queue and two small private slots: one for fresh local work and one for its next continuation. Older local work and surplus continuations go into the queue, where another worker can claim roughly half of them. This favors depth-first execution on the producing worker while leaving useful batches for thieves.

Work submitted from outside the context goes through a shared injection queue. Workers take a fair share rather than draining the whole queue, and local work occasionally yields priority to injection so a busy recursive chain cannot starve outside submissions.

This is still a Crystal execution context, not a separate task system. Fibers can use channels, timers, I/O, and marked blocking syscalls. The runtime may also move a scheduler to another pooled thread while its current thread is blocked.

The implementation borrows specific scheduling ideas from Tokio, Go, Kotlin's coroutine scheduler, and OpenJDK. The design guide explains what came from each runtime and how it was adjusted for Crystal.

Compatibility

Crystal 1.21.0 or newer is required. Execution contexts are a low-level runtime API, so each supported Crystal release is tested explicitly.

Tests and benchmarks

Run the specifications with:

crystal spec

The main scheduler comparison is:

crystal run --release bench/schedulers.cr

See the benchmark notes for the workloads, raw samples, and the limits of those comparisons. The retirement probe is documented separately in EVACUATION.md.

Contributing

Bug reports and workload examples are especially useful for a scheduler. Pull requests are welcome; please include a regression spec for scheduling or lifecycle changes and run crystal spec before opening one.

License

MIT

Maintainer

Ali Naqvi