"mod 4"与"& 3"性能对比

Question

我曾尝试测试在Java中使用var & 3是否比var % 4更快（也可以是& 2^n - 1与% 2^n），我制作了一个简单的程序来计算完成计算所需的平均时间，但是我得到了奇怪的结果，我无法得出结论。对于大约1000个计算，mod 4需要更长的时间，但是当我尝试进行约1000000次计算时，两个平均值大致相同......我怀疑这是由于Java优化我的代码，但我不确定。

这两种操作中哪一种应该更快，以及%如何实现？

谢谢！

编辑：这是我的测试程序。

    long startTime, time, sum;
    int iterations = 1000;
    int v;

    sum = 0;
    for(int i = 0; i < iterations; i++)
    {
        startTime = System.nanoTime();
        v = i % 4;
        time = System.nanoTime();
        sum += time-startTime;
    }
    System.out.println("Mod 4 : "+(sum/iterations));

    sum = 0;
    for(int i = 0; i < iterations; i++)
    {
        startTime = System.nanoTime();
        v = i & 3;
        time = System.nanoTime();
        sum += time-startTime;
    }
    System.out.println("& 3 : "+(sum/iterations));

进行100次迭代，使用mod 4需要130纳秒，而使用& 3需要25060纳秒。

进行1000次迭代，使用mod 4需要1792纳秒，而使用& 3只需要81纳秒。

进行1000000次迭代时，两者所需的时间大约都是50纳秒左右，但使用mod 4总是比& 3略长几个纳秒。

- user3236471

---

这取决于您如何执行测试。我建议也测试负数。 - Peter Lawrey

我确信有专家对此有深入了解，但Java Hotspot VM有时会选择解释代码的某些部分而不是将其编译为本地代码（因为编译可能需要比仅仅解释它更多的时间）。这可能就是情况所在。运行您的代码时使用 -Xint，以查看是否是因为Java将其编译为本地代码在第二个示例中。 - regulus

Regulus说得有道理。然而，如果结果在进行数百万次测试后趋于稳定（因此您拥有大量的统计数据），那么您应该考虑到您不能确定地说一个选项比另一个选项更快 - 它可能只是平局。 - Jorge_B

检查一下如果你在程序中更改测试的顺序是否会有所变化。当JIT编译器激活时，对v的赋值可能会被优化为无操作，因此您测量的只是System.nanoTime。 - zch

不知道Java编译器是否会这样做，但大多数其他编译器将常量除法/模数运算转换为乘法（对于2的幂则使用按位或/移位操作）。您需要检查输出的汇编代码/字节码。 - phuclv

Answer 1

Java，或者说任何编译器，都可能在静态或运行时（具有JIT能力的编译器）进行优化，因此很难确定您的代码实际执行了什么操作。但是，如果您检查在任何主机上最终执行的机器代码，几乎可以肯定地说，在延迟方面使用 AND 操作将比取模操作更快（也可能在吞吐量上更快）。前者只需要非常简单的ALU单元，通常存在于大多数CPU核心中，而取模操作则可能需要通过一个除法器单元执行，这个单元速度更慢且更为稀缺（即存在于较少的执行端口上）。

然而，您的Java代码与实际裸机CPU之间存在太多层，无法给出确切的答案，您应该切换到较低级别的基准测试（C或汇编），或考虑编译器所做的字节码和即时更改等其他因素。

- Leeor

Answer 2

我很好奇，于是写了自己的卡尺 基准测试。结果是每1000个元素。请注意，有一些不可忽略的开销，而操作本身的速度比率要大得多。

- maaartinus