这段Java代码怎样才能更快？

Question

我正在尝试基准测试Java执行简单任务的速度：将一个巨大的文件读入内存，然后对数据执行一些无意义的计算。所有类型的优化都计入其中。无论是以不同的方式重写代码还是使用不同的JVM，欺骗JIT等。

输入文件是一个500万个32位整数对的长列表，由逗号分隔。像这样：

44439,5023 33140,22257 ...

这个文件在我的机器上占用5.5GB。程序不能使用超过8GB的RAM，只能使用单个线程。

package speedracer;

import java.io.FileInputStream;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;

public class Main
{
    public static void main(String[] args)
    {
        int[] list = new int[1000000000];

        long start1 = System.nanoTime();
        parse(list);
        long end1 = System.nanoTime();

        System.out.println("Parsing took: " + (end1 - start1) / 1000000000.0);

        int rs = 0;
        long start2 = System.nanoTime();

        for (int k = 0; k < list.length; k++) {
            rs = calc(list[k++], list[k++], list[k++], list[k]);
        }

        long end2 = System.nanoTime();

        System.out.println(rs);
        System.out.println("Calculations took: " + (end2 - start2) / 1000000000.0);
    }

    public static int calc(final int a1, final int a2, final int b1, final int b2)
    {
        int c1 = (a1 + a2) ^ a2;
        int c2 = (b1 - b2) << 4;

        for (int z = 0; z < 100; z++) {
            c1 ^= z + c2;
        }

        return c1;
    }

    public static void parse(int[] list)
    {
        FileChannel fc = null;
        int i = 0;

        MappedByteBuffer byteBuffer;

        try {
            fc = new FileInputStream("in.txt").getChannel();

            long size = fc.size();
            long allocated = 0;
            long allocate = 0;

            while (size > allocated) {

               if ((size - allocated) > Integer.MAX_VALUE) {
                   allocate = Integer.MAX_VALUE;
               } else {
                   allocate = size - allocated;
               }

               byteBuffer = fc.map(FileChannel.MapMode.READ_ONLY, allocated, allocate);
               byteBuffer.clear();

               allocated += allocate;

               int number = 0;

               while (byteBuffer.hasRemaining()) {
                   char val = (char) byteBuffer.get();
                   if (val == '\n' || val == ',') {
                        list[i] = number;

                        number = 0;
                        i++;
                   } else {
                       number = number * 10 + (val - '0');
                   }
                }
            }

            fc.close();

        } catch (Exception e) {
            System.err.println("Parsing error: " + e);
        }
    }
}

我已经尝试了我能想到的所有方法。尝试不同的阅读器，尝试openjdk6、sunjdk6、sunjdk7。尝试不同的阅读器。由于MappedByteBuffer一次无法映射超过2GB的内存，所以不得不进行一些丑陋的解析。我正在运行：

   Linux AS292 2.6.38-11-generic #48-Ubuntu SMP 
   Fri Jul 29 19:02:55 UTC 2011 
   x86_64 GNU/Linux. Ubuntu 11.04. 
   CPU: is Intel(R) Core(TM) i5-2410M CPU @ 2.30GHz.

目前，我的解析时间为26.50秒，计算时间为11.27秒。我正在与一个类似的C++基准测试竞争，该基准测试在大致相同的时间内进行IO，但计算仅需4.5秒。我的主要目标是以任何可能的方式减少计算时间。有什么想法吗？

更新：看起来主要的速度提升可能来自所谓的自动向量化。我能找到一些提示，表明当前Sun的JIT只做了“一些向量化”，但我无法确认。找到一些具有更好的自动向量化优化支持的JVM或JIT将是很好的。

- Zilvinas

---

C++ 应用程序是否在与您的 Java 应用程序相同的机器上运行？因为如果它在不同的机器上，那很容易意味着不同的性能特征。 - Drizzt321

@monksy：忘了提到我使用-Xmx6048m运行程序。calc方法是任务的一部分，旨在查看Java执行这些操作的速度有多快。 - Zilvinas

另外，您应该注意处理器的使用情况。如果仅使用了大约50％的处理器，您可以通过在另一个线程中执行一半的计算来提高性能。 - Luigi Plinge

你真的需要一个文本文件吗？你不能将int保存为原始类型吗？这样你的文件会更小，运行速度也可能更快。如果你在不同的平台上工作，可能会出现一些大/小端问题。 - toto2

我之所以这样问，是因为那个“无意义的计算”可以被超级优化成极其高效的东西...也许C++编译器能够做到，但Java编译器或JIT不能。 - Mysticial

Answer 1

首先，-O3 会启用以下功能：

-finline-functions
-ftree-vectorize

除其他外，看起来它实际上可能正在进行向量化。

编辑：已经得到确认（请参见评论）。C++版本确实被编译器向量化。禁用向量化后，C++版本的运行速度比Java版本稍慢。

假设JIT不对循环进行向量化，Java版本要想与C++版本的速度相匹配可能会很困难/不可能。

---

现在，如果我是一个聪明的C/C++编译器，这就是我如何安排该循环（在x64上）：

int c1 = (a1 + a2) ^ a2;
int c2 = (b1 - b2) << 4;

int tmp0 = c1;
int tmp1 = 0;
int tmp2 = 0;
int tmp3 = 0;

int z0 = 0;
int z1 = 1;
int z2 = 2;
int z3 = 3;

do{
    tmp0 ^= z0 + c2;
    tmp1 ^= z1 + c2;
    tmp2 ^= z2 + c2;
    tmp3 ^= z3 + c2;
    z0 += 4;
    z1 += 4;
    z2 += 4;
    z3 += 4;
}while (z0 < 100);

tmp0 ^= tmp1;
tmp2 ^= tmp3;

tmp0 ^= tmp2;

return tmp0;

请注意，此循环完全可向量化。

更好的是，我会完全展开这个循环。这些都是C/C++编译器会做的事情。但现在的问题是，JIT会这样做吗？

- Mysticial

---

尝试很不错，但结果仍然是11秒。我会在C++上尝试O2并观察发生了什么，并在一分钟内告诉你。 - Zilvinas

O2版本需要13秒。因此，是O3使C++版本变得非常快。 - Zilvinas

我猜C++版本有完全相同的循环？（基本循环的语法是相同的）只是好奇如果你将这个循环复制到C++版本中会发生什么。我想知道它是否会使C++版本变得更快...哈哈 - Mysticial

啊...刚看到你的评论...所以-O3起了作用。也许它真的在进行向量化处理。唯一的方法是查看汇编转储。:( - Mysticial

如果没有人提出神奇的解决方案或支持自动向量化的JVM实现（如gcc），我会在几天内批准您的答案;) - Zilvinas

Answer 2

有趣的问题。 :-) 这可能更像是一条评论，因为我不会真正回答你的问题，但它太长了，无法放在评论框中。

在Java中进行微基准测试很棘手，因为JIT可能会对优化进行疯狂的调整。但是这段特定的代码以某种方式欺骗了JIT，以至于它无法执行其正常的优化。

通常，此代码将在O(1)时间内运行，因为您的主循环对任何内容都没有影响：

    for (int k = 0; k < list.length; k++) {
        rs = calc(list[k++], list[k++], list[k++], list[k]);
    }

请注意，rs 的最终结果实际上并不取决于运行循环的所有迭代；只有最后一个迭代。您可以计算循环的“k”的最终值，而无需实际运行循环。通常 JIT 会注意到这一点，并将您的循环转换为单个赋值，如果它能够检测到被调用的函数（calc）没有副作用（它确实没有）。

但是，某种方式，calc() 函数中的此语句会搞乱 JIT：

        c1 ^= z + c2;

这样做会给JIT增加太多复杂性，以至于它无法确定所有这些代码最终都没有改变任何东西，原始循环可以被优化掉。

如果你将那个特定的语句改成更加无意义的内容，比如：

        c1 = z + c2;

然后JIT接管并优化您的循环。试试看。:-)

我在本地尝试了一个更小的数据集，并且使用"^="版本计算需要大约1.6秒，而使用"="版本只需要0.007秒（换句话说，它优化掉了循环）。

正如我所说，这不是真正的回答，但我认为这可能很有趣。

- vanza

---

正如@Mysticial已经指出的那样，我已经添加了一个打印语句来强制JIT运行循环。如果您删除XOR，它仍然需要0.007秒，这意味着它只是更快，但整个循环仍在运行。 - Zilvinas

@Zilvinas：什么打印语句？如果你指的是打印"rs"的那个，它不会影响循环，因为正如我所指出的，你可以在不运行循环的情况下计算出rs的值。将XOR移出循环使得JIT意识到这个特定的循环可以被优化，从而导致它意识到main()中的循环也可以被优化掉。我只是不知道为什么它在有XOR的情况下不这样做。如果我从calc()调用处删除"rs ="赋值，我也会得到"0.007s"的运行时间，这意味着在这些情况下它只是不运行循环。 - vanza

如果我注释掉 System.out.println(rs);，那么循环运行时间为0.007秒。 - Zilvinas

完全正确。移除XOR具有相同的效果，使JIT意识到循环是无用的，因此不运行它。移除打印具有相同的效果，因为循环正在修改“rs”和“k”，现在循环后不会使用这两个变量。正如我所说，这并不能解释如何使它更快，但它暗示了为什么JIT没有更多的帮助。 - vanza

Answer 3

在服务器模式下使用热点JVM，并确保预热。如果垃圾收集是测试的主要部分，请给足够的时间让垃圾收集算法稳定下来以达到稳定的速度。乍一看，我没有看到任何东西让我认为它会...

- Ryan Stewart

---

不错的观点，但我已经尝试过了。64位JVM默认运行在-server模式下。此外，calc方法被执行了2.5亿次，因此HotSpot很快就能识别它。然而，我仍然尝试在外部运行calc方法，然后再次测量执行时间，但没有任何区别。 - Zilvinas

Answer 4

如果将计算函数的几行代码移动到列表迭代内部，分数会是多少呢？
我知道这样做不够简洁，但可以减少调用堆栈。

[...]
    for (int k = 0; k < list.length; k++) {
        int a1 = list[k++];
        int a2 = list[k++];
        int b1 = list[k++];
        int b2 = list[k];

        int c1 = (a1 + a2) ^ a2;
        int c2 = (b1 - b2) << 4;

        for (int z = 0; z < 100; z++) {
            c1 ^= z + c2;
        }

        rs = c1;
    }

- Destroyica

---

没有区别。我认为HotSpot能够非常快速地识别出“热点”，并对其进行JIT编译和内联处理。 - Zilvinas

Answer 5

你尝试过将parse()和calc()“内联”，即将所有代码放在main()中吗？

- mbatchkarov

---

是的，我做了。那是我的代码的第一个版本。我相信它会很快地被HotSpot、JIT和自动内联。 - Zilvinas

Answer 6

MappedByteBuffer仅对I/O性能做出了约20％的贡献，而且它是巨大的内存成本 - 如果它导致交换，则治疗比疾病更糟糕。

我会在FileReader周围使用BufferedReader，并可能在其周围使用Scanner来获取整数，或者至少使用Integer.parseInt（），这比您自己的基数转换代码更有可能被HotSpot预热。

- user207421

---

好的，关于内存成本的问题，我同意你的观点。但是就这个基准测试而言，我可以节省内存。BuferedReader、util.split和Integer.parseInt是我的首选。实际上，将文件读入内存需要8分钟。只是为了做一个实验，我刚刚运行了这段代码：`BufferedReader in = new BufferedReader(new FileReader("in.txt")); String line; int i = 0; while ((line = in.readLine()) != null) { list[i++] = 1; list[i++] = 2; }` 运行时间为47秒。 - Zilvinas

Answer 7

我正在尝试基准测试Java在执行一个简单任务时的速度：将一个巨大的文件读入内存，然后对数据执行一些无意义的计算。

如果任务是进行无意义计算，那么最好的优化方法就是不要进行计算。

如果你真正想做的是找出是否有一般性技术可以使计算更快，那么我认为你是在走弯路。 没有这样的技术。 优化无意义的计算所学到的内容可能不适用于其他（希望是有意义的）计算。

如果计算不是无意义的，并且目标是使整个程序更快，则您可能已经达到优化是浪费时间的地步。

当前（Java）- 26.50秒+ 11.27秒=约38秒。 目标（C ++）- ~ 26.5秒+ 4.50 =约31秒。 百分比加速-不到20％。

一次约40秒的计算，如果只能提高不到20%的速度，那么这样的优化可能并不值得。比起让用户额外等待7秒钟，让他悠闲地晃悠可能更加经济实惠。

---

这也告诉你一些有趣的事情。在这种情况下，使用C++或Java相对来说并没有太大的区别。程序的整体性能受到一个阶段的支配，而在这个阶段中，C++和Java是可比较的。

- Stephen C

---

虽然我同意这是毫无意义的练习，但我正在寻找那些喜欢出于好奇心进行调试的爱好者的想法，以便在非常狭窄的范围内看到JVM的极限。 - Zilvinas