Databases
StackOverflow2013
Postsdbo
POJava sort via Comparator<T> spends majority of its time in compare(Object,Object)
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POJava sort via Comparator<T> spends majority of its time in compare(Object,Object)
    primarykey
    data
    text
    <p>I noticed something odd while doing profiling our code base. It seemed that sorting with a typed comparator (e.g. <code>Comparator&lt;MyClass&gt;</code>) always first called a method <code>Comparator&lt;MyClass&gt;.compare(Object,Object)</code> which then called the method <code>Comparator&lt;MyClass&gt;.compare(MyClass,MyClass)</code>. Furthermore, the vast majority of the time was spent in the <code>Comparator&lt;MyClass&gt;.compare(Object,Object)</code>. To explore further, I made a little test program:</p> <pre><code>public class Sandbox { public static void main(String argv[]) { for(int j=0; j&lt;100; j++) { int n = 10000; SortMe[] sortMes = new SortMe[n]; for (int i=0; i&lt;n; i++) { sortMes[i] = new SortMe(Math.random()); } Arrays.sort(sortMes, new SortMeComp()); System.out.println(Arrays.toString(sortMes)); } for(int j=0; j&lt;100; j++) { int n = 10000; SortMe[] sortMes = new SortMe[n]; for (int i=0; i&lt;n; i++) { sortMes[i] = new SortMe(Math.random()); } Arrays.sort(sortMes, new SortMeCompTypeless()); System.out.println(Arrays.toString(sortMes)); } } } </code></pre> <p>The typed Comparator:</p> <pre><code>public class SortMeComp implements Comparator&lt;SortMe&gt;{ public int compare(SortMe one, SortMe two) { if(one.getValue()&gt;two.getValue()) { return -1; } else if (one.getValue()&lt;two.getValue()) { return 1; } else { return 0; } } } </code></pre> <p>The untyped Comparator I made for comparison:</p> <pre><code>public class SortMeCompTypeless implements Comparator{ public int compare(Object oneObj, Object twoObj) { SortMe one = (SortMe) oneObj; SortMe two = (SortMe) twoObj; if(one.getValue()&gt;two.getValue()) { return -1; } else if (one.getValue()&lt;two.getValue()) { return 1; } else { return 0; } } } </code></pre> <p>Here are the results (from <a href="http://www.yourkit.com/" rel="nofollow">YourKit profiler</a>; let me know if you'd rather have a screenshot):</p> <pre><code>+----------------------------------------------------+-----------------+-----------------+--------------------+ | Name | Time (ms) | Own Time (ms) | Invocation Count | +----------------------------------------------------+-----------------+-----------------+--------------------+ | +---java.util.Arrays.sort(Object[], Comparator) | 23,604 100 % | 8,096 | 200 | | | | | | | | +---SortMeComp.compare(Object, Object) | 11,395 48 % | 7,430 | 12,352,936 | | | | | | | | | | +---SortMeComp.compare(SortMe, SortMe) | 3,965 17 % | 3,965 | 12,352,936 | | | | | | | | +---SortMeCompTypeless.compare(Object, Object) | 4,113 17 % | 4,113 | 12,354,388 | +----------------------------------------------------+-----------------+-----------------+--------------------+ </code></pre> <p>I ran the profile without filtering, and you see the recursive calls to mergeSort (which just make it hard to read), but nothing of interest.</p> <p>So what's going on here? Where is that method SortMeComp.compare(Object,Object) coming from? We figured it was something that Java creates internally for dealing with generics, but what could be taking so long? I would think the jvm would just treat a generic method like an "untyped"/Object method. As you can see, a simple cast is far quicker. Besides which, I would think this is exactly the kind of thing that would be JITed away even if the jvm needed to do upfront type stuff. What's going on here?</p> <p>By the way:</p> <pre><code>$ java -version java version "1.6.0_26" Java(TM) SE Runtime Environment (build 1.6.0_26-b03) Java HotSpot(TM) 64-Bit Server VM (build 20.1-b02, mixed mode) </code></pre> <p>Edit:</p> <p>In response to savinos answer, I tried simulating the extra method call with an 'untyped' Comparator that simply cast to a typed compare:</p> <pre><code>public class SortMeCompMethodCalls implements Comparator{ public int compare(Object oneObj, Object twoObj) { return compare((SortMe)oneObj, (SortMe)twoObj); } public int compare(SortMe one, SortMe two) { if(one.getValue()&gt;two.getValue()) { return -1; } else if (one.getValue()&lt;two.getValue()) { return 1; } else { return 0; } } } </code></pre> <p>Here are the results:</p> <pre><code>+---------------------------------------------------------+-----------------+-----------------+--------------------+ | Name | Time (ms) | Own Time (ms) | Invocation Count | +---------------------------------------------------------+-----------------+-----------------+--------------------+ | +---java.util.Arrays.sort(Object[], Comparator) | 31,044 100 % | 8,061 | 200 | | | | | | | | +---SortMeComp.compare(Object, Object) | 11,554 37 % | 7,617 | 12,354,392 | | | | | | | | | | +---SortMeComp.compare(SortMe, SortMe) | 3,936 13 % | 3,936 | 12,354,392 | | | | | | | | +---SortMeCompMethodCalls.compare(Object, Object) | 11,427 37 % | 7,613 | 12,352,146 | | | | | | | | +---SortMeCompMethodCalls.compare(SortMe, SortMe) | 3,814 12 % | 3,814 | 12,352,146 | +---------------------------------------------------------+-----------------+-----------------+--------------------+ </code></pre> <p>So it looks like savinos is right! The extra time is only the extra method call (plus a little for the cast). That seems crazy to me; you'd think that'd be JITed away? Ah well.</p> <p>I removed edit 2 and added it as an answer as it should've been originally.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USBryan Head
    1. USBryan Head
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POJava sort via Comparator<T> spends majority of its time in compare(Object,Object)
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POJava sort via Comparator<T> spends majority of its time in compare(Object,Object)
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POJava sort via Comparator<T> spends majority of its time in compare(Object,Object)
      1. This table or related slice is empty.
      1. VTUpMod
    1. COhmm i'm not familiar with yourkit but somehow the output seems to be messed up. If the toplevel is at 100%, it means the children have to be included in the parent's times. However, the times don't really add up. Could it be that the second one just jit'ed the code in a way so that those 11sec's for the 2nd sort are counted in sort() instead of compare?
      singulars
      1. POJava sort via Comparator<T> spends majority of its time in compare(Object,Object)
      1. USb.buchhold
    2. CO@b.buchhold: Much of the sort time is going to be spent in the mergeSort (doing actual array manipulation, the recursive calls, etc). If I turned filtering, you would see all this (and it would sum to 100%) but it's practically unreadable (especially because of the recursion). By default, yourkit tries to condense calls into java library methods.
      singulars
      1. POJava sort via Comparator<T> spends majority of its time in compare(Object,Object)
      1. USBryan Head
    3. COwhat are you using to calculate the results? benchmark? which program?
      singulars
      1. POJava sort via Comparator<T> spends majority of its time in compare(Object,Object)
      1. USDarthVader
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload