Java lambdas比匿名类慢20倍

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

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

给定一组非重叠间隔，在间隔中插入新间隔（必要时合并）。

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

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

public List insert(List 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 = 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 comparator = new Comparator() { @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表达式本身。

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

 final Comparator 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 comparator1 = (i1, i2) -> Integer.compare(i1.start, i2.start); final Comparator comparator2 = (i1, i2) -> Integer.compare(i1.start, i2.start); final Comparator comparator3 = (i1, i2) -> Integer.compare(i1.start, i2.start); final Comparator comparator4 = (i1, i2) -> Integer.compare(i1.start, i2.start); final Comparator comparator5 = (i1, i2) -> Integer.compare(i1.start, i2.start); 

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

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