ArrayLists 比数组慢 2 倍 [英] ArrayLists 2 times slower than array

问题描述

我正在测试一种分子动力学算法，其中包括一个由 9 个双精度数组组成的粒子类，用于存储粒子分量(3D 环境中的速度、力和位置).

I was testing a Molecular Dynamic algorithm, which have, among others, an class Particle compose by 9 array of doubles to store particles components (velocity, force and position in a 3D environment).

我使用 5 个输入大小测试算法:

I test the algorithm using 5 inputs sizes:

Size (MB) Time (s)
0.06      0.36     (fits in cache L2)
0.14      1.79     (fits in cache L2)
0.60      36.86    (fits in cache L3)
1.35      182.24   (fits in cache L3)
17.38     566.55   (it only fits in RAM)

我将 Particles 布局从 array 更改为 ArrayList.为了有一个连续的内存块，我创建了arrayList，其大小将占用:

Than I change the Particles layout from array to ArrayList. In order to have a continuous memory block, I had created the arrayList with the size that will occupy:

ArrayList <Double> px = new ArrayList <Double>(Input_Size);

我在与上述睾丸相同的条件下运行该版本，结果是:

I run the version in the same conditions of the testes described above, and the results were:

Size (MB) Time (s)
0.06      0.608
0.14      2.78
0.60      57.15
1.35      299.24
17.38     1436,42

测试环境为:

AMD Opteron 处理器 6174，800 MHz，12 MB 三级缓存，24 核；

AMD Opteron Processor 6174, 800 MHz, 12 MB Cache L3, with 24 cores;

我的速度降低了大约 2 倍.这是正常的吗?不应该在两个版本中期望几乎相同的时间，因为 ArrayList 像数组一样在内存中连续分配?

I am getting a speed-down of about 2x. Is this normal? should not be expecting almost the same times in both version, since ArrayList is allocated continuous in memory like the array?

Running with the option **-XX:+PrintCompilation**

  WITH ARRAY:

 1       java.util.jar.Manifest$FastInputStream::readLine (167 bytes)
  2       sun.nio.cs.UTF_8$Decoder::decodeArrayLoop (553 bytes)
  3       java.lang.String::hashCode (60 bytes)
  4       java.lang.String::charAt (33 bytes)
  5       sun.security.util.ManifestDigester::findSection (180 bytes)
  6       java.lang.Object::<init> (1 bytes)
  7       moldyn.random::update (104 bytes)
  8       moldyn.random::seed (80 bytes)
---   n   java.lang.StrictMath::log (static)
  9       java.lang.Math::log (5 bytes)
 10       moldyn.md::scalingVelocity (82 bytes)
 11       moldyn.Particles::distance (192 bytes)
  1%      moldyn.Particles::force @ 42 (211 bytes)
 12       moldyn.Particles::force (211 bytes)
 13       moldyn.Particles::domove (163 bytes)
 14       moldyn.Particles::domove_out (160 bytes)
  2%      moldyn.Particles::cicle_domove @ 5 (23 bytes)
 15       moldyn.Particles::update_force (49 bytes)
  3%      moldyn.Particles::cicle_forces @ 6 (27 bytes)
 16       moldyn.Particles::mkekin (141 bytes)
  4%      moldyn.Particles::cicle_mkekin @ 9 (33 bytes)
 17       moldyn.Particles::velavg (70 bytes)
  5%      moldyn.Particles::cicle_velavg @ 9 (37 bytes)
 18       moldyn.Particles::cicle_domove (23 bytes)
 19       moldyn.Particles::cicle_forces (27 bytes)
 20       moldyn.Particles::cicle_mkekin (33 bytes)
 21       moldyn.Particles::cicle_velavg (37 bytes)
36.763

WITH ArrayList <Double>....
----

  1       java.util.jar.Manifest$FastInputStream::readLine (167 bytes)
  2       sun.nio.cs.UTF_8$Decoder::decodeArrayLoop (553 bytes)
  3       java.lang.String::hashCode (60 bytes)
  4       java.lang.String::charAt (33 bytes)
  5       sun.security.util.ManifestDigester::findSection (180 bytes)
  6       java.lang.Object::<init> (1 bytes)
---   n   java.lang.System::arraycopy (static)
  7       java.lang.Number::<init> (5 bytes)
  8       java.util.ArrayList::ensureCapacity (58 bytes)
  9       java.lang.Double::valueOf (9 bytes)
 10       java.lang.Double::<init> (10 bytes)
 11       java.util.ArrayList::add (100 bytes)
 12       java.util.ArrayList::RangeCheck (48 bytes)
 13       java.util.ArrayList::set (21 bytes)
 14       moldyn.random::update (104 bytes)
 15       moldyn.random::seed (80 bytes)
---   n   java.lang.StrictMath::log (static)
 16       java.lang.Math::log (5 bytes)
 17       java.util.ArrayList::get (12 bytes)
 18       java.lang.Double::doubleValue (5 bytes)
 19       moldyn.md::scalingVelocity (120 bytes)
 20       moldyn.Particles::distance (240 bytes)
  1%      moldyn.Particles::force @ 42 (211 bytes)
 21       moldyn.Particles::force (211 bytes)
 22       moldyn.Particles::domove (337 bytes)
 23       moldyn.Particles::domove_out (292 bytes)
  2%      moldyn.Particles::cicle_domove @ 5 (23 bytes)
 24       moldyn.Particles::update_force (91 bytes)
  3%      moldyn.Particles::cicle_forces @ 6 (27 bytes)
 25       moldyn.Particles::mkekin (297 bytes)
  4%      moldyn.Particles::cicle_mkekin @ 9 (33 bytes)
 26       moldyn.Particles::velavg (118 bytes)
  5%      moldyn.Particles::cicle_velavg @ 9 (37 bytes)
 27       moldyn.Particles::cicle_domove (23 bytes)
 28       moldyn.Particles::cicle_forces (27 bytes)
 29       moldyn.Particles::cicle_mkekin (33 bytes)
 30       moldyn.Particles::cicle_velavg (37 bytes)
55.98

推荐答案

我有一些想法，但没有确定的答案:

I have a few thoughts, but no definitive answer:

1. java.lang.Double 与 double 原语不同.与 Double 对象一起使用的自动装箱开销和额外机制可能会有所不同.我会比较字节码，看看这是否属实.
2. 听起来像 double [] 或 List 的选择对您的 Particle 类中的客户端是隐藏的.如果是这种情况，请使用数组，因为它是内部实现细节.
3. 我会小心，不要用基准测试来欺骗自己.
4. 我想知道您的 Particle 类是否可变.那可能会有所作为.位置、速度和力是否持续变化并在您的对象中更新?

1. A java.lang.Double is not the same thing as a double primitive. It may be that the autoboxing overhead and extra machinery that goes along with the Double object make a difference. I'd compare the byte code to see if that's true.
2. It sounds like the choice of double [] or List<Double> is hidden from clients inside your Particle class. If that's the case, go with the array since it's an internal implementation detail.
3. I'd be careful about fooling myself with a benchmark test.
4. I'd wonder if your Particle class was mutable or not. That might make a difference. Do position, velocity, and force change continuously and get updated in your object?

这篇关于ArrayLists 比数组慢 2 倍的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！