Effective Java Item 17: How can overriding removeRange() improve performance?

Question

In the book Effective Java by Joshua Bloch, there is a discussion on how a class can provide "judiciously chosen protected methods" as hooks into its internal workings.
The author then cites the documentation in AbstractList.removeRange():

This method is called by the clear operation on this list and its subLists. Overriding this method to take advantage of the internals of the list implementation can substantially improve the performance of the clear operation on this list and its subLists.

My question is, how can overriding this method improve performance (more than simply not overriding it)? Can anyone give an example of this?

Answer 1

Let's take a concrete example - suppose that your implementation is backed by a dynamic array (this is how ArrayList works, for example). Now, suppose that you want to remove elements in the range [start, end). The default implementation of removeRange works by getting an iterator to position start, then calling remove() the appropriate number of times.

Each time remove() is called, the dynamic array implementation has to shuffle all the elements at position start + 1 and forward back one spot to fill the gap left in the removed element. This could potentially take time O(n), because potentially all of the array elements might need to get shuffled down. This means that if you're removing a total of k elements from the list, the naive approach will take time O(kn), since you're doing O(n) work k times.

Now consider a much better approach: copy the element at position end to position start, then element end + 1 to position start + 1, etc. until all elements are copied. This requires you to only do a total of O(n) work, because every element is moved at most once. Compared with the O(kn) approach given by the naive algorithm, this is a huge performance improvement. Consequently, overriding removeRange to use this more efficient algorithm can dramatically increase performance.

Hope this helps!

Answer 2

As specified in the method's javadocs:

This implementation gets a list iterator positioned before fromIndex, and repeatedly calls ListIterator.next followed by ListIterator.remove until the entire range has been removed.

Since this abstract class does not know about the internals of its subclasses, it relies on this generic algorithm which will run in time proportional to the number of items being removed.

If, for example, you implemented a subclass that stored elements as a linked list. Then you could take advantage of this fact and override this method to use a linked list specific algorithm (move pointer to fromIndex to point to toIndex) which runs in constant time. You have thus improved performance because you took advantage of internals.

Answer 3

Simply by overriding this method you can utilize this generic algorithm according to your requirement as your indexing issues. As it is a protected method in AbstractList and also in ArrayList and its implementation there works as iterative calls to remove() that need each time shifting of all elements available at right side of removed element by one index. Obviously it is not effective, so you can make it working better.