[stdlib-sig] futures - a new package for asynchronous execution

[Jeffrey Yasskin]

On Thu, Nov 12, 2009 at 10:13 PM, Brian Quinlan <brian at sweetapp.com> wrote:
>
> On Nov 13, 2009, at 4:27 PM, Jeffrey Yasskin wrote:
>
>> On Thu, Nov 12, 2009 at 9:19 PM, Brian Quinlan <brian at sweetapp.com> wrote:
>>>
>>> On Nov 8, 2009, at 6:37 AM, Jeffrey Yasskin wrote:
>>>>
>>>> --- More general points ---
>>>>
>>>> ** Java's Futures made a mistake in not supporting work stealing, and
>>>> this has caused deadlocks at Google. Specifically, in a bounded-size
>>>> thread or process pool, when a task in the pool can wait for work
>>>> running in the same pool, you can fill up the pool with tasks that are
>>>> waiting for tasks that haven't started running yet. To avoid this,
>>>> Future.get() should be able to steal the task it's waiting on out of
>>>> the pool's queue and run it immediately.
>>>
>>> Hey Jeff,
>>>
>>> I understand the deadlock possibilities of the executor model, could you
>>> explain your proposal would work?
>>>
>>> Would it be some sort of flag on the Future.get method e.g.
>>> Future.get(timeout=None, immediate_execution=False)?
>>
>> I don't think a flag is the way to go at first glance, although there
>> could be upsides I haven't thought of. Here's what I had in mind:
>>
>> After I call "fut = executor.submit(task)", the task can be in 3
>> states: queued, running, and finished. The simplest deadlock happens
>> in a 1-thread pool when the running thread calls fut.result(), and the
>> task is queued on the same pool. So instead of just waiting for the
>> task to finish running, the current thread atomically(checks what
>> state it's in, and if it's queued, marks it as stolen instead) and
>> calls it in the current thread. When a stolen task gets to the front
>> of its queue and starts running, it just acts like a no-op.
>>
>> This can't introduce any new lock-order deadlocks, but it can be
>> observable if the task looks at thread-local variables.
>
> So you have something like this:
>
> def Future.result(self, timeout=None):
>  with some_lock:  # would have to think about locking here
>    do_work_locally =  (threading.current_thread in self._my_executor.threads
> and
>        self._my_executor.free_threads == 0 and
>        timeout is None):

You can deadlock from a cycle between multiple pools, too, so it's
probably a bad idea to limit it to only steal if self is one of the
pool's threads, and there's no real reason to limit the stealing to
when there are exactly 0 waiting threads. Depending on the internal
implementation, Future.result() might look something like (untested,
sorry if there are obvious bugs):

class Future:
  def __init__(self, f, args, kwargs):
    self.f, self.args, self.kwargs = f, args, kwargs
    self.state, self.lock = QUEUED, Executor.Lock()

  def run(self):
    with self.lock:
      if self.state != QUEUED: return
      self.state = RUNNING
    self._result = self.f(*self.args, **self.kwargs)
    with self.lock:
      self.state = DONE
      self.notify()

  def result(self, timeout=None):
    if timeout is None:  # Good catch.
      self.run()
    self.wait(timeout)
    return self._result

> That's pretty clever. Some things that I don't like:
> 1. it might only be applicable to executors using a thread pool so people
>    shouldn't count on it (but maybe only thread pool executors have this
>    deadlock problem so it doesn't matter?)

Process pools have the same deadlock problem, unless it's impossible
for a task in a process pool to hold a reference to the same pool, or
another pool whose tasks have a reference to the first one?

> 2. it makes the implementation of Future dependent on the executor that
>     created it - but maybe that's OK too, Future can be an ABC and
>     executor implementations that need customer Futures can subclass it

It makes some piece dependent on the executor, although not
necessarily the whole Future. For example, the run() method above
could be wrapped into a Task class that only knows how to mark work
stolen and run stuff locally.