How to efficiently add multiple new objects to an ArrayList

Question

I have a class of ArrayList MyClass. I want to add new elements into the ArrayList. Currently, I am using a for loop to declare new variables myElement. in each loop and then added to the end of the ArrayList.

But it seems to be very inefficient, especially when myArrayLength is very large. That also cost me a lot of computing time. Is there a way such that I can add multiple new MySubClass instances to MyClass without using a for loop? Thanks.

public class MyClass<K,V> extends ArrayList<MyClass.MySubClass> {

    MyClass(int myArrayLength) {

        super(myArrayLength);
    
        for (int i = 0; i < myArrayLength; i++) {
            MySubClass myElement = new MySubClass();
            this.add(myElement);            
        }
    }

    protected class MySubClass {
    
    }

}

In what way is it inefficient? If `myArrayLength` is 1000000, then it will take some time to create 1 million objects, and it cannot be done any faster than that code is doing it. --- And how did you expect to create 1 million objects without using a loop? — Andreas, Jul 20 '20 at 20:22
You can use multithreading which will shorten the time it takes, but I doubt the time gain will offset the effort it will take implementing (and debugging). — daniu, Jul 20 '20 at 20:28

Basil Bourque · Answer 1 · 2020-07-21T01:12:28.200

To populate a list, you must do two things repeatedly:

Instantiating a new object
Add that new object to the list

Your for loop is doing just that. There is no more efficient way.

The instantiations take time, needing to find a piece of free memory, allocating that memory, filling that memory, and returning the address of that memory.

Adding each object to the list takes a moment, but a very brief moment. Remember that an ArrayList is backed by an array. So the memory for the slots of that list have already been allocated. When you are calling ArrayList::add, you are simply writing the object reference (pointer, memory address) into that existing blank slot.

The only performance hit is if you are adding more elements than is the current size and available room within the backing array. The array must be enlarged, if contiguous memory is available, otherwise a new larger array created and elements copied over. You can eliminate that minor hit by setting the initial capacity of the ArrayList to be the number of expected elements. You set the initial capacity by passing a number to the constructor. If you over-estimated the number of elements, call ArrayList::trimToSize to free up the memory used by the still-empty slots.

On a different subject, do not subclass ArrayList without a very good reason. Your efficiency concerns do not warrant this move. The ArrayList class is meant to be used as-is.

    int limit = 52_000 ;
    ArrayList< MyClass > list = new ArrayList<>( limit );

    for ( int i = 0 ; i < limit ; i++ ) {
        MyClass myElement = new MyClass() ;
        list.add( myElement ) ;            
    }
    // If any slots may not have been used, drop them to free up memory.
    list.trimToSize() ;

You could condense the two lines inside the loop into one line.

    list.add( new MyClass() ) ;

But that condensing will not likely impact performance. The optimizing compiler such as HotSpot or OpenJ9 is likely to this anyways, so I would not bother with the condensing. I prefer short separated lines for easier tracing and logging.

Tarik · Answer 2 · 2020-07-21T00:53:58.450

What about lazy initialization of the array elements by using the Lazy wrapper class. See

https://www.infoworld.com/article/2077568/java-tip-67--lazy-instantiation.amp.html

https://learn.microsoft.com/en-us/dotnet/framework/performance/lazy-initialization This will avoid the upfront cost of creating many objects.

You may also consider object pooling. See

https://learn.microsoft.com/en-us/dotnet/standard/collections/thread-safe/how-to-create-an-object-pool

beware however: https://softwareengineering.stackexchange.com/questions/115163/is-object-pooling-a-deprecated-technique

We may simply ask why you want to allocate so many instances upfront that you have to worry about time. Did profiling indicate that you have a big performance hit in this area of your application?

score 0 · Answer 3 · answered Jul 21 '20 at 08:23

Most probably, the code you showed us comes from some bigger project, stripped down to the core. We can only comment on what we see, and that might not match your overall picture. Having said that, I'll continue.

First of all, when talking about performance, you should get yourself a decent profiler tool and find out where your program consumes its time. I guess, it'll be the new MySubClass() expression, and not the list.add(myElement);, but that's guesswork and might as well be completely wrong.

Your current code, when called with something like new MyClass(1000000) constructs a list of one million elements and populates it with 1 million individual MySubClass instances. These instances are all equal, without any variation, all coming from the same no-args new MySubClass() expression.

I very much doubt that a list of 1 million identical elements is what you really need. I guess, you later want to store more meaningful elements in the list, and the initial elements are just meant to be placeholders for "nothing meaningful assigned so far". Then, you can invent a cheaper placeholder for that, e.g. null.

How to efficiently add multiple new objects to an ArrayList

3 Answers3