标量范围与列出大型集合的性能

Question

我为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 m需要8514-10896 ms

相反，此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需要116毫秒

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

我的问题是，为什么第一个示例如此出色，而第二个示例却如此严重。我尝试创建视图，但未能成功再现该范围的性能优势。

在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<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);
                    }
            }
    }

}

花费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中的数组是唯一未类型擦除的集合。an
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。a的每个元素List由一个名为的对象组成，该对象Cons具有16个字节，并带有指向该元素的指针和指向另一个列表的指针。因此，一个List10.000.000元素由160.000.000个元素（以16字节为一组在内存中分布）加上80.000.000字节（所有8个字节以组为单位）组成。因此，真正的意义ArrayList更在于List

最后，Range。A Range是具有下边界和上边界以及步骤的整数序列。Range10.000.000个元素的A
为40个字节：下限和上限和步长的三个整数（非通用），以及一些预先计算的值（last，numRangeElements）和用于lazy val线程安全的其他两个整数。为了清楚起见，这 不是 10.000.000 的40倍：总共40个字节。范围的大小完全无关紧要，因为
它不存储各个元素 。只是下限，上限和步骤。

现在，由于a Range是a Seq[Int]，它在大多数情况下仍然必须经过装箱：int将a转换为an Integer然后再转换为a
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，它指向另一个缺点，我们已经在计算了。

我将修改估算值，并在可能的情况下提供实际数据。