[concurrency-interest] Single-threaded ForkJoinPool

cowwoc cowwoc at bbs.darktech.org
Mon Feb 8 02:13:51 EST 2016


Peter,

This is an excellent idea! Whoever came up with it was pretty clever :)

I still need to iron out some other aspects of deterministic behavior 
(e.g. making sure items are added to collections in the same order) but 
this is a huge step in the right direction. Thank you!

Gili

On 2016-02-06 12:58 PM, Peter Levart [via JSR166 Concurrency] wrote:
>
>
> On 02/06/2016 12:54 PM, cowwoc wrote:
>> Hi Peter,
>>
>> I'm not sure I understand. Won't I end up with different random 
>> numbers depending on runtime conditions?
>
> No. The initial seed for the root SplittableRandom instance will 
> determine the sequences for all its descendants.
>
> SplittableRandom r1 = new SplittableRandom(1234);
> SplittableRandom r2 = r1.split();
>
> ...is conceptually equivalent to:
>
> Random r1 = new Random(1234);
> Random r2 = new Random(r1.nextLong());
>
>
> Consider the following arrangement:
>
> Task1:
> Random r1 = new Random(1234);
> int i11 = r1.nextInt();
> int i12 = r1.nextInt();
> Random r2 = new Random(r1.nextLong());
> Random r3 = new Random(r1.nextLong());
>
> Task2:
> int i21 = r2.nextInt();
> int i22 = r2.nextInt();
>
> Task3:
> int i31 = r3.nextInt();
> int i32 = r3.nextInt();
>
> It doesn't matter when Task2 and Task3 are executed and by which 
> thread (as long as they are executed after Task1 which creates the r2 
> & r3 instances for them). Each task is using it's own private PRNG 
> instance. If you can make the algorithm within the single task 
> deterministic, the whole composition will be deterministic.
>
>
>> I mean, it sounds as if SplittableRandom is only deterministic if 
>> threads invoke split() in the same order across JVM runs. What 
>> happens if task1 runs faster than task2 in one run, but the opposite 
>> is true in another run? Won't I end up with numbers?
>
> If each task is using its own private instance of PRNG, then other 
> tasks can't have any effect on it, so it doesn't matter when or by 
> which thread they are executed.
>
> Regards, Peter
>
>>
>> Thanks,
>> Gili
>>
>> On 2016-02-06 3:43 AM, Peter Levart [via JSR166 Concurrency] wrote:
>>> Hi Gili,
>>>
>>> Have you thought of using SplittableRandom instead? Initially you 
>>> create it with a predefined seed for the root task. Whenever you 
>>> fork-off a task, you create for it a new instance by invoking 
>>> SplittableRandom.split(). This should give you deterministic 
>>> behavior regardless of how many threads you use for fork-join pool 
>>> and the dynamics of execution. For example:
>>>
>>> public class SumRandomInts extends RecursiveTask<Long> {
>>>     final SplittableRandom rnd;
>>>     final int count;
>>>
>>>     public SumRandomInts(int count, SplittableRandom rnd) {
>>>         this.rnd = rnd;
>>>         this.count = count;
>>>     }
>>>
>>>     @Override
>>>     protected Long compute() {
>>>         if (count < 1000) {
>>>             long sum = 0L;
>>>             for (int i = 0; i < count; i++) {
>>>                 sum += rnd.nextInt();
>>>             }
>>>             return sum;
>>>         } else {
>>>             SumRandomInts t1 = new SumRandomInts(count / 2, 
>>> rnd.split());
>>>             SumRandomInts t2 = new SumRandomInts(count - count / 2, 
>>> rnd.split());
>>>             t1.fork();
>>>             return t2.compute() + t1.join();
>>>         }
>>>     }
>>>
>>>     public static void main(String[] args) throws Exception {
>>>         long result = ForkJoinPool.commonPool().submit(
>>>             new SumRandomInts(100000, new 
>>> SplittableRandom(12345L))).get();
>>>         System.out.println(result);
>>>     }
>>> }
>>>
>>>
>>> Regards, Peter
>>>
>>> On 02/06/2016 04:18 AM, cowwoc wrote:
>>>> Hi,
>>>>
>>>> Is this the correct mailing list for discussing ForkJoinPool in JDK9? If
>>>> not, please point me to the right place.
>>>>
>>>> I have a feature request for ForkJoinPool which doesn't seem to be possible
>>>> to implement without a JDK change:http://stackoverflow.com/q/34012134/14731
>>>>
>>>> Specifically, I need to be able to an application that uses Random and
>>>> ForkJoinPool in a deterministic manner when debugging/profiling but run
>>>> full-speed in normal execution mode. I have all the moving parts nailing
>>>> down except for ForkJoinPool.
>>>>
>>>> If I create ForkJoinPool with a parallelism of 1, sometimes I see two worker
>>>> threads getting used. I am guessing that this is caused by
>>>> ForkJoinTask.get() invoking ForkJoinPool.common.externalHelpComplete(), but
>>>> maybe something else is going on.
>>>>
>>>> Is there a way for me to guarantee that ForkJoinThread will use exactly 1
>>>> worker thread, no less, no more? Would you like me to file a formal feature
>>>> request?
>>>>
>>>> Thank you,
>>>> Gili
>>>>
>>>>
>>>>
>>>> --
>>>> View this message in context:http://jsr166-concurrency.10961.n7.nabble.com/Single-threaded-ForkJoinPool-tp13232.html
>>>> Sent from the JSR166 Concurrency mailing list archive at Nabble.com.
>>>> _______________________________________________
>>>> Concurrency-interest mailing list
>>>> [hidden email] </user/SendEmail.jtp?type=node&node=13233&i=0>
>>>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>>
>>>
>>> _______________________________________________
>>> Concurrency-interest mailing list
>>> [hidden email] </user/SendEmail.jtp?type=node&node=13233&i=1>
>>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>>
>>>
>>> ------------------------------------------------------------------------
>>> If you reply to this email, your message will be added to the 
>>> discussion below:
>>> http://jsr166-concurrency.10961.n7.nabble.com/Single-threaded-ForkJoinPool-tp13232p13233.html 
>>>
>>> To unsubscribe from Single-threaded ForkJoinPool, click here.
>>> NAML 
>>> <http://jsr166-concurrency.10961.n7.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml> 
>>>
>>
>>
>> ------------------------------------------------------------------------
>> View this message in context: Re: Single-threaded ForkJoinPool 
>> <http://jsr166-concurrency.10961.n7.nabble.com/Single-threaded-ForkJoinPool-tp13232p13235.html>
>> Sent from the JSR166 Concurrency mailing list archive 
>> <http://jsr166-concurrency.10961.n7.nabble.com/> at Nabble.com.
>>
>>
>> _______________________________________________
>> Concurrency-interest mailing list
>> [hidden email] </user/SendEmail.jtp?type=node&node=13240&i=0>
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email] </user/SendEmail.jtp?type=node&node=13240&i=1>
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
> ------------------------------------------------------------------------
> If you reply to this email, your message will be added to the 
> discussion below:
> http://jsr166-concurrency.10961.n7.nabble.com/Single-threaded-ForkJoinPool-tp13232p13240.html 
>
> To unsubscribe from Single-threaded ForkJoinPool, click here 
> <http://jsr166-concurrency.10961.n7.nabble.com/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=13232&code=Y293d29jQGJicy5kYXJrdGVjaC5vcmd8MTMyMzJ8MTU3NDMyMTI0Nw==>.
> NAML 
> <http://jsr166-concurrency.10961.n7.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml> 
>





--
View this message in context: http://jsr166-concurrency.10961.n7.nabble.com/Single-threaded-ForkJoinPool-tp13232p13249.html
Sent from the JSR166 Concurrency mailing list archive at Nabble.com.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20160208/ec82b3f9/attachment.html>


More information about the Concurrency-interest mailing list