为什么这个Java代码比相同的C#代码快6倍？

Question

我对Project Euler问题5有一些不同的解决方案,但是这个特定实现中两种语言/平台之间的执行时间差异引起了我的兴趣.我没有使用编译器标志进行任何优化,只是简单javac(通过命令行)和csc(通过Visual Studio).

这是Java代码.它在55ms结束.

public class Problem005b
{
    public static void main(String[] args)
    {
        long begin = System.currentTimeMillis();
        int i = 20;
        while (true)
        {
            if (
                    (i % 19 == 0) &&
                    (i % 18 == 0) &&
                    (i % 17 == 0) &&
                    (i % 16 == 0) &&
                    (i % 15 == 0) &&
                    (i % 14 == 0) &&
                    (i % 13 == 0) &&
                    (i % 12 == 0) &&
                    (i % 11 == 0)
                )
            {
                break;
            }
            i += 20;
        }
        long end = System.currentTimeMillis();
        System.out.println(i);
        System.out.println(end-begin + "ms");
    }

}

这是相同的C#代码.它在320毫秒完成

using System;

namespace ProjectEuler05
{
    class Problem005
    {
        static void Main(String[] args)
        {
            DateTime begin = DateTime.Now;
            int i = 20;
            while (true)
            {
                if (
                        (i % 19 == 0) &&
                        (i % 18 == 0) &&
                        (i % 17 == 0) &&
                        (i % 16 == 0) &&
                        (i % 15 == 0) &&
                        (i % 14 == 0) &&
                        (i % 13 == 0) &&
                        (i % 12 == 0) &&
                        (i % 11 == 0)
                    )
                    {
                        break;
                    }
                i += 20;
            }
            DateTime end = DateTime.Now;
            TimeSpan elapsed = end - begin;
            Console.WriteLine(i);
            Console.WriteLine(elapsed.TotalMilliseconds + "ms");
        }
    }
}

Answer 1

1. 要对代码执行进行计时,您应该使用StopWatch该类.
2. 此外,您必须考虑JIT,运行时等,因此让测试运行足够的次数(例如10,000次,100,000次)并获得某种平均值.重要的是多次运行代码,而不是程序.所以编写一个方法,并在main方法中循环以获得测量结果.
3. 从程序集中删除所有调试内容,让代码在发布版本中独立运行

Answer 2

有一些可能的优化.也许Java JIT正在执行它们而CLR不是.

优化#1:

(x % a == 0) && (x % b == 0) && ... && (x % z == 0)

相当于

(x % lcm(a, b, ... z) == 0)

因此,在您的示例中,比较链可以替换为

if (i % 232792560 == 0) break;

(但是当然如果你已经计算过LCM,那么首先运行程序就没什么意义了!)

优化#2:

这也是等价的:

if (i % (14549535 * 16)) == 0 break;

要么

if ((i % 16 == 0) && (i % 14549535 == 0)) break;

第一个分区可以用掩码替换并与零进行比较:

if (((i & 15) == 0) && (i % 14549535 == 0)) break;

第二个除法可以用模数逆的乘法代替:

final long LCM = 14549535;
final long INV_LCM = 8384559098224769503L; // == 14549535**-1 mod 2**64
final long MAX_QUOTIENT = Long.MAX_VALUE / LCM;
// ...
if (((i & 15) == 0) &&
    (0 <= (i>>4) * INV_LCM) &&
    ((i>>4) * INV_LCM < MAX_QUOTIENT)) {
    break;
}

JIT使用它有点不太可能,但它并不像你想象的那么牵强 - 一些C编译器以这种方式实现指针减法.

Answer 3

使这两者变得更加接近的关键是确保比较公平.

首先确保与运行Debug构建相关的成本,像加载pdb符号一样.

接下来,您需要确保不计算初始成本.显然这些都是实际成本,对某些人来说可能很重要,但在这种情况下,我们对循环本身感兴趣.

接下来,您需要处理特定于平台的行为.如果您使用的是64位Windows机器,则可能在32位或64位模式下运行.在64位模式下,JIT在许多方面都有所不同,通常会大大改变生成的代码.具体来说,我猜是有针对性的,你可以访问两倍的通用寄存器.

在这种情况下,循环的内部部分在天真地转换为机器代码时,需要将模数测试中使用的常数加载到寄存器中.如果没有足够的东西来保存循环中所需的一切,那么它必须将它们从内存中推入.即使来自level1缓存,与将它们全部保存在寄存器中相比,这将是一个重大的打击.

在VS 2010中,MS 将默认目标从anycpu更改为x86.我没有像MSFT的资源或面向客户的知识,所以我不会试图再次猜测.然而,任何看待你正在做的性能分析的人都应该尝试两者.

一旦解决了这些差异,这些数字似乎就更合理了.任何进一步的差异可能需要比有根据的猜测更好,相反,他们需要调查生成的机器代码中的实际差异.

关于优化编译器,我认为有几件事情是有趣的.

• 那些人已经提到:
  • lcm选项很有趣,但我看不到编译器编写者的困扰.
  • 将除法减少到乘法和掩蔽.
    • 我对此并不了解,但是其他人已经尝试过注意他们在更新的intel芯片上更好地调出分频器.
    • 也许你甚至可以用SSE2来安排复杂的事情.
    • 当然,模16操作已经成熟,可以转换成蒙版或移位.
  • 编译器可以发现没有任何测试有副作用.
    • 它可以推测性地尝试同时评估其中的几个,在一个超级标量处理器上,这可以提高速度,但在很大程度上取决于编译器布局与OO执行引擎的交互程度.
  • 如果寄存器压力很小,你可以将常量实现为单个变量,在每个循环的开始处设置,然后随着时间的推移递增.

这些都是完全猜测,应该被视为闲置的蜿蜒曲折.如果你想知道拆解它.