Commentary: work-stealing-queue

Per-worker deques, and the famous rule that thieves take the far end. On an uneven bag of tasks that rule is worth −4.76 ticks and the wrong end wins 271 of 500 orderings. On a divide-and-conquer tree, nothing else changed, it is worth 1.62× — because only one of them has a size gradient. A study guide for wsq.py.

cd work-stealing-queue
python3 demo.py       # the aha (§6)
python3 test_wsq.py   # pins every number this page quotes

1. Orientation

A work-stealing pool gives every worker its own queue instead of sharing one. A worker pushes and pops its own end; when its queue runs dry it becomes a thief, picks a victim, and takes a task from the victim's far end — the end the owner never touches. Cilk did it, Java's ForkJoinPool does it, Rayon does it, Go's scheduler does it, Tokio does it.

Everyone can recite the reason for the end split. The owner runs LIFO because the task it pushed most recently is the one whose data is still in cache; the thief takes FIFO from the other end so it never collides with the owner. It is one of the tidiest pieces of folklore in systems programming.

This toy measures it, and on the first workload the folklore is worth nothing. An uneven bag of 27 tasks over 4 workers: stealing from the correct end finishes in 925 ticks, stealing from the wrong end — the same end the owner is popping — finishes in 854. It is faster. Generate 500 different orderings of the same workload and the wrong end averages 4.76 ticks better, and wins 271 of the 500.

That result is real, reproducible, and completely misleading, and the rest of the page is about why. The resolution is not "well, it's about caches" — this toy has no caches. It is that the two ends of a deque are only different when the deque has a size gradient, and a bag of independent tasks does not have one. Give the workers a divide-and-conquer tree instead, change nothing else — same worker count, same task size, same steal cost — and the identical flip costs 1.62× the makespan, because on the far end sits the largest undivided subtree and one steal there moves 121 ticks of work instead of 33.

The control that nails it down: a root that spawns 128 equal tasks at once has spawning but no gradient, and there the two ends are not merely similar, they are interchangeable — same makespan, same steal count, same failure count, same ticks moved, to the integer.

By the end you should be able to:

• say what a steal actually moves, and why that is not the stolen task's own cost;
• predict, for a workload you already run, whether the deque-end rule can pay at all — by asking one question about whether your tasks spawn tasks;
• derive the makespan floor ⌈W/P⌉, and say why stealing lands 1.25× above it here and what the gap is made of;
• explain why 75 of 91 steal attempts on the headline workload come back empty-handed, and why that is not a bug;
• point at the two lines in the scheduler that decide the whole result, and say what changing each one does, having seen it run.

2. The problem this mechanism exists to solve

You have P workers and a pile of work whose shape you do not know in advance. There are three designs, and they fail in three different places.

Static partitioning. Deal the tasks out W/P each at the start and let everyone run. Zero coordination, perfect scaling — right up until the split is wrong, which it always is, because you cannot know how long a task takes until you run it. Panel A's workload is the pathological case: worker 0 holds 2468 ticks and the others hold a few hundred between them, so the run takes 2468 ticks against a floor of 740. Three workers spend most of the run idle.

One shared queue. Every worker pops from the same place, so the load is balanced by construction and nobody idles while work exists. The cost is that every single task acquisition touches one cache line that all P cores are fighting over. At fine granularity that line becomes the machine's slowest component; the scheduler's throughput stops scaling somewhere around a handful of cores and stays there no matter how many you add.

Per-worker deques, plus stealing. The common case — a worker taking its own next task — touches only memory that worker owns, so it costs nothing and contends with nobody. Coordination happens only when a worker runs out, which on a well-shaped workload is rare. This is the design the toy builds.

The competing goals that make more than one answer defensible:

• Balance vs. contention. The shared queue is perfectly balanced and maximally contended. Static partitioning is the reverse. Stealing tries to buy balance at a price paid only by idle workers.
• Cheap steals vs. useful steals. You want each steal to move enough work that you do not immediately need another one, but the biggest available task is also the one the owner is least likely to have finished with.
• Locality vs. fairness. Running your own most recent task is good for cache and terrible for anyone waiting on your oldest one.

The end split is the design's answer to all three at once — and the claim this toy tests is that the answer is only load-bearing for one of them.

3. Background you need

The two starred rows carry the result. Everything else is scaffolding.

4. The mental model

A worker's deque has two ends, and the whole design rests on the claim that they are different. Here is what is actually at each end, for the two workload shapes the toy builds.

The gradient is not a property of stealing, or of LIFO, or of deques. It is a property of recursive subdivision: a task that has not been touched yet is worth more than one that has been split six times, and depth-first execution sorts the deque by exactly that.

So the rule "steal from the far end" is really the rule "steal the task with the most work still hidden under it", and the far end is merely where that task ends up. Where nothing hides under any task — a pre-enumerated bag of jobs — the rule has nothing to grip.

The clock model, in one line: every worker does exactly one of execute a tick, pop its own end (free), or spend a tick inside a steal_cost-tick steal attempt — and the clock advances one tick when every worker has had its turn.

5. Reading the source

5.1 Task — cost is a function of divisibility

class Task:
    """A unit of work. Divisible tasks cost `SPLIT_TICKS` and produce two
    children; indivisible ones cost their whole size and produce nothing.

    `leaf_size` is the granularity cutoff. `Task(c, c)` is therefore an
    always-indivisible task of cost c, which is what `preload` deals out.
    """

    __slots__ = ("size", "divisible")

    def __init__(self, size, leaf_size):
        self.size = size
        self.divisible = size > leaf_size

    def cost(self):
        return SPLIT_TICKS if self.divisible else self.size

The important thing here is the gap between size and cost(). A divisible task of size 512 costs one tick to run — splitting is cheap — but represents 575 ticks of eventual work. Every intuition on this page lives in that gap, and a scheduler that cannot see it is choosing blind.

Which is exactly the situation of a real work-stealing runtime: it has no idea how big a subtree is. It uses position in the deque as a proxy for size, and the proxy works because depth-first execution keeps the deque sorted. Task(c, c) is the escape hatch that lets preload deal never-divisible tasks through the same type, so the two workloads run through one scheduler with no branches added to it.

5.2 Worker — naming the ends once, so nothing else has to

class Worker:
    """A deque plus the task currently in hand.

    `dq[-1]` is the own end (push/pop, LIFO for the owner); `dq[0]` is the far
    end (oldest task, what a thief takes when `steal_end == FAR`).
    """

    __slots__ = ("wid", "dq", "cur", "left", "stealing", "busy", "overhead")

    def __init__(self, wid):
        self.wid = wid
        self.dq = deque()
        self.cur = None        # task in hand
        self.left = 0          # ticks remaining on it
        self.stealing = 0      # ticks remaining in the current steal attempt
        self.busy = 0          # ticks spent executing tasks
        self.overhead = 0      # ticks spent inside steal attempts

busy and overhead are separated on purpose: busy is work the program asked for and overhead is what the scheduler charged to deliver it. Their ratio is the honest measure of a stealing policy, and it is what makes panel C's 552-tick makespan for 1024 ticks of work over 8 workers explicable rather than mysterious.

cur and left mean a task is executed incrementally, one tick per pass, rather than atomically. That costs nothing in code and buys the ability to ask "where was everyone at tick 7?", which is how CF2 catches the first steal in the act.

5.3 subtree — the number the scheduler is not allowed to know

    def subtree(self, t):
        """Total ticks of work hiding under a task, children included.

        A divisible task of size n eventually becomes n/leaf leaves costing n
        ticks in total, plus n/leaf - 1 internal splits at SPLIT_TICKS each.
        This is the number that makes the far end worth taking: it is what one
        steal actually moves, which is not the same as the task's own cost.
        """
        if not t.divisible:
            return t.size
        return t.size + SPLIT_TICKS * (t.size // self.leaf - 1)

This is instrumentation, not scheduling. Nothing in run or _steal_tick ever consults it to make a decision — it only accumulates into self.moved so the demo can report what a steal was worth after the fact. If the scheduler were allowed to call it before choosing, the toy would be measuring an oracle rather than a heuristic, and the entire result would evaporate.

The arithmetic: 1024 at leaf 8 is 128 leaves of 8 ticks (1024) plus 127 internal splits of 1 tick each, so subtree(Task(1024, 8)) == 1151, which is exactly the total_work the demo reports for panel D. A binary tree with n leaves has n − 1 internal nodes; that is the whole derivation.

5.4 Sim.run — one tick, every worker, in order

    def run(self, stealing=True, limit=10_000_000):
        """Advance until every deque is empty and no worker holds a task.

        Returns the makespan: the tick at which the last worker finished.

        The termination test sits at the *top* of the pass, before any worker
        steps. Put it at the bottom instead and the run bills one extra tick
        for the pass in which everyone discovers there is nothing left --
        enough to break `makespan == the hoarder's own load` in section 6.
        """
        while self.clock < limit:
            if not any(w.dq or w.cur for w in self.w):
                break
            for w in self.w:
                if w.cur is None and w.stealing == 0 and w.dq:
                    w.cur = w.dq.pop()           # own end, free, LIFO
                    w.left = w.cur.cost()
                if w.cur is not None:
                    w.busy += 1
                    w.left -= 1
                    if w.left == 0:
                        t, w.cur = w.cur, None
                        if t.divisible:
                            half = t.size // 2
                            w.dq.append(Task(half, self.leaf))
                            w.dq.append(Task(t.size - half, self.leaf))
                elif stealing:
                    self._steal_tick(w)
            self.clock += 1
        return self.clock

Three decisions worth defending.

w.cur = w.dq.pop(), and the pop is free. The owner takes its own end, and pays nothing to do it. That asymmetry against _steal_tick's steal_cost is the toy's entire model of "local memory is cheap, remote memory is not" — it is the only place the toy encodes that idea, and §8 explains what a real machine charges instead.

This line is load-bearing in its own right, not just as a foil. Change pop() to popleft() — the owner running FIFO over its own deque — and panel D's far-end run goes from 211 ticks to 486, worse than the "wrong" end was under the shipped scheduler (CF3 in §6.6). Owner-LIFO is what builds the gradient; take it away and there is no gradient for the thief to exploit, whichever end it robs.

w.dq.append(half) then w.dq.append(rest), both on the own end. The children go where the owner will get them next, so the recursion proceeds depth-first. Push them on the far end instead and the tree would run breadth-first, the deque would grow to the width of the tree, and the gradient would run the other way.

The termination test at the top of the pass. Put it after self.clock += 1 and every run bills one extra tick for the pass in which everyone discovers there is nothing left. That is a one-tick lie, which is small enough to survive review and large enough to break the cleanest derivation on this page: with stealing=False, the makespan of panel A must equal worker 0's own pile, 2468, exactly. It did not, until this moved.

Note what is missing: any notion of a worker sleeping. An idle worker with nowhere to steal from spins forever on failed attempts until the run ends. That is faithful to a real runtime's spin phase and unfaithful to what happens after it, which §8.2 picks up.

5.5 _steal_tick — one line decides the page

    def _steal_tick(self, w):
        """Spend one tick inside a steal attempt; resolve it when the window
        closes. A failed attempt costs exactly what a successful one costs --
        the thief cannot know the deque was empty without going to look.
        """
        if w.stealing == 0:
            w.stealing = self.steal_cost
        w.stealing -= 1
        w.overhead += 1
        if w.stealing != 0:
            return
        v = self.pick_victim(w)
        if not v.dq:
            self.failed += 1
            return
        t = v.dq.popleft() if self.steal_end == FAR else v.dq.pop()
        self.steals += 1
        self.moved += self.subtree(t)
        self.log.append((self.clock, v.wid, w.wid, t.size, self.subtree(t)))
        w.cur, w.left = t, t.cost()

t = v.dq.popleft() if self.steal_end == FAR else v.dq.pop() is the line the entire toy exists to interrogate. Everything else is the apparatus for running it both ways against identical inputs.

Two supporting decisions matter more than they look:

The victim is chosen at the end of the window, not the start. The thief pays first and looks second, which is the right model: by the time a real steal's cache line arrives, the deque it describes may have changed. Choosing the victim up front would let the thief reserve work it has not yet paid for.

A failed attempt costs full price. if not v.dq: self.failed += 1; return happens after the entire steal_cost has been burned. This is not pessimism — a thief genuinely cannot discover a deque is empty without going to look at it, and on a remote core that look is the expensive part. It is also load-bearing: refund the failures and panel D's 1.62× collapses to 1.13× (CF4 in §6.6), because the own end's disadvantage is largely that it needs so many more attempts.

5.6 The two workloads, side by side

def spawn_flat(sim, n, each, wid=0):
    """One worker holding n equal indivisible tasks: spawning without a
    gradient. The control that isolates task *size* from LIFO-vs-FIFO.
    """
    for _ in range(n):
        sim.w[wid].dq.append(Task(each, each))


def spawn_tree(sim, root, wid=0):
    """One divisible root. Splitting it builds the size gradient: the far end
    keeps the shallowest, largest subtree; the own end holds the smallest.
    """
    sim.w[wid].dq.append(Task(root, sim.leaf))

Thirteen lines, and they are the experiment. Both start all the work on worker 0, both hand the scheduler tasks of the same granularity (8 ticks at the leaves), both run through the identical run loop. The only difference is that spawn_tree's root is divisible, so the deque acquires an ordering by remaining size and spawn_flat's never does.

That is why panel C is a control and not just another data point: it holds everything constant except the one property the page claims is responsible.

6. The demo, and what it proves

python3 demo.py prints five panels. Taken in order they set up a result, demolish it, and then explain what was really going on.

6.1 Panel A — stealing works, exactly as advertised

Every number here is derivable.

W = 2959. uneven_bag(7) deals 24 tasks to worker 0 and one each to workers 1, 2 and 3, costs drawn from 20–200 by a seeded LCG. 27 tasks, 2959 ticks between them.

2468, the no-stealing makespan. With stealing=False an idle worker simply idles, so the run lasts exactly as long as the busiest initial pile — worker 0's 24 tasks, which sum to 2468. Not 2469: see §5.4. Workers 1–3 finish their single tasks in the first few hundred ticks and then contribute nothing for the remaining ~2200. That is static partitioning failing, and 3.34x floor is the size of the failure.

925, with stealing. 16 steals move 1691 ticks off worker 0 — 57% of the total work, at 105.7 ticks per steal. The result lands at 1.25× the floor, so stealing recovers most but not all of the 3.34× gap.

Where the remaining 25% goes, since a headline number with an unexplained residue is not a result. Three places: (1) 91 steal attempts × 8 ticks = 728 ticks of overhead charged to thieves, of which 75 attempts found nothing; (2) tasks are indivisible, so the last one to start — up to 200 ticks — runs alone at the end while everyone else is finished; (3) at tick 0 only worker 0 has anything to give, so the first three steals serialize behind steal_cost. None of these is avoidable by choosing a different end, which is the next panel's point.

6.2 Panel B — and now break the famous rule

The wrong end wins by 71 ticks, 7.7% — and a single instance proves nothing, which is why the demo runs 500 of them. Across 500 orderings of the same workload shape the mean difference is −4.756 ticks against a makespan around 900, or half a percent, with a standard deviation eight times larger than the mean. The own end is better 271 times and worse 224.

There is no rule here. There is a coin flip with a barely detectable tilt, and the tilt is not even in the direction the folklore predicts.

Anyone who has read the Cilk papers now has an objection ready — it's about cache locality, and your toy has no cache. That objection is correct and it is not the answer, because the toy is about to reproduce a large, one-directional, entirely cache-free difference between the same two ends.

6.3 Panel C — the control: spawning, without a gradient

Identical. Not close — identical. Same makespan, same 60 successful steals, same 364 failures, same 480 ticks moved, same 8.0 ticks per steal. And test_wsq.py checks this at steal_cost 1, 2, 4, 8, 16 and 32, so it is not an artifact of the chosen price either.

This is the panel that turns panel B from an anecdote into a claim. A deque of 128 equal tasks is a set, not a sequence: popleft and pop return objects that differ in identity and in nothing else, so the two schedulers make literally the same decisions. Whatever the deque-end rule is about, it is not about which end.

Note in passing how badly this workload does in absolute terms: 1024 ticks of work over 8 workers has a floor of 128, and it takes 552. 364 of the 424 attempts fail — 86% — and every failure costs 8 ticks. Fine-grained independent tasks are expensive to balance no matter which end you take them from, because each steal moves 8 ticks and costs 8 ticks to obtain.

6.4 Panel D — the same flip, on a tree

Eight workers, leaf tasks of 8 ticks, steal cost 8 — every parameter that panel C used. The only change is that the work arrives as one divisible root instead of 128 indivisible pieces. The end flip now costs 1.62×.

The mechanism is in the last column. 121.1 ticks per steal against 33.4. The far end hands a thief a large undivided subtree; the own end hands it whatever the owner was about to run, which is by construction the smallest thing in the deque. So the own-end thief comes back for more: 50 steals and 145 failures, against 16 and 48. 195 attempts against 64, each costing 8 ticks.

Both numbers matter and they compound: less work per steal and more steals, each one billed.

There is a published bound to check this against. Blumofe and Leiserson prove the expected number of steal attempts under randomised work stealing is O(P·T∞), where T∞ is the span — the longest dependency chain. Here the tree is 1024 → 512 → … → 8, which is 7 splits of 1 tick plus one 8-tick leaf, so T∞ = 15:

The far end stays under P·T∞ at every worker count. The own end runs 1.6× to 2× over it — which is not a refutation of the theorem, it is a demonstration that the theorem's algorithm and the own-end variant are different algorithms, and the deque end is the difference.

6.5 What one steal actually carries

Two exhibits, both from verify_cf.py. First, the gradient itself — worker 0 subdividing the root with no thieves running at all:

Seven ticks of depth-first recursion sort the deque into a near-perfect descending gradient, and 393 ticks later the 512 has still not moved. That is the structural fact the far-end rule exploits: the biggest remaining piece of work is the one the owner will get to last.

Second, the steal log — the first six steals under each policy:

The far end's very first steal, at tick 7, moves 575 of the program's 1151 ticks — half the entire computation, in one steal, before tick 8. And it cascades: worker 7 is a victim at tick 15, having been a thief at tick 7, so the work fans out at the rate a binary tree fans out. Six steals in and the work is distributed to a depth of 128-sized subtrees.

The own-end log next to it: 8, 8, 32, 8, 8, 8. Worker 0 is robbed of a leaf, finishes the leaf, and the thief is back 8 ticks later. Notice that worker 0 appears as the victim in five of the first six rows — the own-end thieves cannot fan out, because the crumbs they steal never make them worth robbing in turn.

6.6 Panel E, and where the effect vanishes

The one tuned constant on this page is steal_cost = 8 — a steal costs the same as one leaf task. That is defensible for fine-grained parallelism: a real steal is a contended atomic operation plus a cache line pulled off another core, and a leaf task at that granularity is a few hundred nanoseconds. But it is a choice, and it moves the answer:

At steal_cost = 1 the effect is 1.03× — gone. If a steal is as cheap as a tick of work, needing three times as many is nearly free, and the far-end rule is not worth the sentence it takes to state. Everything on this page about the tree is conditional on steals being expensive relative to tasks, which they are on real hardware and are not in this toy by default.

Three more boundaries, all measured.

The bag has to be uneven. Deal panel A's identical 2959 ticks round-robin instead of hoarding them:

Round-robin: no stealing at all gives 824 against a floor of 740, stealing gives 796, and the two ends produce the same 796 from the same 3 steals. When the initial deal is already balanced the mechanism barely engages, and a scheduler you never invoke cannot have a policy worth arguing about.

The owner's end is load-bearing too. Make the owner pop popleft() instead of pop() — FIFO over its own deque — and re-run panel D:

486 against 211 — worse than the "wrong" steal end ever was. Owner-FIFO makes the owner take the biggest subtree first and push its halves back behind everything else, which levels the deque: ticks per steal fall from 121.1 to 12.8. The gradient was never a property of the thief's choice. It was manufactured by the owner's, and the thief only harvests it.

Failed steals have to cost something. Refund them and re-run all three workloads:

1.62× falls to 1.13×. Most of the own end's penalty is not the small tasks it takes; it is the 145 fruitless trips it makes looking for more. Panel C stays identical between the ends under both billing rules, as it must.

6.7 The tests

test_wsq.py pins every figure quoted above — the 500-ordering distribution including its standard deviation, panel C's byte-identical counters at six different steal costs, the O(P·T∞) comparison, and the invariant that no schedule ever finishes below ⌈W/P⌉. It also checks the result is not one lucky tree: the far end wins by more than 1.5× at roots 256 through 4096 and at 4, 8 and 16 workers.

7. Design decisions and roads not taken

7.1 A virtual clock instead of real threads

The obvious build is threading.Thread with a real deque and a real lock, and it was rejected before a line was written. Real threads would make every number on this page a distribution rather than a value: the 71-tick gap in panel B and the 500-ordering mean of −4.756 are differences of half a percent and cannot be measured against OS scheduler noise. Panel C's claim — the two ends produce identical counters — would be unstatable.

The clock is an integer advanced only when a worker spends a tick. There is no time.monotonic(), no random module, no thread. victim="rr" is the default precisely so the headline numbers owe nothing even to a seed. The cost of this choice is §8, and it is a real cost.

7.2 Round-robin victims, and the oracle that beats them

Three victim policies ship. The default is round-robin because it is deterministic; random uses a seeded LCG; richest picks the victim with the longest deque — which no real scheduler can afford, since it means reading P remote counters on every attempt.

The oracle is 20% faster and its failure rate collapses from 48 to 4. That is a large prize, and real schedulers decline it anyway. Reading every worker's queue length means touching P cache lines that P cores are writing to — you would spend more on choosing a victim than on robbing one, and you would reintroduce exactly the shared-state contention that per-worker deques exist to eliminate. Random victims need no shared state at all, and are what Blumofe and Leiserson's bound is proved against.

Worth stating plainly: no victim policy rescues the wrong end. The far end wins under all three, and test_wsq.py asserts it.

7.3 Failed steals are billed at full price

75 of 91 attempts fail in panel A; 364 of 424 fail in panel C — 86%. A first draft that made failures free would look kinder and be wrong: discovering a deque is empty means reading it, and reading it is what costs. CF4 shows the decision is load-bearing rather than cosmetic — refunding failures shrinks panel D's result from 1.62× to 1.13×.

The failure rate is also the most transferable number here. A pool that spends most of its steal attempts finding nothing is a pool whose parallelism has run out, and the fix is never a better victim policy — it is coarser tasks or fewer workers.

7.4 No Chase–Lev, no atomics, no lock

The real artifact at the heart of this design is the Chase–Lev lock-free deque: push and pop on the owner's end are almost always plain loads and stores, steal is a CAS on the far end, and the two only synchronise when the deque has one element left and the owner and a thief are reaching for the same task. That last case is genuinely subtle and it is where the ends being different pays its largest real dividend.

It is absent because implementing it in Python would be theatre — the GIL makes the atomics meaningless — and because it would double the line count to demonstrate a property this toy cannot measure. §8.1 states the consequence rather than hiding it.

7.5 SPLIT_TICKS = 1, and a fixed leaf size

Subdividing costs one tick and the recursion stops at a fixed leaf. Real fork–join runtimes make this decision per call site, and getting it wrong is the single most common performance bug in Rayon and ForkJoinPool code: too coarse and there is nothing to steal, too fine and the split overhead eats the parallelism. Panel D's tree spends 127 of its 1151 ticks — 11% — purely on splitting, which is a realistic tax and is included in every figure.

7.6 One steal per attempt, never a batch

A thief takes exactly one task. Go's scheduler steals half the victim's run-queue in one operation, which is the flat-workload answer to panel C's 86% failure rate: if you cannot make each stolen task bigger, take more of them per trip. It is not implemented here because batch stealing changes the result being measured — it would improve the own end more than the far end, since the far end already gets a whole subtree — and the honest place for that comparison is a second toy.

8. What's simplified vs. the real thing

8.1 The disclosure that matters: this measures one of three reasons

Real work-stealing deques split the ends for three reasons. This toy can only measure the third, and the one it cannot measure is arguably the primary one.

1. Contention. In a Chase–Lev deque the owner's push/pop touch one end and a thief's steal touches the other, so the overwhelmingly common operation — a worker taking its own next task — needs no atomic and contends with nobody. Put both operations on the same end and every single task acquisition becomes a contended CAS. This is very plausibly the reason the design exists at all. The toy has no locks, no atomics and no memory model, so it cannot see this cost, and stealing from the own end costs it nothing in that dimension.
2. Locality. The owner's end is cache-hot: the task pushed most recently references data the worker just touched. A thief taking the far end takes the coldest task in the deque, which is the right task to take precisely because it is going to a different core anyway. The toy has no caches, so a task costs the same ticks regardless of which core runs it or what ran before it.
3. Granularity. The far end holds the largest undivided subtree, so one steal moves the most work. This is the only one the toy measures.

So read panel B correctly. It does not show that the deque-end rule is worthless; it shows that in a pure scheduling model — no caches, no atomics — the rule buys nothing on a workload with no size gradient. Panel B's zero is a statement about scheduling, not about memory. A real machine running panel A's workload would still prefer the far end, for reasons 1 and 2, and this page cannot tell you how much they are worth.

The virtual clock is also what makes panels C and E possible at all. "Every counter is identical at six different steal costs" and a clean 1.03× → 2.40× sweep are claims a wall-clock harness could not make, because it would produce a different table every run.

8.2 The other simplifications

• Idle workers never sleep. A thief with nothing to steal spins on failed attempts until the run ends, burning overhead forever. Real runtimes spin briefly and then park the thread on a futex or condition variable, which saves power and destroys latency — an unparked worker takes microseconds to wake, so runtimes agonise over how many to keep spinning. Nothing here models that, and panel C's 364 failures would in reality be a few dozen followed by a nap.
• No dependencies between tasks. A parent that spawns children here does not wait for them; it is finished the moment it splits. Real fork–join has a join point, which introduces blocked workers, continuation stealing and the whole question of what a worker does while its child is elsewhere. That is the largest structural omission on the list.
• Perfect fairness, no preemption. Every worker gets exactly one tick per pass, in worker-id order. There is no OS scheduler, no core running at a different frequency, no worker descheduled mid-task. Real makespans are worse than these, never better.
• Task costs are declared integers. Task(137, 137) means "assume this takes 137 ticks". Real task costs are data-dependent distributions, and the whole reason work stealing exists is that you cannot know them ahead of time — a toy that hands the workload an exact cost is being handed the answer to the question the mechanism is trying to solve.
• One fixed steal cost. Real steal costs vary by an order of magnitude with the victim's location: same core complex, across an L3, across a NUMA socket. Production schedulers care intensely — Go and Tokio bias victim selection toward nearby workers — and the toy models a flat topology where every worker is equidistant from every other.
• The deque is unbounded and never overflows. Chase–Lev's circular array has to grow, and growing it while a thief is reading is one of the sharper problems in the original paper. Python's deque makes it disappear.
• No task affinity or priority. Every task is interchangeable with every other. Real runtimes carry pinned tasks, priorities and "run this on the worker that produced its input" hints, all of which override the end rule.

9. Check yourself

10. Further reading

• Scheduling Multithreaded Computations by Work Stealing — Blumofe & Leiserson, JACM 46(5), 1999. The proof that randomised work stealing runs in T₁/P + O(T∞) expected time. Lemma 12 is the one §6.4 checks against: "The expected number of steal attempts is O(PT∞)." Read §4 for the potential-function argument even if you skip the delay-sequence proof; the bucketing intuition (every step, each processor puts a dollar in either the WORK bucket or the STEAL bucket) is the clearest thing written about why stealing scales.
• The Implementation of the Cilk-5 Multithreaded Language — Frigo, Leiserson & Randall, PLDI'98. Where the "work-first principle" comes from: move overhead off the common path and onto the critical path, even when that seems backwards. The THE protocol section is the practical answer to what happens when the owner and a thief reach for the last task in a deque.
• Dynamic Circular Work-Stealing Deque — Chase & Lev, SPAA'05. The deque this toy pointedly does not implement: owner-end operations are plain loads and stores, the thief's end is a CAS, and the array grows without stopping either. §8.1's first reason is this paper.
• Correct and Efficient Work-Stealing for Weak Memory Models — Lê, Pop, Cohen & Zappa Nardelli, PPoPP'13. What Chase–Lev needs on ARM and Power, where the hardware does not give you sequential consistency for free. Worth reading to see how much of the "obvious" deque protocol was quietly assuming x86.
• ForkJoinPool — Java's production work-stealing pool. The class documentation is unusually candid about granularity: it recommends tasks of "between 100 and 10000 basic computational steps" and explains what goes wrong on either side, which is panel C's failure rate stated as engineering advice.
• Making the Tokio scheduler 10x faster — Carl Lerche, 2019. A production rewrite with measurements, including why a global injection queue coexists with per-worker deques and how they handle the "everyone is asleep and work just arrived" problem this toy ignores entirely.
• Rayon — the Rust data-parallelism library built on a work-stealing pool. join is the API-level version of §5.6's spawn_tree, and Rayon's split heuristics are exactly the SPLIT_TICKS/leaf trade-off of §7.5 made adaptive.
• runtime/proc.go — Go's scheduler. Search for runqsteal and stealWork: Go steals half of a victim's run queue rather than one task, which is the road not taken in §7.6, and the comments around the spinning-thread accounting are the best short explanation of the parking problem in §8.2.