[concurrency-interest] Strange behaviour when sorting anuniform array

David Holmes davidcholmes at aapt.net.au
Tue May 25 04:45:26 EDT 2010


I'm sure Doug will respond once his timezone is awake :) but some sorting
algorithms exhibit their worst performance when given already sorted data.

David Holmes
  -----Original Message-----
  From: concurrency-interest-bounces at cs.oswego.edu
[mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf Of Lukas Krecan
  Sent: Tuesday, 25 May 2010 6:15 PM
  To: concurrency-interest at cs.oswego.edu
  Subject: Re: [concurrency-interest] Strange behaviour when sorting
anuniform array


  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> 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
      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


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20100525/2d41b841/attachment-0001.html>


More information about the Concurrency-interest mailing list