removeIf implementation detail

Question

I have a small implementation detail question that I fail to understand in ArrayList::removeIf. I don't think I can simply put it the way it is without some preconditions first.

As such: the implementation is basically a bulk remove, unlike ArrayList::remove. An example should make things a lot easier to understand. Let's say I have this list:

List<Integer> list = new ArrayList<>(); // 2, 4, 6, 5, 5
list.add(2);
list.add(4);
list.add(6);
list.add(5);
list.add(5); 

And I would like to remove every element that is even. I could do:

Iterator<Integer> iter = list.iterator();
while (iter.hasNext()) {
    int elem = iter.next();
    if (elem % 2 == 0) {
         iter.remove();
    }
}

Or :

list.removeIf(x -> x % 2 == 0);

The result will be the same, but the implementation is very different. Since the iterator is a view of the ArrayList, every time I call remove, the underlying ArrayList has to be brought to a "good" state, meaning that the inner array will actually change. Again, on every single call of remove, there will be calls System::arrayCopy internally.

On the contrast removeIf is smarter. Since it does the iteration internally, it can make things more optimized. The way it does this is interesting.

It first computes the indexes where the elements are supposed to be removed from. This is done by first computing a tiny BitSet, an array of long values where at each index, resides a 64 bit value (a long). Multiple 64 bit values make this a BitSet. To set a value at a particular offset, you first need to find out the index in the array and then set the corresponding bit. This is not very complicated. Let's say you want to set bit 65 and 3. First we need a long [] l = new long[2] (because we went beyond 64 bits, but not more than 128):

|0...(60 more bits here)...000|0...(60 more bits here)...000|

You first find the index : 65 / 64 (they actually do 65 >> 6) and then in that index (1) put the needed bit:

1L << 65 // this will "jump" the first 64 bits, so this will actually become 00000...10. 

Same thing for 3. As such that long array will become:

|0...(60 more bits here)...010|0...(60 more bits here)...1000|

In source code they call this BitSet - deathRow (nice name!).

---

Let's take that even example here, where list = 2, 4, 6, 5, 5

• they iterate the array and compute this deathRow (where Predicate::test is true).

deathRow = 7 (000... 111)

meaning indexes = [0, 1, 2] are to be removed

• they now replace elements in the underlying array based on that deathRow (not going into the details how this is done)

inner array becomes : [5, 5, 6, 5, 5]. Basically they move the elements that are supposed to remain in front of the array.

---

I can finally bring in the question.

At this point in time, they know:

 w   ->  number of elements that have to remain in the list (2)
 es  ->  the array itself ([5, 5, 6, 5, 5])
 end ->  equal to size, never changed

To me, there is a single step to do here :

void getRidOfElementsFromWToEnd() {
    for(int i=w; i<end; ++i){
       es[i] = null;
    }
    size = w;
}

Instead, this happens:

private void shiftTailOverGap(Object[] es, int w, int end) {
    System.arraycopy(es, end, es, w, size - end);
    for (int to = size, i = (size -= end - w); i < to; i++)
        es[i] = null;
}

I've renamed the variables on purpose here.

What is the point in calling:

 System.arraycopy(es, end, es, w, size - end);

Especially size - end, since end is size all the time - it is never changed (so this is always zero). This is basically a NO-OP here. What corner case am I missing here?

Answer 1

You are looking at the specific (common) case that the list, you call removeIf on, is the same as the ArrayList. Only in this case, you can assume that end is always equal to size.

A counter-example would be:

ArrayList<Integer> l = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6, 7));
l.subList(2, 5).removeIf(i -> i%2 == 1);

Likewise, removeAll will call shiftTailOverGap with an end argument which can differ from size when being applied to a subList.

A similar situation arises when you call clear(). In that case, the actual operation, performed when calling it on the ArrayList itself, is so trivial that it does not even calls the shiftTailOverGap method. Only when using something like l.subList(a, b).clear(), it’ll end up at removeRange(a, b) on l, which will in turn, as you already found out yourself, invoke shiftTailOverGap(elementData, a, b) with a bwhich can be smaller than size.