How does ForkJoinPool's work-stealing algorithm work?

Each worker thread in a ForkJoinPool maintains its own double-ended queue (deque) of tasks. A thread pushes new subtasks it creates onto the front of its own deque and also pops tasks to execute from that same front, which behaves like a LIFO stack and gives good cache locality since a thread tends to keep working on the subtasks it most recently created. When a thread's own deque runs empty, it becomes a "thief": it looks at another thread's deque and steals a task from the back of that queue instead, which behaves like FIFO and tends to grab the oldest, typically largest, available chunk of work. Because the owning thread only ever touches the front of its deque while thieves only ever touch the back, the two rarely need to synchronize against each other, which keeps contention low. The overall effect is that as long as there is work anywhere in the pool, idle threads will keep finding and stealing it rather than sitting unused.