在 Scala 中以 3 为基数组合数字时如何避免装箱

Question

我想以 3 为基数组成数字，表示为固定长度 Array[Byte]。

这里有一些尝试：

val byteBoard = Array.fill(9)(1.toByte)

val cache: Seq[(Int, Int)] = (0 to 8).map(i => (i, math.pow(3d, i.toDouble).toInt))

@Benchmark
def composePow(): Unit = {
  val _ = (0 to 8).foldLeft(0) { case (acc, i) => acc + math.pow(3d, i.toDouble).toInt * byteBoard(i) }
}

@Benchmark
def composeCachedPowWithFold(): Unit = {
  val _ = cache.foldLeft(0) { case (acc, (i, k)) => acc + k * byteBoard(i).toInt }
}

@Benchmark
def composeCachedPowWithForeach(): Unit = {
  var acc = 0
  cache.foreach { case (i, k) => acc = acc + k * byteBoard(i)}
}

@Benchmark
def composeUnrolled(): Unit = {
  val _ = byteBoard(0) +
    3 * byteBoard(1) +
    3 * 3 * byteBoard(2) +
    3 * 3 * 3 * byteBoard(3) +
    3 * 3 * 3 * 3 * byteBoard(4) +
    3 * 3 * 3 * 3 * 3 * byteBoard(5) +
    3 * 3 * 3 * 3 * 3 * 3 * byteBoard(6) +
    3 * 3 * 3 * 3 * 3 * 3 * 3 * byteBoard(7) +
    3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * byteBoard(8)
}

你能否证实以下结论：

composePow：装箱+类型转换使用math.pow
composeCachedPowWithFold: 装箱因为fold是参数化方法
composeCachedPowWithForeach: 没有装箱，不太惯用 Scala（本地突变）
composeUnrolled: 没有装箱

并解释为什么 4. 比 3. 快得多？

PS：这是 JMH 基准测试的结果

[info] IndexBenchmark.composeCachedPowWithFold                    thrpt   10    7180844,823 ± 1015310,847  ops/s
[info] IndexBenchmark.composeCachedPowWithForeach                 thrpt   10   14234192,613 ± 1449571,042  ops/s
[info] IndexBenchmark.composePow                                  thrpt   10    1515312,179 ±   34892,700  ops/s
[info] IndexBenchmark.composeUnrolled                             thrpt   10  152297653,110 ± 2237446,053  ops/s

Answer 1

我基本同意你对案例 1、2、4 的分析，但第三个变体真的很有趣！

我同意你关于前两个版本的看法：foldLeft 不是 @specialized，所以，是的，有一些 boxing-unboxing。但是 math.pow 无论如何对整数运算都是有害的，所有这些转换只会产生额外的开销。

现在让我们仔细看看第三种变体。它是如此之慢，因为您正在构建可变状态的闭包。查看 scala -print 的输出。这是你的方法被重写成：

private def composeCachedPowWithForeach(): Unit = {
  var acc: runtime.IntRef = scala.runtime.IntRef.create(0);
  anon.this.cache().foreach({
    ((x0: Tuple2) => 
      anon.this.
        $anonfun$composeCachedPowWithForeach(acc, x0))
  })
};

这里是foreach中使用的函数：

final <artifact> private[this] def 
$anonfun$composeCachedPowWithForeach(
   acc: runtime.IntRef, x0: Tuple2
): Unit = {
  case <synthetic> val x1: Tuple2 = x0;
  case4(){
    if (x1.ne(null))
      {
        val i: Int = x1._1$mcI$sp();
        val k: Int = x1._2$mcI$sp();
        matchEnd3({
          acc.elem = acc.elem.+(k.*(anon.this.byteBoard().apply(i)));
          scala.runtime.BoxedUnit.UNIT
        })
      }
    else
      case5()
  };
  case5(){
    matchEnd3(throw new MatchError(x1))
  };
  matchEnd3(x: scala.runtime.BoxedUnit){
    ()
  }
};

您看到显然有很多代码是由模式匹配生成的。我不确定它是否对开销有很大贡献。我个人觉得更有趣的是 runtime.IntRef 部分。这是一个对象，它保留一个可变变量，该变量对应于代码中的 var acc。尽管它在代码中看起来像一个简单的局部变量，但它必须以某种方式从闭包中引用，因此被包装到一个对象中，并被驱逐到堆中。我假设在堆上访问这个可变变量会导致大部分开销。

与此相反，如果 byteBoard 作为参数传递，那么第四种变体中的任何内容都不会离开函数的堆栈帧：

private def composeUnrolled(): Unit = {
  val _: Int = 
    anon.this.byteBoard().apply(0).+  
    (3.*(anon.this.byteBoard().apply(1))).+
    (9.*(anon.this.byteBoard().apply(2))).+
    (27.*(anon.this.byteBoard().apply(3))).+
    (81.*(anon.this.byteBoard().apply(4))).+
    (243.*(anon.this.byteBoard().apply(5))).+
    (729.*(anon.this.byteBoard().apply(6))).+
    (2187.*(anon.this.byteBoard().apply(7))).+
    (6561.*(anon.this.byteBoard().apply(8)));
  ()
};

基本上没有控制流可言，没有任何方法调用（apply用于访问数组元素，不算），总的来说它只是一个非常简单的算术运算，甚至可能适合您处理器的寄存器。这就是它如此之快的原因。

当您使用它时，您可能想要对这两种方法进行基准测试：

def ternaryToInt5(bytes: Array[Byte]): Int = {
  var acc = 0
  val n = bytes.size
  var i = n - 1
  while (i >= 0) {
    acc *= 3
    acc += bytes(i)
    i -= 1
  }
  acc
}

def ternaryToInt6(bytes: Array[Byte]): Int = {
  bytes(0) + 
  3 * (bytes(1) + 
  3 * (bytes(2) + 
  3 * (bytes(3) + 
  3 * (bytes(4) + 
  3 * (bytes(5) + 
  3 * (bytes(6) + 
  3 * (bytes(7) + 
  3 * (bytes(8)))))))))
}

此外，如果您经常使用字节数组，您可能会发现 this syntactic sugar 很有用。

在 Scala 中以 3 为基数组合数字时如何避免装箱

How to avoid boxing when composing numbers in base 3 in Scala

performance

boxing

scala