Arraylist Java Size Announcement and Performance

Question

Consider the following Java code (complete, compiles and runs fine).

The code creates an array containing 5,000,000 integers (from 1 to 5 million), iterates over it and creates an ArrayList from the perfect squares it finds. Ideal squares are detected using the naive method, not bit manipulation, but this does not apply to the problem.

Mathematically, between 1 and 5 M, there are 2236 perfect squares. Thus, the ArrayList array, in which ideal squares are placed, will have a final size of 2236.

import java.util.ArrayList; public class PerfSquares { public static ArrayList<Integer> perfectSquares(int[] arr) { ArrayList<Integer> al = new ArrayList<Integer>(); // ArrayList<Integer> al = new ArrayList<Integer>(arr.length); for (int i = 0; i < arr.length; i++) { double root = Math.sqrt(arr[i]); int irt = (int) Math.floor(root); if (irt * irt == arr[i]) { al.add(arr[i]); } } return al; } public static void main(String[] args) { int[] arr = new int[5000000]; for (int i = 0; i < arr.length; i++) { arr[i] = i + 1; } long s = System.currentTimeMillis(); perfectSquares(arr); long e = System.currentTimeMillis(); System.out.println(e - s); } } 

---

I would like to focus on declaring an ArrayList. These two lines, one of which is commented out:

  ArrayList<Integer> al = new ArrayList<Integer>(); //ArrayList<Integer> al = new ArrayList<Integer>(arr.length); 

When I run with the first declaration ( without the size explicitly specified), I see the timediff:

 ~96 milliseconds. 

When I run with the second declaration ( with the size explicitly provided), the timediff increases to:

 ~105 milliseconds 

---

Question:

Why is this so? Should the second case (size supplied) be faster?

According to my understanding, in the first case, when we omit the size parameter in ArrayList, an array of length 10 will be initialized backstage. And when this bandwidth is exceeded, a new array with a larger capacity (not sure how much more) will be allocated, and previous items will be copied.

For 2236 elements and without an initial size, this cycle is "exceeded - assign a new one - copy over - add more until the cap" cycle should be repeated many times, slowing it down.

Therefore, I expected the ad provided by the size to be faster. Since the distribution will happen once, and there will be no way to exceed / create and copy new arrays.

Or is this basically the case, because 2236 joins an ArrayList, even with all cycles exceeding the number of copies, will still be faster than creating an ArrayList of size 5,000,000?

Answer 1

You create an arraylist of 5 million, so this is clearly slower. You need only 2236. This is a lot of waste.

If you change the size of your array list to 10k, for example, you will see that the time difference decreases.

To make it easier, just try this test several times in different orders -

 public static void main(String[] args) { long timea = System.currentTimeMillis(); // ArrayList<Integer> al = new ArrayList<Integer>(); ArrayList<Integer> al = new ArrayList<Integer>(5000000); System.out.println(System.currentTimeMillis() - timea); } 

You will see that initializing an arraylist up to 5 million takes about 10 ms (on my macbook), and one that doesn't have a default size is pretty much instantaneous. This is the same mater who orders you to check.

Answer 2

First of all, your measurement method is erroneous. However, under these conditions, the measurement is not easy, because for such a large distribution of arrays, each subsequent new one can be slower.

As for your problem: allocating memory (and even freeing up) is an expensive operation. Not when you use new - currently vms are quite optimized for many small short-lived objects, but more often when the JVM needs to reserve / allocate (aka malloc() ) memory at the lower system level. Moreover, the memory allocation time also depends on the amount of memory allocated - the more you need, the longer it will take.

In your case: the number of ideal squares AFAIR is easy to calculate. Just use (Math.sqrt(arr.length) + 1) to determine the initial size of the ArrayList and immediately get the size directly.

Answer 3

Since memory allocation is usually a slow operation. I calculated the number of distributions and the new element for both cases.

In this case

 ArrayList<Integer> al = new ArrayList<Integer>(); 

You have a total of 15 appropriations for 8317 items. And in this case

 ArrayList<Integer> al = new ArrayList<Integer>(arr.length); 

you have one selection for 5,000,000 items.

Answer 4

When you call add() on an ArrayList that is already populated, it automatically increases by 50%. Thus, it will be large enough and there will not be as many memory allocations.