Scala 2.10 基准测试 : generic methods from the collections are useless when performance is important?

Question

我对折叠大量基元的几种方法(“直接”和使用迭代器)进行了基准测试，结果令人失望。 (是的，我已经完成了预热、中间 GC 和许多运行过程，在服务器模式下运行 JVM 并启用了 scalac 优化(并且禁用了调试信息)。

我认为代码太大，无法在这里发布，所以这里是链接:http://pastebin.com/18dWWBM4 唯一运行得几乎与普通的命令式循环一样好的方法是这个不那么通用的手写函数:

@inline def array_foldl[@specialized A, @specialized B](init: B)(src: Array[A])(fun: (B, A) => B) = {
  var res = init
  var i = 0
  var len = src.length
  while (i < len) {
    res = fun(res, src(i))
    i += 1
  }
  res
}

其他视觉上不错的方法完全是局外人。此外，使用迭代器抽象在所有情况下都会失败，对称为 SpecializedIterator 的标准迭代器的手写模仿会稍微快一些。所以有什么问题？可以以某种方式改进吗？有没有办法制作“快速”迭代器，或者原理本身有很大问题？
感谢您的关注。

Answer 1

问题是拳击。创建一个对象比将两个数字相加花费的时间要长得多，但是如果您使用通用(非专用)折叠，则每次都必须创建一个对象。只专门化所有内容的问题是，您会使整个库增大 100 倍，因为您需要两个基本参数(包括非基本参数)的每种组合，以及原始的无类型参数版本。 (100x，因为有 8 个基元加上 Unit 加上 AnyRef/非专用 T。)这是站不住脚的，因为没有现成的可用方法作为替代解决方案，这些集合目前尚未专门化。

此外，特化本身相对较新，因此在实现中仍然存在一些缺陷。特别是，您似乎用 SpecializedIterator 击中了一个:foreach 中的函数最终并没有专门化(我将特征/对象事物折叠到一个类中以使得更容易追踪):

public class Main$SpecializedArrayIterator$mcJ$sp extends Main$SpecializedArrayIterator{
public final void foreach$mcJ$sp(scala.Function1);
  Code:
   0:   aload_0
   1:   invokevirtual   #39; //Method Main$SpecializedArrayIterator.hasNext:()Z
   4:   ifeq    24
   7:   aload_1
   8:   aload_0
   9:   invokevirtual   #14; //Method next$mcJ$sp:()J
   12:  invokestatic    #45; //Method scala/runtime/BoxesRunTime.boxToLong:(J)Ljava/lang/Long;
   15:  invokeinterface #51,  2; //InterfaceMethod scala/Function1.apply:(Ljava/lang/Object;)Ljava/lang/Object;
   20:  pop
   21:  goto    0
   24:  return

看到第 12 行的框，后面是对非专用 Function1 的调用吗？哎呀。 (sum 中使用的元组 (A, (A,A) => A) 也搞乱了专门化。)像这样的实现是全速的:

class SpecializedArrayIterator[@specialized A](src: Array[A]) {
  var i = 0
  val l = src.length
  @inline final def hasNext: Boolean = i < l
  @inline final def next(): A = { val res = src(i); i += 1; res }
  @inline final def foldLeft[@specialized B](z: B)(op: (B, A) => B): B = {
    var result = z
    while (hasNext) result = op(result,next)
    result
  }
}

...
measure((new SpecializedArrayIterator[Long](test)).foldLeft(0L)(_ + _))
...

结果如下:

Launched 51298 times in 2000 milliseconds, ratio = 25.649    // New impl
Launched 51614 times in 2000 milliseconds, ratio = 25.807    // While loop