Re: CHM.compute restrictions

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

Re: CHM.compute restrictions

JSR166 Concurrency mailing list
Hi Doug, Concurrency Interest

Sorry I lost the subject when I reposted.

I understand that updating other keys or recursively initializing the same key is illegal in a CHM.compute. I don't understand how this example code could be recursive though?

It seems to be a defect in parallel stream. Using a for loop to submit the tasks in parallel for the out loop has no issue. These should be effectively the same. There is some interaction between the outer parallel stream that I don't understand.

I don't think Stream.parallel is expected to result in stream operators executing recursively on stream elements? 

Thanks

On Mon, Aug 6, 2018 at 12:01 PM <[hidden email]> wrote:
Send Concurrency-interest mailing list submissions to
        [hidden email]

To subscribe or unsubscribe via the World Wide Web, visit
        http://cs.oswego.edu/mailman/listinfo/concurrency-interest
or, via email, send a message with subject or body 'help' to
        [hidden email]

You can reach the person managing the list at
        [hidden email]

When replying, please edit your Subject line so it is more specific
than "Re: Contents of Concurrency-interest digest..."


Today's Topics:

   1. (no subject) (David Stuebe)
   2. Re: CHM.compute restrictions (was: no     subject) (Doug Lea)


----------------------------------------------------------------------

Message: 1
Date: Mon, 6 Aug 2018 10:10:33 -0400
From: David Stuebe <[hidden email]>
To: "[hidden email]"
        <[hidden email]>
Subject: [concurrency-interest] (no subject)
Message-ID:
        <CAJh0pqEVuzteLqiijAsFiVMFm1XL+KO7o12MzH5wu=[hidden email]>
Content-Type: text/plain; charset="utf-8"

Hey folks

Attempted to post this last week while I was joining the list. I think it
bounced. Please ignore if it is a repeat. I have not seen any responses and
I am sad.

I found some great discussion of a previous issue* with nested
Stream.parallel operations here and hoping I might find some answers to a
related question.
* http://cs.oswego.edu/pipermail/concurrency-interest/2014-May/012652.html

I am using a ConcurrentHashMap.compute operation in an outer
Stream.parallel forEach operation. A library used in the compute method
also uses Stream.parallel.

I have written a test that illustrates the issue and explores different
implementations in 215 lines of code.
https://gist.github.com/dstuebe/89361f64dc44a935e53d0a49f149317c#file-nestedparallel-java

The code deadlocks with the following stack trace:
https://gist.github.com/dstuebe/89361f64dc44a935e53d0a49f149317c#file-stacktrace-txt

I do not understand why line 87 (the compute block) appears to be called
recursively leading to deadlock when I use Stream.parallel for the outer
loop.

Best

David
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20180806/543a8fb9/attachment-0001.html>

------------------------------

Message: 2
Date: Mon, 6 Aug 2018 10:31:55 -0400
From: Doug Lea <[hidden email]>
To: [hidden email]
Subject: Re: [concurrency-interest] CHM.compute restrictions (was: no
        subject)
Message-ID: <[hidden email]>
Content-Type: text/plain; charset=utf-8

On 08/06/2018 10:10 AM, David Stuebe via Concurrency-interest wrote:
> Hey folks 
>
> Attempted to post this last week while I was joining the list.

To reduce spam, non-member posts are silently dropped. Sorry.

>
> I am using a ConcurrentHashMap.compute operation in an outer
> Stream.parallel forEach operation. A library used in the compute method
> also uses Stream.parallel.
>
> I have written a test that illustrates the issue and explores different
> implementations in 215 lines of code.
> https://gist.github.com/dstuebe/89361f64dc44a935e53d0a49f149317c#file-nestedparallel-java
>
> The code deadlocks with the following stack trace:
> https://gist.github.com/dstuebe/89361f64dc44a935e53d0a49f149317c#file-stacktrace-txt
>
> I do not understand why line 87 (the compute block) appears to be called
> recursively leading to deadlock when I use Stream.parallel for the outer
> loop.

A recursive CHM.compute call appears to invoked while trying to
initialize the contents of an element in the same map, which is
disallowed in general, but sometimes works anyway. In most other cases,
CHM successfully detects this and throws an exception, but it cannot
catch all of them.

-Doug






------------------------------

Subject: Digest Footer

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


------------------------------

End of Concurrency-interest Digest, Vol 162, Issue 1
****************************************************

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

Re: CHM.compute restrictions

JSR166 Concurrency mailing list
Hi David,

Doug can correct me if I'm wrong, but I think that the following is taking place:

If the CHM.compute is executed in a ForkJoinPool as a ForkJoinTask (as a consequence of invoking it from parallel Stream.forEach) and the remapping function passed to CHM.compute contains a computation that uses parallel Stream, then the ForkJoinWorkerThread executing the remapping function may help in execution of other pending ForkJoinTasks, meaning that other Stream.forEach tasks may get executed nested in the remapping function passed to CHM.compute - hence you get re-entry to CHM.compute from the same thread.

Am I right?

Regards, Peter

On 08/07/2018 04:39 PM, David Stuebe via Concurrency-interest wrote:
Hi Doug, Concurrency Interest

Sorry I lost the subject when I reposted.

I understand that updating other keys or recursively initializing the same key is illegal in a CHM.compute. I don't understand how this example code could be recursive though?

It seems to be a defect in parallel stream. Using a for loop to submit the tasks in parallel for the out loop has no issue. These should be effectively the same. There is some interaction between the outer parallel stream that I don't understand.

I don't think Stream.parallel is expected to result in stream operators executing recursively on stream elements? 

Thanks

On Mon, Aug 6, 2018 at 12:01 PM <[hidden email]> wrote:
Send Concurrency-interest mailing list submissions to
        [hidden email]

To subscribe or unsubscribe via the World Wide Web, visit
        http://cs.oswego.edu/mailman/listinfo/concurrency-interest
or, via email, send a message with subject or body 'help' to
        [hidden email]

You can reach the person managing the list at
        [hidden email]

When replying, please edit your Subject line so it is more specific
than "Re: Contents of Concurrency-interest digest..."


Today's Topics:

   1. (no subject) (David Stuebe)
   2. Re: CHM.compute restrictions (was: no     subject) (Doug Lea)


----------------------------------------------------------------------

Message: 1
Date: Mon, 6 Aug 2018 10:10:33 -0400
From: David Stuebe <[hidden email]>
To: "[hidden email]"
        <[hidden email]>
Subject: [concurrency-interest] (no subject)
Message-ID:
        <CAJh0pqEVuzteLqiijAsFiVMFm1XL+KO7o12MzH5wu=[hidden email]>
Content-Type: text/plain; charset="utf-8"

Hey folks

Attempted to post this last week while I was joining the list. I think it
bounced. Please ignore if it is a repeat. I have not seen any responses and
I am sad.

I found some great discussion of a previous issue* with nested
Stream.parallel operations here and hoping I might find some answers to a
related question.
* http://cs.oswego.edu/pipermail/concurrency-interest/2014-May/012652.html

I am using a ConcurrentHashMap.compute operation in an outer
Stream.parallel forEach operation. A library used in the compute method
also uses Stream.parallel.

I have written a test that illustrates the issue and explores different
implementations in 215 lines of code.
https://gist.github.com/dstuebe/89361f64dc44a935e53d0a49f149317c#file-nestedparallel-java

The code deadlocks with the following stack trace:
https://gist.github.com/dstuebe/89361f64dc44a935e53d0a49f149317c#file-stacktrace-txt

I do not understand why line 87 (the compute block) appears to be called
recursively leading to deadlock when I use Stream.parallel for the outer
loop.

Best

David
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20180806/543a8fb9/attachment-0001.html>

------------------------------

Message: 2
Date: Mon, 6 Aug 2018 10:31:55 -0400
From: Doug Lea <[hidden email]>
To: [hidden email]
Subject: Re: [concurrency-interest] CHM.compute restrictions (was: no
        subject)
Message-ID: <[hidden email]>
Content-Type: text/plain; charset=utf-8

On 08/06/2018 10:10 AM, David Stuebe via Concurrency-interest wrote:
> Hey folks 
>
> Attempted to post this last week while I was joining the list.

To reduce spam, non-member posts are silently dropped. Sorry.

>
> I am using a ConcurrentHashMap.compute operation in an outer
> Stream.parallel forEach operation. A library used in the compute method
> also uses Stream.parallel.
>
> I have written a test that illustrates the issue and explores different
> implementations in 215 lines of code.
> https://gist.github.com/dstuebe/89361f64dc44a935e53d0a49f149317c#file-nestedparallel-java
>
> The code deadlocks with the following stack trace:
> https://gist.github.com/dstuebe/89361f64dc44a935e53d0a49f149317c#file-stacktrace-txt
>
> I do not understand why line 87 (the compute block) appears to be called
> recursively leading to deadlock when I use Stream.parallel for the outer
> loop.

A recursive CHM.compute call appears to invoked while trying to
initialize the contents of an element in the same map, which is
disallowed in general, but sometimes works anyway. In most other cases,
CHM successfully detects this and throws an exception, but it cannot
catch all of them.

-Doug






------------------------------

Subject: Digest Footer

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


------------------------------

End of Concurrency-interest Digest, Vol 162, Issue 1
****************************************************


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


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

Re: CHM.compute restrictions

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
How often is this supposed to deadlock? And in what environment? Because
I can't get it to. Also, the code is *very* confusing.

- Jonas

On 08/07/2018 04:39 PM, David Stuebe via Concurrency-interest wrote:

> Hi Doug, Concurrency Interest
>
> Sorry I lost the subject when I reposted.
>
> I understand that updating other keys or recursively initializing the
> same key is illegal in a CHM.compute. I don't understand how this
> example code could be recursive though?
>
> It seems to be a defect in parallel stream. Using a for loop to submit
> the tasks in parallel for the out loop has no issue. These should be
> effectively the same. There is some interaction between the outer
> parallel stream that I don't understand.
>
> I don't think Stream.parallel is expected to result in stream operators
> executing recursively on stream elements?
>
> Thanks
>
> On Mon, Aug 6, 2018 at 12:01 PM
> <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     Send Concurrency-interest mailing list submissions to
>     [hidden email]
>     <mailto:[hidden email]>
>
>     To subscribe or unsubscribe via the World Wide Web, visit
>     http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>     or, via email, send a message with subject or body 'help' to
>     [hidden email]
>     <mailto:[hidden email]>
>
>     You can reach the person managing the list at
>     [hidden email]
>     <mailto:[hidden email]>
>
>     When replying, please edit your Subject line so it is more specific
>     than "Re: Contents of Concurrency-interest digest..."
>
>
>     Today's Topics:
>
>         1. (no subject) (David Stuebe)
>         2. Re: CHM.compute restrictions (was: no     subject) (Doug Lea)
>
>
>     ----------------------------------------------------------------------
>
>     Message: 1
>     Date: Mon, 6 Aug 2018 10:10:33 -0400
>     From: David Stuebe <[hidden email]
>     <mailto:[hidden email]>>
>     To: "[hidden email]
>     <mailto:[hidden email]>"
>              <[hidden email]
>     <mailto:[hidden email]>>
>     Subject: [concurrency-interest] (no subject)
>     Message-ID:
>            
>     <CAJh0pqEVuzteLqiijAsFiVMFm1XL+KO7o12MzH5wu=[hidden email]
>     <mailto:[hidden email]>>
>     Content-Type: text/plain; charset="utf-8"
>
>     Hey folks
>
>     Attempted to post this last week while I was joining the list. I
>     think it
>     bounced. Please ignore if it is a repeat. I have not seen any
>     responses and
>     I am sad.
>
>     I found some great discussion of a previous issue* with nested
>     Stream.parallel operations here and hoping I might find some answers
>     to a
>     related question.
>     *
>     http://cs.oswego.edu/pipermail/concurrency-interest/2014-May/012652.html
>
>     I am using a ConcurrentHashMap.compute operation in an outer
>     Stream.parallel forEach operation. A library used in the compute method
>     also uses Stream.parallel.
>
>     I have written a test that illustrates the issue and explores different
>     implementations in 215 lines of code.
>     https://gist.github.com/dstuebe/89361f64dc44a935e53d0a49f149317c#file-nestedparallel-java
>
>     The code deadlocks with the following stack trace:
>     https://gist.github.com/dstuebe/89361f64dc44a935e53d0a49f149317c#file-stacktrace-txt
>
>     I do not understand why line 87 (the compute block) appears to be called
>     recursively leading to deadlock when I use Stream.parallel for the outer
>     loop.
>
>     Best
>
>     David
>     -------------- next part --------------
>     An HTML attachment was scrubbed...
>     URL:
>     <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20180806/543a8fb9/attachment-0001.html>
>
>     ------------------------------
>
>     Message: 2
>     Date: Mon, 6 Aug 2018 10:31:55 -0400
>     From: Doug Lea <[hidden email] <mailto:[hidden email]>>
>     To: [hidden email]
>     <mailto:[hidden email]>
>     Subject: Re: [concurrency-interest] CHM.compute restrictions (was: no
>              subject)
>     Message-ID: <[hidden email]
>     <mailto:[hidden email]>>
>     Content-Type: text/plain; charset=utf-8
>
>     On 08/06/2018 10:10 AM, David Stuebe via Concurrency-interest wrote:
>      > Hey folks
>      >
>      > Attempted to post this last week while I was joining the list.
>
>     To reduce spam, non-member posts are silently dropped. Sorry.
>
>      >
>      > I am using a ConcurrentHashMap.compute operation in an outer
>      > Stream.parallel forEach operation. A library used in the compute
>     method
>      > also uses Stream.parallel.
>      >
>      > I have written a test that illustrates the issue and explores
>     different
>      > implementations in 215 lines of code.
>      >
>     https://gist.github.com/dstuebe/89361f64dc44a935e53d0a49f149317c#file-nestedparallel-java
>      >
>      > The code deadlocks with the following stack trace:
>      >
>     https://gist.github.com/dstuebe/89361f64dc44a935e53d0a49f149317c#file-stacktrace-txt
>      >
>      > I do not understand why line 87 (the compute block) appears to be
>     called
>      > recursively leading to deadlock when I use Stream.parallel for
>     the outer
>      > loop.
>
>     A recursive CHM.compute call appears to invoked while trying to
>     initialize the contents of an element in the same map, which is
>     disallowed in general, but sometimes works anyway. In most other cases,
>     CHM successfully detects this and throws an exception, but it cannot
>     catch all of them.
>
>     -Doug
>
>
>
>
>
>
>     ------------------------------
>
>     Subject: Digest Footer
>
>     _______________________________________________
>     Concurrency-interest mailing list
>     [hidden email]
>     <mailto:[hidden email]>
>     http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
>     ------------------------------
>
>     End of Concurrency-interest Digest, Vol 162, Issue 1
>     ****************************************************
>
>
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: CHM.compute restrictions

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list

Hi Peter, Doug

That is very interesting!

I am not sure I fully grok your explanation, but it did suggest changing the inner task pool to be a fixed thread pool rather than a forkjoin pool. This appears to alleviate the issue!

More experiments to follow.

David

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

Re: CHM.compute restrictions

JSR166 Concurrency mailing list
Looking at stack trace, it can be seen that this is indeed taking the place:

    at java.util.concurrent.ConcurrentHashMap.compute([hidden email])
    - waiting to lock <0x00000006cfb30b58> (a java.util.concurrent.ConcurrentHashMap$ReservationNode)
    at com.upserve.NestedParallel.lambda$streamParallelOuterTask$4(NestedParallel.java:87)
    at com.upserve.NestedParallel$$Lambda$6/354291670.accept(Unknown Source)
    at java.util.stream.ForEachOps$ForEachOp$OfLong.accept([hidden email])
    at java.util.Random$RandomLongsSpliterator.forEachRemaining([hidden email])
    at java.util.Spliterator$OfLong.forEachRemaining([hidden email])
    at java.util.stream.AbstractPipeline.copyInto([hidden email])
    at java.util.stream.ForEachOps$ForEachTask.compute([hidden email])
    at java.util.concurrent.CountedCompleter.exec([hidden email])
    at java.util.concurrent.ForkJoinTask.doExec([hidden email])
    at java.util.concurrent.ForkJoinPool.awaitJoin([hidden email])
    at java.util.concurrent.ForkJoinTask.doJoin([hidden email])
    at java.util.concurrent.ForkJoinTask.get([hidden email])
    at com.upserve.NestedParallel.streamParallelInnerTask(NestedParallel.java:172)
    at com.upserve.NestedParallel.lambda$biFunction$9(NestedParallel.java:147)
    at com.upserve.NestedParallel$$Lambda$12/1333040169.apply(Unknown Source)
    at java.util.concurrent.ConcurrentHashMap.compute([hidden email])

ForkJoinPool.awaitJoin - is a method that awaits for the task to complete while helping to execute other tasks so that the thread is not wasted. In above stack trace, the task executing awaitJoin is an inner task, while the task being executed by awaitJoin is an outer task.

To avoid that, outer and inner tasks should not share the same ForkJoinPool.

Regards, Peter

On 08/07/2018 05:32 PM, David Stuebe wrote:

Hi Peter, Doug

That is very interesting!

I am not sure I fully grok your explanation, but it did suggest changing the inner task pool to be a fixed thread pool rather than a forkjoin pool. This appears to alleviate the issue!

More experiments to follow.

David


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

Re: CHM.compute restrictions

JSR166 Concurrency mailing list


On 08/07/2018 06:12 PM, Peter Levart wrote:
> To avoid that, outer and inner tasks should not share the same
> ForkJoinPool.

But Stream(s) are currently not designed to work with anything else than
default ForkJoinPool.

Would it make sense to extend the Stream API with an overloaded method like:

Stream.parallel(ForkJoinPool) ?


Regards, Peter

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

Re: CHM.compute restrictions

JSR166 Concurrency mailing list
Shouldn't streams use the current FJP when executed inside one? As in,
if the current thread is a ForkJoinWorkerThread, it'll use that thread's
pool.

- Jonas

On 08/07/2018 06:19 PM, Peter Levart via Concurrency-interest wrote:

>
>
> On 08/07/2018 06:12 PM, Peter Levart wrote:
>> To avoid that, outer and inner tasks should not share the same
>> ForkJoinPool.
>
> But Stream(s) are currently not designed to work with anything else than
> default ForkJoinPool.
>
> Would it make sense to extend the Stream API with an overloaded method
> like:
>
> Stream.parallel(ForkJoinPool) ?
>
>
> Regards, Peter
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: CHM.compute restrictions

JSR166 Concurrency mailing list
They do - but there’s no contract enforcing that - that’s just an implementation trick and you should not rely on that

> On 07 Aug 2018, at 18:28, Jonas Konrad via Concurrency-interest <[hidden email]> wrote:
>
> Shouldn't streams use the current FJP when executed inside one? As in, if the current thread is a ForkJoinWorkerThread, it'll use that thread's pool.
>
> - Jonas
>
> On 08/07/2018 06:19 PM, Peter Levart via Concurrency-interest wrote:
>> On 08/07/2018 06:12 PM, Peter Levart wrote:
>>> To avoid that, outer and inner tasks should not share the same ForkJoinPool.
>> But Stream(s) are currently not designed to work with anything else than default ForkJoinPool.
>> Would it make sense to extend the Stream API with an overloaded method like:
>> Stream.parallel(ForkJoinPool) ?
>> Regards, Peter
>> _______________________________________________
>> Concurrency-interest mailing list
>> [hidden email]
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

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

Re: CHM.compute restrictions

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
On 08/07/2018 12:19 PM, Peter Levart via Concurrency-interest wrote:

> On 08/07/2018 06:12 PM, Peter Levart wrote:
>> To avoid that, outer and inner tasks should not share the same
>> ForkJoinPool.

This might happen to work. But the underlying issue is that the call to
CHM.compute causes a nested call to compute that may modify the same
map. This is is specifically disallowed for Map.compute,
See:
https://docs.oracle.com/javase/9/docs/api/java/util/Map.html#compute-K-java.util.function.BiFunction-

The spec says "should not" vs "must not" because there are special cases
in which it may be OK. And also cases in which it is trapped as an
exception. Which does not happen here because the logically nested call
occurs in another thread, which evades CHM checks. Some execution
schedules will encounter lockup, some won't.

A better fix to the program would be to not nest parallelism within the
compute method itself (forcing reservation), but instead in another
method that finally sets the entry with result of call. Possibly using
CHM.replace for atomicity.

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