javaarraylist

Alternatives to ArrayList<Double> for primitive types in Java for numerical computation

My question is: What are the best practices to avoid the mentioned overhead? I don't understand why my question was closed with the reason: 'This question needs to be more focused.'

I am currently working on numerical computations in a specific research domain and have inherited a Java package implemented long time ago by my team. My task now is to optimize its performance. The package makes extensive use of ArrayList<Double>. As far as I know, Java, at least up to version 9 which I am using, does not support ArrayList of primitive types due to type erasure in Java generics.

There are a few issues with this:

  1. Storage overhead: Double is a wrapper class for double. Since Double is an object, it includes an object header, which takes up 8 bytes. Therefore, each Double object takes up 16 bytes of memory.

  2. Non-contiguous memory: ArrayList internally uses an array to store Double objects, i.e., Double[] data. This array holds references to Double instances. These instances are not stored contiguously in the heap. For example, if Double[] data = {1.0, 2.0}, the references in data are contiguous, but the actual Double objects that these references point to are not. This leads to poor locality and frequent cache misses due to the need to dereference these pointers.

  3. Unboxing and autoboxing: There is additional overhead due to unboxing and autoboxing when performing comparisons and calculations with Double.

My questions are:

What are the best practices to avoid the mentioned overhead? I welcome any answers regarding the questions below.

  1. Are there any new features in the latest versions of Java that allow the use of ArrayList with primitive types?

  2. Are there any experimental features, frameworks, or libraries that support this?

  3. If not, would it be feasible to to create a personal DoubleArrayList by replacing all Object in the ArrayList source code by primitive double? What would be the potential pitfalls of this approach?

PS:

  1. We are on a very tight schedule and do not have the time to rewrite the entire package in C++, where vector<double> is available.

  2. In our use case, the container will change size during computation, and we don't know the size beforehand. Therefore, we must use a resizable array (such as ArrayList) instead of double[].

Solution

  • Project Valhalla

    Are there any new features in the latest versions of Java that allow the use of ArrayList with primitive types?

    Work is underway that may blur the two type systems in Java, primitives versus objects. See Project Valhalla.

    Are there any experimental features

    The Project Valhalla work has not yet released any features to meet your needs. While under active development now, you will not soon benefit from this work.

    Eclipse Collections

    libraries that support this?

    The Eclipse Collections library offers primitives collections. This includes interfaces:

    … with these implementations:

    Example:

    MutableDoubleList doubleList = DoubleLists.mutable.of( 1.0, 2.0, 3.0 );

    You should see a dramatic reduction in memory usage. For example, see this chart of memory saved with the primitive-based IntArrayList in Eclipse Foundation rather than the ArrayList<Integer> bundled with Java.

    chart of memory saved with integer primitive array rather than ArrayList<Integer>

    See the manual for more info.

    would it be feasible to to create a personal DoubleArrayList

    Yes, you could, as discussed in Answer by Bohemian.

    But I would first examine the Eclipse Collections classes before any consideration of writing my own.

    Eclipse Collections is open-source. So you can verify the implementation details yourself.

    do not have the time to rewrite the entire package in C++, where vector is available.

    I would expect that massaging the Java code to take advantage of Eclipse Collections classes would be much easier, quicker, and less error-prone than a total re-write in another language.

    Java versions

    version 9 which I am using,

    Know that Java 9 is end-of-life.

    I strongly recommend moving to an LTS version of Java: 8, 11, 17, 21, and likely 25.

    See Java Version History at Wikipedia.