Java lambda 比匿名类慢 20 倍

Question

我在这里看到了很多关于 Java lambda 性能的问题，但大多数都是这样的:“Lambda 稍快一些，但使用闭包时会变慢”或“预热与执行时间不同”或其他类似的问题事情。

但是，我在这里遇到了一件相当奇怪的事情。考虑this LeetCode problem :

Given a set of non-overlapping intervals, insert a new interval intothe intervals (merge if necessary).

You may assume that the intervals were initially sorted according totheir start times.

这个问题被标记为“硬”，所以我认为线性方法不是他们想要的。因此，我决定想出一种巧妙的方法，将二分搜索与对输入列表的修改结合起来。现在修改输入列表的问题不是很清楚——它说“插入”，尽管签名要求返回对列表的引用，但现在不用介意。这是完整的代码，但只有前几行与这个问题相关。我将其余部分保留在这里，以便任何人都可以尝试:

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    int start = Collections.binarySearch(intervals, newInterval,
                                         (i1, i2) -> Integer.compare(i1.start, i2.start));
    int skip = start >= 0 ? start : -start - 1;
    int end = Collections.binarySearch(intervals.subList(skip, intervals.size()),
                                       new Interval(newInterval.end, 0),
                                       (i1, i2) -> Integer.compare(i1.start, i2.start));
    if (end >= 0) {
        end += skip; // back to original indexes
    } else {
        end -= skip; // ditto
    }
    int newStart = newInterval.start;
    int headEnd;
    if (-start - 2 >= 0) {
        Interval prev = intervals.get(-start - 2);
        if (prev.end < newInterval.start) {
            // the new interval doesn't overlap the one before the insertion point
            headEnd = -start - 1;
        } else {
            newStart = prev.start;
            headEnd = -start - 2;
        }
    } else if (start >= 0) {
        // merge the first interval
        headEnd = start;
    } else { // start == -1, insertion point = 0
        headEnd = 0;
    }
    int newEnd = newInterval.end;
    int tailStart;
    if (-end - 2 >= 0) {
        // merge the end with the previous interval
        newEnd = Math.max(newEnd, intervals.get(-end - 2).end);
        tailStart = -end - 1;
    } else if (end >= 0) {
        newEnd = intervals.get(end).end;
        tailStart = end + 1;
    } else { // end == -1, insertion point = 0
        tailStart = 0;
    }
    intervals.subList(headEnd, tailStart).clear();
    intervals.add(headEnd, new Interval(newStart, newEnd));
    return intervals;
}

这个方法运行良好并被接受，但运行时间为 80 毫秒，而大多数解决方案为 4-5 毫秒，有些为 18-19 毫秒。当我查找它们时，它们都是线性的并且非常原始。人们不会期望从标记为“困难”的问题中得到什么。

但问题来了:我的解决方案在最坏情况下也是线性的(因为添加/清除操作是线性时间)。为什么那么慢？然后我这样做了:

Comparator<Interval> comparator = new Comparator<Interval>() {
    @Override
    public int compare(Interval i1, Interval i2) {
        return Integer.compare(i1.start, i2.start);
    }
};
int start = Collections.binarySearch(intervals, newInterval, comparator);
int skip = start >= 0 ? start : -start - 1;
int end = Collections.binarySearch(intervals.subList(skip, intervals.size()),
                                   new Interval(newInterval.end, 0),
                                   comparator);

从 80 毫秒降至 4 毫秒!这里发生了什么？不幸的是，我不知道 LeetCode 运行什么样的测试或在什么环境下运行，但是 20 倍不是太多了吗？

Answer 1

您显然遇到了 lambda 表达式的首次初始化开销。正如评论中已经提到的，lambda 表达式的类是在运行时生成的，而不是从类路径加载的。

但是，生成并不是减速的原因。毕竟，生成具有简单结构的类甚至比从外部源加载相同字节还要快。并且内部类也必须被加载。但是，当应用程序以前没有使用过 lambda 表达式时，甚至必须加载用于生成 lambda 类的框架(Oracle 当前的实现在幕后使用 ASM)。这是十几个内部使用的类的加载和初始化速度减慢的实际原因，而不是 lambda 表达式本身²。

您可以轻松验证这一点。在当前使用 lambda 表达式的代码中，有两个相同的表达式 (i1, i2) -> Integer.compare(i1.start, i2.start)。当前的实现无法识别这一点(实际上，编译器也不提供提示)。因此，这里生成了两个具有不同类的 lambda 实例。您可以重构代码，使其只有一个比较器，类似于您的内部类变体:

final Comparator<? super Interval> comparator
  = (i1, i2) -> Integer.compare(i1.start, i2.start);
int start = Collections.binarySearch(intervals, newInterval, comparator);
int skip = start >= 0 ? start : -start - 1;
int end = Collections.binarySearch(intervals.subList(skip, intervals.size()),
                                   new Interval(newInterval.end, 0),
                                   comparator);

您不会注意到任何显着的性能差异，因为重要的不是 lambda 表达式的数量，而是框架的类加载和初始化，这只会发生一次。

您甚至可以通过插入额外的 lambda 表达式来最大化它，例如

final Comparator<? super Interval> comparator1
    = (i1, i2) -> Integer.compare(i1.start, i2.start);
final Comparator<? super Interval> comparator2
    = (i1, i2) -> Integer.compare(i1.start, i2.start);
final Comparator<? super Interval> comparator3
    = (i1, i2) -> Integer.compare(i1.start, i2.start);
final Comparator<? super Interval> comparator4
    = (i1, i2) -> Integer.compare(i1.start, i2.start);
final Comparator<? super Interval> comparator5
    = (i1, i2) -> Integer.compare(i1.start, i2.start);

没有看到任何放缓。这实际上是您在这里注意到的整个运行时的第一个 lambda 表达式的初始开销。由于 Leetcode 本身在输入代码之前显然不使用 lambda 表达式，代码的执行时间会被测量，因此此开销会增加您的执行时间。

另请参阅“How will Java lambda functions be compiled?”和 “Does a lambda expression create an object on the heap every time it's executed?”

这意味着在将控制权移交给应用程序之前执行的 JDK 代码本身不使用 lambda 表达式。由于此代码源于 lambda 表达式引入之前的时代，因此通常是这种情况。使用较新的 JDK，模块化软件将由不同的较新代码进行初始化，这些代码似乎使用 lambda 表达式，因此在这些设置中，无法再在应用程序内测量运行时设施的初始化。

² 在较新的 JDK 中，初始化时间已显着减少。有不同的可能原因、一般性能改进、专用 lambda 优化或两者兼而有之。一般来说，改进初始化时间是 JDK 开发人员没有忘记的一个问题。