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 Sat, 29 Dec 2007 10:51:38 GMT
Results on Linux (2x2.67GHz CPU):

Java HotSpot(TM) Server VM (build 1.6.0-b105, mixed mode): *5789ms*
DRLVM, svn = r607183, (Dec 28 2007), Linux/ia32/gcc 3.3.3, release build
(-Xem:server mode): *4231ms*

What's wrong with my system? :)

Running this test the warm up phase on Harmony DRLVM is indeed very slow.
But, once all code is compiled, on my system DRLVM is faster than RI on this
test.

Thanks,
Pavel

On 12/28/07, Pavel Ozhdikhin <pavel.ozhdikhin@gmail.com> wrote:
>
>
>
>  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