Custom Executor Design

In this lesson, you will learn how to design a work-stealing executor to maximize CPU utilization by dynamically balancing task loads across threads.

The Problem: Thread Starvation

In a simple executor, each thread typically manages its own local queue of tasks. If Thread A finishes its work while Thread B is stuck processing a massive batch of compute-heavy futures, Thread A goes idle. This wastes hardware resources. A work-stealing executor solves this by allowing idle threads to "steal" tasks from the back of other threads' queues.

Anatomy of a Work-Stealing Executor

To implement this, we need three primary components:

1. Local Run Queues: Each worker thread owns a Deque (Double-Ended Queue). Threads push/pop tasks from the front of their own queue (LIFO for cache locality).
2. Global Queue: A shared queue used as a fallback for tasks submitted from outside the executor.
3. The Stealing Logic: When a worker's local queue is empty, it attempts to steal tasks from the back of other workers' queues (FIFO for better load distribution).

Here is a simplified look at the worker loop:

fn worker_loop(local_queue: &mut Deque<Task>, all_queues: &[Deque<Task>]) {
    loop {
        // 1. Try local queue
        if let Some(task) = local_queue.pop_front() {
            task.run();
        } 
        // 2. Try stealing from others
        else if let Some(stolen_task) = steal_from_others(all_queues) {
            stolen_task.run();
        } 
        // 3. Park thread to save power
        else {
            thread::park();
        }
    }
}

Why Bother?

By using pop_front for local work and pop_back for stealing, you maximize cache locality. The thread processing the task keeps the data in its L1/L2 cache, while stealing threads only intervene when they would otherwise be idle, minimizing synchronization overhead. Using crossbeam-deque is the industry standard for implementing these lock-free data structures safely, as raw Mutex contention across every steal attempt would quickly negate the performance gains of parallelism.

Key Takeaway: A work-stealing executor ensures high CPU throughput by allowing idle workers to migrate pending tasks from overloaded queues, effectively balancing the load without the bottleneck of a single global lock.