7

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/ArrayList.java#473

public void clear() {
    modCount++;

    // Let gc do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

My question is, why did they have to do an cycle through the backing array { O(n) } to make each element eligible for garbage collection when they could just have reinitialized the backing array, discarding references to the entire array as a whole { O(1) } and making it eligible for garbage collection? O(n) performance for clear() doesn't seem so nice to me or am I missing something?

Sayo Oladeji
  • 741
  • 4
  • 15
  • 28
  • 2
    possible duplicate of [list.clear() vs list = new ArrayList();](http://stackoverflow.com/questions/6961356/list-clear-vs-list-new-arraylistinteger) – Tala Aug 14 '13 at 13:14
  • I dont think this is a duplicate. – nawfal Jun 02 '14 at 16:21

4 Answers4

9

Doing it the way they did lets you reuse the array without re-allocating its backing storage. If you wanted to reallocate the array, you could have done it yourself, since the representation of ArrayList mostly consists of its backing storage.

If they released the array as a whole, there would be very little difference between calling clear() and re-assigning the ArrayList itself. Now they give you an option to choose between reusing the array or replacing it with a brand-new one.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • Almost the same way, one could have done something like: `for (loop_through_list as e) { e = null }` //pseudo code – Sayo Oladeji Aug 14 '13 at 13:29
  • 1
    @SayoOladeji Right, but that would require a loop, and would take additional argument checking each time you set an element to `null`. When you do `new ArrayList()` you trade one line for one line, not one line for a loop. – Sergey Kalinichenko Aug 14 '13 at 13:35
  • Now I have a completely different perspective of the innocent-looking `def arr = new Object[n]` Thanks! – Sayo Oladeji Aug 14 '13 at 13:45
  • Trivia: When allocating a new array in java, java automatically makes sure there is no "garbage" left in it by setting every value to `null` or 0, unless the JIT can detect the whole array is written to before its read. Settings all values manually to null would give more performance than creating a new array of the same size. – Ferrybig Aug 22 '17 at 16:16
3

This implementation allows array reuse without reallocation. Allocating an array in java can be O(n) anyway because the JVM will initialize all the elements to default values.

Community
  • 1
  • 1
Dev
  • 11,919
  • 3
  • 40
  • 53
2

If you're clear()ing an ArrayList, you obviously intend to reuse it - and so any reuse may well have the same number of objects in it. So avoiding resize operations seems like a good idea.

Also, bare in mind that JIT compilation matters here, potentially a lot - that loop is going to be extremely cache friendly & the individual operations are very cheap - probably just a single machine instruction for each in the compiled case.

kittylyst
  • 5,640
  • 2
  • 23
  • 36
0

It is the same reason as clear() impl in Java's LinkedList which is the Java Generational Garbage Collection.

This ArrayList and the backing array are more likely to be promoted to the 'old generation' where it is possible for it to hold on to objects referenced by the array indexes that are more likely to be in the young generation. Setting all of the indexes to null allows those younger objects to be collected before the backing array is collected.

jmehrens
  • 10,580
  • 1
  • 38
  • 47