我为 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)
}
460-455 米需要 8514-10896 毫秒
相比之下，此 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));
}
}
JVM 大小为 59m 需要 116ms
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<Integer> elements = new ArrayList<Integer>();
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
我的问题是，为什么第一个示例的性能如此之高，而第二个示例却受到如此严重的影响。我尝试创建 View ，但未能成功重现该范围的性能优势。
在 Mac OS X Snow Leopard 上运行的所有测试， Java 6u26 64 位服务器 斯卡拉 2.9.1.final
编辑:
为了完成，这是使用 LinkedList 的实际实现(就空间而言，这是比 ArrayList 更公平的比较，因为正如正确指出的那样，scala 的列表是链接的)
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<Integer> elements = test.createElements();
test.findElementsToPrint(elements);
long end = System.nanoTime();
System.out.println("Time: " + MILLISECONDS.convert(end-start, NANOSECONDS));
}
private List<Integer> createElements(){
List<Integer> elements = new LinkedList<Integer>();
for(int i = 0; i < 10000000; i++){
elements.add(i);
}
return elements;
}
private void findElementsToPrint(List<Integer> elements){
for(Integer x: elements){
if(x % 1000000 == 0) {
System.out.println("x: " + x);
}
}
}
}
480-460 mb 需要 3621-6749 毫秒。这更符合第二个 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 MB
非常感谢您的回答。
最佳答案
哦，这里发生了很多事情!!!
让我们从 Java 开始 int[] . Java 中的数组是唯一没有类型删除的集合。 int[] 的运行时表示不同于 Object[] 的运行时表示，因为它实际上使用了 int直接地。因此，使用它不涉及拳击。
在内存方面，内存中有 40.000.000 个连续字节，每当读取或写入一个元素时，一次读取和写入 4 个字节。
相比之下，ArrayList<Integer> -- 以及几乎所有其他通用集合 -- 由 40.000.000 或 80.000.00 个连续字节(分别在 32 位和 64 位 JVM 上)以及 80.000.000 字节以 8 字节为一组分布在内存中组成。对一个元素的每次读取和写入都必须经过两个内存空间，当您执行的实际任务如此之快时，处理所有这些内存所花费的时间是非常重要的。
因此，回到 Scala，对于您操作 List 的第二个示例.现在，Scala 的 List更像是 Java 的 LinkedList比严重错误的命名ArrayList . List 的每个元素由一个名为 Cons 的对象组成，它有 16 个字节，有一个指向元素的指针和一个指向另一个列表的指针。所以，一个 List 10.000.000 个元素由 160.000.000 个元素组成，这些元素以 16 字节为一组分布在内存中，加上 80.000.000 字节以 8 字节为一组分布在内存中。那么ArrayList 是真的吗？ List 更是如此
最后，Range . Range是具有下边界和上边界的整数序列，加上步长。 Range 10.000.000 个元素是 40 个字节:三个整数(非通用)用于下限和上限以及步长，加上一些预先计算的值( last ， numRangeElements )和另外两个用于 lazy val 的整数线程安全。澄清一下，这不是 40 乘以 10.000.000:总共 40 个字节。范围的大小完全无关紧要，因为它不存储单个元素。只是下限、上限和步骤。
现在，因为 Range是 Seq[Int] , 对于大多数用途，它仍然必须经过装箱:int将转换为 Integer然后回到 int再次，这是可悲的浪费。
缺点尺寸计算
所以，这是对缺点的初步计算。首先，阅读 this article关于对象占用多少内存的一些一般准则。重点是:
- Java 为普通对象使用 8 个字节，为对象数组使用 12 个字节，用于“管理”信息(该对象的类是什么等)。
- 对象以 8 字节 block 的形式分配。如果您的对象比那个小，它将被填充以补充它。
其实我以为是16个字节，不是8个，反正Cons也比我想象的小。它的字段是:
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 ，它指向另一个我们已经在计算的缺点。
我将尽可能使用实际数据修改估计值。
关于java - Scala 范围与列表在大型集合上的性能，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8027801/