[concurrency-interest] jsr166y bug - NPE sorting a ParallelArray

Mark Mahieu mark at twistedbanana.demon.co.uk
Mon Dec 10 21:09:05 EST 2007


Hi,

Apologies if this is already known about, or if I should be sending  
this somewhere else (did look, couldn't see anywhere obvious).

I believe I've tripped over a bug calling ParallelArray.sort() - it  
only appears to work with arrays of certain lengths, and throws  
NullPointerExceptions for all other cases.  I'm using the current  
code from CVS.

It should be possible to reproduce this by altering the value of the  
variable 'n' at the start of main() in the SortDemo class, for  
example to 10, which for me results in something like the following:

Exception in thread "main" java.lang.NullPointerException
         at jsr166y.forkjoin.ParallelArray$FJComparableMerger.merge 
(ParallelArray.java:4275)
         at jsr166y.forkjoin.ParallelArray$FJComparableMerger.compute 
(ParallelArray.java:4256)
         at jsr166y.forkjoin.ParallelArray$FJComparableSorter.compute 
(ParallelArray.java:4136)
         at jsr166y.forkjoin.ParallelArray 
$FJComparableSubSorter.compute(ParallelArray.java:4200)
         at jsr166y.forkjoin.RecursiveAction.exec 
(RecursiveAction.java:226)
         at jsr166y.forkjoin.ForkJoinWorkerThread.run 
(ForkJoinWorkerThread.java:286)


I think the problem lies in the calculation of the size of the 2nd of  
the 4 'quarters' which FJSorter.compute() and  
FJComparableSorter.compute() attempt to divide a subarray into.  The  
following code is taken directly from ParallelArray, starting at line  
3913:

     (new FJSubSorter<T>
      (new FJSorter<T>(cmp, a, w, origin,   q,   g),
       new FJSorter<T>(cmp, a, w, origin+q, q,   g),
       new FJMerger<T>(cmp, a, w, origin,   q,
                       origin+q, q, origin, g)
       ),

The problem being that it is only works if the first and second  
quarters are equal in size, which will depend on the size of the  
array.  The code immediately following the above, which deals with  
the 3rd and 4th quarters, appears to do this correctly already.   
Changing the code (and its counterpart in FJComparableSorter.compute 
()) to the following certainly seems to fix the problem:

     (new FJSubSorter<T>
      (new FJSorter<T>(cmp, a, w, origin,   q,   g),
       new FJSorter<T>(cmp, a, w, origin+q, h-q,   g),
       new FJMerger<T>(cmp, a, w, origin,   q,
                       origin+q, h-q, origin, g)
       ),


(If it's of any interest, I ran into this whilst experimenting with  
Neal Gafter's port of jsr166y to use BGGA closures.)

Best regards,

Mark Mahieu



More information about the Concurrency-interest mailing list