Java lambdas 比匿名类慢 20 倍 [英] Java lambdas 20 times slower than anonymous classes

问题描述

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

I've seen a lot of questions here about Java lambdas performance, but most of them go like "Lambdas are slightly faster, but become slower when using closures" or "Warm-up vs execution times are different" or other such things.

然而，我在这里遇到了一个相当奇怪的事情.考虑这个 LeetCode 问题:

However, I hit a rather strange thing here. Consider this LeetCode problem:

给定一组不重叠的区间，插入一个新区间到间隔(必要时合并).

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

你可以假设区间最初是根据他们的开始时间.

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

这个问题被标记得很困难，所以我认为线性方法不是他们想要的.所以我决定想出一种巧妙的方法来将二分搜索与对输入列表的修改结合起来.现在修改输入列表的问题不是很清楚——它说插入"，即使签名需要返回对列表的引用，但暂时不要介意.这是完整的代码，但只有前几行与此问题相关.我把剩下的留在这里，这样任何人都可以尝试:

The problem was tagged hard, so I assumed that a linear approach is not what they want there. So I decided to come up with a clever way to combine binary search with modifications to the input list. Now the problem is not very clear on modifying the input list—it says "insert", even though the signature requires to return a reference to list, but never mind that for now. Here's the full code, but only the first few lines are relevant to this question. I'm keeping the rest here just so that anyone can try it:

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 毫秒.当我抬头看时，它们都是线性的，非常原始.对于标记为困难"的问题，人们不会期望得到什么.

This worked fine and got accepted, but with 80 ms runtime, while most solutions were 4-5 ms and some 18-19 ms. When I looked them up, they were all linear and very primitive. Not something one would expect from a problem tagged "hard".

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

But here comes the question: my solution is also linear at worst case (because add/clear operations are linear time). Why is it that slower? And then I did this:

    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 倍不是太多吗?

From 80 ms down to 4 ms! What's going on here? Unfortunately I have no idea what kind of tests LeetCode runs or under what environment, but still, isn't 20 times too much?

推荐答案

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

You are obviously encountering the first-time initialization overhead of lambda expressions. As already mentioned in the comments, the classes for lambda expressions are generated at runtime rather than being loaded from your class path.

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

However, being generated isn’t the cause for the slowdown. After all, generating a class having a simple structure can be even faster than loading the same bytes from an external source. And the inner class has to be loaded too. But when the application hasn’t used lambda expressions before¹, even the framework for generating the lambda classes has to be loaded (Oracle’s current implementation uses ASM under the hood). This is the actual cause of the slowdown, loading and initialization of a dozen internally used classes, not the lambda expression itself².

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

You can easily verify this. In your current code using lambda expressions, you have two identical expressions (i1, i2) -> Integer.compare(i1.start, i2.start). The current implementation doesn’t recognize this (actually, the compiler doesn’t provide a hint neither). So here, two lambda instances, having even different classes, are generated. You can refactor the code to have only one comparator, similar to your inner class variant:

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 表达式的数量，而只是框架的类加载和初始化，这恰好发生一次.

You won’t notice any significant performance difference, as it’s not the number of lambda expressions that matters, but just the class loading and initialization of the framework, which happens exactly once.

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

You can even max it out by inserting additional lambda expressions like

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 表达式，其执行时间会被测量，因此这种开销会增加您的执行时间.

without seeing any slowdown. It’s really the initial overhead of the very first lambda expression of the entire runtime you are noticing here. Since Leetcode itself apparently doesn’t use lambda expressions before entering your code, whose execution time gets measured, this overhead adds to your execution time here.

另见Java lambda 函数将如何编译?" 和 是否lambda 表达式每次执行时都会在堆上创建一个对象?"

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

¹ This implies that JDK code that will be executed before handing control over to your application doesn’t use lambda expressions itself. Since this code stems from times before the introduction of lambda expressions, this is usually the case. With newer JDKs, modular software will be initialized by different, newer code, which seems to use lambda expressions, so the initialization of the runtime facility can’t be measured within the application anymore in these setups.

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

² The initialization time has been reduced significantly in newer JDKs. There are different possible causes, general performance improvements, dedicated lambda optimizations, or both. Improving initialization time in general, is an issue that the JDK developers did not forget.

这篇关于Java lambdas 比匿名类慢 20 倍的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！