JCiP Memoizer

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

JCiP Memoizer

Alexandru Popescu ☀
Hi!

I would start by saying that till now Chapter 5 is my favorite so far
:">. Still, I have a small problem (indeed it is 5am) understanding
the final version of Memoizer (page 108), or at least one line from
it:

[code]
public V compute(final A arg) throws InterruptedException {
   while(true) {
            // code
    }
}
[/code]

I feel I am missing the meaning of this "infinite" loop. Can you
please help me out?

many thanks,

./alex
--
.w( the_mindstorm )p.
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JCiP Memoizer

Joe Bowbeer
On 10/17/06, Alexandru Popescu <[hidden email]> wrote:

>
> I would start by saying that till now Chapter 5 is my favorite so far
> :">. Still, I have a small problem (indeed it is 5am) understanding
> the final version of Memoizer (page 108), or at least one line from
> it:
>
> public V compute(final A arg) throws InterruptedException {
>    while(true) {
>             // code
>     }
> }
>

It's because of this line further down:

            } catch (CancellationException e) {
                cache.remove(arg, f);

from http://jcip.net/listings/Memoizer.java

Here's a partial explanation:

The memoizing compute method is trying to reflect the exception from
the wrapped method back to the caller, but it also has to handle the
case where the task may have been cancelled (somehow).

In this case, the compute method removes its task from the cache (iff
it created the task) and tries again.

--Joe
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JCiP Memoizer

tpeierls
It's only 1am here, but it looks funny to me, too. I remember that the intent was that a thread interrupted in the middle of a long computation should not leave the incomplete computation lying around in the cache. So any thread that detects a cancellation removes the task from the cache and tries again.

But an interruption during ft.run() will not be seen as a cancellation of the FutureTask, so this doesn't work. The fix would probably involve checking for interruption after the call to ft.run().

I just read Joe's response, but I don't see how a Memoizer-created FutureTask, encapsulated as it is, could ever be cancelled. (Also, I don't think cache.remove(arg, f) ensures that only the task creator removes the task; it just ensures that the only the failed task is removed.)

--tim


On 10/18/06, Joe Bowbeer <[hidden email]> wrote:
On 10/17/06, Alexandru Popescu <[hidden email]> wrote:
>
> I would start by saying that till now Chapter 5 is my favorite so far
> :">. Still, I have a small problem (indeed it is 5am) understanding
> the final version of Memoizer (page 108), or at least one line from
> it:
>
> public V compute(final A arg) throws InterruptedException {
>    while(true) {
>             // code
>     }
> }
>

It's because of this line further down:

            } catch (CancellationException e) {
                cache.remove(arg, f);

from http://jcip.net/listings/Memoizer.java

Here's a partial explanation:

The memoizing compute method is trying to reflect the exception from
the wrapped method back to the caller, but it also has to handle the
case where the task may have been cancelled (somehow).

In this case, the compute method removes its task from the cache (iff
it created the task) and tries again.

--Joe
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JCiP Memoizer

Alexandru Popescu ☀
On 10/18/06, Tim Peierls <[hidden email]> wrote:

> It's only 1am here, but it looks funny to me, too. I remember that the
> intent was that a thread interrupted in the middle of a long computation
> should not leave the incomplete computation lying around in the cache. So
> any thread that detects a cancellation removes the task from the cache and
> tries again.
>
> But an interruption during ft.run() will not be seen as a cancellation of
> the FutureTask, so this doesn't work. The fix would probably involve
> checking for interruption after the call to ft.run().
>
>  I just read Joe's response, but I don't see how a Memoizer-created
> FutureTask, encapsulated as it is, could ever be cancelled. (Also, I don't
> think cache.remove(arg, f) ensures that only the task creator removes the
> task; it just ensures that the only the failed task is removed.)
>

(a bit later: early in the morning): Things are starting to become
more clear. I don't think there is any way a FutureTask can be
cancelled (cause I don't see it published). Also, I am not sure how
can you reach a CancellationException (for the same reasons).

Another question related to the same code would be: what if the
compute method must not perpetuate the InterruptedException? Wouldn't
this qualify for the cache.remove call? (because as far as I get it,
if the expensive computation resulted in an InterruptedException, then
you will never get the change to compute the real value.

Sorry if I ask wrong questions, but the code looks pretty interesting
(and I am doing an attempt to further detail it to my collegues, that
may need to use something similar).

./alex
--
.w( the_mindstorm )p.



> --tim
>
>
>
> On 10/18/06, Joe Bowbeer < [hidden email]> wrote:
> > On 10/17/06, Alexandru Popescu <
> [hidden email]> wrote:
> > >
> > > I would start by saying that till now Chapter 5 is my favorite so far
> > > :">. Still, I have a small problem (indeed it is 5am) understanding
> > > the final version of Memoizer (page 108), or at least one line from
> > > it:
> > >
> > > public V compute(final A arg) throws InterruptedException {
> > >    while(true) {
> > >             // code
> > >     }
> > > }
> > >
> >
> > It's because of this line further down:
> >
> >             } catch (CancellationException e) {
> >                 cache.remove(arg, f);
> >
> > from http://jcip.net/listings/Memoizer.java
> >
> > Here's a partial explanation:
> >
> > The memoizing compute method is trying to reflect the exception from
> > the wrapped method back to the caller, but it also has to handle the
> > case where the task may have been cancelled (somehow).
> >
> > In this case, the compute method removes its task from the cache (iff
> > it created the task) and tries again.
> >
> > --Joe
> > _______________________________________________
> > Concurrency-interest mailing list
> > [hidden email]
> >
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
> >
>
>
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JCiP Memoizer

David Holmes-3
Alex,

I have to concur with Tim. The intent was that interruption during ft.run()
implied cancellation and so there was a need to do clean-up of the cache
entry. But there is nothing to convert the interruption to a cancel()
request and so all that happens in the current case is that everyone who
calls f.get() will get ExecutionException with a cause of
InterruptedException.

Assuming the general case and there was a means to cancel() the FutureTask
then I would be tempted to rewrite the code as follows:

    try {
       return f.get();
    }
    catch (CancellationException e) {
       cache.remove(arg, f);
    }
    catch (ExecutionException e) {
       Throwable t = e.getCause();
       if (t instanceof InterruptedException) // ft.run was 'cancelled'
          cache.remove(arg,f);
       throw launderThrowable(t);
    }

But this doesn't quite work right as it causes an InterruptionException in
both the thread that actually got the interrupt (the one that ran ft.run() )
and any thread that happened to be blocked on f.get() at the time. (Later
threads will re-compute due to the cache removal). What we want to be able
to do is determine if the current thread is the one that executed ft.run()
and only in that case throw the InterruptException. One way to do that would
be to declare ft at the top of the while loop and check for ft != null eg:

    try {
       return f.get();
    }
    catch (CancellationException e) {
       cache.remove(arg, f);
    }
    catch (ExecutionException e) {
       Throwable t = e.getCause();
       if (t instanceof InterruptedException) { // ft.run was 'cancelled'
          cache.remove(arg,f);
          if (ft != null)  // we did ft.run() so we were interrupted
             throw (InterruptedException) t;
          // else retry
       else {
          throw launderThrowable(t);
       }
    }


Note that if compute() doesn't convert an interrupt to InterruptedException
then we presume it did not actually abort the computation. Hence finding the
interrupt bit set after ft.run() is not an indication of cancellation.

And as per the text if you might be able to recompute then any
ExecutionException might be used to just remove the cache entry, and only
throw if the current thread was the one that invoked ft.run().

Cheers,
David Holmes

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]]On Behalf Of
> Alexandru Popescu
> Sent: Wednesday, 18 October 2006 6:06 PM
> To: concurrency-interest
> Subject: Re: [concurrency-interest] JCiP Memoizer
>
>
> On 10/18/06, Tim Peierls <[hidden email]> wrote:
> > It's only 1am here, but it looks funny to me, too. I remember that the
> > intent was that a thread interrupted in the middle of a long computation
> > should not leave the incomplete computation lying around in the
> cache. So
> > any thread that detects a cancellation removes the task from
> the cache and
> > tries again.
> >
> > But an interruption during ft.run() will not be seen as a
> cancellation of
> > the FutureTask, so this doesn't work. The fix would probably involve
> > checking for interruption after the call to ft.run().
> >
> >  I just read Joe's response, but I don't see how a Memoizer-created
> > FutureTask, encapsulated as it is, could ever be cancelled.
> (Also, I don't
> > think cache.remove(arg, f) ensures that only the task creator
> removes the
> > task; it just ensures that the only the failed task is removed.)
> >
>
> (a bit later: early in the morning): Things are starting to become
> more clear. I don't think there is any way a FutureTask can be
> cancelled (cause I don't see it published). Also, I am not sure how
> can you reach a CancellationException (for the same reasons).
>
> Another question related to the same code would be: what if the
> compute method must not perpetuate the InterruptedException? Wouldn't
> this qualify for the cache.remove call? (because as far as I get it,
> if the expensive computation resulted in an InterruptedException, then
> you will never get the change to compute the real value.
>
> Sorry if I ask wrong questions, but the code looks pretty interesting
> (and I am doing an attempt to further detail it to my collegues, that
> may need to use something similar).
>
> ./alex
> --
> .w( the_mindstorm )p.
>
>
>
> > --tim
> >
> >
> >
> > On 10/18/06, Joe Bowbeer < [hidden email]> wrote:
> > > On 10/17/06, Alexandru Popescu <
> > [hidden email]> wrote:
> > > >
> > > > I would start by saying that till now Chapter 5 is my
> favorite so far
> > > > :">. Still, I have a small problem (indeed it is 5am) understanding
> > > > the final version of Memoizer (page 108), or at least one line from
> > > > it:
> > > >
> > > > public V compute(final A arg) throws InterruptedException {
> > > >    while(true) {
> > > >             // code
> > > >     }
> > > > }
> > > >
> > >
> > > It's because of this line further down:
> > >
> > >             } catch (CancellationException e) {
> > >                 cache.remove(arg, f);
> > >
> > > from http://jcip.net/listings/Memoizer.java
> > >
> > > Here's a partial explanation:
> > >
> > > The memoizing compute method is trying to reflect the exception from
> > > the wrapped method back to the caller, but it also has to handle the
> > > case where the task may have been cancelled (somehow).
> > >
> > > In this case, the compute method removes its task from the cache (iff
> > > it created the task) and tries again.
> > >
> > > --Joe
> > > _______________________________________________
> > > Concurrency-interest mailing list
> > > [hidden email]
> > >
> > http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
> > >
> >
> >
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JCiP Memoizer

Joe Bowbeer
I think the existing cancellation exception handling would make more
sense if the task were submitted to an executor.  Then a forced
shutdown of the executor, for example, could cause a cancellation
exception.

Btw, when I've coded this kind of thing in the past, I've usually
finessed the problem by adding "throws Exception" to the method in
question :-)

On 10/18/06, David Holmes <[hidden email]> wrote:

> Alex,
>
> I have to concur with Tim. The intent was that interruption during ft.run()
> implied cancellation and so there was a need to do clean-up of the cache
> entry. But there is nothing to convert the interruption to a cancel()
> request and so all that happens in the current case is that everyone who
> calls f.get() will get ExecutionException with a cause of
> InterruptedException.
>
> [...]
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JCiP Memoizer

Alexandru Popescu ☀
On 10/18/06, Joe Bowbeer <[hidden email]> wrote:
> I think the existing cancellation exception handling would make more
> sense if the task were submitted to an executor.  Then a forced
> shutdown of the executor, for example, could cause a cancellation
> exception.
>
> Btw, when I've coded this kind of thing in the past, I've usually
> finessed the problem by adding "throws Exception" to the method in
> question :-)
>

He he... in my case I must have no throws :-).

./alex
--
.w( the_mindstorm )p.

> On 10/18/06, David Holmes <[hidden email]> wrote:
> > Alex,
> >
> > I have to concur with Tim. The intent was that interruption during ft.run()
> > implied cancellation and so there was a need to do clean-up of the cache
> > entry. But there is nothing to convert the interruption to a cancel()
> > request and so all that happens in the current case is that everyone who
> > calls f.get() will get ExecutionException with a cause of
> > InterruptedException.
> >
> > [...]
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JCiP Memoizer

tpeierls
In reply to this post by Joe Bowbeer
One of the things that makes the Memoizer example so interesting (and suitable for inclusion in chapter 5 of JCiP) is that it is a rare example of FutureTask used outside of an Executor.

Does David's last fix with additional interrupt checking in the Callable adapter do the trick? Something like this:
    public V compute(final A arg) throws InterruptedException {
while (true) {
Future<V> f = cache.get(arg);
FutureTask<V> ft = null;
if (f == null) {
Callable<V> eval = new Callable<V>() {
public V call() throws InterruptedException {
V result = c.compute(arg);
if ( Thread.interrupted())
throw new InterruptedException();
return result;
}
};
FutureTask<V> ft = new FutureTask<V>(eval);
f = cache.putIfAbsent(arg, ft);
if (f == null) {
f = ft;
ft.run();
} else {
ft = null;
}
}
try {
return f.get();
} catch (CancellationException e) {
throw new IllegalStateException("can't have been cancelled"); // ??
} catch (ExecutionException e) {
      Throwable t = e.getCause();
      if (t instanceof InterruptedException) { // ft.run() was interrupted
          cache.remove(arg,f);
          if (ft != null)  // we did ft.run() so we were interrupted
            throw (InterruptedException) t;
// else retry
      } else {
          throw launderThrowable(t);
      }
}
}
}

Yuck. Makes that final example a lot harder to explain than we were hoping for.

--tim


On 10/18/06, Joe Bowbeer <[hidden email]> wrote:
I think the existing cancellation exception handling would make more
sense if the task were submitted to an executor.  Then a forced
shutdown of the executor, for example, could cause a cancellation
exception.

Btw, when I've coded this kind of thing in the past, I've usually
finessed the problem by adding "throws Exception" to the method in
question :-)

On 10/18/06, David Holmes <[hidden email]> wrote:

> Alex,
>
> I have to concur with Tim. The intent was that interruption during ft.run()
> implied cancellation and so there was a need to do clean-up of the cache
> entry. But there is nothing to convert the interruption to a cancel()
> request and so all that happens in the current case is that everyone who
> calls f.get() will get ExecutionException with a cause of
> InterruptedException.
>
> [...]
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JCiP Memoizer

David Holmes-3
In reply to this post by Alexandru Popescu ☀
Hi Tim,

You don't need the interrupted() check in the Callable adapter. If the thread was interrupted during call() then if call() "aborted" it should have thrown InterruptedException. The fact that call() didn't throw indicates that call() completed successfully and the result is available.

What we'd really like is to specialise FutureTask.run so that InterruptedException is treated as a cancel request. But there is no way to do that without writing your own Future implementation because any attempt to "wrap" super.run() is too late to stop the IE from being treated as a general exception. Hmmm - with the fixes in the Java 6 version (I think they got in!) that ensures sync.innerRun calls ft.setException then it might be possible to do this:

    ft = new FutureTask(eval) {
        protected void setException(Throwable t) {
            if (t instanceof InterruptedException)
                cancel(false);
            else
                super.setException(t);
        }
    };  

Still not "pretty" though.

The complexity has arisen in this example because of the attempt to treat interruption as a transient error rather than a permanent one, combined with the desire to show handling cancellation even though it isn't actually possible.

Cheers,
David




> Tim Peierls <[hidden email]> wrote:
>
> One of the things that makes the Memoizer example so interesting (and
> suitable for inclusion in chapter 5 of JCiP) is that it is a rare
> example of
> FutureTask used outside of an Executor.
>
> Does David's last fix with additional interrupt checking in the Callable
> adapter do the trick? Something like this:
>
>     public V compute(final A arg) throws InterruptedException {
>         while (true) {
>             Future<V> f = cache.get(arg);
>             FutureTask<V> ft = null;
>             if (f == null) {
>                 Callable<V> eval = new Callable<V>() {
>                     public V call() throws InterruptedException {
>                         V result = c.compute(arg);
>                         if (Thread.interrupted())
>                             throw new InterruptedException();
>                         return result;
>                     }
>                 };
>                 FutureTask<V> ft = new FutureTask<V>(eval);
>                 f = cache.putIfAbsent(arg, ft);
>                 if (f == null) {
>                     f = ft;
>                     ft.run();
>                 } else {
>                     ft = null;
>                 }
>             }
>             try {
>                 return f.get();
>             } catch (CancellationException e) {
>                 throw new IllegalStateException("can't have been
> cancelled"); // ??
>             } catch (ExecutionException e) {
>                 Throwable t = e.getCause();
>                 if (t instanceof InterruptedException) { // ft.run()
> was interrupted
>                     cache.remove(arg,f);
>                     if (ft != null)  // we did ft.run() so we were
> interrupted
>                         throw (InterruptedException) t;
>                     // else retry
>                 } else {
>                     throw launderThrowable(t);
>                 }
>             }
>         }
>     }
>
>
> Yuck. Makes that final example a lot harder to explain than we were
> hoping
> for.
>
> --tim
>
>
> On 10/18/06, Joe Bowbeer <[hidden email]> wrote:
> >
> > I think the existing cancellation exception handling would make more
> > sense if the task were submitted to an executor.  Then a forced
> > shutdown of the executor, for example, could cause a cancellation
> > exception.
> >
> > Btw, when I've coded this kind of thing in the past, I've usually
> > finessed the problem by adding "throws Exception" to the method in
> > question :-)
> >
> > On 10/18/06, David Holmes <[hidden email]> wrote:
> > > Alex,
> > >
> > > I have to concur with Tim. The intent was that interruption during
> > ft.run()
> > > implied cancellation and so there was a need to do clean-up of the
> cache
> > > entry. But there is nothing to convert the interruption to a
> cancel()
> > > request and so all that happens in the current case is that everyone
> who
> > > calls f.get() will get ExecutionException with a cause of
> > > InterruptedException.
> > >
> > > [...]
> > _______________________________________________
> > Concurrency-interest mailing list
> > [hidden email]
> > http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
> >
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest