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 Thu, 27 Dec 2007 15:22:25 GMT
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..

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
View raw message