fra*_*cca 4 java collections performance scala range
我为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<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毫升
非常感谢您的回答.
Dan*_*ral 12
哦,这么多事情都在这里!
让我们从Java开始吧int[].Java中的数组是唯一不被类型擦除的集合.a的运行时表示int[]与运行时表示不同Object[],因为它实际上int直接使用.因此,使用它没有拳击.
在内存方面,内存中有40.000.000个连续字节,每当读取或写入一个元素时,每次读取和写入4个字节.
相反,ArrayList<Integer>-以及几乎任何其它通用集合-由连续40.000.000或80.000.00字节(32位和64位分别JVM),PLUS 80.000.000字节散布四周在组存储器8个字节.每次读取对元素的写入都必须通过两个存储空间,并且当您正在执行的实际任务如此之快时,处理所有内存所花费的时间非常重要.
所以,回到Scala,对于你操纵a的第二个例子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线程安全的两个其他整数.只是要说清楚,那不是 40倍10.000.000:那是40个字节总计.范围的大小完全无关紧要,因为它不存储个人元素.只是下限,上限和步.
现在,因为a Range是a Seq[Int],它仍然必须通过拳击大多数用途:一个int将被转换为一个Integer然后再回到一个int,这是可悲的浪费.
尺寸计算
所以,这是对Cons的初步计算.首先,阅读本文关于对象占用多少内存的一般指导原则.重点是:
我实际上认为它是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它,它指向另一个我们已经在计算的缺点.
我将尽可能修改估算值,并提供实际数据.
在第一个示例中，您通过计算范围的步长创建了一个包含 10 个元素的链表。
在第二个示例中，您创建了一个包含 1000 万个元素的链表，并将其过滤为一个包含 10 个元素的新链表。
在第三个示例中，您创建了一个包含 1000 万个元素的数组支持缓冲区，您可以遍历和打印这些元素，但不会创建新的数组支持缓冲区。
结论：
每段代码都做不同的事情，这就是性能差异很大的原因。