Java lambdas比匿名类慢20倍

Question

我在这里看到了很多关于Java lambdas性能的问题,但是大多数问题都像"Lambdas稍快一点,但在使用闭包时变慢"或"预热与执行时间不同"或其他类似的东西.

但是,我在这里遇到了一件相当奇怪的事情.考虑这个LeetCode问题:

给定一组非重叠间隔,在间隔中插入新间隔(必要时合并).

您可以假设间隔最初是根据其开始时间排序的.

问题被标记为难,所以我认为线性方法不是他们想要的.所以我决定想出一种聪明的方法将二进制搜索与修改结合到输入列表中.现在问题在修改输入列表时并不是很清楚 - 它表示"插入",即使签名需要返回对列表的引用,但现在也不用担心.这是完整的代码,但只有前几行与此问题相关.我在这里保留其余部分,以便任何人都可以尝试:

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表达式,因此这个开销会增加执行时间.

另请参阅"如何编译Java lambda函数？"和"每次执行时lambda表达式是否在堆上创建对象？"