0

We found out that ArrayList.addAll(...) method doesn't check if the given collection is not empty. It means we will re-allocate memory (System.arrayCopy(...) will be called) even if we don't actually need it.

Shoud we add an IF check for an optimization?

For example: elapsed time for the first code is more than 8 times faster than the second one. It seems like our optimization works properly, so why it wasn't implemented already?

List<Integer> existed = new ArrayList<>();
List<Integer> empty = new ArrayList<>();
for (int i = 0; i < 100_000_000; i++) {
    if(!empty.isEmpty())
       existed.addAll(empty);
}

VS

List<Integer> existed  = new ArrayList<>();
List<Integer> empty = new ArrayList<>();
for (int i = 0; i < 100_000_000; i++) {
    existed.addAll(empty);
}
Vladimir Budanov
  • 19
  • 6
  • 1
    What do you mean with “re-allocate memory (System.arrayCopy(...) will be called)”? `System.arraycopy(…)` doesn’t allocate memory. Recommended read: [How do I write a correct micro-benchmark in Java?](https://stackoverflow.com/q/504103/2711488) – Holger Oct 02 '20 at 16:01
  • Also please specify JDK version and how you measured – fps Oct 02 '20 at 16:03
  • @fps we use Java 8 – Vladimir Budanov Oct 05 '20 at 08:47

1 Answers1

1

In JDK14 ArrayList.addAll() makes a copy of the collection to add as an array and increments the ArrayList modification count - even if there are no elements to add.

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    modCount++;
    int numNew = a.length;
    if (numNew == 0)
        return false;
    ...

So your testcase which is not using isEmpty() beforehand, it will cause unnecessary allocation of 100,000,000 instances of new Object[0] and increments the modification count same number of times and which would explain why it appears slower.

Note that System.arrayCopy is not called unless the array is growing beyond the capacity of the existing array.

I've scanned in my own code just now and I doubt whether adding the isEmpty() test would speed up the code as there is generally something to add each time, and so putting in these extra checks would unnecessary. You'd need to decide for your own situation.

DuncG
  • 12,137
  • 2
  • 21
  • 33