title: Java sort via Comparator<T> spends majority of its time in compare(Object,Object)
body: <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>