ArrayLists are 2 times slower than an array

Question

I tested the Molecular Dynamic Algorithm, which, among other things, made up the Particle class using an array of 9 doublings to store particle components (speed, force and position in a three-dimensional medium).

I am testing an algorithm using 5 input values:

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) 

How the Particles layout is changed from array to ArrayList . To have a contiguous block of memory, I created an array of List with a size that would occupy:

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

I run the version under the same test conditions 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 

Testing conditions:

AMD Opteron processor 6174, 800 MHz, 12 MB L3 cache with 24 cores;

I get an acceleration of about 2 times. This is normal? should not expect almost the same time in both versions, since the ArrayList is allocated contiguous in memory, like an 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 

Answer 1

I have a few thoughts, but no final answer:

• A java.lang.Double is not the same as a double primitive. It may be that the overhead of autoboxing and the extra mechanisms that go with the double object matter. I would compare the byte code to make sure this is true.
• It appears that the choice of double [] or List<Double> is hidden from clients inside your Particle class. If so, go with the array, as this is an internal implementation detail.
• I would be careful to fool myself with testing.
• I wonder if your Particle class has been changed or not. It can make a difference. Constantly change position, speed and strength and update in your facility?

Answer 2

I see two potential problems:

1: object overhead around the array ...

ArrayList stores a variable number of objects in an array. This is similar to creating an array of objects, but using ArrayList elements can be easily added and removed from ArrayList using public methods and dynamically changed.

This can be very convenient, but it is slower than creating an array of objects using many elements.

ArrayList can be a good choice if you need a very flexible array type with limited functionality. But if you go at speed, then the Array will win. To avoid re-copying the arrays inside the ArrayList, you can use

 ensureCapacity(int requestCapacity) 

2: And in your particular case there is probably also a lot of boxing / unBoxing going from double to double and vice versa, this will also give you some delay.

Answer 3

I would advise using either an array or an ArrayList in this use case. You have a very obvious object-oriented solution that is ignored in favor of an array.

You should use composition to build a better structured program, which should be easier to read and (possibly) not lead to any additional overhead.

eg.

 import javax.vecmath.Vector3d; public class Particle { private Vector3d velocity; private Vector3d force; // acceleration? private Vector3d position; ... } 

Thus, you do not need to worry about checcking borders (as is the case with an array and ArrayList), nor do you need to worry about auto-boxing (as is the case with ArrayLists). You also benefit from the fact that each value of velocity, acceleration and particle position is precisely named. That is, who knows what particle.getData()[7] refers to, whereas with particle.getPosition().y this is completely obvious. Finally, Vector3d contains several built-in functions that may be useful.