[concurrency-interest] Strange behaviour when sorting an uniform array

Lukas Krecan lukas.krecan at gmail.com
Tue May 25 10:24:42 EDT 2010


Thanks for your comment. I did not want to claim that I have done a 
benchmark. I just wanted to illustrate that non-parallel implementation 
does not exhibit the n*n behaviour. That's all.

On 05/25/2010 04:05 PM, Michael Spiegel wrote:
> I think the benchmark would benefit from a warmup phase.  It would
> ensure the methods in question are JIT compiled. Stackoverflow has a
> reasonable set of links on how to write a Java microbenchmark:
> http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java.
>
> --Michael
>
> On Tue, May 25, 2010 at 7:00 AM, Lukas Krecan<lukas.krecan at gmail.com>  wrote:
>    
>> Sure, the synchronized statement is just a leftover from previous
>> experiments.
>>
>> I have tried the same test with standard java.util.Arrays.sort and I am
>> getting
>>
>> 1) Uniform array (full of 1L) ~ 200ms
>> 2) rand.nextInt(20) ~ 1400ms
>> 3) rand.nextLong() ~ 7700ms
>>
>> The reason might be that a modified quicksort algorithm is used there. Would
>> it be possible to use the same algorithm for ParallelArray? I am afraid that
>> most programmers have already forgotten the details of sorting algorithms
>> and would be as surprised as I was.
>>       Cheers
>>            Lukas
>>
>> On 05/25/2010 11:44 AM, Kasper Nielsen wrote:
>>      
>>> Ahh, got it. You still want to remove that synchronized statement for
>>> serious usage though.
>>>
>>> What you are seing is the worst case behavior for quicksort which
>>> ParallelArray is using under the hood. All equal elements will kill most
>>> quicksort implementations. Instead of the average running time of n*logn you
>>> are seing worst case behaviour of n*n.
>>>
>>> Even large datasets with just a few different values will slow most
>>> implementations down significantly.
>>> I tried replacing
>>>   return 1L;//rand.nextLong();
>>> with
>>>   return rand.nextInt(20)
>>> and PA was still around 70 times slower compared to using rand.nextLong().
>>>
>>> We might want to switch to the dual pivot implementation introduced in
>>> OpenJDK 7. Don't know about licensing issues though.
>>>
>>> - Kasper
>>>
>>>
>>> On 25/5/2010 15:10, Lukas Krecan wrote:
>>>        
>>>> Hi,
>>>>     I am quite sure that it has nothing to do the synchronization. The
>>>> problem remains even if synchronized keyword is removed. Besides, the
>>>> method was used only for generating values, which works well. Problem is
>>>> with sorting. It works well on random values, but runs for ages on
>>>> uniform array.
>>>>
>>>>
>>>> On Tue, May 25, 2010 at 10:00 AM, Kasper Nielsen<kasper at kav.dk
>>>> <mailto:kasper at kav.dk>>  wrote:
>>>>
>>>>     Hi Lukas,
>>>>
>>>>     try removing the synchronized keyword in your op.
>>>>
>>>>     Taken from the extra166y.Ops javadoc:
>>>>
>>>>     In addition to stated signatures, implementations of these
>>>>     interfaces must work safely in parallel. In general, this means
>>>>     methods should operate only on their arguments, and should not rely
>>>>     on ThreadLocals, unsafely published globals, or other unsafe
>>>>     constructions. Additionally, they should not block waiting for
>>>>     synchronization.
>>>>
>>>>     If you want to return random numbers you should use the
>>>>     ThreadLocalRandom.
>>>>
>>>>
>>>>     - Kasper
>>>>
>>>>
>>>>     On 25/5/2010 07:9, Lukas Krecan wrote:
>>>>
>>>>         Hi,
>>>>             I have been playing with extra166y library and found that
>>>>         when I try
>>>>         to sort an uniform array (full of ones) it takes ages. With older
>>>>         version of the library it even threw StackOverflowError. After
>>>>         update it
>>>>         runs for minutes (I always kill the process after while so I do
>>>>         not know
>>>>         if it ends successfully).
>>>>
>>>>         Probably it's nothing new for you, maybe it's expected
>>>>         behaviour. But
>>>>         for me it's confusing and I just wanted to let you know about
>>>>         the issue
>>>>         in case you were not aware of it.
>>>>                Best regards
>>>>                  Lukas Krecan
>>>>
>>>>         -------------------------------------
>>>>         package net.krecan.forkjoin;
>>>>
>>>>         import java.util.Random;
>>>>
>>>>         import jsr166y.ForkJoinPool;
>>>>         import extra166y.Ops;
>>>>         import extra166y.ParallelLongArray;
>>>>
>>>>
>>>>         public class SortTest {
>>>>              private static final int THREADS = 2;
>>>>              private static final int SIZE = 40000000;
>>>>
>>>>              public static void testSort()
>>>>              {
>>>>                  ForkJoinPool fjPool = new ForkJoinPool(THREADS);
>>>>                  ParallelLongArray pa =
>>>> ParallelLongArray.createEmpty(SIZE,
>>>>         fjPool);
>>>>                  createData(pa);
>>>>                  System.out.println("Sorting "+pa.summary());
>>>>                  long start = System.currentTimeMillis();
>>>>                  pa.sort();
>>>>                  System.out.println("Done in
>>>>         "+(System.currentTimeMillis()-start)+"ms.");
>>>>                  System.out.println(pa.summary());
>>>>
>>>>
>>>>              }
>>>>              private static void createData(ParallelLongArray pa) {
>>>>                  long start = System.currentTimeMillis();
>>>>                  System.out.println("Creating data using "+THREADS+"
>>>>         threads.");
>>>>                  pa.setLimit(SIZE);
>>>>                  final Random rand = new Random();
>>>>                  pa.replaceWithGeneratedValue(new Ops.LongGenerator(){
>>>>                      public synchronized long op() {
>>>>                          return 1L;//rand.nextLong();
>>>>                      }
>>>>                  });
>>>>                  System.out.println("Done in
>>>>         "+(System.currentTimeMillis()-start)+"ms.");
>>>>              }
>>>>
>>>>              public static void main(String[] args) {
>>>>                  testSort();
>>>>              }
>>>>
>>>>         }
>>>>
>>>>
>>>>
>>>>         _______________________________________________
>>>>         Concurrency-interest mailing list
>>>>         Concurrency-interest at cs.oswego.edu
>>>> <mailto:Concurrency-interest at cs.oswego.edu>
>>>>         http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>>>
>>>>
>>>>     _______________________________________________
>>>>     Concurrency-interest mailing list
>>>>     Concurrency-interest at cs.oswego.edu
>>>> <mailto:Concurrency-interest at cs.oswego.edu>
>>>>     http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>>>
>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> Concurrency-interest mailing list
>>>> Concurrency-interest at cs.oswego.edu
>>>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>>>          
>>> _______________________________________________
>>> Concurrency-interest mailing list
>>> Concurrency-interest at cs.oswego.edu
>>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>>        
>> _______________________________________________
>> Concurrency-interest mailing list
>> Concurrency-interest at cs.oswego.edu
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>
>>      
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>    



More information about the Concurrency-interest mailing list