How to write the clear() method in the list data structure?

Question

I have read some frameworks source code recently and noticed that they written the clear() method of a list-like data structure like this. Delete the elements one by one.

while (_arr.length > 0 )
{

    remove(_arr[0]);

}       

(maybe the above look like a little confusing,but it's because the native array type in this language itself was a dynamic array) or

 for (int i = 0; i < size; i++)
  { elementData[i] = null;}
 size = 0;

But i remembered i have written some code like this. The list decorated native array type,and I have written clear() method like this.

 _arr=new Array();
 _size=0;

instantiate a new native array type directly.

and this code are written in the language that has the garbage collection. so I think all elements finally will be collected,so why there need a loop?Is a new will be fast?

Answer 1

I guess the motivation is re-using the existing backing array instead of allocating a new one. This is important especially when the backing array is very large (which in some rare cases can even mean the new array cannot be allocated before the old one is garbage collected).

Allocating a new array (and garbage collecting the old one) is probably more time consuming than iterating over the existing array and setting the references of all the elements to null.

EDIT: As mentioned in the comments, setting the references to null in an array based List is not enough. You also have to indicate that the List is empty. In java.util.ArrayList this is done by setting the size property to 0.

Answer 2

In some contexts, it is more efficient to clear and reuse the backing array. (Obviously, you need a size field and you need to set that to zero when you clear the list!)

• Clearing reduces the garbage generated when you empty the list.
• If you grow the list incrementally (i.e. without a capacity hint), clearing also reduces garbage generated by reallocations.

But the flipside is that it isn't always a good idea to clear. For example;

• If you call clear on a ArrayList, the size of the backing array remains the same size as it was when the list was full. If the list was very long, the array can be very big big. And if you never need the list to be that long again, the large array can waste a lot of space.

• The GC has to check every cell in an ArrayList's backing array anyway, irrespective of the current value of the size field. And it needs to copy the entire array to the "to" space.

• That also means that you need to assign null to the "cleared" cells to avoid memory leaks.

• There can be secondary performance issues due to generational and/or locality factors if you are continually putting "new" objects into a large "old" array.

In short, if an array-backed list is likely to survive multiple GC cycles, then clearing (i.e. the procedure of clearing out and reusing the backing array) is a dubious proposition.

Answer 3

Should probably be a comment, but it will not fit as such I assume.

There is also the fact that besides allocating an array might be too expensive and clearing the previous array would be cheaper, there is also the fact that allocating an array in the form new byte[100] or whatever has to also do the zeroing the contents, which might be expensive also.

As such in java-9 String concatenation uses the UNSAFE.allocateUninitializedArray that specifically says Allocates an array of a given type, but does not do zeroing. and of course also adds:

This method should only be used in the very rare cases where a high-performance code overwrites the destination array completely, and compilers cannot assist in zeroing elimination. In an overwhelming majority of cases, a normal Java allocation should be used instead.

And this is how the actual method looks like:

    @ForceInline
    private static byte[] newArray(int length, byte coder) {
        return (byte[]) UNSAFE.allocateUninitializedArray(byte.class, length << coder);
    }

This is just to prove that there are cases where it is in fact too expensive to create arrays and it's cheaper not to. Especially since arrays might require contiguous memory allocation - but this is not mandated by the spec.

Answer 4

Agree with @Eran response on creating a new array or re-using the existing one!

I want to add one more info here.

The source code for clear() is as below:

public void clear() {
    modCount++;
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

The source code for removeAll()(defined in AbstractCollection):

public boolean removeAll(Collection<?> c) {
    boolean modified = false;
    Iterator<?> e = iterator();
    while (e.hasNext()) {
        if (c.contains(e.next())) {
            e.remove();
            modified = true;
        }
    }
    return modified;
}

clear() is of course faster since it doesn't have to deal with all those extra calls. So It's better to set the element to null instead of removing it.

Answer 5

In my opinion When creating a new Array and instantiating it with zeros, it should be slower. In this case the initialization and the iteration is done to set default value. In the case of using an existing array, only the iteration bit is done. Therefore using an existing array and iterate over it should be faster.

In our project we do frequently create array object during some calculation in a long running batch process.After create a pool from where you can get and return after use show a significant improvement.

Answer 6

Neither. Just set _arr to an empty array. You should certainly not call remove() in a loop, for efficiency reasons, and setting all the elements to null is semantically incorrect.