Java beats C++ on recursive algorithm speed comparison on my simple test

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.

Both of Java and C++ runs on 1 CPU core.

What kind of optimization is done on the JVM to make this possible?

JVM 1 used:

Java version "1.6.0_21"

Java(TM) SE Runtime Environment (build 1.6.0_21-b07)

Java HotSpot(TM) 64-Bit Server VM (build 17.0-b17, mixed mode)

VM Argument -Xmx12000m

JVM 2 used: jrockit-jdk1.6.0_24-R28.1.3-4.0.1

VM argument -Xmx12000m

C++ compiler:

Default Microsoft compiler that comes with Visual Studio 2008 x64

Times:

 //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, 

final int MAX = 0x3fffffff; 
Pearls1 pearls1 = new Pearls1();
pearls1.arr = new int[MAX];
for (int i = 0; i < 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 << "binaryForce("<< lower << ","<< upper <<")" << std::endl;

    if( lower > 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 >=lower; i-- ) {
        sum += arr[(int) i];        
        lmax = Math.max( lmax, sum);
    }

    long rmax = 0;
    sum = 0;

    //for( long i = middle+1; i <= upper; i++ ) {
    for( long i = upper; i > 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 > binarySumLeft && theMax > binarySumRight ) {
        return theMax;
    }
    else if( binarySumLeft > theMax && binarySumLeft > binarySumRight ) {
        return binarySumLeft;
    }
    else if ( binarySumRight > theMax && binarySumRight > binarySumLeft ) {
        return binarySumRight;
    }

    else {
        return theMax;      
    }

}

 int main(...) {
    MAX = 0x3fffffff;
    arr = new long[MAX];
    for( long i=0;i<MAX;i++) {
        //arr[i] = rand();
        arr[i] = i;
    }

    timeb startTime, endTime;
    ftime( &startTime);
    std::cout << "Start time: " << startTime.time << " sec, " << startTime.millitm << " ms" << std::endl;

    sum = binaryForce(0, MAX-1);
    std::cout << "sum: " << sum <<std::endl;
    ftime( &endTime);
    std::cout << "End time: " << endTime.time << " sec, " << endTime.millitm << " ms" << std::endl;

    long runTimeSec = endTime.time - startTime.time;
    long runTimeMs = endTime.millitm - startTime.millitm;

    std::cout << "Run time: " << runTimeSec << " sec, " << runTimeMs << " ms" << std::endl;
 }

long long binaryForce(long lower, long upper) {
    //std::cout << "binaryForce("<< lower << ","<< upper <<")" << std::endl;

    if( lower > 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 >=lower; i-- ) {
        sum += arr[i];        
        lmax = std::max( lmax, sum);
    }

    long long rmax = 0;
    sum = 0;

    //for( long i = middle+1; i <= upper; i++ ) {
    for( long i = upper; i > 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 > binarySumLeft && theMax > binarySumRight ) {
        //std::cout << arr[theMax] << std::endl;
        return theMax;
    }
    else if( binarySumLeft > theMax && binarySumLeft > binarySumRight ) {
        //std::cout << arr[binarySumLeft] << std::endl;
        return binarySumLeft;
    }
    else if ( binarySumRight > theMax && binarySumRight > binarySumLeft ) {
        //std::cout << arr[binarySumRight] << std::endl;开发者_如何学编程
        return binarySumRight;
    }

    else {
        //std::cout << arr[theMax] << std::endl;
        return theMax;        
    }
}

---

Java uses a Just-in-Time compiler at runtime to compile the bytecode into the appropriate machine code for the architecture you're running on. As it runs, it collects execution metrics to examine what the code is doing; if it determines a more optimal mechanism that doesn't alter the results of the code, it will recompile the code that runs, which means it's optimized for the most-commonly-used paths.

C++ doesn't do this, as it's optimized using a series of static optimizations. Java can do those, but the JIT means that the optimizations can be aimed at the data you're using, too.

You're not saying which JVM you're using, either. Different JVMs have different characteristics. JRockit, for example, will actually optimize much better than the standard Oracle JVM will, although it also takes much longer to warm up.

---

I am guessing here but an int in C++ is represented as 32 bits (4 bytes) -- on a 64 bit system the kernel needs to perform 2 operations to access an int: 1/ read a WORD (64 bit) then 2/ apply an AND mask to reduce this to 32 bit. JVM as far as I know would probably store internally the int as a 64 bit but it's only at the point when you are reading this you will get the AND bitwise operator applied (i.e. sums/comparisons/etc will be done on 64 bit valued under the cover). Try to change the C++ code to use a WORD data structure (64 bit) or run the same on 32-bit processor.