harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Egor Pasko <egor.pa...@gmail.com>
Subject Re: [performance] quick sort is 4x slower on Harmony
Date Tue, 08 Jan 2008 20:27:45 GMT
On the 0x3BB day of Apache Harmony Pavel Ozhdikhin wrote:
> 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? :)

there was something wrong with mine :) Now I recompiled classlib in
release mode (Andrew, did you do that?) and experiencing Harmony 1.4x
slower.. still cannot get to your numbers.

I should also note that my laptop is far from the best tool to measure
performance since a lot of services is running on it..

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

-- 
Egor Pasko


Mime
View raw message