harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Andrew Zhang" <zhanghuang...@gmail.com>
Subject Re: [performance] quick sort is 4x slower on Harmony
Date Thu, 27 Dec 2007 11:09:56 GMT
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:

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/

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message