Mailing-List: contact dev-help@harmony.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@harmony.apache.org
Received-SPF: pass (athena.apache.org: domain of zhanghuangzhu@gmail.com
 designates 64.233.166.182 as permitted sender)
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=gamma;
        h=message-id:date:from:to:subject:in-reply-to:mime-version:content-type:references;
        b=nwlb5r9za8Deb3sB2mtxuPjwIdH7N2DMcRBljiy0gZ4Hx7zcPzjQXd0+IAJW7HeQbiw0K4SkuzVCsuMnmNNGX/Ld6oAt1ZG6GlKPTby6rvLIAnmlfJq2dp1KCdpD17TcEdN/BdepA9ClZo2i0FnVw63LmK8BjZBgymbjmlyzfWc=
Message-ID: <4d0b24970801082006k35fc9558vcf57e23a4fe1af22@mail.gmail.com>
Date: Wed, 9 Jan 2008 12:06:54 +0800
From: "Andrew Zhang" <zhanghuangzhu@gmail.com>
To: dev@harmony.apache.org
Subject: Re: [performance] quick sort is 4x slower on Harmony
In-Reply-To: <0vqsl18m5a6.fsf@gmail.com>
MIME-Version: 1.0
Content-Type: multipart/alternative;
	boundary="----=_Part_1499_16894859.1199851614486"
References: <4d0b24970712220935q7fd98a08oc3f6220628dbb688@mail.gmail.com>
	 <3b3f27c60712231544t34e3b176i8b8796e03dddb57b@mail.gmail.com>
	 <4d0b24970712232036m3e142c6fvaf2c62a5e81e182d@mail.gmail.com>
	 <0vqabo0o9dl.fsf@gmail.com>
	 <4d0b24970712270309i1e24cb5fg40a30554a72f82f6@mail.gmail.com>
	 <0vq63yknowe.fsf@gmail.com>
	 <469bff730712272314y6699967dw7091c992ff44a4c@mail.gmail.com>
	 <469bff730712290251l279b897etfbc5e32620b2efa8@mail.gmail.com>
	 <0vqsl18m5a6.fsf@gmail.com>

------=_Part_1499_16894859.1199851614486
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

On 08 Jan 2008 23:27:45 +0300, Egor Pasko <egor.pasko@gmail.com> wrote:

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


Hi Egor,

I use M4 release. Are you using the latest code? maybe some major
enhancement after M4?

btw, the number of RI (*5789ms*) is very similar as my machine. Thanks!


>

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


-- 
Best regards,
Andrew Zhang

db4o - database for Android: www.db4o.com
http://zhanghuangzhu.blogspot.com/

------=_Part_1499_16894859.1199851614486--