Why fill() , copy() ,reverse() and shuffle() of Collections in java is implemented this way

Question

According to javadoc... Collections.fill() is written as below :

public static <T> void fill(List<? super T> list, T obj) {
        int size = list.size();

        if (size < FILL_THRESHOLD || list instanceof RandomAccess) {
            for (int i=0; i<size; i++)
                list.set(i, obj);
        } else {
            ListIterator<? super T> itr = list.listIterator();
            for (int i=0; i<size; i++) {
                itr.next();
                itr.set(obj);
            }
        }
    }

Its easy to understand why they didn't use listIterator for

if (size < FILL_THRESHOLD || list instanceof RandomAccess) 

condition as of RandomAccess. But whats the use of size < FILL_THRESHOLD in above?

I mean is there any significant performance benefit over using iterator for size>=FILL_THRESHOLD and not for size < FILL_THRESHOLD ?

I see the same approach for Collections.copy() also :

 public static <T> void copy(List<? super T> dest, List<? extends T> src) {
        int srcSize = src.size();
        if (srcSize > dest.size())
            throw new IndexOutOfBoundsException("Source does not fit in dest");

        if (srcSize < COPY_THRESHOLD ||
            (src instanceof RandomAccess && dest instanceof RandomAccess)) {
            for (int i=0; i<srcSize; i++)
                dest.set(i, src.get(i));
        } else {
            ListIterator<? super T> di=dest.listIterator();
        ListIterator<? extends T> si=src.listIterator();
            for (int i=0; i<srcSize; i++) {
                di.next();
                di.set(si.next());
            }
        }
    }

FYI:

 private static final int FILL_THRESHOLD           =   25;

 private static final int COPY_THRESHOLD           =   10;

Same Approach for below :

 public static void reverse(List<?> list)
 public static void shuffle(List<?> list, Random rnd) 

EDIT :

My confusion is for size<FILL_THRESHOLD part , not for RandomAccess

Answer 1

I guess this is because a generic list is not meant to be an ArrayList. There is no guarantee that setting a random index is done in constant O(1) time. At the same time building an iterator and working over it has its overhead.

In conclusion for small lists you can sacrifice the fact that using an iterator would give a lower complexity for accessing consecutive elements, by saving the overhead of creating the iterator itself.

This because list.set(i, obj) can be more expensive then itr.set(obj) but in the latter you would have implicit overhead of managing the iterator. Since complexity can be linear O(n), using list.set(i, obj) for larger lists could be effectively a problem.

Answer 2

Java 1.2, which introduced the collection framework, and Java 1.3 used the straightforward approach with a ListIterator:

public static void fill(List list, Object o) {
    for (ListIterator i = list.listIterator(); i.hasNext(); ) {
        i.next();
        i.set(o);
    }
}

The thresholds were introduced alongside the RandomAccess marker interface in Java 1.4 (all based on the legacy code for the JDK from Oracle's website).

I think that this is an optimization older garbage collection algorithms - these older algorithms had rather heavy penalties for creating a new object (such as a ListIterator). Therefore, using setters for non-O(1)-lists made sense.

Rather ironically, Java 1.4.1 introduced a new garbage collector that made object creation much cheaper for short lived objects such as an iterator.