title: Java beats C++ on recursive algorithm speed comparison on my simple test
body: <p>With this divide and conquer algorithm (Programming Pearls p80) to find the max sum found in any contiguous subvector of an array, the Java program is faster than the C++ counterpart tested on Win7 x64 with 8GB of RAM.</p>
  
  <p>Both of Java and C++ runs on 1 CPU core.</p>
  
  <p>What kind of optimization is done on the JVM to make this possible?</p>
  
  <p>JVM 1 used:</p>
  
  <p>Java version "1.6.0_21"<br>
  Java(TM) SE Runtime Environment (build 1.6.0_21-b07)<br>
  Java HotSpot(TM) 64-Bit Server VM (build 17.0-b17, mixed mode) <br>
  VM Argument -Xmx12000m</p>
  
  <p>JVM 2 used:
  jrockit-jdk1.6.0_24-R28.1.3-4.0.1 <br>
  VM argument -Xmx12000m</p>
  
  <p>C++ compiler:</p>
  
  <p>Default Microsoft compiler that comes with Visual Studio 2008 x64</p>
  
  <p>Times:        </p>
  
  <pre><code> //Java JVM 1, Oracle JRE
   //0x1fffffff: about 38s, sum 144115187270549505
   //0x2fffffff: about 56s, sum 324259171962716161
   //0x3fffffff: about 81s, sum 576460750692810753
  
   //Java JVM 2, Oracle JRockit jrockit-jdk1.6.0_24-R28.1.3-4.0.1
   //0x1fffffff: about 46s
   //0x2fffffff: about 69s
   //0x3fffffff: about 95s     
  
   //Cpp
   //0x1fffffff: around 45s, x64 Release
   //0x2fffffff: around 68s, x64 Release sum: 324259171962716161
   //0x3fffffff: around 93s, x64 Release sum: 576460750692810753, 
  </code></pre>
  
  
  
  <pre class="lang-java prettyprint-override"><code>final int MAX = 0x3fffffff; 
  Pearls1 pearls1 = new Pearls1();
  pearls1.arr = new int[MAX];
  for (int i = 0; i &lt; MAX; i++)
  {
      pearls1.arr[(int) i] = i;                
  }
  long startTime = System.nanoTime();
  long sum = pearls1.binaryForce(0, MAX - 1);
  long endTime = System.nanoTime();
  
  long binaryForce(long lower, long upper) {
      //std::cout &lt;&lt; "binaryForce("&lt;&lt; lower &lt;&lt; ","&lt;&lt; upper &lt;&lt;")" &lt;&lt; std::endl;
  
      if( lower &gt; upper ) {
          return 0;
      } 
      if( lower == upper ) {      
          return Math.max( 0L, arr[(int) lower] ) ;       
      }
  
      long middle = ( lower + upper ) /2 ;
  
      long lmax = 0,  sum = 0;
  
      for( long i = middle; i &gt;=lower; i-- ) {
          sum += arr[(int) i];        
          lmax = Math.max( lmax, sum);
      }
  
      long rmax = 0;
      sum = 0;
  
      //for( long i = middle+1; i &lt;= upper; i++ ) {
      for( long i = upper; i &gt; middle; i-- ) {
          sum += arr[(int) i];
          rmax = Math.max(rmax, sum);     
      }
  
      long theMax = lmax+rmax;
  
      long binarySumLeft = binaryForce(lower, middle);
      long binarySumRight = binaryForce(middle+1, upper);
  
      if( theMax &gt; binarySumLeft &amp;&amp; theMax &gt; binarySumRight ) {
          return theMax;
      }
      else if( binarySumLeft &gt; theMax &amp;&amp; binarySumLeft &gt; binarySumRight ) {
          return binarySumLeft;
      }
      else if ( binarySumRight &gt; theMax &amp;&amp; binarySumRight &gt; binarySumLeft ) {
          return binarySumRight;
      }
  
      else {
          return theMax;      
      }
  
  }
  </code></pre>
  
  
  
  <pre class="lang-c prettyprint-override"><code> int main(...) {
      MAX = 0x3fffffff;
      arr = new long[MAX];
      for( long i=0;i&lt;MAX;i++) {
          //arr[i] = rand();
          arr[i] = i;
      }
  
      timeb startTime, endTime;
      ftime( &amp;startTime);
      std::cout &lt;&lt; "Start time: " &lt;&lt; startTime.time &lt;&lt; " sec, " &lt;&lt; startTime.millitm &lt;&lt; " ms" &lt;&lt; std::endl;
  
      sum = binaryForce(0, MAX-1);
      std::cout &lt;&lt; "sum: " &lt;&lt; sum &lt;&lt;std::endl;
      ftime( &amp;endTime);
      std::cout &lt;&lt; "End time: " &lt;&lt; endTime.time &lt;&lt; " sec, " &lt;&lt; endTime.millitm &lt;&lt; " ms" &lt;&lt; std::endl;
  
      long runTimeSec = endTime.time - startTime.time;
      long runTimeMs = endTime.millitm - startTime.millitm;
  
      std::cout &lt;&lt; "Run time: " &lt;&lt; runTimeSec &lt;&lt; " sec, " &lt;&lt; runTimeMs &lt;&lt; " ms" &lt;&lt; std::endl;
   }
  
  long long binaryForce(long lower, long upper) {
      //std::cout &lt;&lt; "binaryForce("&lt;&lt; lower &lt;&lt; ","&lt;&lt; upper &lt;&lt;")" &lt;&lt; std::endl;
  
      if( lower &gt; upper ) {
          return 0;
      } 
      if( lower == upper ) {        
          return std::max( 0L, arr[lower] ) ;        
      }
  
      long middle = ( lower + upper ) /2 ;
  
      long long lmax = 0,  sum = 0;
  
      for( long i = middle; i &gt;=lower; i-- ) {
          sum += arr[i];        
          lmax = std::max( lmax, sum);
      }
  
      long long rmax = 0;
      sum = 0;
  
      //for( long i = middle+1; i &lt;= upper; i++ ) {
      for( long i = upper; i &gt; middle; i-- ) {
          sum += arr[i];
          rmax = std::max(rmax, sum);        
      }
  
      long long theMax = lmax+rmax;
  
      long long binarySumLeft = binaryForce(lower, middle);
      long long binarySumRight = binaryForce(middle+1, upper);
  
      if( theMax &gt; binarySumLeft &amp;&amp; theMax &gt; binarySumRight ) {
          //std::cout &lt;&lt; arr[theMax] &lt;&lt; std::endl;
          return theMax;
      }
      else if( binarySumLeft &gt; theMax &amp;&amp; binarySumLeft &gt; binarySumRight ) {
          //std::cout &lt;&lt; arr[binarySumLeft] &lt;&lt; std::endl;
          return binarySumLeft;
      }
      else if ( binarySumRight &gt; theMax &amp;&amp; binarySumRight &gt; binarySumLeft ) {
          //std::cout &lt;&lt; arr[binarySumRight] &lt;&lt; std::endl;
          return binarySumRight;
      }
  
      else {
          //std::cout &lt;&lt; arr[theMax] &lt;&lt; std::endl;
          return theMax;        
      }
  }
  </code></pre>