ArrayLists 2 times slower than array

Question

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).

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)

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

The test environment as:

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

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?

EDIT:

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

related : http://stackoverflow.com/questions/716597/array-or-list-in-java-which-is-faster — daniel gratzer, Nov 25 '12 at 18:19

duffymo · Accepted Answer · 2012-11-25T22:47:03.187

I have a few thoughts, but no definitive answer:

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.
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.
I'd be careful about fooling myself with a benchmark test.
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?

Frank · Answer 2 · 2012-11-25T18:35:51.820

I see 2 potential problems:

1: The overhead of an Object around the Array...

An ArrayList stores a variable number of objects in an Array. This is similar to making an array of objects, but with an ArrayList, items can be easily added and removed from the ArrayList using the exposed methods and it is resized dynamically.

This can be very convenient, but it's slower than making an array of objects when using many elements.

An ArrayList could be a good choice if you need very flexible Array type of collection with limited functionality. But if you go for speed the Array will win. To avoid internal re-copying of Arrays inside the ArrayList you can use

ensureCapacity(int requestCapacity)

2: And in your specific case there is probably also a lot of Boxing/unBoxing going on from double to Double and back, this will give you some latency too.

score 1 · Answer 3 · answered Nov 25 '12 at 20:06

I would advise against using either an array or ArrayList in this use case. You have a very obvious Object Orientated solution to this which is being ignored in favour of an array.

You should rather use composition to build a better structured program, which should be easier to read and (probably) not result in any additional overhead.

eg.

import javax.vecmath.Vector3d;

public class Particle {

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

    ...

}

This way you do not have to worry about bounds checcking (as in the case of both array and ArrayList) and also you do not need to worry about auto-boxing (as in the case of ArrayLists). You also gain the benefit that each value of the particle's velocity, acceleration and position is aptly named. That is, who knows what particle.getData()[7] refers to, whereas with particle.getPosition().y it's quite obvious. Finally, Vector3d comes with a few bits of inbuilt functionality that might be of use.

ArrayLists 2 times slower than array

3 Answers3

Linked