Spice Parallelism Library

Spice employs several low-level optimizations to minimize overhead and stack usage:

1. Branch-free Doubly-Linked List: The work queue uses a sentinel (head) node so that push and pop operations are completely branch-free, which is critical for performance during recursive calls.
2. Minimized Stack Usage: A Future uses a specialized tagged union structure. When a future is _queued_, it only consumes space for pointers (prev and next). The heavier ExecuteState (containing results and synchronization primitives) is only allocated in a separate pool when the task actually begins executing.
3. Register-based Context Passing: To ensure the Task context (worker pointer and job tail) is passed in CPU registers rather than on the stack, Spice uses an internal callWithContext pattern that forces inlining and passes individual fields as direct parameters to the LLVM backend.

Spice uses a fork/join model designed to avoid the inefficiencies of traditional work-stealing systems (such as dynamic dispatch overhead, non-local work queues, and CPU spinning).

Instead of putting every piece of work into a generic dynamic function queue, Spice optimizes for static dispatch. When you fork a task, the code is duplicated inside the function. If the task is not picked up by another thread, it runs locally as a regular, highly-optimized function call. If it is picked up by another thread, the original thread calls .wait() to synchronize.

This approach makes the common case (local execution) behave like a sequential program with predictable branches, allowing for compiler inlining and efficient CPU execution.

// Conceptual representation of Spice's fork/join logic
job1 = fork { code1 }  // Place on the queue
job2 = fork { code2 }  // Place on the queue

code3 // Run right away

if (job2.isExecuting()) {
  // Job was picked up by another thread. Wait for it.
  job2.wait()
} else {
  code2
}

if (job1.isExecuting()) {
  // Job was picked up by another thread. Wait for it.
  job1.wait()
} else {
  code1
}

To parallelize a function in Spice, you must follow a specific pattern involving a Task parameter and a fork/join workflow.

Core Requirements:

1. Task Parameter: Every parallel function must accept a *spice.Task as its first parameter to coordinate work.
2. Use t.call: Never call your parallel function directly. Always use the t.call method on the task object to ensure the function is invoked through the Spice scheduler.
3. Forking Work: Use spice.Future(ReturnType, Type).init().fork(t, function, args) to signal that a piece of work can be executed by another thread.
4. Joining Work: Use fut.join(t) to attempt to retrieve the result from the forked task.
5. Fallback Mechanism: join(t) may return null if no other thread picked up the work. If it returns null, you must execute the work yourself using t.call to ensure the task is completed.

This pattern ensures that if no other threads are available, the work is simply executed locally, maintaining low overhead.

const spice = @import("spice");

// (1) Add task as a parameter.
fn sum(t: *spice.Task, node: *const Node) i64 {
    var res: i64 = node.val;

    if (node.left) |left_child| {
        if (node.right) |right_child| {
            var fut = spice.Future(*const Node, i64).init();

            // (3) Call `fork` to set up work for another thread.
            fut.fork(t, sum, right_child);

            // (4) Do some work yourself.
            res += t.call(i64, sum, left_child);

            if (fut.join(t)) |val| {
                // (5) Wait for the other thread to complete the work.
                res += val;
            } else {
                // (6) ... or do it yourself if join returned null.
                res += t.call(i64, sum, right_child);
            }
            return res;
        }

        res += t.call(i64, sum, left_child);
    }

    if (node.right) |right_child| {
        // (2) Recursive calls must use `t.call`
        res += t.call(i64, sum, right_child);
    }

    return res;
}