harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Pavel Ozhdikhin" <pavel.ozhdik...@gmail.com>
Subject Re: [performance] quick sort is 4x slower on Harmony
Date Fri, 28 Dec 2007 07:14:10 GMT
On 27 Dec 2007 18:22:25 +0300, Egor Pasko <egor.pasko@gmail.com> wrote:
>
> On the 0x3B9 day of Apache Harmony Andrew Zhang wrote:
> > On 24 Dec 2007 10:11:02 +0300, Egor Pasko <egor.pasko@gmail.com> wrote:
> >
> > > On the 0x3B6 day of Apache Harmony Andrew Zhang wrote:
> > > > On Dec 24, 2007 7:44 AM, Nathan Beyer <nbeyer@gmail.com> wrote:
> > > >
> > > > > Can post the code that you're seeing this in? At least a
> > > > > representative example of the code would be needed to do any
> analysis.
> > > >
> > > >
> > > > Hi,
> > > >
> > > > You can find code here:
> > > >
> > >
> http://zhanghuangzhu.blogspot.com/2007/12/quicksort-runs-slower-on-harmony.html
> > >
> > > How to compile this?
> >
> >
> > Sorry, my mistake...
> >
> > I pasted the source code directly to the blog. I didn't use &lt, &gt ,
> so
> > "<...>" is gone.  Here's the code:
>
> hm, for me it is more that 4x :(
> details:
> 1. Harmony r605841 -Xem:server
> 2. RI build 1.5.0_11-b03
> 3. both on Linux
>
> to make it 3.5x I changed the test like this to let the code show itself
> as hot
>
> @@ -3,6 +3,15 @@
> public class GenericQuicksort {
>
>     public static void main(String[] args) {
> +        {
> +        int[] ints = new int[5000];
> +        for (int i = 0; i < ints.length; i++) {
> +            ints[i] = i + 1;
> +        }
> +        QuickSortableIntArray sample = new QuickSortableIntArray(ints);
> +        GenericQuicksort.qsort(sample);
> +        }
> +        {
>         int[] ints = new int[50000];
>         for (int i = 0; i < ints.length; i++) {
>             ints[i] = i + 1;
> @@ -12,6 +21,7 @@
>         GenericQuicksort.qsort(sample);
>         long end = System.currentTimeMillis();
>         System.out.println("elapsed: " + (end - begin) + "ms");
> +        }
>     }
>
>
> It helps, thus showing our old known recompilation problem is still
> there :) This problem is also damaging our SciMark score. Fixing it
> requires the on-stack-replacement feature from VM and JIT, which is
> very tricky, not implemented yet :)
>
>
> After this change Harmony is still 3.5x times slower. I suspect that
> the reason is: hot interface call to QuickSortable::swap is not
> devirtualized. Devirt told:
>
> ------------------------------------------------------------
> Devirtualizing interface/abstract call in the method :
> |___GenericQuicksort::swap(LQuickSortable;II)V
> call to the method:.
> |___QuickSortable::swap(II)V
> ------------------------------------------------------------
>
> but did not actually devirtualize, leaving the same IR as it was. Need
> to debug. Or maybe Pavel Ozhdikhin can fire up the reasons quickly..



Hmm, I've got different results on Windows :

Java HotSpot(TM) Client VM (build 1.6.0-b105, mixed mode): *4297ms *(even
slower on server VM)
DRLVM svn = r607175, (Dec 28 2007), Windows/ia32/msvc 1310, release,
-Xem:server mode: *4234ms*
and the test fails with NPE on JRockit 1.5 :)

Probably the probleem is specific to Linux. I'll check there a bit later.

Thanks,
Pavel


Andrew, please, try my change addressed on the recompilation issue and
> report how it works for you.
>
> > import java.util.*;
> >
> > public class GenericQuicksort {
> >
> >     public static void main(String[] args) {
> >         int[] ints = new int[50000];
> >         for (int i = 0; i < ints.length; i++) {
> >             ints[i] = i + 1;
> >         }
> >         QuickSortableIntArray sample = new QuickSortableIntArray(ints);
> >         long begin = System.currentTimeMillis();
> >         GenericQuicksort.qsort(sample);
> >         long end = System.currentTimeMillis();
> >         System.out.println("elapsed: " + (end - begin) + "ms");
> >     }
> >
> >     private static class Range {
> >         int _from;
> >         int _to;
> >
> >         public Range(int from, int to) {
> >             _from = from;
> >             _to = to;
> >         }
> >     }
> >
> >     public static void qsort(QuickSortable sortable) {
> >         LinkedList<Range> stack = new LinkedList<Range>();
> >         addRange(stack, 0, sortable.size() - 1);
> >         qsort(sortable, stack);
> >     }
> >
> >     private static void qsort(QuickSortable sortable, LinkedList<Range>
> > stack) {
> >         while (!stack.isEmpty()) {
> >             Range range = stack.removeFirst();
> >             int from = range._from;
> >             int to = range._to;
> >             int pivot = to;
> >             int left = from;
> >             int right = to;
> >             while (left < right) {
> >                 while (left < right && sortable.compare(left, pivot)
<
> 0) {
> >                     left++;
> >                 }
> >                 while (left < right && sortable.compare(right, pivot)
>=
> 0)
> > {
> >                     right--;
> >                 }
> >                 swap(sortable, left, right);
> >             }
> >             swap(sortable, to, right);
> >             addRange(stack, from, right - 1);
> >             addRange(stack, right + 1, to);
> >         }
> >     }
> >
> >     private static void addRange(LinkedList<Range> stack, int from, int
> to)
> > {
> >         if (to - from < 1) {
> >             return;
> >         }
> >         stack.addFirst(new Range(from, to));
> >     }
> >
> >     private static void swap(QuickSortable sortable, int left, int
> right) {
> >         if (left == right) {
> >             return;
> >         }
> >         sortable.swap(left, right);
> >     }
> >
> >     public static class QuickSortableIntArray implements QuickSortable {
> >
> >         private int[] ints;
> >
> >         public QuickSortableIntArray(int[] ints) {
> >             this.ints = ints;
> >         }
> >
> >         public int compare(int leftIndex, int rightIndex) {
> >             return ints[leftIndex] - ints[rightIndex];
> >         }
> >
> >         public int size() {
> >             return ints.length;
> >         }
> >
> >         public void swap(int leftIndex, int rightIndex) {
> >             int temp = ints[leftIndex];
> >             ints[leftIndex] = ints[rightIndex];
> >             ints[rightIndex] = temp;
> >         }
> >     }
> >
> > }
> >
> > public interface QuickSortable {
> >
> >     public int size();
> >
> >     public int compare(int leftIndex, int rightIndex);
> >
> >     public void swap(int leftIndex, int rightIndex);
> >
> > }
> >
> >
> >
> > >
> > > |shell> javac GenericQuicksort.java
> > > |GenericQuicksort.java:36: incompatible types
> > > |found   : java.lang.Object
> > > |required: GenericQuicksort.Range
> > > |Range range = stack.removeFirst();
> > > |                               ^
> > > |Note: GenericQuicksort.java uses unchecked or unsafe operations.
> > > |Note: Recompile with -Xlint:unchecked for details.
> > > |1 error
> > >
> > > P.S. I suspect this is a recompilation problem since Jitrino.JET
> > > generates very push-pop intensive code. Plz, check with -Xtrace:em (on
> > > debug build) that recomilation to Jitrino.OPT actually happened.
> > >
> > > >
> > > > >
> > > > > -Nathan
> > > > >
> > > > > On Dec 22, 2007 11:35 AM, Andrew Zhang <zhanghuangzhu@gmail.com>
> > > wrote:
> > > > > > Hi,
> > > > > >
> > > > > > I just found quick sort is very slow (4x) on Harmony compared
> with
> > > RI. I
> > > > > > didn't mean Arrays.sort method here, but a stack based
> > > implementation of
> > > > > > quick sort. The code has a lot of push/pop operation. Any idea?
> > > > > >
> > > > > > --
> > > > > > Best regards,
> > > > > > Andrew Zhang
> > > > > >
> > > > > > http://zhanghuangzhu.blogspot.com/
> > > > > >
> > > > >
> > > >
> > > >
> > > >
> > > > --
> > > > Best regards,
> > > > Andrew Zhang
> > > >
> > > > db4o - database for Android: www.db4o.com
> > > > http://zhanghuangzhu.blogspot.com/
> > >
> > > --
> > > Egor Pasko
> > >
> > >
> >
> >
> > --
> > Best regards,
> > Andrew Zhang
> >
> > db4o - database for Android: www.db4o.com
> > http://zhanghuangzhu.blogspot.com/
>
> --
> Egor Pasko
>
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message