JDK8 LocalDate.toEpochDay 性能怪异下降

Question

我很好奇我们是否最终会得到一个快速的JDK8日期时间库。几乎所有的LocalDate计算都使用toEpochDay，所以我看了一下源代码，大量的除法和分支让我好奇能否做得更好。

我消除了一些分支和除了一个之外的所有除法，但加速比预期更差。那么我的第一个问题是，一个使用多个除法的算法如何可能只需要约30个周期(吞吐量)。Holger的评论似乎已经回答了这个问题:除以一个小常数会被JIT编译为乘法。我手动完成并且现在一直以2倍的速度击败原始实现。 这个基准测试非常简单，只需迭代随机LocalDate数组，并将每个转换为toEpochDay。尽管数据是随机的，但结果非常一致。数组的大小是一个参数，我的主要问题是2000到30000之间的大型减速来自哪里。随着数据不再适合L1缓存，应该会有一些减速，但两种算法的内存访问完全相同(即没有除了从数组中获取date之外的操作)。

仍然存在的问题是:当迭代数组时，两个简单的无内存访问实现的相同函数的行为如何改变?原始算法的减速要比我的严重得多。

我的算法可能不值得在这里复制，它没有文档，与原始算法一样晦涩难懂，并且只有非常基本的测试。

- maaartinus

Answer 1

我没有直接找到原因，但肯定是基准测试框架的缺陷。与GC和每次调用成本有关。我在使用JMH时也出现了相同的性能下降，除了使用100个日期进行基准测试比2000个日期更好以外。我尝试始终创建最大大小的dates数组，并仅迭代前100、2000、30000个元素。在这种情况下，所有版本的表现都相同（在我的机器上为15.3+-0.3 ns）。

import org.openjdk.jmh.annotations.*;

import java.time.LocalDate;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;


@State(Scope.Benchmark)
@BenchmarkMode(Mode.AverageTime)
@OperationsPerInvocation(LocalDateBenchmark.ITERATIONS)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class LocalDateBenchmark {
    public static final int MAX_ITERATIONS = 1000000;
    public static final int ITERATIONS = 30000;

    private static final LocalDate MIN_DATE = LocalDate.of(1900, 1, 1);
    private static final LocalDate MAX_DATE = LocalDate.of(2100, 1, 1);
    private static final int DAYS_BETWEEN = (int) (MAX_DATE.toEpochDay() - MIN_DATE.toEpochDay());

    public LocalDate[] dates = new LocalDate[MAX_ITERATIONS];
    private Random random;

    @Setup(Level.Trial)
    public void setUpAll() {
        Random r = ThreadLocalRandom.current();
        for (int i=0; i< dates.length; ++i) {
            dates[i] = MIN_DATE.plusDays(r.nextInt(DAYS_BETWEEN));
        }
    }

    @Setup(Level.Iteration)
    public void setUpRandom() {
        random = new Random();
    }

    @GenerateMicroBenchmark
    public int timeToEpochDay(LocalDateBenchmark state) {
        int result = 0;
        LocalDate[] dates = state.dates;
        int offset = random.nextInt(MAX_ITERATIONS - ITERATIONS);
        for (int i = offset; i < offset + ITERATIONS; i++) {
            LocalDate date = dates[i];
            result += date.toEpochDay();
        }
        return result;
    }
}

- leventov

---

我无法确认。对我来说，结果几乎没有改变。你能发布你的基准测试吗？ - maaartinus

我明白了。但你在创建缓存缺失，对抗预取器，甚至可能是范围检查消除。这解释了为什么 100 是输家，也可能解释了其他大小速度保持不变的原因。但是，在原始情况下，我不认为它可以解释（当它在 caliper 和 JMH 中都发生时，我也不会称之为框架故障）。 - maaartinus

@maaartinus 可能是因为缓存的原因吗？在 L1 中循环遍历 100 个日期。 - leventov

Answer 2

这是因为算法中没有使用除法。所有的/4都被替换成了移位操作。而所有的/100实际上都是*0.01。这些除法只是为了提高可读性（哈哈）。我不确定这种优化是在字节码生成时还是JIT编译时发生的，看一下类文件会很有趣。

- aepurniet

---

在字节码中肯定没有这样的优化（javac在这方面几乎什么都不做）。通常情况下，/4不能被>>2替换（因为除法的奇怪向零舍入语义，在这里可以）。有时您可以通过浮点乘法和舍入来替换整数除法，但我不确定它是否有帮助。对于一般的长操作数，这很可能是不可能的，因为double只有56位的尾数。 - maaartinus

@maaartinus：如果你看代码，你会发现在除法之前有一个 if (y >= 0)。因此JVM可以证明被除数在某种情况下不是负数，所以将 /4 替换为 >>2 是可行的，即使在另一种情况下，它也可以生成正确的代码来修复它，例如 -((-y)>>2) 如果你知道 y 是负数。 - Holger

对于除以 100，不需要使用浮点数。由于源值是 int 和 short 类型，并且除法在 long 范围内进行，因此可以应用“小数的整数除法”优化。维基百科 对该概念进行了简要解释。简单地说，/100 被替换为 *X/Y，其中选择 X 和 Y 使得 Y 是 2 的幂次方，因此 /Y 被替换为移位操作，而 X/Y 则足够接近 0.01 以获得整数结果。 - Holger

@Holger：关于使用移位而不是除法，是的（我甚至在上面混乱的句子中写道“这里可以”）。然而，这只是四个部分中的一个。 - maaartinus

@maaartinus：它是用来初始化一个来自“int”的值的“long”。其他值甚至来自“short”。这就是我已经写过的；这是那种完美的情况，因为JVM可以证明“long”的上位比特未使用。也许这就是在这个地方使用“long”来表示“y”和“m”的唯一原因。 - Holger