On 27 Dec 2007 18:22:25 +0300, Egor Pasko <[EMAIL PROTECTED]> wrote:
>
> On the 0x3B9 day of Apache Harmony Andrew Zhang wrote:
> > On 24 Dec 2007 10:11:02 +0300, Egor Pasko <[EMAIL PROTECTED]> wrote:
> >
> > > On the 0x3B6 day of Apache Harmony Andrew Zhang wrote:
> > > > On Dec 24, 2007 7:44 AM, Nathan Beyer <[EMAIL PROTECTED]> 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 <, > ,
> 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 <[EMAIL PROTECTED]>
> > > 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
>
>
