Memory Management Recursion Java

Question

I am entering a recursion in Java with a large ArrayList. In one recursion step I split this list into two lists of half the size each and apply the same method recursively to both lists. However, since I do not need the large list any more after splitting it, I would like to delete it from memory. After searching here for a while, I came up with this:

public some_object recursiveMethod(ArrayList large_List) {
    //Compute the two sublists
    ArrayList lower_half = lowerHalf(large_List);
    ArrayList upper_half = upperHalf(large_List);

   //Delete large list from memory
   large_List = null;

   //Recursively call on smaller lists
   return procedure(recursiveMethod(lower_half),recursiveMethod(upper_half));
}

Will this work, i.e. will the GC remove the large list?

Answer 1

It won't work because lower_half and upper_class are still referencing the list in the caller which doesn't unreference them until it has finished.

For example, take the first actual parameter of procedure: recursiveMethod(lower_half). lower_half reference is copied into called recursiveMethod large_List actual parameter. So you have the same list:

• Referenced at the caller as lower_half.
• And within the current call scope as large_list

In your current call you null the reference large_list but not caller's lower_half. Thus the list is still referenced somewhere and therefore not collected by the GC.

Answer 2

Looks like divide & conquer. In such cases it is best do avoid local (hard) references (parameters and temporaries) and GC overhead alltogether by keeping that one, large list along with lightweight sub list views using List.subList() (wrappers, referencing the large backing list) or a plain pair of indexes.

If these sublists must be modified independently from the original list, one may duplicate that large list once, before entering the recursive processing, which should still be more efficient than multiple independent sublist copies.

public some_object recursiveMethod(List large_List) {
    //Create views of the two sublists
    List lower_half = large_List.subList(0,large_List.size()/2);
    List upper_half = large_List.subList(large_List.size()/2,large_List.size());

   //Recursively call on list views
   return procedure(recursiveMethod(lower_half),recursiveMethod(upper_half));
}

public some_object recursiveMethod2(ArrayList large_List, int begin, int end) {
    //Create views of the two sublists
    int size = end - begin;
    int lowerBegin = begin;
    int lowerEnd = begin + size/2; //exclusive
    int upperBegin = lowerEnd;
    int upperEnd = begin + size; //exclusive

   //Recursively call on list views
   return procedure(recursiveMethod2(large_List,lowerBegin,lowerEnd),recursiveMethod2(large_List,upperBegin,upperEnd));
}