Java VM 1.6.0 Sorting Collections

Discussion in 'Java' started by petek1976, Jun 10, 2010.

  1. petek1976

    petek1976 Guest

    I have been having some trouble with the performance of Java. In my
    code I have narrowed it down to the sort:

    For instance:


    import java.util.*;
    public class SortTest
    {
    public static void main(String args[])
    {
    final int vecSize = 1000000;
    ArrayList<Double> vec = new ArrayList<Double>(vecSize);
    final int numItr = 10;
    ArrayList<Double> times = new ArrayList<Double>(numItr);
    for (int i=0; i<numItr; ++i)
    {
    for (int k=0; k<vecSize; ++k)
    {
    vec.add(k,Math.random());
    }
    long startTime = System.nanoTime();
    java.util.Collections.sort(vec);
    long endTime = System.nanoTime();
    times.add(i,(endTime-startTime)*1.e-9);
    vec = new ArrayList<Double>(vecSize);
    }
    double avg=0.0;
    for (Double val:times)
    {
    avg += val;
    }
    avg /= times.size();
    System.out.println("To sort " + vec.size() + " elements " +
    numItr + " times took " + avg + " seconds on average");

    }
    }



    This prints about 0.58 seconds on average. How can I optimize this
    reasonably? Note I am only timing the sort function. Using an array
    instead of ArrayList is not an option. I tried Vector but it didn't
    help. The equivalent C++ code (using vector) runs in about 0.37
    seconds when built with optimization (g++ version 4.2.1 using -03
    optimization ). I am running on a MacBook Pro 2.66 GHz Intel Core i7
    with 4 GB of ram. I also tried this example on Linux and saw no
    difference. What is causing over 40% difference in speed? I must be
    doing something wrong in my java code.


    #include <iostream>
    #include <vector>
    #include <cstdlib>
    #include <algorithm>
    #include <sys/time.h>
    #include <numeric>
    using namespace std;

    template <class T>
    void FillRand(T start, T end)
    {
    while (start != end)
    {
    *start++ = double(rand())/RAND_MAX;
    }
    }

    class TimeStamp
    {
    public:
    void start()
    {
    gettimeofday(&st_val,0);
    }
    void stop()
    {
    gettimeofday(&end_val,0);
    }
    double elapsedSec() const
    {
    return end_val.tv_sec-st_val.tv_sec +
    (end_val.tv_usec-st_val.tv_usec)*1.e-6;
    }
    private:
    timeval st_val;
    timeval end_val;
    };

    int main()
    {
    vector<double> vec(1000000);
    const long num_itr = 10;
    vector<double> time_stamps(num_itr);
    TimeStamp ts;
    for (long i=0; i<num_itr; ++i)
    {
    FillRand(vec.begin(),vec.end());
    ts.start();
    std::sort(vec.begin(),vec.end());
    ts.stop();
    time_stamps = ts.elapsedSec();
    }
    double avg=std::accumulate(time_stamps.begin(),time_stamps.end(),
    0.0)/time_stamps.size();
    cout << "To sort " << vec.size() << " elements took " << avg << "
    seconds on average\n";
    }
     
    petek1976, Jun 10, 2010
    #1
    1. Advertising

  2. petek1976

    markspace Guest

    petek1976 wrote:

    > This prints about 0.58 seconds on average. How can I optimize this
    > reasonably? Note I am only timing the sort function. Using an array
    > instead of ArrayList is not an option.



    Unfortunately I think using an array of double is the only option. I
    didn't see anything obviously wrong with your code.

    I got about a 450% speed-up by switching to double[] instead of
    ArrayList<Double>. Why is using double[] proscribed? If it's the need
    for a List, you can roll your own.
     
    markspace, Jun 10, 2010
    #2
    1. Advertising

  3. petek1976

    Tom Anderson Guest

    On Wed, 9 Jun 2010, petek1976 wrote:

    > This prints about 0.58 seconds on average. How can I optimize this
    > reasonably?Note I am only timing the sort function. Using an array
    > instead of ArrayList is not an option. I tried Vector but it didn't
    > help. The equivalent C++ code (using vector) runs in about 0.37
    > seconds


    In terms of the java vs C++ comparison:

    1. Java's standard sort has to be stable, which means in practice it's a
    mergesort, whereas STL's doesn't, so it can be a quicksort. Quicksort will
    typically be faster than mergesort for random data.

    2. Java handles the doubles as objects on the heap here, whereas C++, i
    believe, will handle them as primitives (because it resolves templates at
    compile time, essentially, whereas java just erases types and uses the
    same code at runtime for all element types). Which means:

    (a) Java's data takes up more memory, and so requires more cache and
    memory bandwidth to work with (you have a million objects, so you're
    looking at 8 MB just for the raw numbers; the object overhead probably
    about quadruples that).

    (b) Java has to do comparisons by making virtual (worse - interface!)
    method calls, whereas C++ can just use a single machine instruction.
    Java's runtime compiler stands a good chance of optimising that overhead
    away; i have no idea if it will catch none, some, most, or all of it. You
    could try dumping the compiled code to see what HotSpot is up to:

    http://wikis.sun.com/display/HotSpotInternals/PrintAssembly

    If performance is vital but you want a List interface, than as Mark
    suggested, write a List<Double> implementation that wraps a double[]. You
    can then use Arrays.sort to sort the content - for doubles, this is a
    quicksort and uses direct comparisons, so it should be fast. AbstractList
    makes this rather easy to implement. You could also try this guy's
    DoubleArrayList:

    http://pcj.sourceforge.net/

    to which you could easily add internal sorting. It would be nice if there
    was such a class in the Apache or Google collections libraries, but there
    isn't.

    tom

    --
    I'm angry, but not Milk and Cheese angry. -- Mike Froggatt
     
    Tom Anderson, Jun 10, 2010
    #3
  4. petek1976

    Jim Janney Guest

    petek1976 <> writes:

    > I have been having some trouble with the performance of Java. In my
    > code I have narrowed it down to the sort:
    >
    > For instance:
    >
    >
    > import java.util.*;
    > public class SortTest
    > {
    > public static void main(String args[])
    > {
    > final int vecSize = 1000000;
    > ArrayList<Double> vec = new ArrayList<Double>(vecSize);
    > final int numItr = 10;
    > ArrayList<Double> times = new ArrayList<Double>(numItr);
    > for (int i=0; i<numItr; ++i)
    > {
    > for (int k=0; k<vecSize; ++k)
    > {
    > vec.add(k,Math.random());
    > }
    > long startTime = System.nanoTime();
    > java.util.Collections.sort(vec);
    > long endTime = System.nanoTime();
    > times.add(i,(endTime-startTime)*1.e-9);
    > vec = new ArrayList<Double>(vecSize);
    > }
    > double avg=0.0;
    > for (Double val:times)
    > {
    > avg += val;
    > }
    > avg /= times.size();
    > System.out.println("To sort " + vec.size() + " elements " +
    > numItr + " times took " + avg + " seconds on average");
    >
    > }
    > }
    >
    >
    >
    > This prints about 0.58 seconds on average. How can I optimize this
    > reasonably? Note I am only timing the sort function. Using an array
    > instead of ArrayList is not an option. I tried Vector but it didn't
    > help. The equivalent C++ code (using vector) runs in about 0.37
    > seconds when built with optimization (g++ version 4.2.1 using -03
    > optimization ). I am running on a MacBook Pro 2.66 GHz Intel Core i7
    > with 4 GB of ram. I also tried this example on Linux and saw no
    > difference. What is causing over 40% difference in speed? I must be
    > doing something wrong in my java code.
    >
    >
    > #include <iostream>
    > #include <vector>
    > #include <cstdlib>
    > #include <algorithm>
    > #include <sys/time.h>
    > #include <numeric>
    > using namespace std;
    >
    > template <class T>
    > void FillRand(T start, T end)
    > {
    > while (start != end)
    > {
    > *start++ = double(rand())/RAND_MAX;
    > }
    > }
    >
    > class TimeStamp
    > {
    > public:
    > void start()
    > {
    > gettimeofday(&st_val,0);
    > }
    > void stop()
    > {
    > gettimeofday(&end_val,0);
    > }
    > double elapsedSec() const
    > {
    > return end_val.tv_sec-st_val.tv_sec +
    > (end_val.tv_usec-st_val.tv_usec)*1.e-6;
    > }
    > private:
    > timeval st_val;
    > timeval end_val;
    > };
    >
    > int main()
    > {
    > vector<double> vec(1000000);
    > const long num_itr = 10;
    > vector<double> time_stamps(num_itr);
    > TimeStamp ts;
    > for (long i=0; i<num_itr; ++i)
    > {
    > FillRand(vec.begin(),vec.end());
    > ts.start();
    > std::sort(vec.begin(),vec.end());
    > ts.stop();
    > time_stamps = ts.elapsedSec();
    > }
    > double avg=std::accumulate(time_stamps.begin(),time_stamps.end(),
    > 0.0)/time_stamps.size();
    > cout << "To sort " << vec.size() << " elements took " << avg << "
    > seconds on average\n";
    > }


    Take a look at the source for Collections.sort:

    public static <T extends Comparable<? super T>> void sort(List<T> list) {
    Object[] a = list.toArray();
    Arrays.sort(a);
    ListIterator<T> i = list.listIterator();
    for (int j=0; j<a.length; j++) {
    i.next();
    i.set((T)a[j]);
    }
    }

    You're copying the list to an array, sorting the array, and then
    copying the array back to the list. You might try coding up a simple
    quicksort that operates directly on the ArrayList to see what kind of
    times that gives you.

    --
    Jim Janney
     
    Jim Janney, Jun 10, 2010
    #4
  5. petek1976

    Jim Janney Guest

    Jim Janney <> writes:

    > You're copying the list to an array, sorting the array, and then
    > copying the array back to the list. You might try coding up a simple
    > quicksort that operates directly on the ArrayList to see what kind of
    > times that gives you.


    The evil approach would be to use reflection to get the elementData
    field in ArrayList, and call Arrays.sort directly on that.

    --
    Jim Janney
     
    Jim Janney, Jun 10, 2010
    #5
  6. petek1976

    Lew Guest

    petek1976 wrote:
    > This prints about 0.58 seconds on average. How can I optimize this
    > reasonably? Note I am only timing the sort function. Using an array
    > instead of ArrayList is not an option. I tried Vector but it didn't
    >


    One would expect 'Vector' to be slightly slower than 'ArrayList'.

    > help. The equivalent C++ code (using vector) runs in about 0.37
    >


    Java programs typically run at 50-105% of the speed of optimized C++
    programs. What optimizations did you hand the JVM?

    One would expect that you at least specified "-server", yes?

    > seconds when built with optimization (g++ version 4.2.1 using -03
    > optimization ). I am running on a MacBook Pro 2.66 GHz Intel Core i7
    > with 4 GB of ram. I also tried this example on Linux and saw no
    > difference. What is causing over 40% difference in speed? I must be
    > doing something wrong in my java [sic] code.
    >


    HotSpot takes something like 10,000 visits to the same code to compile
    to native code. Other optimizations may or may not take that many
    iterations.

    Run your loop 100,000 times or so without timing it, then repeat it
    under timing. This should prime the optimizer.

    Microbenchmarks are deceptive and usually not indicative of real-world
    performance.

    --
    Lew
     
    Lew, Jun 10, 2010
    #6
  7. petek1976

    Tom Anderson Guest

    On Thu, 10 Jun 2010, Jim Janney wrote:

    > Jim Janney <> writes:
    >
    >> You're copying the list to an array, sorting the array, and then
    >> copying the array back to the list. You might try coding up a simple
    >> quicksort that operates directly on the ArrayList to see what kind of
    >> times that gives you.

    >
    > The evil approach would be to use reflection to get the elementData
    > field in ArrayList, and call Arrays.sort directly on that.


    Your ideas are intriguing to me, and i wish to subscribe to your
    newsletter.

    tom

    --
    They Set Up Us The Revolution - Now We Have Set Up It Them Back
     
    Tom Anderson, Jun 10, 2010
    #7
  8. petek1976

    Jim Janney Guest

    Lew <> writes:

    > petek1976 wrote:
    >> This prints about 0.58 seconds on average. How can I optimize this
    >> reasonably? Note I am only timing the sort function. Using an array
    >> instead of ArrayList is not an option. I tried Vector but it didn't
    >>

    >
    > One would expect 'Vector' to be slightly slower than 'ArrayList'.
    >
    >> help. The equivalent C++ code (using vector) runs in about 0.37
    >>

    >
    > Java programs typically run at 50-105% of the speed of optimized C++
    > programs. What optimizations did you hand the JVM?
    >
    > One would expect that you at least specified "-server", yes?
    >
    >> seconds when built with optimization (g++ version 4.2.1 using -03
    >> optimization ). I am running on a MacBook Pro 2.66 GHz Intel Core i7
    >> with 4 GB of ram. I also tried this example on Linux and saw no
    >> difference. What is causing over 40% difference in speed? I must be
    >> doing something wrong in my java [sic] code.
    >>

    >
    > HotSpot takes something like 10,000 visits to the same code to compile
    > to native code. Other optimizations may or may not take that many
    > iterations.
    >
    > Run your loop 100,000 times or so without timing it, then repeat it
    > under timing. This should prime the optimizer.
    >
    > Microbenchmarks are deceptive and usually not indicative of real-world
    > performance.


    Assuming n log(n) performance for the sorting algorithm, sorting a
    million-element list once gives you well over a million visits to the
    comparison code, and presumably to the inner loops of the sort.

    --
    Jim Janney
     
    Jim Janney, Jun 10, 2010
    #8
  9. petek1976

    Lew Guest

    Jim Janney wrote:
    > Assuming n log(n) performance for the sorting algorithm, sorting a
    > million-element list once gives you well over a million visits to the
    > comparison code, and presumably to the inner loops of the sort.
    >


    Good point, but if he doesn't have "-server" then it might not even do
    that optimization.

    --
    Lew
     
    Lew, Jun 10, 2010
    #9
  10. petek1976

    Jim Janney Guest

    Tom Anderson <> writes:

    > On Thu, 10 Jun 2010, Jim Janney wrote:
    >
    >> Jim Janney <> writes:
    >>
    >>> You're copying the list to an array, sorting the array, and then
    >>> copying the array back to the list. You might try coding up a simple
    >>> quicksort that operates directly on the ArrayList to see what kind of
    >>> times that gives you.

    >>
    >> The evil approach would be to use reflection to get the elementData
    >> field in ArrayList, and call Arrays.sort directly on that.

    >
    > Your ideas are intriguing to me, and i wish to subscribe to your
    > newsletter.
    >


    "Why you should buy what you hate"

    http://online.wsj.com/article/SB10001424052748704025304575285000265955016.html

    --
    Jim Janney
     
    Jim Janney, Jun 10, 2010
    #10
  11. petek1976

    Tom Anderson Guest

    On Thu, 10 Jun 2010, Jim Janney wrote:

    > Tom Anderson <> writes:
    >
    >> On Thu, 10 Jun 2010, Jim Janney wrote:
    >>
    >>> Jim Janney <> writes:
    >>>
    >>>> You're copying the list to an array, sorting the array, and then
    >>>> copying the array back to the list. You might try coding up a simple
    >>>> quicksort that operates directly on the ArrayList to see what kind of
    >>>> times that gives you.
    >>>
    >>> The evil approach would be to use reflection to get the elementData
    >>> field in ArrayList, and call Arrays.sort directly on that.

    >>
    >> Your ideas are intriguing to me, and i wish to subscribe to your
    >> newsletter.

    >
    > "Why you should buy what you hate"
    >
    > http://online.wsj.com/article/SB10001424052748704025304575285000265955016.html


    Waaay ahead of you. Most of my money's in (a) tobacco companies and (b)
    Russia.

    tom

    --
    All historians agree that George Washington's greatest regret was not
    being PERMANENTLY INVISIBLE.
     
    Tom Anderson, Jun 10, 2010
    #11
  12. petek1976

    Roedy Green Guest

    On Wed, 9 Jun 2010 21:00:08 -0700 (PDT), petek1976
    <> wrote, quoted or indirectly quoted
    someone who said :

    >Using an array
    >instead of ArrayList is not an option


    Why? You can always convert an ArrayList to an array and back again.
    It might not buy you anything, but code outside that would not even
    know about it.
    --
    Roedy Green Canadian Mind Products
    http://mindprod.com

    Have you ever noticed that any computer search in the movies, is always linear, with, for example, candidate fingerprints flashing up on the screen one after another? The public is still under the delusion that electronic files are microscopic filing cabinets made out of tiny wires or magnetic patches inside the computer. Most lay people are surprised that it is easy for a computer to file things simultaneously by a dozen different schemes, and that they can have any report printed in any number of different sorted orders. With physical files, they are limited to one ordering/access.
     
    Roedy Green, Jun 10, 2010
    #12
  13. petek1976

    Roedy Green Guest

    On Wed, 9 Jun 2010 21:00:08 -0700 (PDT), petek1976
    <> wrote, quoted or indirectly quoted
    someone who said :

    > final int vecSize = 1000000;
    > ArrayList<Double> vec = new ArrayList<Double>(vecSize);


    This is a fair hunk of RAM to carve out of the heap. You might want
    to do some experiments with the command line options that tune the
    heap. See http://mindprod.com/jgloss/javaexe.html

    --
    Roedy Green Canadian Mind Products
    http://mindprod.com

    Have you ever noticed that any computer search in the movies, is always linear, with, for example, candidate fingerprints flashing up on the screen one after another? The public is still under the delusion that electronic files are microscopic filing cabinets made out of tiny wires or magnetic patches inside the computer. Most lay people are surprised that it is easy for a computer to file things simultaneously by a dozen different schemes, and that they can have any report printed in any number of different sorted orders. With physical files, they are limited to one ordering/access.
     
    Roedy Green, Jun 10, 2010
    #13
  14. petek1976

    Roedy Green Guest

    On Wed, 9 Jun 2010 21:00:08 -0700 (PDT), petek1976
    <> wrote, quoted or indirectly quoted
    someone who said :

    > ArrayList<Double> vec = new ArrayList<Double>(vecSize);


    Arraylist of Double is HUGELY fatter than array of double because
    there is the object header overhead for every item in the ArrayList.

    The sort comparison routine with the ArrayList has to find the values
    to compare with extra indirection. That is mostly what consumes the
    cycles in a sort.
    --
    Roedy Green Canadian Mind Products
    http://mindprod.com

    Have you ever noticed that any computer search in the movies, is always linear, with, for example, candidate fingerprints flashing up on the screen one after another? The public is still under the delusion that electronic files are microscopic filing cabinets made out of tiny wires or magnetic patches inside the computer. Most lay people are surprised that it is easy for a computer to file things simultaneously by a dozen different schemes, and that they can have any report printed in any number of different sorted orders. With physical files, they are limited to one ordering/access.
     
    Roedy Green, Jun 10, 2010
    #14
  15. petek1976

    Tom Anderson Guest

    On Thu, 10 Jun 2010, Lew wrote:

    > Jim Janney wrote:
    >> Assuming n log(n) performance for the sorting algorithm, sorting a
    >> million-element list once gives you well over a million visits to the
    >> comparison code, and presumably to the inner loops of the sort.

    >
    > Good point, but if he doesn't have "-server" then it might not even do
    > that optimization.


    This document:

    http://java.sun.com/performance/reference/whitepapers/tuning.html

    is so old it's virtually scripture (last revised in 2005, for 1.5.0_06, i
    think), so i don't know how applicable it is to the OP's JVM, but it
    alleges that:

    Most computers that have at least 2 CPU's and at least 2 GB of physical
    memory are considered server-class machines which means that by default
    the settings are:

    * The -server compiler

    If 'CPUs' means 'cores', and the OP's machine is reasonably recent,
    there's a strong chance that -server is on already. Doesn't hurt to turn
    it on explicitly, of course. I know i do!

    tom

    --
    All historians agree that George Washington's greatest regret was not
    being PERMANENTLY INVISIBLE.
     
    Tom Anderson, Jun 10, 2010
    #15
  16. petek1976

    Roedy Green Guest

    On Thu, 10 Jun 2010 10:09:17 -0600, Jim Janney
    <> wrote, quoted or indirectly quoted
    someone who said :

    >You're copying the list to an array, sorting the array, and then
    >copying the array back to the list. You might try coding up a simple
    >quicksort that operates directly on the ArrayList to see what kind of
    >times that gives you.


    see http://mindprod.com/products.html#QUICKSORT for Java source.

    For a really fast sort, see
    http://mindprod.com/products.html#RADIXSORT

    which should do very with your short keys.

    --
    Roedy Green Canadian Mind Products
    http://mindprod.com

    Have you ever noticed that any computer search in the movies, is always linear, with, for example, candidate fingerprints flashing up on the screen one after another? The public is still under the delusion that electronic files are microscopic filing cabinets made out of tiny wires or magnetic patches inside the computer. Most lay people are surprised that it is easy for a computer to file things simultaneously by a dozen different schemes, and that they can have any report printed in any number of different sorted orders. With physical files, they are limited to one ordering/access.
     
    Roedy Green, Jun 10, 2010
    #16
  17. petek1976

    Roedy Green Guest

    On Thu, 10 Jun 2010 10:14:50 -0600, Jim Janney
    <> wrote, quoted or indirectly quoted
    someone who said :

    >The evil approach would be to use reflection to get the elementData
    >field in ArrayList, and call Arrays.sort directly on that.


    You are still using Doubles rather than doubles, so you won't get the
    full benefit of a true array.
    --
    Roedy Green Canadian Mind Products
    http://mindprod.com

    Have you ever noticed that any computer search in the movies, is always linear, with, for example, candidate fingerprints flashing up on the screen one after another? The public is still under the delusion that electronic files are microscopic filing cabinets made out of tiny wires or magnetic patches inside the computer. Most lay people are surprised that it is easy for a computer to file things simultaneously by a dozen different schemes, and that they can have any report printed in any number of different sorted orders. With physical files, they are limited to one ordering/access.
     
    Roedy Green, Jun 10, 2010
    #17
  18. petek1976

    Roedy Green Guest

    On Wed, 9 Jun 2010 21:00:08 -0700 (PDT), petek1976
    <> wrote, quoted or indirectly quoted
    someone who said :

    >I have been having some trouble with the performance of Java. In my
    >code I have narrowed it down to the sort:


    another optimisation is to use a native compiler. See
    http://mindprod.com/jgloss/jet.html
    http://mindprod.com/jgloss/nativecompiler.html
    --
    Roedy Green Canadian Mind Products
    http://mindprod.com

    Have you ever noticed that any computer search in the movies, is always linear, with, for example, candidate fingerprints flashing up on the screen one after another? The public is still under the delusion that electronic files are microscopic filing cabinets made out of tiny wires or magnetic patches inside the computer. Most lay people are surprised that it is easy for a computer to file things simultaneously by a dozen different schemes, and that they can have any report printed in any number of different sorted orders. With physical files, they are limited to one ordering/access.
     
    Roedy Green, Jun 10, 2010
    #18
  19. On 06/10/2010 07:57 AM, Tom Anderson wrote:
    > 1. Java's standard sort has to be stable, which means in practice it's a
    > mergesort, whereas STL's doesn't, so it can be a quicksort. Quicksort
    > will typically be faster than mergesort for random data.


    Arrays.sort() will use quicksort for integral types.

    --
    Beware of bugs in the above code; I have only proved it correct, not
    tried it. -- Donald E. Knuth
     
    Joshua Cranmer, Jun 10, 2010
    #19
  20. petek1976

    Lew Guest

    Roedy Green wrote:

    > another optimisation is to use a native compiler.


    Theoretically HotSpot will be a native compiler for this test, as was
    pointed out to me upthread.

    --
    Lew
     
    Lew, Jun 10, 2010
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Doug Poland
    Replies:
    9
    Views:
    763
    VisionSet
    Sep 27, 2003
  2. Joona I Palaste

    Trees in the Java Collections framework

    Joona I Palaste, Jun 8, 2004, in forum: Java
    Replies:
    5
    Views:
    574
    Chris Uppal
    Jun 9, 2004
  3. mikeotp
    Replies:
    2
    Views:
    380
    Ryan Stewart
    Dec 20, 2004
  4. alex_us01

    Collections.sort() in Java 5

    alex_us01, Oct 16, 2005, in forum: Java
    Replies:
    7
    Views:
    26,777
    Roedy Green
    Oct 16, 2005
  5. mutex
    Replies:
    0
    Views:
    230
    mutex
    Jul 27, 2003
Loading...

Share This Page