2

我已经对几种折叠大量原语（“直接”和使用迭代器）的方法进行了基准测试，结果令人失望。（是的，我已经完成了预热、中间 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稍快。所以有什么问题？它可以以某种方式改进吗？有没有办法制作“快速”的迭代器，还是原理本身存在很大问题？
感谢关注。

4

1 回答 1

4

问题是拳击。创建一个对象比添加两个数字需要更长的时间，但是如果您使用通用（非专业）折叠，则每次都必须创建一个对象。只对所有内容进行专门化的问题在于，您将整个库扩大了 100 倍，因为您需要两个原始参数（包括非原始参数）的每种组合，以及原始的无类型参数版本。（100 倍，因为有 8 个原语加上Unit/ AnyRefnon-specialized T。）这是站不住脚的，并且由于没有现成的替代解决方案，因此集合目前是非专业化的。

此外，专业化本身相对较新，因此在实施方面仍有一些缺陷。特别是，您似乎遇到了一个问题SpecializedIterator： in 中的函数foreach最终没有专门化（我将 trait/object 东西折叠成一个类，以便更容易追踪）：

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？哎呀。（其中(A, (A,A) => A)使用的元组sum也搞乱了专业化。）这样的实现是全速的：

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
于 2013-02-11T23:34:06.213 回答