Making agents able to temporarily yield place on thread pool

[Anand Patil]

Hi all,

My concurrent dabblings in Clojure have been a real pleasure so far.
In terms of concurrency, it's just in a completely different league
from any other language I've tried. However, I think agents could be
made even more friendly by allowing them to temporarily surrender
their place in the thread pool pending another computation.

Specifically, I'm thinking of a function 'yield' called as (yield
other-agent msg-fn args) from within agent actions. If agent a yields
to agent b, a gets off the thread pool and msg is sent to b with given
args. When b finishes executing the message, the yield call returns
b's new value, and a gets back on the thread pool.

I _think_ the language could prevent deadlocks by:
- making agents not take any messages while they are 'yielded'
- keeping a 'yield stack' and checking that no cycles happen.

Here are two use cases for yield:

1) Say an 'auto-agent' cell needs to run an expensive, parallelizable
computation to update its value. Without yield you could do this by
dispatching the action with send-off, or by splitting the cell up into
multiple cells, each handling a chunk of the computation. Yield would
be nicer than both: send-off spawns an expensive kernel thread (as I
understand it) and breaking up the cell complicates the dataflow model
unnecessarily.

2) Currently this program, which creates a tree of dependent futures,
deadlocks on my 8-core mac pro:

(def breadth 4)

(defn with-deref [fun]
(fn [& x] (apply fun (map deref x))))

(defn future-tree [depth]
(if (= depth 0) (future 1)
(let [new-futures (map future-tree (repeat breadth (- depth
1)))]
(future (apply (with-deref +) new-futures)))))

; WARNING: This deadlocks on 8-core Mac Pro!
(future-tree 4)

I'm guessing it deadlocks because the thread pool fills up with
futures that aren't ready to go, but it feels like the language should
be able to avoid the deadlock without requiring the programmer to
think about how many threads are actually in the thread pool. If
futures were based on agents, which yielded when deref-ing other
futures, the deadlock wouldn't happen.

I have no idea how hard it would be to implement yield, as I have very
little practice with Java. Thoughts?

Anand

[Rich Hickey]

I've made futures use the Agents' CachedThreadPool, which should
prevent the thread pool exhaustion (svn 1316). You shouldn't worry
about the expense of the threads, that's why there's a pool.

Yield as you've described it is definitely not going to happen.

Rich

[MikeM]

Not sure if I understand what you need, but could you build on the
existing capability to send to the current agent: (send *agent* ...) ?
You could have the agent send to itself, then exit the function with
some work left to do that would be restarted on the next go-around.

[Timothy Pratley]

Hi Rich,

Would you accept a patch to allow either pool to be selected? (you
have my CA)
http://groups.google.com/group/clojure/web/futures.patch
(future (+ 1 2))
(future-pool (+ 1 2))
I think the naming is a bit tricky and might need adjusting (something
that shadows send/send-off might be better).

Why would I want this? When I have lots of tasks to do but want to
keep roughly to the CPU size number of threads.


Regards,
Tim.

[Timothy Pratley]

A non-important follow up question too:
When I initially implemented without a type-hint for 'pool', it didn't
work at all (deref would always be nil). I'm just curious why.

[Anand Patil]

I could get away with sending to b with instructions to send back to
a... the yield suggestion was just syntactic sugar for doing that.

Anand

[Anand Patil]

Rich,

If you'll bear with me a bit longer- what if I set breadth=1000 and
depth=1000 in the program above. The thread pool would have to grow by
thousands to avoid a deadlock, whereas with something like yield it
could stay alive using only the standard, fixed-size thread pool.

Anand

Anand

[Rich Hickey]

I understand the problem and there is already a solution - it's called
the Fork/Join framework, and you can use it easily from Clojure:

http://www.ibm.com/developerworks/java/library/j-jtp11137.html
http://gee.cs.oswego.edu/dl/concurrency-interest/index.html

I'm not going to reinvent that.

There are some wrappers for ParallelArray in clojure.parallel.
Unfortunately it seems like ParallelArray is not going to make it into
Java 7 (although it is still available in 'extra').

jsr166y only targets only Java 1.6+. It seems like the API is
stabilizing though, and might be a good time to look at wrapping more
of Fork/Join for use with Clojure (volunteers welcome).

Rich

[Anand Patil]

On Mar 2, 12:48 pm, Rich Hickey <richhic...@gmail.com> wrote:
> On Mar 2, 2009, at 5:15 AM, Anand Patil wrote:
>
>
> > On Mar 1, 10:58 pm, Rich Hickey <richhic...@gmail.com> wrote:
> >> On Mar 1, 2009, at 1:53 PM, Anand Patil wrote:
> >> I've made futures use the Agents' CachedThreadPool, which should
> >> prevent the thread pool exhaustion (svn 1316). You shouldn't worry
> >> about the expense of the threads, that's why there's a pool.
>
> >> Yield as you've described it is definitely not going to happen.
>
> > Rich,
>
> > If you'll bear with me a bit longer- what if I set breadth=1000 and
> > depth=1000 in the program above. The thread pool would have to grow by
> > thousands to avoid a deadlock, whereas with something like yield it
> > could stay alive using only the standard, fixed-size thread pool.
>
> I understand the problem and there is already a solution - it's called  
> the Fork/Join framework, and you can use it easily from Clojure:
>
> http://www.ibm.com/developerworks/java/library/j-jtp11137.htmlhttp://gee.cs.oswego.edu/dl/concurrency-interest/index.html

Good to know- I'll have a look at Fork/Join.

Thanks,
Anand

[Anand Patil]

On Mar 2, 2:34 pm, Anand Patil <anand.prabhakar.pa...@gmail.com>
wrote:

> >http://www.ibm.com/developerworks/java/library/j-jtp11137.htmlhttp://...

>
> Good to know- I'll have a look at Fork/Join.

OK, ForkJoin really does solve exactly that problem. Nice. Out of
curiosity, what's your vision for how ForkJoin would ideally
interoperate with Clojure's own agents and futures? Specifically,
would they share a thread pool, and would the availability of ForkJoin
actually change the behavior of agents and futures at all?

Thanks,
Anand