为什么填充数组在while循环是如此缓慢在Scala 3?

Question

我有2个填充Array[Int]的实现，如下所述。第一个执行84毫秒，第二个慢100倍:

Execute 'filling via Array.fill' in 84 ms
Execute 'filling via while' in 8334 ms

为什么第二种变体需要100倍的时间?它不是GC，因为我可以在相同的时间删除第一次执行。我在Java 11上运行它，使用Scala 3:

.jdks/adopt-openjdk-11.0.11/bin/java ... Fill

更重要的是，如果你打开Array.fill实现，你会看到实现通过while…

object Fill extends App {
def timeMeasure[R](name: String)(block: => R): R = {
val startTime = System.currentTimeMillis()
val r = block
val endTime = System.currentTimeMillis()
println(s"Execute '$name' in ${endTime - startTime} ms")
r
}
val n = 1000 * 1000 // * 10
var ar = timeMeasure("filling via Array.fill") {
Array.fill[Int](n)(10)
}
ar = timeMeasure("filling via while") {
val array = new Array[Int](n)
var i = 0
while (i < n) {
array(i) = i
i += 1
}
array
}
}

PS:我在Scala 2.12上重复这个测试:

Execute 'filling via Array.fill' in 118 ms
Execute 'filling via while' in 6 ms

Scala 3中的问题…

PPS:在这种情况下，for (i <- 0 until n)以正常速度工作，时间与Scala 2.12一样。但在某些情况下，for的工作速度比while慢2或3倍。

PPPS:对于那些认为它是随机的或什么的人来说，它不是:100个测试执行516秒(今天我的PC更快)，所以平均时间是如此之大。但是无论如何，在一些程序中，一些代码块只执行一个，所以你不应该对任何性能测试执行平均时间。

更新:我发现当val n位于代码块之外时，执行时间大约慢了1000倍。但我不明白为什么。

你可以在Scala 3编译器的存储库中看到这个问题的注释:https://github.com/lampepfl/dotty/issues/13819

Answer 1

Scala 3对这段代码做了一些非常奇怪的事情。

如果我在不改变逻辑的情况下将其重构为不同的结构，那么一切都按预期工作(Array.fill比while慢一点)。

object Fill extends App {
def timeMeasure[R](f: => R): (java.lang.Long, R) = {
val startTime = System.nanoTime()
val r = f
val endTime = System.nanoTime()
(endTime - startTime, r)
}
def warmup(): Unit =  {
println("== warmup start =====================")
for (i <- 0 to 10) {
measureForN(1000000)
}
println("== warmup finish =====================")
}
def measureForN(n: Int): Unit = {
val t1 = timeMeasure { Array.fill[Int](n)(10) }
val t2 = timeMeasure({
val array = new Array[Int](n)
var i = 0
while (i < n) {
array(i) = 10
i += 1
}
array
})
val t3 = timeMeasure({
val array = new Array[Int](n)
var i = 0
while (i < n) {
array(i) = i
i += 1
}
array
})
// just to ensure actual array creations
val length = List(t1._2.length, t2._2.length, t3._2.length).min
println(s"n: ${n}, length: ${length}, fill: ${t1._1 / 1000} μs , while constant: ${t2._1 / 1000} μs, while changing: ${t3._1 / 1000} μs")
}
warmup()
measureForN(10)
measureForN(100)
measureForN(1000)
measureForN(10000)
measureForN(100000)
measureForN(1000000)
measureForN(10000000)
measureForN(100000000)
}

输出:

== warmup start =====================
n: 1000000, length: 1000000, fill: 23533 μs , while constant: 3804 μs, while changing: 3716 μs
n: 1000000, length: 1000000, fill: 7070 μs , while constant: 1606 μs, while changing: 1783 μs
n: 1000000, length: 1000000, fill: 3911 μs , while constant: 1497 μs, while changing: 1689 μs
n: 1000000, length: 1000000, fill: 3821 μs , while constant: 1543 μs, while changing: 1718 μs
n: 1000000, length: 1000000, fill: 3798 μs , while constant: 1510 μs, while changing: 1662 μs
n: 1000000, length: 1000000, fill: 3801 μs , while constant: 1524 μs, while changing: 1796 μs
n: 1000000, length: 1000000, fill: 3896 μs , while constant: 1541 μs, while changing: 1703 μs
n: 1000000, length: 1000000, fill: 3805 μs , while constant: 1486 μs, while changing: 1687 μs
n: 1000000, length: 1000000, fill: 3854 μs , while constant: 1606 μs, while changing: 1712 μs
n: 1000000, length: 1000000, fill: 3836 μs , while constant: 1509 μs, while changing: 1698 μs
n: 1000000, length: 1000000, fill: 3846 μs , while constant: 1553 μs, while changing: 1672 μs
== warmup finish =====================
n: 10, length: 10, fill: 3 μs , while constant: 0 μs, while changing: 0 μs
n: 100, length: 100, fill: 2 μs , while constant: 3 μs, while changing: 0 μs
n: 1000, length: 1000, fill: 6 μs , while constant: 1 μs, while changing: 2 μs
n: 10000, length: 10000, fill: 41 μs , while constant: 19 μs, while changing: 17 μs
n: 100000, length: 100000, fill: 378 μs , while constant: 156 μs, while changing: 170 μs
n: 1000000, length: 1000000, fill: 3764 μs , while constant: 1464 μs, while changing: 1676 μs
n: 10000000, length: 10000000, fill: 36976 μs , while constant: 15687 μs, while changing: 10860 μs
n: 100000000, length: 100000000, fill: 312242 μs , while constant: 190274 μs, while changing: 221980 μs

编辑::所需的更改就像不直接使用blocks中的n一样简单。

object Fill extends App {
def timeMeasure[R](name: String)(block: => R): R = {
val startTime = System.currentTimeMillis()
val r = block
val endTime = System.currentTimeMillis()
println(s"Execute '$name' in ${endTime - startTime} ms")
r
}
val n = 1000 * 1000 // * 10
def measureFill(x: Int): Unit = {
val ar1 = timeMeasure("filling via Array.fill") {
Array.fill[Int](x)(10)
}
}
def measureWhile(x: Int): Unit = {
val ar2 = timeMeasure("filling via while") {
val array = new Array[Int](x)
var i = 0
while (i < x) {
array(i) = i
i += 1
}
array
}
}
println("== warmup ==================")
measureFill(n)
measureWhile(n)
println("== warmup ==================")
measureFill(n)
measureWhile(n)
}

输出:

== warmup start ==================
Execute 'filling via Array.fill' in 26 ms
Execute 'filling via while' in 5 ms
== warmup finish ==================
Execute 'filling via Array.fill' in 6 ms
Execute 'filling via while' in 1 ms

编辑2:正如Mikhail指出的那样，这是因为在生成的Java代码中，n的使用被编译成n()方法的使用。

object Test3 {
val n = 1
val k = n
}

被编译为

//decompiled from Test3.class
public final class Test3 {
public static int k() {
return Test3$.MODULE$.k();
}
public static int n() {
return Test3$.MODULE$.n();
}
}
//decompiled from Test3$.class
import java.io.Serializable;
import scala.runtime.ModuleSerializationProxy;
public final class Test3$ implements Serializable {
private static final int n = 1;
private static final int k;
public static final Test3$ MODULE$ = new Test3$();
private Test3$() {
}
static {
k = MODULE$.n();
}
private Object writeReplace() {
return new ModuleSerializationProxy(Test3$.class);
}
public int n() {
return n;
}
public int k() {
return k;
}
}

但是，Scala 2.13.6生成的Java代码几乎是一样的(只有ScalaSignature部分不同)

//decompiled from Test3.class
import scala.reflect.ScalaSignature;
@ScalaSignature(
bytes = "u0006u0005r:Qau0002u0005tu0002=1Q!u0005u0005tu0002IAQ!Gu0001u0005u0002iAqaGu0001Cu0002u0013u0005Au0004u0003u0004!u0003u0001u0006I!bu0005bCu0005u0011ru0011"u0001u001du0011u0019u0011u0013u0001)Au0005;u0005)A+Z:ug)u0011u0011BCu0001tau0016u0014X.u00192be*u00111u0002Du0001u0005gu0016u0014u0018NCu0001u000eu0003tiWmu0001u0001u0011u0005AtQ"u0001u0005u0003u000bQ+7u000f^u001au0014u0005u0005u0019u0002Cu0001u000bu0018u001bu0005)""u0001fu0002u000bMu001cu0017r\1nu0005a)"AB!osJ+g-u0001u0004=S:LGOu0010u000bu0002u001fu0005ta.Fu0001u001e!t!b$u0003u0002 +tu0019u0011Ju001c;u0002u00059u0004u0013!A6u0002u0005-u0004u0003"
)
public final class Test3 {
public static int k() {
return Test3$.MODULE$.k();
}
public static int n() {
return Test3$.MODULE$.n();
}
}
//decompiled from Test3$.class
public final class Test3$ {
public static final Test3$ MODULE$ = new Test3$();
private static final int n = 1;
private static final int k;
static {
k = MODULE$.n();
}
public int n() {
return n;
}
public int k() {
return k;
}
private Test3$() {
}
}

这意味着这是由Scala 3中的一些其他错误(导致n()有这样的性能影响)引起的。