Scala 性能问题
在 Daniel Korzekwa 撰写的文章，他说下面代码的性能：
list.map(e => e*2).filter(e => e>10)
比用Java写的迭代方案差很多。
谁能解释为什么？ Scala 中此类代码的最佳解决方案是什么（我希望它不是 Scala 化的 Java 迭代版本）？
In the article written by Daniel Korzekwa, he said that the performance of following code:
list.map(e => e*2).filter(e => e>10)
is much worse than the iterative solution written using Java.
Can anyone explain why? And what is the best solution for such code in Scala (I hope it's not a Java iterative version which is Scala-fied)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
特定代码速度慢的原因是因为它处理基元但使用通用操作，因此必须对基元进行装箱。 （如果
List及其祖先是专门化的，这可能会得到改善。）这可能会使速度减慢 5 倍左右。另外，从算法上来说，这些操作有点昂贵，因为您创建一个完整的列表，然后创建一个全新的列表，扔掉中间列表的一些组件。如果你一次性做到了，那么你的情况会更好。你可以这样做：
但是如果计算
e*2真的很昂贵怎么办？那么你就可以避免这会出现倒退。 （如果需要，您可以反转它，但这需要创建一个新列表，这在算法上也不是理想的。）
当然，如果您使用单链表，您在 Java 中也会遇到同样类型的算法问题 -你的新列表最终会向后，或者你必须创建它两次，首先是反向，然后是向前，或者你必须使用（非尾）递归来构建它（这在 Scala 中很容易，但对于这种事情来说是不可取的）无论哪种语言，因为您都会耗尽堆栈），或者您必须创建一个可变列表，然后假装它不可变。 （顺便说一句，您也可以在 Scala 中执行此操作 - 请参阅
mutable.LinkedList。）The reason that particular code is slow is because it's working on primitives but it's using generic operations, so the primitives have to be boxed. (This could be improved if
Listand its ancestors were specialized.) This will probably slow things down by a factor of 5 or so.Also, algorithmically, those operations are somewhat expensive, because you make a whole list, and then make a whole new list throwing a few components of the intermediate list away. If you did it in one swoop, then you'd be better off. You could do something like:
but what if the calculation
e*2is really expensive? Then you couldexcept that this would appear backwards. (You could reverse it if need be, but that requires creating a new list, which again isn't ideal algorithmically.)
Of course, you have the same sort of algorithmic problems in Java if you're using a singly linked list--your new list will end up backwards, or you have to create it twice, first in reverse and then forwards, or you have to build it with (non-tail) recursion (which is easy in Scala, but inadvisable for this sort of thing in either language since you'll exhaust the stack), or you have to create a mutable list and then pretend afterwards that it's not mutable. (Which, incidentally, you can do in Scala also--see
mutable.LinkedList.)基本上它遍历了一个列表两次。一次用于将每个元素乘以 2。然后再一次过滤结果。
将其视为一个 while 循环，生成一个包含中间结果的 LinkedList。然后另一个循环应用过滤器来产生最终结果。
这应该更快：
Basically it's traversing a list twice. Once for multiplying every element with two. And then another time to filter the results.
Think of it as one while loop producing a LinkedList with the intermediate results. And then another loop applying the filter to produce the final results.
This should be faster:
解决方案主要在于 JVM。尽管 Scala 有一个@specialization 图中的解决方法，但这会极大地增加任何专用类的大小，并且只能解决一半问题——另一半是临时对象的创建。
JVM实际上对很多方面的优化做得很好，否则性能会更糟糕，但是Java不需要Scala所做的优化，所以JVM不提供它们。我预计随着 Java 中非真实闭包的引入，这种情况会在一定程度上发生改变。
但最终，还是要平衡需求。 Java 和 Scala 的
while循环比 Scala 的等效函数快得多，但在 C 中也可以更快地完成。然而，不管微基准测试告诉我们什么，人们仍然使用 Java。The solution lies mostly with JVM. Though Scala has a workaround in the figure of
@specialization, that increases the size of any specialized class hugely, and only solves half the problem -- the other half being the creation of temporary objects.The JVM actually does a good job optimizing a lot of it, or the performance would be even more terrible, but Java does not require the optimizations that Scala does, so JVM does not provide them. I expect that to change to some extent with the introduction of
SAMnot-real-closures in Java.But, in the end, it comes down to balancing the needs. The same
whileloop that Java and Scala do so much faster than Scala's function equivalent can be done faster yet in C. Yet, despite what the microbenchmarks tell us, people use Java.Scala 方法更加抽象和通用。因此，很难优化每一个案例。
我可以想象，如果 HotSpot JIT 编译器发现未使用即时结果，它将来可能会对代码应用流和循环融合。
此外，Java 代码还可以做更多的事情。
如果您确实只想改变数据结构，请考虑
transform。它看起来有点像
map但不会创建新的集合，例如：我真的希望将来会添加一些额外的就地操作......
Scala approach is much more abstract and generic. Therefore it is hard to optimize every single case.
I could imagine that HotSpot JIT compiler might apply stream- and loop-fusion to the code in the future if it sees that the immediate results are not used.
Additionally the Java code just does much more.
If you really just want to mutate over a datastructure, consider
transform.It looks a bit like
mapbut doesn't create a new collection, e. g.:I really hope some additional in-place operations will be added ion the future...
为了避免两次遍历列表，我认为
for语法是一个不错的选择：To avoid traversing the list twice, I think the
forsyntax is a nice option here:Rex Kerr 正确地陈述了主要问题：在不可变列表上操作，所陈述的代码片段在内存中创建中间列表。请注意，这不一定比等效的 Java 代码慢；你只是永远不会在 Java 中使用不可变的数据结构。
Wilfried Springer 有一个很好的 Scala idomatic 解决方案。使用
view，不会创建整个列表的（经过操作的）副本。请注意，使用视图可能并不总是理想的。例如，如果您的第一个调用是
filter，预计会丢弃大部分列表，则可能值得显式创建较短的版本并仅在此之后使用view以提高后续迭代的内存局部性。Rex Kerr correctly states the major problem: Operating on immutable lists, the stated piece of code creates intermediate lists in memory. Note that this is not necessarily slower than equivalent Java code; you just never use immutable datastructures in Java.
Wilfried Springer has a nice, Scala idomatic solution. Using
view, no (manipulated) copies of the whole list are created.Note that using view might not always be ideal. For example, if your first call is
filterthat is expected to throw away most of the list, is might be worthwhile to create the shorter version explicitly and useviewonly after that in order to improve memory locality for later iterations.list.filter(e => e*2>10).map(e => e*2)
此尝试首先减少 List。所以第二次遍历是在较少的元素上。
list.filter(e => e*2>10).map(e => e*2)
This attempt reduces first the List. So the second traversing is on less elements.