Java ArrayList真的比C++向量慢吗？

Question

我不想开始另一个毫无意义的火焰战争,关于Java或C++是否是更好的语言.我想知道我为特定任务做的比较是否公平,测量数据是否正确.

我们需要决定是否将Java或C++用于我们的下一个项目.我在C++阵营,但我想为我的案子提供坚实的论据.我们的应用是特殊的,具有以下需求:

• 该程序必须运行得相当快,并且具有合理的内存效率.我们不关心最近20%的表现.然而,10倍的性能差异是一个显示停止.
• 我们有很多阵列.我们不知道他们的规模.因此,重要的是阵列可以在摊销的O(1)运行时间内在后面生长.
• 数组中的元素由少量基本数据类型组成.典型的例子是整数或浮点数的元组.
• 阵列可以变大.10 ^ 6个元素是标准的.我们有10 ^ 7个元素的应用程序,支持10 ^ 8会很棒.

我用C++和Java实现了一个玩具程序.首先,我介绍C++版本:

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

struct Point{
        float x, y;
};

int main(int argc, char*argv[]){
        int n = atoi(argv[1]);

        vector<Point>arr;

        for(int i=0; i<n; ++i){
                Point p;
                p.x = i;
                p.y = i+0.5f;
                arr.push_back(p);
        }

        float dotp = 0;
        for(int i=0; i<n; ++i)
                dotp += arr[i].x * arr[i].y;

        cout << dotp << endl;
}

接下来是执行相同操作的Java版本:

import java.util.*;

class Point{
        public float x, y;
}

class Main{
        static public void main(String[]args){
                int n = Integer.parseInt(args[0]);

                ArrayList<Point> arr = new ArrayList<Point>();

                for(int i=0; i<n; ++i){
                        Point p = new Point();
                        p.x = i;
                        p.y = i+0.5f;
                        arr.add(p);
                }

                float dotp = 0;
                for(int i=0; i<n; ++i)
                        dotp += arr.get(i).x * arr.get(i).y;

                System.out.println(dotp);
        }
}

我使用命令行将元素数传递给程序,以防止优化器在编译期间执行程序.计算出的值无用.唯一有趣的问题是程序的运行速度和使用的内存量.我从C++开始:

$ g++ --version
g++ (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4
$ g++ -O3 test.cpp -o test
$ /usr/bin/time ./test 1000000
3.33381e+17
0.01user 0.00system 0:00.02elapsed 100%CPU (0avgtext+0avgdata 10084maxresident)k
0inputs+0outputs (0major+2348minor)pagefaults 0swaps
$ /usr/bin/time ./test 10000000
3.36984e+20
0.08user 0.01system 0:00.09elapsed 100%CPU (0avgtext+0avgdata 134380maxresident)k
0inputs+0outputs (0major+4074minor)pagefaults 0swaps
$ /usr/bin/time ./test 100000000
2.42876e+23
0.77user 0.09system 0:00.87elapsed 99%CPU (0avgtext+0avgdata 1050400maxresident)k
0inputs+0outputs (0major+6540minor)pagefaults 0swaps

"用户"时间是程序运行的时间.对于10 ^ 6个元素,它运行0.01秒,10 ^ 7个元素0.08秒,以及10 ^ 8个元素0.77秒."maxresident"是内核为程序提供的以千字节为单位的物理内存量.10 ^ 6 10 MB,10 ^ 7 132 MB,10 ^ 8 1 GB.

内存消耗听起来不错.具有x个元素的数组需要sizeof(float)*2*x = 8*x字节的内存.对于大约8MB的10 ^ 6个元素,对于10 ^ 7个大约76MB,对于10 ^ 8大约762个MB.

接下来,我运行Java程序:

$ javac -version
javac 1.6.0_41
$ javac Main.java
$ java -version
java version "1.7.0_131"
OpenJDK Runtime Environment (IcedTea 2.6.9) (7u131-2.6.9-0ubuntu0.14.04.2)
OpenJDK 64-Bit Server VM (build 24.131-b00, mixed mode)
$ /usr/bin/time java Main 1000000
3.33381168E17
0.16user 0.00system 0:00.09elapsed 173%CPU (0avgtext+0avgdata 79828maxresident)k
0inputs+64outputs (0major+4314minor)pagefaults 0swaps
$ /usr/bin/time java Main 10000000
3.3698438E20
5.23user 0.18system 0:02.07elapsed 261%CPU (0avgtext+0avgdata 424180maxresident)k
0inputs+64outputs (0major+13508minor)pagefaults 0swaps
$ /usr/bin/time java Main 100000000
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at Main.main(Main.java:14)
Command exited with non-zero status 1
3840.72user 13.06system 17:11.79elapsed 373%CPU (0avgtext+0avgdata 2281416maxresident)k
0inputs+1408outputs (0major+139893minor)pagefaults 0swaps

对于10 ^ 6个元素,它需要0.16秒和78 MB.对于10 ^ 7个元素,它需要5.23秒和414 MB.我尝试为10 ^ 8个元素运行程序,但Java崩溃了.它使用了我机器的所有内核(在顺序程序中!)并运行了17分钟,同时占用了2.2GB.我的机器有8 GB的内存.

对于10 ^ 6个元素,C++是0.16/0.01 =快16倍,需要78/10 = 7.8倍的内存.对于10 ^ 7个元素,C++的速度为5.23/0.08 = 65倍,需要414/132 = 3.1倍的内存.Java没有在10 ^ 8个元素的测试实例上完成,而C++程序在远低于一秒的时间内完成.

对于10 ^ 6 Java似乎可管理但不太理想.对于10 ^ 7和10 ^ 8,它是绝对禁止的.我期望C++相对于Java有轻微的性能优势但不是这么大的优势.

最可能的解释是我的测试方法是错误的,或者我的Java代码中存在非明显的性能瓶颈.另一种解释是OpenJDK JVM明显缺乏来自其他供应商的JVM.

请向我解释为什么Java在这个基准测试中表现如此糟糕.我是如何无意中让Java看起来更糟糕的？

谢谢

Answer 1

因此，JIT 未运行可以解释一小部分影响，但不能解释主要的减速。

是的，由于 JIT，Java 在启动时很慢，并且需要一些时间才能全速运行。

但是你描述的表现是灾难性的，还有另一个原因：你写道

它使用了我机器的所有内核（在一个顺序程序中！）

这一定是垃圾收集器。GC 运行困难意味着您的内存不足。在我的机器上，时间是

  28.689 millis for 1 M pairs
 143.104 millis for 10 M pairs
3100.856 millis for 100 M pairs
  10.404 millis for 1 M pairs
 113.054 millis for 10 M pairs
2528.371 millis for 100 M pairs

这仍然是一种痛苦，但可能是一个可用的起点。观察到第二次运行速度更快，因为它得到了更好的优化。请注意，这不是 Java 基准测试的编写方式！

内存消耗的原因是您有一个List对包含两个浮点数而不是成对的浮点数的对象的引用vector。每个引用都会增加 4 或 8 个字节的开销，每个对象都会增加更多。此外，每次访问都有一个间接访问。

如果内存很重要，那么这不是在 Java 中编写代码的正确方法。肯定有更好的方法（我尝试过），但代码可能会变得丑陋。没有值类型的Java在这种计算上很糟糕。恕我直言，它几乎在其他任何地方都表现出色（个人意见）。

等效的 C++ 代码将使用vector<Point*>. 如果你这样做，你的代码会变慢，内存会变大，但仍然比 Java 好（对象头开销）。

我重写了代码，因此它使用PointArray将两个相邻的浮点数存储在一个数组中。没有测量任何东西，我声称内存消耗现在大致相同。现在的时代是

  31.505 millis for 1 M pairs
 232.658 millis for 10 M pairs
1870.664 millis for 100 M pairs
  17.536 millis for 1 M pairs
 219.222 millis for 10 M pairs
1757.475 millis for 100 M pairs

这仍然太慢了。我想，这是绑定检查，它不能在 Java 中关闭（除非您决定使用Unsafe）。通常，JIT（即时编译器）可以将它们移出循环，这使得它们的成本可以忽略不计。

这也可能是我的缓慢（因子 1.5）阵列调整大小（IIRCvector使用因子 2）。或者在您快完成时调整数组大小时只是遗憾。由于您对数组无所事事，因此它的权重可能很大。

无论如何，当您想要快速处理原语数组时，您至少需要一名优秀的 Java 程序员。他们可能需要一两天的时间才能获得良好的表现。一个好的图书馆也可以。List<Point>在 Java 10（或 11，或 ...）之前使用效率太低了。