45

我对Project Euler 问题 5有几个不同的解决方案，但是在这个特定实现中两种语言/平台之间的执行时间差异让我很感兴趣。我没有对编译器标志进行任何优化，只是简单javac（通过命令行）和csc（通过 Visual Studio）。

这是Java代码。它在 55 毫秒内完成。

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");
        }
    }
}
4

7 回答 7

40
  1. 要计时代码执行，您应该使用StopWatch该类。
  2. 此外，您必须考虑 JIT、运行时等，因此让测试运行足够的次数（如 10,000、100,000 次）并获得某种平均值。重要的是多次运行代码，而不是程序。因此，编写一个方法，并在 main 方法中循环以获取您的测量结果。
  3. 从程序集中删除所有调试内容并让代码在发布版本中独立运行
于 2011-05-10T15:17:44.363 回答
24

有一些可能的优化。也许 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 编译器以这种方式实现指针减法。

于 2011-05-10T16:32:25.840 回答
12

让这两者变得更接近的关键是确保比较是公平的。

首先确保与运行调试构建相关的成本，像您一样加载 pdb 符号。

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

接下来，您需要处理平台特定的行为。如果您使用的是 64 位 Windows 机器，则您可能在 32 位或 64 位模式下运行。在 64 位模式下，JIT 在许多方面都不同，通常会显着改变生成的代码。具体来说，我会恰当地猜测，您可以访问两倍的通用寄存器。

在这种情况下，循环的内部部分，当天真地翻译成机器代码时，需要将模测试中使用的常量加载到寄存器中。如果没有足够的东西来保存循环中需要的所有东西，那么它必须从内存中推送它们。即使来自一级缓存，与将其全部保存在寄存器中相比，这将是一个重大打击。

在 VS 2010 中，MS将默认目标从 anycpu 更改为 x86。我对 MSFT 的资源或面向客户的知识一无所知，所以我不会再猜测了。但是，任何查看您正在做的性能分析之类的东西的人都应该尝试两者。

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

我认为这对于优化编译器来说有几件事情会很有趣。

  • finnw 已经提到的那些：
    • lcm 选项很有趣，但我看不到编译器编写者在打扰。
    • 将除法减少为乘法和掩码。
      • 我对此知之甚少，但其他人尝试过注意，他们在最近的英特尔芯片上调出分频器要好得多。
      • 也许您甚至可以使用 SSE2 安排一些复杂的事情。
      • 当然，模 16 运算已经成熟，可以转换为掩码或移位。
    • 编译器可以发现所有测试都没有副作用。
      • 它可以推测性地尝试一次评估其中的几个，在超级标量处理器上，这可以更快地推动事情，但这在很大程度上取决于编译器布局与 OO 执行引擎交互的程度。
    • 如果寄存器压力很紧，您可以将常量实现为单个变量，在每个循环开始时设置，然后随着您的进行而增加。

这些都是完全的猜测，应该被视为闲散的曲折。如果你想知道拆机。

于 2011-05-11T20:55:02.597 回答
3

（从 OP 移出）

将目标从 x86 更改为anycpu已将每次运行的平均执行时间从 282 毫秒降至 84 毫秒。也许我应该把它分成第二个线程？

更新：
感谢下面的 Femaref指出了一些测试问题，事实上，在遵循他的建议之后，时间变短了，这表明 VM 设置时间在 Java 中很重要，但在 C# 中可能没有。在 C# 中，重要的是调试符号。

我更新了我的代码以运行每个循环 10,000 次，最后只输出平均毫秒数。我所做的唯一重大更改是 C# 版本，我切换到 [StopWatch 类][3] 以获得更高的分辨率。我坚持毫秒，因为它已经足够好了。

结果：
测试更改并不能解释为什么 Java（仍然）比 C# 快得多。C# 性能更好，但这完全可以通过删除调试符号来解释。如果您阅读 [Mike Two][4] 并且我与此 OP 所附的评论进行了交流，您会看到我在 C# 代码的五次运行中平均得到了大约 280 毫秒，只需从调试切换到发布。

数字：

  • 未经修改的 Java 代码的 10,000 计数循环给了我平均 45 毫秒（低于 55 毫秒）
  • 使用 StopWatch 类的 C# 代码的 10,000 计数循环给了我平均 282 毫秒（低于 320 毫秒）

所有这些都使差异无法解释。事实上，差异变得更糟了。Java 的速度从约 5.8 倍提高到约 6.2 倍。

于 2014-11-02T23:42:12.527 回答
2

这是一项太短的任务，无法进行适当的计时。您需要同时运行至少 1000 次，看看会发生什么。看起来您是从命令行运行这些，在这种情况下，您可能会比较两者的 JIT 编译器。尝试将两个按钮都放在一个简单的 GUI 中，并在返回经过的时间之前让该按钮循环至少几百次。即使忽略 JIT 编译，OS 调度程序的粒度也会影响时间。

哦，因为 JIT... 只计算按下按钮的第二个结果。:)

于 2011-05-10T15:29:32.523 回答
1

也许是因为DateTime对象的构造比System.currentTimeMillis.

于 2011-05-10T15:17:54.407 回答
1

在 Java 中，我会使用 System.nanoTime()。任何少于 2 秒的测试都应该运行更长时间。值得注意的是，Java 非常擅长优化低效代码或什么都不做的代码。如果您优化了代码，一个更有趣的测试将是。

您正在尝试获得一个无需使用循环即可确定的解决方案。即一个可以用另一种方式做得更好的问题。

您想要 11 到 20 的因子的乘积，它们是 2,2,2,2,3,3,5,7,11,13,17,19。将这些相乘，您就有了答案。

于 2011-05-10T15:28:03.403 回答