Java似乎比C++更快地执行简单算法.为什么？

Question

介绍:

使用两个相同的mergesort算法,我测试了C++(使用Visual Studios C++ 2010 express)和Java(使用NetBeans 7.0)的执行速度.我推测C++执行至少会稍微快一点,但测试显示C++执行速度比Java执行慢4到10倍.我相信我已经为C++设置了所有速度优化,而且我发布的是发布而不是调试.为什么会出现这种速度差异？

码:

Java的:

public class PerformanceTest1
{
 /**
  * Sorts the array using a merge sort algorithm
  * @param array The array to be sorted
  * @return The sorted array
  */
 public static void sort(double[] array)
 {
      if(array.length > 1)
      {
           int centre;
           double[] left;
           double[] right;
           int arrayPointer = 0;
           int leftPointer = 0;
           int rightPointer = 0;

           centre = (int)Math.floor((array.length) / 2.0);

           left = new double[centre];
           right = new double[array.length - centre];

           System.arraycopy(array,0,left,0,left.length);
           System.arraycopy(array,centre,right,0,right.length);

           sort(left);
           sort(right);

           while((leftPointer < left.length) && (rightPointer < right.length))
           {
                if(left[leftPointer] <= right[rightPointer])
                {
                     array[arrayPointer] = left[leftPointer];
                     leftPointer += 1;
                }
                else
                {
                     array[arrayPointer] = right[rightPointer];
                     rightPointer += 1;
                }
                arrayPointer += 1;
           }
           if(leftPointer < left.length)
           {
                System.arraycopy(left,leftPointer,array,arrayPointer,array.length - arrayPointer);
           }
           else if(rightPointer < right.length)
           {
                System.arraycopy(right,rightPointer,array,arrayPointer,array.length - arrayPointer);
           }
      }
 }

 public static void main(String args[])
 {
      //Number of elements to sort
      int arraySize = 1000000;

      //Create the variables for timing
      double start;
      double end;
      double duration;

      //Build array
      double[] data = new double[arraySize];
      for(int i = 0;i < data.length;i += 1)
      {
           data[i] = Math.round(Math.random() * 10000);
      }

      //Run performance test
      start = System.nanoTime();
      sort(data);
      end = System.nanoTime();

      //Output performance results
      duration = (end - start) / 1E9;
      System.out.println("Duration: " + duration);
 }
}

C++:

#include <iostream>
#include <windows.h>
using namespace std;

//Mergesort
void sort1(double *data,int size)
{
if(size > 1)
{
    int centre;
    double *left;
    int leftSize;
    double *right;
    int rightSize;
    int dataPointer = 0;
    int leftPointer = 0;
    int rightPointer = 0;

    centre = (int)floor((size) / 2.0);
    leftSize = centre;
    left = new double[leftSize];
    for(int i = 0;i < leftSize;i += 1)
    {
        left[i] = data[i];
    }
    rightSize = size - leftSize;
    right = new double[rightSize];
    for(int i = leftSize;i < size;i += 1)
    {
        right[i - leftSize] = data[i];
    }

    sort1(left,leftSize);
    sort1(right,rightSize);

    while((leftPointer < leftSize) && (rightPointer < rightSize))
    {
        if(left[leftPointer] <= right[rightPointer])
        {
            data[dataPointer] = left[leftPointer];
            leftPointer += 1;
        }
        else
        {
            data[dataPointer] = right[rightPointer];
            rightPointer += 1;
        }
        dataPointer += 1;
    }
    if(leftPointer < leftSize)
    {
        for(int i = dataPointer;i < size;i += 1)
        {
            data[i] = left[leftPointer++];
        }
    }
    else if(rightPointer < rightSize)
    {
        for(int i = dataPointer;i < size;i += 1)
        {
            data[i] = right[rightPointer++];
        }
    }
            delete left;
            delete right;
}
}

void main()
{
//Number of elements to sort
int arraySize = 1000000;

//Create the variables for timing
LARGE_INTEGER start; //Starting time
LARGE_INTEGER end; //Ending time
LARGE_INTEGER freq; //Rate of time update
double duration; //end - start
QueryPerformanceFrequency(&freq); //Determinine the frequency of the performance counter (high precision system timer)

//Build array
double *temp2 = new double[arraySize];
QueryPerformanceCounter(&start);
srand((int)start.QuadPart);
for(int i = 0;i < arraySize;i += 1)
{
    double randVal = rand() % 10000;
    temp2[i] = randVal;
}

//Run performance test
QueryPerformanceCounter(&start);
sort1(temp2,arraySize);
QueryPerformanceCounter(&end);
    delete temp2;

//Output performance test results
duration = (double)(end.QuadPart - start.QuadPart) / (double)(freq.QuadPart);
cout << "Duration: " << duration << endl;

//Dramatic pause
system("pause");
}

观察:

对于10000个元素,C++执行大约是Java执行时间的4倍.对于100000个元素,比例约为7:1.对于10000000个元素,该比率约为10:1.超过10000000,Java执行完成,但C++执行停止,我必须手动终止进程.

Answer 1

我认为你运行程序的方式可能有误.当你在Visual C++ Express中点击F5时,程序在调试器下运行,它会慢很多.在其他版本的Visual C++ 2010中(例如我使用的Ultimate),尝试按CTRL + F5(即启动而不调试)或尝试运行可执行文件本身(在Express中),你会发现差异.

我在我的机器上运行你的程序只有一个修改(添加delete[] left; delete[] right;以消除内存泄漏;否则它会以32位模式耗尽内存!).我有一个i7 950.公平地说,我也将相同的数组传递给Java中的Arrays.sort()和C++中的std :: sort.我使用的数组大小为10,000,000.

以下是结果(以秒为单位的时间):

Java code:            7.13
Java Arrays.sort:     0.93

32 bits
C++ code:             3.57
C++ std::sort         0.81

64 bits
C++ code:             2.77
C++ std::sort         0.76

因此,C++代码要快得多,甚至标准库(在Java和C++中都经过高度调整)往往对C++有轻微的优势.

编辑:我刚刚在您的原始测试中意识到,您在调试模式下运行C++代码.你应该切换到发布模式并在调试器之外运行它(正如我在帖子中解释的那样)以获得公平的结果.

Answer 2

我没有专业地编程C++(甚至不专业:)但我注意到你在堆上分配一个double(double*temp2 = new double [arraySize];).与Java初始化相比,这是昂贵的,但更重要的是,它构成了内存泄漏,因为你永远不会删除它,这可以解释为什么你的C++实现停止,它基本上耗尽了内存.

Answer 3

首先,您是否尝试使用std::sort(或std::stable_sort通常是mergesort)来获得C++的基准性能？

我无法评论Java代码,但对于C++代码:

• 与Java不同,new在C++中需要手动干预来释放内存.每次递归都会泄漏记忆.我建议使用,std::vector因为它为你管理所有的内存,iterator, iterator构造函数甚至会做副本(可能比你的for循环更好地优化).这几乎可以肯定是您性能差异的原因.
• 您arraycopy在Java中使用但不使用std::copyC++中的库facility(),尽管如果您使用它也无关紧要vector.
• Nit:在你第一次需要它的时候,在同一行声明并初始化你的变量,而不是在函数的顶部.
• 如果您被允许使用标准库的一部分,则std::merge可以替换您的合并算法.

编辑:如果你真的使用说delete left;清理内存,这可能是你的问题.正确的语法是delete [] left;解除分配数组.