Advice on running tasks with limited parallelism against a shared executor service?

[Bryan Thompson-2]

Hello,

I often have situations where I would like a set of tasks to execute with limited parallelism against a shared executor service with an unbounded thread pool.  I am interested in limited parallelism because there can be 1000s of subtasks for the designed operation that are decomposed onto tasks.  Typically, those subtasks are performing remote reads on different database shards.  I would like to use an unbounded thread pool to avoid the possibility of deadlock.  I would like to use a shared thread pool because some subtasks can be very light operations and I would like to avoid the overhead of establishing a new executor service and creating its threads and have better control over the executor service on which all of this is running, e.g., for monitoring task service rates.

So the "pattern" that I use is to submit the subtasks of a given task in chunks to the shared executor service, and then submit another chunk when the first one is finished.  This means that all subtasks in a chunk must complete before the next chunk of subtasks for a given caller can be processed.  Different high-level tasks may be submitting their own chunks concurrently, so the total concurrency of the task execution is not bounded by the #of subtasks submitted at once for any given high-level task.

Is there a better way to go about this without having to create an executor service for each set of tasks whose decomposed subtasks I want to run with limited parallelism?

Thanks,

-bryan

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Holger Hoffstätte-4]

Bryan Thompson wrote:
> Is there a better way to go about this without having to create an
> executor service for each set of tasks whose decomposed subtasks I want
> to run with limited parallelism?

Sounds like ExecutorCompletionService might fit the bill?

-h

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Bryan Thompson-2]

Holger,

It would appear that the ExecutionCompletionService does not limit the concurrency of the tasks accepted for processing except by the backing thread pool.  In my case, with an unbounded thread pool, it would accept all tasks and create new threads as necessary to execute those tasks.

Thanks,

-bryan

> -----Original Message-----
> From: concurrency-interest-bounces@...
> [mailto:concurrency-interest-bounces@...] On Behalf
> Of Holger Hoffstätte
> Sent: Thursday, October 15, 2009 11:08 AM
> To: concurrency-interest@...
> Subject: Re: [concurrency-interest] Advice on running tasks
> with limited parallelism against a shared executor service?
>
> Bryan Thompson wrote:
> > Is there a better way to go about this without having to create an
> > executor service for each set of tasks whose decomposed subtasks I
> > want to run with limited parallelism?
>
> Sounds like ExecutorCompletionService might fit the bill?
>
> -h
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest@...
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Joe Bowbeer]

I'm imagining that a completion service was suggested as a way to incrementally feed new tasks to the unbounded executor -- as existing tasks complete.

Something along these lines has been discussed before, searching the archives for "completion service" might find it.

A similar approach is to create something like a (lightweight) SerialExecutor for each chunk of tasks.  See example in Executor javadoc:

  http://java.sun.com/javase/6/docs/api/index.html?java/util/concurrent/Executor.html

The serial executor is similar to a completion service, in that it wraps tasks in order to hook their done() method.

In this approach, each chunk of tasks would be gated by a serial executor.

Joe

On Thu, Oct 15, 2009 at 10:19 AM, Bryan Thompson wrote:

Holger,

It would appear that the ExecutionCompletionService does not limit the concurrency of the tasks accepted for processing except by the backing thread pool.  In my case, with an unbounded thread pool, it would accept all tasks and create new threads as necessary to execute those tasks.

Thanks,

-bryan

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Joe Bowbeer]

Correction:

The SerialExecutor example doesn't hook the done() method (as ExecutorCompletionService does); it wraps the Runnable task in a try-finally.  Same difference...

--Joe

On Thu, Oct 15, 2009 at 11:22 AM, Joe Bowbeer wrote:

I'm imagining that a completion service was suggested as a way to incrementally feed new tasks to the unbounded executor -- as existing tasks complete.

Something along these lines has been discussed before, searching the archives for "completion service" might find it.

A similar approach is to create something like a (lightweight) SerialExecutor for each chunk of tasks.  See example in Executor javadoc:

  http://java.sun.com/javase/6/docs/api/index.html?java/util/concurrent/Executor.html

The serial executor is similar to a completion service, in that it wraps tasks in order to hook their done() method.

In this approach, each chunk of tasks would be gated by a serial executor.

Joe

On Thu, Oct 15, 2009 at 10:19 AM, Bryan Thompson wrote:

Holger,

It would appear that the ExecutionCompletionService does not limit the concurrency of the tasks accepted for processing except by the backing thread pool.  In my case, with an unbounded thread pool, it would accept all tasks and create new threads as necessary to execute those tasks.

Thanks,

-bryan

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Phil Goodwin]

Hi Bryan,

I have had success in the past with the following techniques:

To avoid deadlocks, tasks with dependencies are expressed as
continuations. When the gating task completes, it places all dependent
tasks into the work queue of the thread pool. That way the thread pool
contains only tasks that have hope of progressing. Placing timeouts on
remote operations prevents the system from becoming clogged with
threads waiting on hung operations.

To optimize parallelization of remote processes I dedicate a thread
pool of limited size (very often one) to each remote server and tune
the rate of requests to that server to optimize the load for
throughput. Then I dispatch incoming tasks according to the server
they will query so that I am keeping as many machines busy as
possible.

It would probably be better to make remote requests asynchronous, but
I don't have direct experience with that. My thinking is that sleeping
threads are a waste of system resources. I'd rather have a pointer to
a callback sitting around waiting for a response than the huge chunk
of ram that gets allocated as the stack for a thread.

I don't like the approach of using an unbounded thread pool. Threads
are expensive resources both in terms of the memory needed for their
stacks and the time it takes to schedule and context switch between
them, not to mention the hit taken by flushing CPU cache lines. Basing
their allocation strategy on the random demands produced by contention
between threads will lead to similarly random fluctuations on
performance. I think that it is better to allocate threads according
to the number of CPU cores available and the number of hardware
devices that require synchronous access, with some tuning to trade off
throughput for reduced latency.

If it is not feasible to anticipate the dependencies between tasks, it
is still possible to obtain the deadlock breaking effects of unlimited
threads by using a fair scheduler and putting timeouts on all
attempted resource acquisitions. If a task encounters a timeout it
responds by rolling back its work, placing itself at the back of the
work queue, and terminating. This is the moral equivalent of a thread
stalling and being replaced by a new thread, but with drastically
smaller overhead. You end up with the same benefit as "unlimited"
threads, but with a higher effective upper limit on tasks that can be
attempting to make forward progress at any given time.

Batching makes sense in that scenario (assuming that earlier batches
are not gated by tasks that are contained in later batches) because it
will limit the amount of churn that can be caused by task timeouts.
But in general I would prefer to manage dependencies and load
explicitly in order to get more predictable (and debuggable) results.

Nice to see you again, Bryan,

Phil

On Thu, Oct 15, 2009 at 7:24 AM, Bryan Thompson <bryan@...> wrote:

> Hello,
>
> I often have situations where I would like a set of tasks to execute with limited parallelism against a shared executor service with an unbounded thread pool.  I am interested in limited parallelism because there can be 1000s of subtasks for the designed operation that are decomposed onto tasks.  Typically, those subtasks are performing remote reads on different database shards.  I would like to use an unbounded thread pool to avoid the possibility of deadlock.  I would like to use a shared thread pool because some subtasks can be very light operations and I would like to avoid the overhead of establishing a new executor service and creating its threads and have better control over the executor service on which all of this is running, e.g., for monitoring task service rates.
>
> So the "pattern" that I use is to submit the subtasks of a given task in chunks to the shared executor service, and then submit another chunk when the first one is finished.  This means that all subtasks in a chunk must complete before the next chunk of subtasks for a given caller can be processed.  Different high-level tasks may be submitting their own chunks concurrently, so the total concurrency of the task execution is not bounded by the #of subtasks submitted at once for any given high-level task.
>
> Is there a better way to go about this without having to create an executor service for each set of tasks whose decomposed subtasks I want to run with limited parallelism?
>
> Thanks,
>
> -bryan
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest@...
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Bryan Thompson-2]

Joe,

 

Thanks - that makes sense.

 

-bryan

---

From: concurrency-interest-bounces@... [mailto:concurrency-interest-bounces@...] On Behalf Of Joe Bowbeer
Sent: Thursday, October 15, 2009 2:23 PM
To: concurrency-interest
Subject: Re: [concurrency-interest] Advice on running tasks with limited parallelism against a shared executor service?

I'm imagining that a completion service was suggested as a way to incrementally feed new tasks to the unbounded executor -- as existing tasks complete.

Something along these lines has been discussed before, searching the archives for "completion service" might find it.

A similar approach is to create something like a (lightweight) SerialExecutor for each chunk of tasks.  See example in Executor javadoc:

  http://java.sun.com/javase/6/docs/api/index.html?java/util/concurrent/Executor.html

The serial executor is similar to a completion service, in that it wraps tasks in order to hook their done() method.

In this approach, each chunk of tasks would be gated by a serial executor.

Joe

On Thu, Oct 15, 2009 at 10:19 AM, Bryan Thompson wrote:

Holger,

It would appear that the ExecutionCompletionService does not limit the concurrency of the tasks accepted for processing except by the backing thread pool.  In my case, with an unbounded thread pool, it would accept all tasks and create new threads as necessary to execute those tasks.

Thanks,

-bryan

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest