In Java 8, does Executors.newWorkStealingPool() also provide a task queue?

Question

Is there a queue of pending tasks used in conjunction with Java 8's Executors.newWorkStealingPool()?

For example, suppose the # available cores is 2, and Executors.newWorkStealingPool() is empty because 2 tasks are already running. Then what happens if a 3rd task is submitted to the work-stealing executor? Is it queued? And if it is, what are the bounds if any on said queue?

Thanks in advance.

Corsair

I don't have a specific answer, and I'm surprised this isn't documented better. But at least in OpenJDK 8, this method produces a ForkJoinPool, which doesn't simply use a BlockingQueue as other implementations do...that causes a lot of contention, leading to overhead. Tasks that cannot be immediately executed are still queued however. This is discussed (along with queue bounds) in another answer: https://mcmap.net/q/1909783/-how-to-block-a-queue-in-forkjoinpool – Heading

Answer 1

Is there a queue of pending tasks used in conjunction with Java 8's Executors.newWorkStealingPool()?

Yes, every thread is backed with it's own deque. When one thread is done with it's tasks it takes task from other thread's deque and executes it.

And if it is, what are the bounds if any on said queue?

Maximum size for the queues is limited by the number: static final int MAXIMUM_QUEUE_CAPACITY = 1 << 26; // 64M

When the queue is full an unchecked exception is thrown: RejectedExecutionException("Queue capacity exceeded")

Jesse

Answer 2

From grepcode of Executors and ForkJoinPool

Executors.newWorkStealingPool returns ForkJoinPool

Executors:

 public static ExecutorService newWorkStealingPool() {
        return new ForkJoinPool
            (Runtime.getRuntime().availableProcessors(),
             ForkJoinPool.defaultForkJoinWorkerThreadFactory,
             null, true);
    }

ForkJoinPool:

public ForkJoinPool(int parallelism,
                        ForkJoinWorkerThreadFactory factory,
                        UncaughtExceptionHandler handler,
                        boolean asyncMode) {
        this(checkParallelism(parallelism),
             checkFactory(factory),
             handler,
             asyncMode ? FIFO_QUEUE : LIFO_QUEUE,
             "ForkJoinPool-" + nextPoolId() + "-worker-");
        checkPermission();
    }

On execute() :

public void execute(ForkJoinTask<?> task) {
        if (task == null)
            throw new NullPointerException();
        externalPush(task);
    }

externalPush calls externalSubmit and you can see WorkQueue details in that implementation.

externalSubmit:

// External operations

/**
 * Full version of externalPush, handling uncommon cases, as well
 * as performing secondary initialization upon the first
 * submission of the first task to the pool.  It also detects
 * first submission by an external thread and creates a new shared
 * queue if the one at index if empty or contended.
 *
 * @param task the task. Caller must ensure non-null.

 */

You can find more details about queue sizes in WorkQueue class

 static final class WorkQueue {

Documentation on WokrQueue:

/**
     * Queues supporting work-stealing as well as external task
     * submission. See above for descriptions and algorithms.
     * Performance on most platforms is very sensitive to placement of
     * instances of both WorkQueues and their arrays -- we absolutely
     * do not want multiple WorkQueue instances or multiple queue
     * arrays sharing cache lines. The @Contended annotation alerts
     * JVMs to try to keep instances apart.
     */
    @sun.misc.Contended

 /**
     * Capacity of work-stealing queue array upon initialization.
     * Must be a power of two; at least 4, but should be larger to
     * reduce or eliminate cacheline sharing among queues.
     * Currently, it is much larger, as a partial workaround for
     * the fact that JVMs often place arrays in locations that
     * share GC bookkeeping (especially cardmarks) such that
     * per-write accesses encounter serious memory contention.
     */
    static final int INITIAL_QUEUE_CAPACITY = 1 << 13;

    /**
     * Maximum size for queue arrays. Must be a power of two less
     * than or equal to 1 << (31 - width of array entry) to ensure
     * lack of wraparound of index calculations, but defined to a
     * value a bit less than this to help users trap runaway
     * programs before saturating systems.
     */
    static final int MAXIMUM_QUEUE_CAPACITY = 1 << 26; // 64M

Yachting