ArrayList比数组慢2倍

Question

我正在测试一种分子动力学算法，其中包括一个粒子类，由9个双精度数组组成，用于存储粒子的组成部分（速度、力和在三维环境中的位置）。

我使用5个不同的输入大小来测试该算法：

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：

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

我在与上述测试相同的条件下运行了该版本，并得到以下结果：

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 Processor 6174，800 MHz，12 MB Cache L3，有 24 个核心；

我发现速度下降了约两倍。这正常吗？由于 ArrayList 在内存中是连续分配的，所以两个版本的时间应该几乎相同，不应该期望有太大差异吧？

编辑：

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

- dreamcrash

---

相关内容：https://dev59.com/IHRB5IYBdhLWcg3wHkPi - daniel gratzer

Answer 1

我有一些想法，但没有明确的答案：

1. java.lang.Double不同于double原始类型。可能是自动装箱开销和与Double对象相关的额外机制造成了差异。我会比较字节码以查看是否正确。
2. 听起来，double []或List<Double>的选择对客户端而言在Particle类中是隐藏的。如果是这样，请使用数组，因为它是内部实现细节。
3. 我会小心谨慎地进行基准测试，以免欺骗自己。
4. 我会想知道你的Particle类是否可变。这可能会有所不同。位置、速度和力是否持续变化并在对象中更新？

- duffymo

Answer 2

我看到了两个潜在的问题：

1：在数组周围增加一个对象的开销...

ArrayList可以在数组中存储可变数量的对象。这类似于制作对象数组，但使用ArrayList时，可以使用公开的方法轻松地向其中添加和删除项目，并且它可以动态调整大小。

这非常方便，但是当使用许多元素时，它比制作对象数组要慢。

如果您需要非常灵活的数组类型集合但功能有限，则ArrayList可能是一个不错的选择。但是，如果您追求速度，则数组会胜出。 为避免在ArrayList内部重新复制数组，您可以使用

ensureCapacity(int requestCapacity) 

2：在您的特定情况下，可能还涉及大量从double到Double的装箱和拆箱操作，这也会导致一些延迟。

- Frank

Answer 3

我建议在这种情况下不要使用数组或ArrayList。您有一个非常明显的面向对象的解决方案，但却被忽略了，而选择使用数组。

相反，您应该使用组合来构建更好结构化的程序，这样应该更容易阅读，并且（可能）不会导致任何额外的开销。

例如：

import javax.vecmath.Vector3d;

public class Particle {

    private Vector3d velocity;
    private Vector3d force; // acceleration?
    private Vector3d position; 

    ...

}

这样做，您就不必担心边界检查（与数组和ArrayList的情况相同），也不必担心自动装箱（与ArrayLists的情况相同）。您还获得了每个粒子速度、加速度和位置值都被恰当命名的好处。也就是说，谁知道particle.getData()[7]指的是什么，而使用particle.getPosition().y就很明显了。最后，Vector3d带有一些内置功能，可能会有用。

- Dunes