scala范围与列表在大型集合上的性能

我为10,000,000个元素运行了一组性能基准测试，并且我发现每个实现的结果差别很大。

任何人都可以解释为什么创建Range.ByOne会导致性能优于简单的基元数组，但将相同范围转换为列表会导致性能甚至比最差情况更糟糕吗？

创建10,000,000个元素，并打印出模数为1,000,000的元素。 JVM大小始终设置为相同的最小值和最大值：-Xms？m -Xmx？m

import java.util.concurrent.TimeUnit import java.util.concurrent.TimeUnit._ object LightAndFastRange extends App { def chrono[A](f: => A, timeUnit: TimeUnit = MILLISECONDS): (A,Long) = { val start = System.nanoTime() val result: A = f val end = System.nanoTime() (result, timeUnit.convert(end-start, NANOSECONDS)) } def millions(): List[Int] = (0 to 10000000).filter(_ % 1000000 == 0).toList val results = chrono(millions()) results._1.foreach(x => println ("x: " + x)) println("Time: " + results._2); } 

JVM大小为27m，需要141毫秒

相比之下，转换为List会显着影响性能：

 import java.util.concurrent.TimeUnit import java.util.concurrent.TimeUnit._ object LargeLinkedList extends App { def chrono[A](f: => A, timeUnit: TimeUnit = MILLISECONDS): (A,Long) = { val start = System.nanoTime() val result: A = f val end = System.nanoTime() (result, timeUnit.convert(end-start, NANOSECONDS)) } val results = chrono((0 to 10000000).toList.filter(_ % 1000000 == 0)) results._1.foreach(x => println ("x: " + x)) println("Time: " + results._2) } 

它需要8514-10896毫秒，460-455米

相反，此Java实现使用基元数组

 import static java.util.concurrent.TimeUnit.*; public class LargePrimitiveArray { public static void main(String[] args){ long start = System.nanoTime(); int[] elements = new int[10000000]; for(int i = 0; i < 10000000; i++){ elements[i] = i; } for(int i = 0; i < 10000000; i++){ if(elements[i] % 1000000 == 0) { System.out.println("x: " + elements[i]); } } long end = System.nanoTime(); System.out.println("Time: " + MILLISECONDS.convert(end-start, NANOSECONDS)); } } 

它需要116ms，JVM大小为59m

Java整数列表

 import java.util.List; import java.util.ArrayList; import static java.util.concurrent.TimeUnit.*; public class LargeArrayList { public static void main(String[] args){ long start = System.nanoTime(); List elements = new ArrayList(); for(int i = 0; i < 10000000; i++){ elements.add(i); } for(Integer x: elements){ if(x % 1000000 == 0) { System.out.println("x: " + x); } } long end = System.nanoTime(); System.out.println("Time: " + MILLISECONDS.convert(end-start, NANOSECONDS)); } 

}

JVM大小为283m，需要3993 ms

我的问题是，为什么第一个例子如此高效，而第二个例子受到的影响非常严重。 我尝试创建视图，但没有成功再现该范围的性能优势。

所有测试都在Mac OS X Snow Leopard，Java 6u26 64位服务器Scala 2.9.1.final上运行

编辑：

为了完成，这里是使用LinkedList的实际实现（这在空间方面比ArrayList更公平的比较，因为正确地指出，scala的List被链接）

 import java.util.List; import java.util.LinkedList; import static java.util.concurrent.TimeUnit.*; public class LargeLinkedList { public static void main(String[] args){ LargeLinkedList test = new LargeLinkedList(); long start = System.nanoTime(); List elements = test.createElements(); test.findElementsToPrint(elements); long end = System.nanoTime(); System.out.println("Time: " + MILLISECONDS.convert(end-start, NANOSECONDS)); } private List createElements(){ List elements = new LinkedList(); for(int i = 0; i < 10000000; i++){ elements.add(i); } return elements; } private void findElementsToPrint(List elements){ for(Integer x: elements){ if(x % 1000000 == 0) { System.out.println("x: " + x); } } } } 

需要3621-6749毫秒，480-460 mbs。 这更符合第二个scala示例的性能。

最后，一个LargeArrayBuffer

 import collection.mutable.ArrayBuffer import java.util.concurrent.TimeUnit import java.util.concurrent.TimeUnit._ object LargeArrayBuffer extends App { def chrono[A](f: => A, timeUnit: TimeUnit = MILLISECONDS): (A,Long) = { val start = System.nanoTime() val result: A = f val end = System.nanoTime() (result, timeUnit.convert(end-start, NANOSECONDS)) } def millions(): List[Int] = { val size = 10000000 var items = new ArrayBuffer[Int](size) (0 to size).foreach (items += _) items.filter(_ % 1000000 == 0).toList } val results = chrono(millions()) results._1.foreach(x => println ("x: " + x)) println("Time: " + results._2); } 

大约需要2145毫秒和375毫升

非常感谢您的回答。

Answer 1

哦，这么多事情都在这里！

让我们从Java int[] 。 Java中的数组是唯一不被类型擦除的集合。 int[]的运行时表示与Object[]的运行时表示不同，因为它实际上直接使用int 。 因此，使用它没有拳击。

在内存方面，内存中有40.000.000个连续字节，每当读取或写入一个元素时，每次读取和写入4个字节。

相比之下， ArrayList – 以及几乎任何其他通用集合 – 由40.000.000或80.000.00连续字节组成（分别在32位和64位JVM上），PLUS 80.000.000字节全部传播以8字节为一组的内存。 每次读取对元素的写入都必须通过两个存储空间，并且当您正在执行的实际任务如此之快时，处理所有内存所花费的大量时间是非常重要的。

所以，回到Scala，第二个例子是你操作List 。 现在，Scala的List更像是Java的LinkedList不是严重错误的ArrayList 。 List每个元素由一个名为Cons的对象组成，该对象有16个字节，带有指向该元素的指针和指向另一个列表的指针。 因此，10.000.000个元素的List由160.000.000个元素组成，这些元素以16个字节为一组在内存中传播，加上80.000.000个字节以8个字节为一组在内存中传播。 所以ArrayList真实情况对于List来说更是如此

最后， Range 。 Range是具有下边界和上边界的整数序列，加上一个步长。 10.000.000元素的Range是40个字节：下限和上限和步骤的三个整数（非通用），加上一些预先计算的值（ last ， numRangeElements ）和另外两个用于lazy val线程安全的整数。 只是要说清楚，那不是 40倍10.000.000：那是40个字节总计。 范围的大小完全无关紧要，因为它不存储个人元素 。 只是下限，上限和步。

现在，因为一个Range是一个Seq[Int] ，它仍然需要经过装箱才能进行大多数使用：一个int将被转换为一个Integer ，然后再转换回一个int ，这是非常浪费的。

尺寸计算

所以，这是对Cons的初步计算。 首先，阅读本文关于对象占用多少内存的一般指导原则。 重点是：

1. Java使用8个字节表示普通对象，12个表示对象数组，用于“管家”信息（这个对象的类是什么等）。
2. 对象以8个字节的块分配。 如果您的对象小于该对象，则将对其进行填充以补充它。

我实际上认为它是16字节，而不是8.无论如何，缺点也比我想象的要小。 它的领域是：

 public static final long serialVersionUID; // static, doesn't count private java.lang.Object scala$collection$immutable$$colon$colon$$hd; private scala.collection.immutable.List tl; 

引用至少为 4个字节（64位JVM可能更多）。 所以我们有：

 8 bytes Java header 4 bytes hd 4 bytes tl 

这使得它只有16个字节长。 实际上非常好。 在示例中， hd将指向一个Integer对象，我假设该对象长度为8个字节。 至于tl ，它指向另一个缺点，我们已经在计算。

我将尽可能修改估算值，并提供实际数据。

Answer 2

在第一个示例中，您通过计算范围的步骤来创建包含10个元素的链接列表 。

在第二个示例中，您将创建一个包含10百万个元素的链接列表 ，并将其过滤到包含10个元素的新链接列表 。

在第三个示例中，您将创建一个数组支持的缓冲区 ，其中包含您遍历和打印的数百万个元素，不会创建新的arrays支持的缓冲区 。

结论：

每一段代码都有不同之处，这就是性能差异很大的原因。

Answer 3

这是一个有根据的猜测……

我认为这是因为在快速版本中，Scala编译器能够将密钥语句转换为类似的东西（在Java中）：

 List millions = new ArrayList(); for (int i = 0; i <= 10000000; i++) { if (i % 1000000 == 0) { millions.add(i); } } 

如您所见， (0 to 10000000)不会生成10,000,000个Integer对象的中间列表。

相比之下，在慢速版本中，Scala编译器无法进行该优化，并且正在生成该列表。

（中间数据结构可能是int[] ，但观察到的JVM大小表明它不是。）

Answer 4

在我的iPad上很难读取Scala源代码，但看起来Range的构造函数实际上并没有生成一个列表，只记得开始，增量和结束。 它使用这些来根据请求生成它的值，因此迭代一个范围比一个简单的for循环更接近于检查数组的元素。

一旦你说range.toList你就强迫Scala生成一个范围内’values’的链接列表（为值和链接分配内存），然后你迭代它。 作为链表，其性能将比Java ArrayList示例更糟糕。